数据结构与算法（关于线性表）.ppt

* * 算法与数据结构 主讲教师: 葛日波 联系方式: teacher_ge@dlut.edu.cn 办公室: 教学楼1904 2.线性表的顺序存储结构 1.线性表的定义和运算 第2章 线性表 3.线性表的链式存储结构 一.线性表的定义和运算 一.线性表的定义和运算 1.线性表的定义 n(n≥0)个具有相同特性的数据元素的有限序列 （1）n为表的长度，即元素个数 （2）n=0时为空表 （3）n0时通常记为:（a1,a2,…,ai,…,an） 2.线性表的特点 （1）当1in时 ai的直接前驱是ai-1 ， a1无直接前驱 ai的直接后继是ai+1 ，an无直接后继 （2）元素同构不能出现缺项 3.线性表的运算 (1)存取线性表中某个元素 (2)查找满足给定条件的数据元素 (3)插入一个新的数据元素 (4)删除线性表中的某个数据元素 (5)把两个表合并为一个 (6)把一个表拆分为两个 (7)重新排列线性表中的数据元素 (8)求线性表的长度 二.线性表的顺序存储结构 二.线性表的顺序存储结构 1.顺序表的含义 用一组连续的存储单元依次存放线性表的数据元素 2.顺序表的特点 (1)逻辑上相邻的数据元素，它们的物理位置也是邻接的 (2)线性关系利用物理上的相邻关系来体现 3.位置确定 Loc(ai)=Loc(a1)+(i-1) * m 4.数据描述 #define MAX 100 typedef strct{ int data[MAX]; int len; } SList; len data[MAX-1] … data[1] data[0] 5.顺序表中元素的访问方式 若有: SList *p； n data[MAX-1] … data[1] data[0] p 则: 线性表的表长应表示为(*p).n或p-n 第i个元素写为p-data[i-1]或(*p).data[i-1] 6.顺序表中的常用运算 (1)插入运算 在线性表的第i个数据元素之前插入一个新的数据元素，使长度为n的线性表(a1, …, ai-1, ai, …, an)变为长度为n＋1的线性表 (a1, …, ai-1, x, ai, …, an) 结论: (1)平均需移动表长的一半 (2)最坏时间复杂度为T(n)=O(n) (2)删除运算 将线性表的第i个数据元素删去，使长度为n的线性表 (a1 ,...,ai-1 ,ai ,ai+1 ,...,an ) 变成长度为n-1的线性表 (a1 ,...,ai-1 ,ai+1 ,...,an ) 结论: (1)平均需移动表长的一半 (2)最坏时间复杂度为T(n)=O(n) (3)查找运算 查找元素x在表中的序号 结论: 最坏时间复杂度为T(n)=O(n) 7.顺序表优缺点 (1)优点 简单直观 随机存取容易 插入删除困难 扩展不灵活容易造成空间浪费 (2)缺点 三.线性表的链式存储结构 三.线性表的链式存储结构 1.链表的含义 (1)用一组任意的存储单元存储线性表的数据元素 (2)这组存储单元可以是连续的，也可以是不连续的 (3)数据元素之间的逻辑关系由指示元素存储位置的指针来表示 (4)这种存储方式叫做线性表的链式存储结构，简称链表 (5)含一个指针的链表叫单链表 2.单链表的特点 (1)用一组任意的存储单元存储线性表的数据元素 (2)用不相邻的存储单元存放逻辑上相邻的元素 (3)每个元素除存储本身信息外,还需存储其后继结点的信息 数据域：元素本身信息 指针域：指示直接后继的存储位置 data next 数据域 指针域 3.单链表的数据描述 若有: LNode *p； p = (LNode *)malloc(sizeof(LNode)); 则: 访问结点的数据域：(*p).data或p-data 访问结点的指针域：p-link或(*p).link typedef struct node{ dataType data; struct node *link; }LNode; data link 4.单链表的基本运算 1）在链表中查找是否存在值为x的结点 2)实现方法 从第一个结点开始扫描单链表，逐个和x比较 找到该结点后返回指向该结点的指针 (1)查找 1）在p结点后插入一个新结点(值为x) 2)实现方法 新生成一个结点s,把值域置为x 把p的后继结点连到s后面，s连到p的后面 (