第二章线性表

1、主讲人 陈玉华2022-3-3线性表定义： 线性表是由n(n0)个类型相同数据元素组成的有限序列，记作： (a1 ,a2 ,ai-1 ,ai ,ai+1 ,an )。首元尾元元素ai的前驱元素ai的后继2022-3-3ADT LinearList 数据元素：D=ai|aiD0,i=1,2,n,n0,D0是某数据类型 结构关系：R=|ai,ai+1D0，i=1,2,n 基本操作： 表的初始化 求表长 求表中第i个元素的值 插入元素 删除元素 元素的查找（定位） 表的清空 表的判空ADT LinearList； 2022-3-3线性表的顺序存储： 用一组地址连续的存储单元依次存储线性表中的各个元素

2、，使得线性表中在逻辑上相邻的数据元素存储在连续的物理存储单元中，即逻辑上相邻的元素，其存储位置也相邻。2022-3-32022-3-3a1a2.ai.anai+1逻辑地址12.ii+1.n存储地址Loc10001000+c.1000+(i-1)*c1000+i*c.1000+(n-1)*c空闲#define MAXSIZE 100typedef 已经定义过的类型 ElemType；typedef struct ElemType elemMAXSIZE; int last;SeqList;2022-3-3 int int2022-3-3该运算的目的是建立一张空的顺序表L。void InitSeq

3、List(SeqList void InitSeqList(SeqList * *L)L) 如何表示如何表示L L是一张空表？是一张空表？ 2022-3-3这个过程很重要！L-last=-1;该运算的目的是在顺序表L的位置i插入某个元素e。插入成功返回1，否则返回0。int InsertSeqList(SeqList int InsertSeqList(SeqList * *L , int i , ElemType e)L , int i , ElemType e) 判满判满：首先判定表L是否还可以插入元素，如果不可以， 则返回0，否则进行插入操作。 插入插入： 将插入位置腾空 将要插入的元素

4、放置在插入位置上 表中的标识表尾元素位置改变返回 12022-3-3不难看出，顺序表的插入运算所花费时间不总是一样的，在表尾插入一个元素和在表头插入一个元素所花费的时间就不同。平均移动次数2022-3-3nniinsnkninninE1k1n1i11i211) 1(11) 1(P在顺序表中查找一个元素，分为两种情况：1）按序号查找：查找顺序表L中的第i个位置上的元素2）按内容查找：查找顺序表中与给定值e相等的元素2022-3-3该函数的目的是查找顺序表L中的第i个元素，如果该元素存在，则返回该元素，否则，返回一个表中不可能存在的数。ElemType GetData（SeqList L , in

5、t i) ElemType e=初始值； 如果表中的第i个元素存在，则更新e的值，并返回e； 如果表中的第i个元素的值不存在，则直接返回e2022-3-3在顺序表L中去查找元素e，如果e在L中出现，则返回该元素在表中的位置，否则，返回0.int Locate(SeqList L , ElemType e) 从表的首元开始依次与e进行比较，如果相等，则查找成功结束，返回该元素在表中的序号； 如果e与表中的所有元素都不想等，则查找失败，返回02022-3-3该运算的目的是删除表中的第i个元素，如果删除失败，则返回0；如果删除成功，则带回被删除的元素，并且返回1。 该算法实现中要注意的一个问题是，删

6、除一个元素后，剩余的元素在存储的时候仍然保证逻辑上相邻的两个元素存储也是相邻的。2022-3-3int DelSeqList( SeqList *L , int i , ElemType *e) 判断表是否是空？如果空，则返回0 判断被删除的元素是否存在？若该元素不存在则返回0删除： 获取被删除元素 采用元素覆盖方式实现删除 更改表尾元素位置返回1 2022-3-3与插入算法类似，我们对删除算法的时间分析也是去计算平均移动次数平均移动次数2022-3-3nininkinkninninQ1110del211)(1)(E如果一个线性表中的数据元素是有序的序列，则称该线性表为有序表。顺序存储的有序表

7、称为有序顺序表。两个有有序表的合并算法中对两个同顺序（同是递增顺序，或者同是递减顺序）的有序表进行合并操作，要求合并之后的新表仍然是同顺序的有序表。2022-3-32022-3-322 31 3 3 4ijk0 1 2 0 1 2 3 0 1 2 3 4 5 6 122 33 34void MergeList(SeqList void MergeList(SeqList * *LA, SeqList LA, SeqList * *LB, SeqList LB, SeqList * *Lc)Lc) int i , j, k ; int i , j, k ; /三个标志变量三个标志变量 i=j=k

8、=0; i=j=k=0; /标志量初始值标志量初始值 while(ilast & jlast) while(ilast & jlast) if(LA-elemielemj) if(LA-elemielemj) LC-elemk=LA-elemi; i+;k+; LC-elemk=LA-elemi; i+;k+; else else LC-elemk=LB-elemj;j+;k+; LC-elemk=LB-elemj;j+;k+; while(ilast) while(ilast) LC-elemk=LA-elemi; i+;k+; LC-elemk=LA-elemi; i+;k

9、+; while(jlast) while(jlast) LC-elemk=LB-elemj; j+; k+; LC-elemk=LB-elemj; j+; k+; 2022-3-3优点： (1) 无须为表示结点间的逻辑关系而增加额外的存储空间，因为逻辑上相邻的元素其存储位置也相邻。 (2) 对表中的元素的随机访问很方便。缺点： (1) 插入或删除运算效率低。 (2) 静态分配空间使得空间的使用不充分。2022-3-3采用链式存储结构的线性表称为线性链表。从链接方式的角度看，链表可分为单链表、循环链表和双链表从实现角度看，链表可分为动态链表和静态链表2022-3-3结点 单链表示意图2022-

10、3-3data nextdata next指针域，专指针域，专门用来刻画门用来刻画逻辑后继关逻辑后继关系的系的数据域数据域A AB BC CD DE E 通过指针来描述数据元素间的逻辑关系H头指针2022-3-3带有头结点的单链表带有头结点的单链表A AB BC CD D H头结点2022-3-3单链表的存储结构单链表的存储结构typedef struct Node typedef struct Node ElemType data; ElemType data; struct Node struct Node * *next ; next ; Node , Node , * *LinkLis

11、t ; LinkList ; 2022-3-3Node e；/定义了一个结点类型的变量eNode *p；/定义了一个结点类型的指针变量pp-data/p指向的结点的数据域p-next/p指向的结点的后继结点指针LinkList p；/与Node *p；作用相同2022-3-3定义了结点指针变量之后需要对变量进行赋值！比如：p=&e;/p指向了结点e更多的时候，我们为了节省变量的使用，不再定义结点变量，而是直接向内存申请一个结点需要的空间，让结点指针指向这个结点空间。操作如下：p=（Node*)malloc(sizeof(Node); /p指向由malloc函数申请的一个结点空间2022

12、-3-3如果有：p=(Node*)malloc(sizeof(Node);则该指针变量有两个分量：p-data-用来存储数据元素p-next-用来指向p的后继结点2022-3-3p语句与对应的示意图：p=(Node*)malloc(sizeof(Node);p-data=A;A A pp-next=NULL;A Ap请根据如下语句画出对应的示意图Node *q,*r;q=(Node*)malloc(sizeof(Node);q-data=3;r=(Node*)malloc(sizeof(Node);r-data=5;q-next=r;r-next=NULL;2022-3-3根据示意图写出对应的

13、语句 Node *p; p=(Node*)malloc(sizeof(Node); p-data=A; Node *r; r=p; 2022-3-3A ApA Apr在这里，我们主要讨论的单链表的基本运算有：l 初始化单链表l 建立单链表：头部插入法和尾部插入法l 查找l 求表长l 单链表的插入l 单链表的删除l 输出一个单链表中的结点数据l 合并两个单链表 .2022-3-3如果说顺序表的操作是对表L的数组L.elem和表尾元素标志L.last的操作，那么单链表的操作就是对结点指针p、结点的数据域p-data、结点的指针域p-next的操作。2022-3-32022-3-3初始化单链表的目的

14、是创建一张带有头结点的空的单链表。带有头结点的空单链表示意图如下：InitList (LinkList *L) *L=(LinkList)malloc(sizeof(Node); (*L)-next=NULL;2022-3-3 L根据线性表的元素建立相对应的单链表，比如有如下线性表： L=( 3，6，8，12)对应着该线性表的单链表存储示意图为：单链表的创建其实就是从一个空单链表通过逐一将存放数据元素的结点链接到表中过程。2022-3-33 36 68 812 12 L2022-3-3 L3 36 68 812 12 L6 68 812 12 L8 812 12 L12 12 L3 36 68

15、 812 12 L头部插入法头部插入法：头部插入法：void CreateFromHead(LinkList L)void CreateFromHead(LinkList L) Node Node * *s ; s ; int v; int v; int flag=1; int flag=1; while(flag) while(flag) scanf(“%d”,&v); scanf(“%d”,&v); if(v!=-100) if(v!=-100) s=(Node s=(Node* *)malloc(sizeof(Node);)malloc(sizeof(Node); s-d

16、ata=v; s-data=v; s-next=L-next; s-next=L-next; L-next=s; L-next=s; /if/if else flag=0; else flag=0; /while/while /CreateFromHead /CreateFromHead 2022-3-32022-3-3 L3 36 68 812 12 L3 36 68 8 L3 36 6 L3 3 L3 36 68 812 12 L尾部插入法尾部插入法：尾部插入法：void CreateFromTail(LinkList L)void CreateFromTail(LinkList L) N

17、ode Node * *r ,r ,* *s ; s ; int v , flag=1; int v , flag=1; r=L; r=L; while(flag) while(flag) scanf(“%d”,&v); scanf(“%d”,&v); if(v!=-100) if(v!=-100) s=(Node s=(Node * *)malloc(sizeof(Node);)malloc(sizeof(Node); s-data=v; s-data=v; r-next=s; r-next=s; r=s; r=s; /if/if else flag=0; r-next=NU

18、LL; else flag=0; r-next=NULL; /while/while /CreateFromTail /CreateFromTail 2022-3-3在顺序表中，用数组下标来表示数据元素的存储地址，因此，如果当前元素的位置为i，则它的后继的存储位置为i+1,换句话说，执行一次i=i+1，就可以获取当前元素的后继元素的下标位置。在一个单链表中，如果已经知道了当前数据元素结点的存储地址为p，那么，该结点的后继结点的地址为什么？2022-3-3将单链表中的结点中的数据依次输出。算法思想：首先从首元结点开始输出其数据域中存储的数据，然后输出该结点的后继结点的数据域中的数据，一直到该链表

19、的最后一个结点，也就是表尾结点为止。2022-3-32022-3-33 36 68 812 12 L3 6 8 12 0 1 2 3 4 MAXSIZE-1 i ip pL.elemL.elem要获取当前元素的后继元素位置，就要执行一次i=i+1要获取当前结点的后继结点位置，就要执行一次p=p-next3首元数据元素的位置为0,输出当前位置的数据元素指向首元结点的指针为L-next,输出当前指针所指向的结点的数据366881212L.last+1NULLi=0;/ 顺序表首元的下标位置,即从首元开始输出while(inext; i+; return i;2022-3-3该算法的目的是查找单链表

20、中序号为i的那个结点，也就是第i个结点。方法：从头结点开始依次顺着链域扫描，用指针p指向当前扫描到的结点。初始指向头结点，用j作为计数器，初值为0，当j=i的时候，指针p所指向的结点就是要找寻的第i个结点。2022-3-3请同学自己完成。2022-3-3该算法的目的是在单链表中查找是否有值等于e的结点。查找算法与顺序表的按值查找类似，从头结点出发，顺链逐个将结点值和给定的值e作比较，若查找不成功，返回NULL，若查找成功，则返回该结点的地址（也就是指向该结点的指针）2022-3-3请同学们自己描述 ！2022-3-3该操作的目的是在单链表的第i个结点的位置上插入存储数据为e的结点。我们可以理解

21、为在第i-1个结点的后面插入新结点。当i=3,e=7时，观察下面的示意图，考虑插入前到插入后都发生了什么样的变化。插入前：插入后：2022-3-33 36 68 812 12 L3 36 67 712 12 L8 82022-3-33 36 68 812 12 L3 36 67 712 12 L8 87 7prepres sp-nextp-nextpre-next=spre-next=ss-nexts-nexts-next=pre-nexts-next=pre-next2022-3-31.找到插入位置：从头结点（第0个结点）开始，通过指针的移动获得指向第i-1个结点的指针2.申请新结点空间，存

22、储带插入的数据3.改变结点的后继指针，将待插入结点插入到插入位置后2022-3-3算法：int InsertLinkListint InsertLinkList（LinkList LLinkList L，int i int i ，ElemType e)ElemType e) Node Node * *pre , pre , * *s; int j ; s; int j ; pre=L; j=0; pre=L; j=0; while(pre!=NULL&ji-1) while(pre!=NULL&jnext; j+; pre=pre-next; j+; if(!pre)print

23、f(“ if(!pre)printf(“插入位置不合理！插入位置不合理！”);return 0”);return 0； s=(Node s=(Node* *)malloc(sizeof(Node);)malloc(sizeof(Node); s-data=e; s-data=e; s-next=p-next; p-next=s; s-next=p-next; p-next=s; return 1 return 1； 查看一下单链表的插入算法，看一看插入算法中最查看一下单链表的插入算法，看一看插入算法中最费时间的是什么操作？费时间的是什么操作？插入的过程时间复杂度为多少？插入的过程时间复杂度为多

24、少？2022-3-3该运算的目的是删除单链表中的第i个结点，并带回被删除结点的数据。若i=3，查看一下删除之前和删除之后的状态。删除前：删除后：2022-3-33 36 68 812 12 L3 36 67 712 12 L8 82022-3-33 36 68 812 12 L6 63 37 712 12 L8 8r rr-nextr-nextpreprepre-next=r-nextfree(r)1 . 找到待删除结点的前驱结点并由指针pre指向2. 利用指针的赋值删除第i个结点 3. 释放被删除结点所占用空间2022-3-3int DelList(LinkList L , int i ,

25、ElemType *e) Node *pre , *r ; int k ; pre=L; k=0; while(pre-next!=NULL & knext; k=k+1; if(!(pre-next)return 0; r=pre-next; pre-next=r-next; *e=r-data; free(r); return 1;2022-3-3有两个单链表LA和LB，其元素均为非递减有序排列。编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：新表LC利用现有的LA和LB中的元素结点空间，而不要额外申请结点空间。2022-3-32022-3-32 22

26、23 3 LALA1 13 33 3LBLB4 4 LCLCpapapbpb r r将单链表的最后一个结点的指针域由NULL改为指向表头结点，就是循环单链表。如下图：很多情况下，采用带有尾指针的循环单链表，如图：2022-3-33 36 67 712 12 L8 83 36 67 712 12 8 8rearrear空的循环单链表示意图什么样？空的循环单链表示意图什么样？写出初始化一个空循环单链表的的算写出初始化一个空循环单链表的的算法法一个非空的循环单链表的表尾结点的一个非空的循环单链表的表尾结点的特征是什么？特征是什么？2022-3-3问题：有两个带有头结点的循环单链表，编写算法，问题：有两个带有头结点的循环单链表，编写算法，将两个循环单链表链接成为一个循环单链表。将两个循环单链表链接成为一个循环单链表。情况情况1 1：如果两个循