数据结构课件：02.线性表[47].ppt

1、第二章第二章一、线性数据结构的特点一、线性数据结构的特点2第一节线性表第一节线性表n在数据元素的非空有限集中在数据元素的非空有限集中、存在惟一的一个被称作、存在惟一的一个被称作“第一个第一个”的数据元素的数据元素( (如如“”) )、存在惟一的一个被称作、存在惟一的一个被称作“最后一个最后一个”的数据元素的数据元素( (如如“”) )、除第一个元素外，每个数据元素均只有一个前驱、除第一个元素外，每个数据元素均只有一个前驱、除最后一个元素外，每个数据元素均只有一个后继、除最后一个元素外，每个数据元素均只有一个后继( (next)(next)(如如“1 1”的的nextnext是是“2 2”, ,

2、 “2 2”的的nextnext是是“3 3”) )第章线性表第章线性表123456二、线性表二、线性表3第一节线性表第一节线性表n线性表是最简单的一类线性数据结构线性表是最简单的一类线性数据结构n线性表是由线性表是由n n个数据元素组成的有限序列，相个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系，可以写为：邻数据元素之间存在着序偶关系，可以写为：( (a a1 1, a, a2 2, ,a ai-1i-1, a, ai i, a, ai+1i+1, ,a an-1n-1, a, an n) )其中,ai是表中元素,i表示元素ai的位置,n是表的长度第章线性表第章线性表二、线性表二、

3、线性表4第一节线性表第一节线性表n线性表中的元素具有相同的特性，属于同一数线性表中的元素具有相同的特性，属于同一数据对象，如：据对象，如：1.261.26个字母的字母表个字母的字母表: (: (A,B,C,D,A,B,C,D,Z),Z)2.2.近期每天的平均温度近期每天的平均温度:(30:(30, 28 28, 29 29,) )第章线性表第章线性表一、顺序表一、顺序表5第二节顺序表第二节顺序表n顺序表是线性表的顺序表示顺序表是线性表的顺序表示n用一组地址连续的存储单元依次存储线性表的用一组地址连续的存储单元依次存储线性表的数据元素数据元素第章线性表第章线性表ABCDEYZ b b+1 b+2

4、 b+3 b+4 b+24 b+25一、顺序表（元素位置）一、顺序表（元素位置）6第二节顺序表第二节顺序表n顺序表数据元素的位置：顺序表数据元素的位置： LOC(a i) = LOC( a i-1 ) + l LOC(a i) = LOC(a1)+(i-1)*l l表示元素占用的内存单元 数第章线性表第章线性表 a1 a2 a i an 1 2 i n b b+l b+(i-1)*l b+(n-1)*l idle二、顺序表的定义二、顺序表的定义7第二节顺序表第二节顺序表n采用采用C C语言中动态分配的语言中动态分配的一维数组一维数组表示顺序表表示顺序表第章线性表第章线性表#define LIS

5、T_INIT_SIZE 100/ 线性表存储空间的初始分配量#define LISTINCREMENT 10/ 线性表存储空间的分配增量Typedef struct ElemType*elem;/ 存储空间基址intlength;/ 当前长度int listsize;/ 当前分配的存储容量(元素数) Sqlist;三、顺序表的初始化三、顺序表的初始化8第二节顺序表第二节顺序表n创建一个顺序表创建一个顺序表L L第章线性表第章线性表Status InitList_Sq(Sqlist &L) L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(Ele

6、mType);if (!L.elem) exit(OVERFLOW);/ 存储分配失败L.length = 0;/ 空表长度为0L.listsize = LIST_INIT_SIZE;/ 初始存储容量return OK; / InitList_Sq三、顺序表的插入三、顺序表的插入9第二节顺序表第二节顺序表n顺序表的插入操作是指在顺序表的第顺序表的插入操作是指在顺序表的第i-1i-1个数个数据元素和第据元素和第i i个数据元素之间插入一个新的数个数据元素之间插入一个新的数据元素，即将长度为据元素，即将长度为n n的顺序表：的顺序表：( (a a1 1, ,a ai-1i-1, a, ai i,

7、, , a, an n) ) 变成长度为变成长度为n+1n+1的顺序表：的顺序表：( (a a1 1, ,a ai-1i-1, e, a, e, ai i, , , a, an n) )第章线性表第章线性表三、顺序表的插入三、顺序表的插入10第二节顺序表第二节顺序表n在第在第3 3个元素与第个元素与第4 4个元素之间插入新元素个元素之间插入新元素b bn需要将最后元素需要将最后元素n n至第至第4 4元素元素( (共共7-4+1)7-4+1)都向后移一位都向后移一位置置第章线性表第章线性表 25 34 57 16 48 09 63 0 1 2 3 4 5 6 725 34 57 50 16 4

8、8 09 63 5050插入 ei=4 0 1 2 3 4 5 6 7三、顺序表的插入三、顺序表的插入11第二节顺序表第二节顺序表第章线性表第章线性表Status ListInsert_Sq(Sqlist &L, int i, ElemType e) if (iL.length+1) return ERROR; if (L.length = L.listsize) newbase = realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem = newbase; L.list

9、size += LISTINCRMENT; / 以上皆为准备阶段 q = &(L.elemi-1);/ 找到插入位置 for (p=&(L.elemL.length-1); p=q; -p) *(p+1) = *p;/ 右移 *q = e; +L.length; return OK; / ListInsert_Sq/ 请注意元素位置数值较元素序号少1三、顺序表的插入三、顺序表的插入12第二节顺序表第二节顺序表n在顺序表中插入一个元素，需要向后移动元素在顺序表中插入一个元素，需要向后移动元素个数为：个数为：n-i+1n-i+1n平均移动元素数为：平均移动元素数为： n+1 n+1 E Eisis

10、 = = p pi i x (n-i+1) x (n-i+1) i=1 i=1第章线性表第章线性表三、顺序表的插入三、顺序表的插入13第二节顺序表第二节顺序表n当插入位置等概率时，当插入位置等概率时，p pi i=1/(n+1)=1/(n+1)，因此：因此： n+1 n+1 E Eisis = = 1/(n+1) x (n-i+1) = n/2 1/(n+1) x (n-i+1) = n/2 i=1 i=1n顺序表插入操作的时间复杂度为顺序表插入操作的时间复杂度为O(n)O(n)第章线性表第章线性表四、顺序表的删除四、顺序表的删除14第二节顺序表第二节顺序表n顺序表的删除操作是指将顺序表的第顺

11、序表的删除操作是指将顺序表的第i i个数据个数据元素删除，即将长度为元素删除，即将长度为n n的顺序表：的顺序表：( (a a1 1, ,a ai-1i-1, a, ai i, a, ai+1i+1, , a, an n) ) 变成长度为变成长度为n-1n-1的顺序表：的顺序表：( (a a1 1, ,a ai-1i-1, a, ai+1i+1, , , a, an n) )第章线性表第章线性表四、顺序表的删除四、顺序表的删除15第二节顺序表第二节顺序表n将第将第4 4个元素删除个元素删除n需要将最后元素需要将最后元素n n至第至第5 5元素元素( (共共7-4)7-4)都向前移一位置都向前移

12、一位置第章线性表第章线性表 25 34 57 48 09 63 0 1 2 3 4 5 6 725 34 57 48 09 63 16删除16i=4 0 1 2 3 4 5 6 7四、顺序表的删除四、顺序表的删除16第二节顺序表第二节顺序表第章线性表第章线性表Status ListDelete_Sq(Sqlist &L, int i, ElemType e) if (iL.length) return ERROR; p = &(L.elemi-1);/ 找到要删除的元素位置 e = *p; q = L.elem + L.length 1;/ 找到最后一个元素位置 for (+p; pnext;

13、 j=1;/ p指向第一个结点while (p & jnext; j+;/ 顺指针查指if (!p | ji) return ERROR;/ 第i元素不存在e = p-data;/ 取第i元素值return OK; / GetElem_L第章线性表第章线性表na1aian L四、找指定元素四、找指定元素26第二节线性链表第二节线性链表n算法时间复杂度主要取决于算法时间复杂度主要取决于while循环中的语循环中的语句频度句频度n频度与被查找元素在单链表中的位置有关频度与被查找元素在单链表中的位置有关n若若1in，则频度为则频度为i-1，否则为否则为nn因此时间复杂度为因此时间复杂度为O(n)第章

14、线性表第章线性表na1aian L五、线性链表的插入五、线性链表的插入27第二节线性链表第二节线性链表n在线性链表的第在线性链表的第i-1元素与第元素与第i元素之间插入一元素之间插入一个新元素个新元素第章线性表第章线性表ai-1aise插入前pai-1aise插入后ps-next = p-next; p-next = s;五、线性链表的插入五、线性链表的插入28第二节线性链表第二节线性链表Status ListInsert_L(LinkList &L, int i, ElemType e) / 在带头结点的单链表L中第i个位置之前插入元素ep = L; j = 0;while (p & jne

15、xt; j+;/ 寻找i-1结点if (!p | ji-1) return ERROR;s = (LinkList) malloc(sizeof(LNode);/ 生成新结点s-data = e; s-next = p-next; p-next = s;/ 插入L中return OK; / ListInsert_L第章线性表第章线性表五、线性链表的插入五、线性链表的插入29第二节线性链表第二节线性链表n同样，算法时间复杂度主要取决于同样，算法时间复杂度主要取决于while循环循环中的语句频度中的语句频度n频度与在线性链表中的元素插入位置有关频度与在线性链表中的元素插入位置有关n因此线性链表插入

16、的时间复杂度为因此线性链表插入的时间复杂度为O(n)第章线性表第章线性表六、线性链表的删除六、线性链表的删除30第二节线性链表第二节线性链表n将线性链表的第将线性链表的第i元素删除元素删除第章线性表第章线性表pai-1ai+1ai删除前ai-1aiai+1pq删除后p-next = p-next -next六、线性链表的删除六、线性链表的删除31第二节线性链表第二节线性链表Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在带头结点的单链表L中，删除第i个位置的元素p = L; j = 0;while (p-next & jnext;

17、 j+;/ 寻找i结点if (!p-next | ji-1) return ERROR;q = p-next; p-next = q-next;/ 删除i结点e = q-data; free(q);/ 取值并释放结点return OK; / ListDelete_L第章线性表第章线性表六、线性链表的删除六、线性链表的删除32第二节线性链表第二节线性链表n同样，算法时间复杂度主要取决于同样，算法时间复杂度主要取决于while循环循环中的语句频度中的语句频度n频度与被删除元素在线性链表中的位置有关频度与被删除元素在线性链表中的位置有关n因此线性链表删除元素的时间复杂度为因此线性链表删除元素的时间复

18、杂度为O(n)第章线性表第章线性表七、静态链表七、静态链表33第二节线性链表第二节线性链表n线性链表也可以采用静态数组实现线性链表也可以采用静态数组实现n与顺序表有两点不同：与顺序表有两点不同：、每个元素包括数据域和指针域、每个元素包括数据域和指针域、元素的逻辑关系由指针确定、元素的逻辑关系由指针确定第章线性表第章线性表DCFBAE7592836 10 4 110 1 2 3 4 5 6 7 8 9 10 数据指针七、静态链表七、静态链表34第二节线性链表第二节线性链表n与单链表区别：与单链表区别：、静态链表暂时不用结点，链成一个备用链表、静态链表暂时不用结点，链成一个备用链表、插入时，从备用

19、链表中申请结点、插入时，从备用链表中申请结点、删除结点时，将结点放入备用链表、删除结点时，将结点放入备用链表第章线性表第章线性表一、循环链表一、循环链表35第三节循环链表第三节循环链表n循环链表是一种特殊的线性链表循环链表是一种特殊的线性链表n循环链表中最后一个结点的指针域指向头结点，循环链表中最后一个结点的指针域指向头结点，整个链表形成一个环。整个链表形成一个环。第章线性表第章线性表na1aianL二、查找、插入和删除二、查找、插入和删除36第三节循环链表第三节循环链表n在循环链表中查找指定元素，插入一个结点或在循环链表中查找指定元素，插入一个结点或删除一个结点的操作与线性链表基本一致删除一

20、个结点的操作与线性链表基本一致n差别仅在于算法中的循环条件不是差别仅在于算法中的循环条件不是p-next或或p是否为空是否为空()，而是它们是否等于头指针，而是它们是否等于头指针(L)第章线性表第章线性表na1aianL一、双向链表一、双向链表37第四节双向链表第四节双向链表n双向链表也是一种特殊的线性链表双向链表也是一种特殊的线性链表n双向链表中每个结点有两个指针，一个指针指双向链表中每个结点有两个指针，一个指针指向直接后继向直接后继(next)，另一个指向直接前驱另一个指向直接前驱(prior)第章线性表第章线性表指向直接前驱指向直接前驱 指向直接指向直接后继后继二、双向循环链表二、双向循

21、环链表38第四节双向链表第四节双向链表n双向循环链表中存在两个环双向循环链表中存在两个环(一个是直接后继一个是直接后继环环(红)，另一个是直接前驱环，另一个是直接前驱环(蓝)第章线性表第章线性表非空表非空表 空表空表LL三、双向链表的定义三、双向链表的定义39第四节双向链表第四节双向链表n定义一个双向链表的结点定义一个双向链表的结点Typedef struct DuLNode ElemTypedata;struct DuLNode*prior;struct DuLNode*next;DuLNode, *DuLinkList;第章线性表第章线性表指向直接前驱指向直接前驱 指向直接指向直接后继后继

22、对于任何一个中间结点有：p = p-next-priorp = p-prior-next四、双向链表的插入四、双向链表的插入40第四节双向链表第四节双向链表n双向链表的插入操作需要改变两个方向的指针双向链表的插入操作需要改变两个方向的指针第章线性表第章线性表L314815pL31482515pss-next = p;s-prior = p-prior;p-prior-next = s;p-prior = s;四、双向链表的删除四、双向链表的删除41第四节双向链表第四节双向链表n双向链表的删除操作需要改变两个方向的指针双向链表的删除操作需要改变两个方向的指针第章线性表第章线性表L314815pL

23、3115p-prior-next = p-next;p-next-prior = p-prior;一、基于空间的比较一、基于空间的比较42第五节顺序表与链表的比较第五节顺序表与链表的比较n存储分配的方式存储分配的方式u顺序表的存储空间是静态分配的顺序表的存储空间是静态分配的u链表的存储空间是动态分配的链表的存储空间是动态分配的n存储密度存储密度 = = 结点数据本身所占的存储量结点数据本身所占的存储量/ /结点结点结构所占的存储总量结构所占的存储总量u顺序表的存储密度顺序表的存储密度 = 1 = 1u链表的存储密度链表的存储密度 1 1第章线性表第章线性表二、基于时间的比较二、基于时间的比较4

24、3第五节顺序表与链表的比较第五节顺序表与链表的比较n存取方式存取方式u顺序表可以随机存取，也可以顺序存取顺序表可以随机存取，也可以顺序存取u链表必须顺序存取链表必须顺序存取n插入插入/ /删除时移动元素个数删除时移动元素个数u顺序表平均需要移动近一半元素顺序表平均需要移动近一半元素u链表不需要移动元素，只需要修改指针链表不需要移动元素，只需要修改指针第章线性表第章线性表三、基于应用的比较三、基于应用的比较44第五节顺序表与链表的比较第五节顺序表与链表的比较n如果线性表主要是存储大量的数据，并主要用如果线性表主要是存储大量的数据，并主要用于查找时，采用顺序表较好，如数据库于查找时，采用顺序表较好

25、，如数据库n如果线性表存储的数据元素经常需要做插入与如果线性表存储的数据元素经常需要做插入与删除操作，则采用链表较好，如操作系统中进删除操作，则采用链表较好，如操作系统中进程控制块程控制块( (PCB)PCB)的管理，内存空间的管理等的管理，内存空间的管理等第章线性表第章线性表一、一元多项式的表示一、一元多项式的表示45第六节单链表应用举例第六节单链表应用举例n设有一元多项式设有一元多项式AH:AH:AH = 1 - 3x6 + 7x12可以单链表表示为：可以单链表表示为：第章线性表第章线性表AH 1 0-3 67 12二、一元多项式的相加算法二、一元多项式的相加算法46第六节单链表应用举例第

26、六节单链表应用举例n扫描两个多项式，若都未检测完：扫描两个多项式，若都未检测完：u 若当前被检测项指数相等，系数相加。若若当前被检测项指数相等，系数相加。若未变成未变成 0 0，则将结果加到结果多项式。，则将结果加到结果多项式。u 若当前被检测项指数不等，将指数小者加若当前被检测项指数不等，将指数小者加到结果多项式。到结果多项式。n若一个多项式已检测完，将另一个多项式剩余若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。部分复制到结果多项式。第章线性表第章线性表三、一元多项式的相加举例三、一元多项式的相加举例47第六节单链表应用举例第六节单链表应用举例n设有两个一元多项式设有两个一元多项式AHAH，BH, BH, 相加之后为相加之后为CX:CX: AH = 1 - 3x6 + 7x12 BH = - x4 + 3x6 - 9x10 + 8x14第章线性表第章线性表BH CH 1 0-1 4-1 43 6-9 10-9 10AH 1 0-3 67 127 128 148 14