第2章 线性表(2)

1、60-1第2章 线性表(二)60-21 线性表的链式存储结构表示让每个存储结点都包含两部分：让每个存储结点都包含两部分：数据域数据域和和指针域指针域指针指针指针指针指针指针或或样式：样式：数据域：数据域：存储存储元素的值元素的值指针域：指针域：存储存储直接后继直接后继或或直接前驱直接前驱元素的存储地址元素的存储地址设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率60-3其结点在存储器中的位置是其结点在存储器中的位置是随意随意的，的，即逻辑逻辑上相邻的数据元素在物理上不一定相邻。上相邻的数据元素在物理上不一定相邻。如何实现？ 通过来实现！链式存储结构特点La1a2a360-4

2、与链式存储有关的术语与链式存储有关的术语1）结点：）结点：数据元素的存储映像。由数据域和指针域数据元素的存储映像。由数据域和指针域两部分两部分组成；组成；2）链表：）链表： n n 个结点由个结点由指针链指针链组成一个链表。它是线性表的链式组成一个链表。它是线性表的链式存储映像存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。3）单链表、双向链表、循环链表）单链表、双向链表、循环链表： 结点只有一个指针域的链表，称为结点只有一个指针域的链表，称为单链表单链表或或线性链表线性链表；有两个指针域（有两个指针域（直接前驱和直接后继直接前驱和直接后继）的链表，称为）的链表，称为双向双向链表链

3、表；首尾相接的链表称为循环链表首尾相接的链表称为循环链表。a1heada2an循环链表示意图：循环链表示意图：60-5头指针L头指针L头结点首元结点首元结点空表：L=NULLL 1264126440164016头结点的作用头结点的作用：插入和删除第一个数据元素时不必对头指针进行特殊处理。与链式存储有关的术语与链式存储有关的术语60-6 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。1a头结点头结点 a1 a2 . an 头指针头指针 为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空 60-7

4、一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存储结构用储结构用单链表单链表表示如下，表示如下，请问其请问其头指针头指针的的值值是多少？是多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例1：答：答：头指针头指针是指向链是指向链表中表中第一个第一个结点的指结点的指针，因此关键是要寻针，因此关键是要寻找找第一个结点第一个结点的

5、的地址地址。7ZHAOH31称：头指针称：头指针H的值是的值是31练习：练习：60-8： 线性表具有两种存储方式，即顺序方式和链接方式。现线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表有一个具有五个元素的线性表L=23L=23，1717，4747，0505，3131，若它以链接方式存储在下列若它以链接方式存储在下列100100119119号地址空间号地址空间中，每个结点中，每个结点由数据（占由数据（占2 2个字节个字节）和指针（占）和指针（占2 2个字节个字节）组成，如下图所示。）组成，如下图所示。其中指针其中指针X X，Y Y，Z Z的的值值分别为多少？该线性表的

6、分别为多少？该线性表的首结点起始首结点起始地址地址为多少？为多少？末结点的起始地址末结点的起始地址为多少？为多少？答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = . .练习：练习：60-92 单链表 单链表单链表: 链表中的每个结点只有一个指针域链表中的每个结点只有一个指针域,我们将这种链表称为单链表。我们将这种链表称为单链表。 单链表包括单链表包括两个域两个域: 数据域数据域用来存储结点的值用来存储结点的值; 指针域指针域用来存储数据元素的直接后继的地用来存储数据元素的直接后继的地址址(或位置或位置)。DATA FIELDLINK FIELDi60-10 链

7、表图示(a) 链表的图示；(b) 链表的一般表示ABCDHead(a )Head(b )60-11讨论: 链表的数据元素有两个域，不再是简单数据链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。以要采用结构数据类型。答：答：以以2626个字母的链表为例，每个结点都有两个分量：个字母的链表为例，每个结点都有两个分量：字符型字符型指针型指针型假设每个结点用变量假设每个结点用变量表示，结点表示，结点指针用指针用 表示，其中两个分量分别用表示，其

8、中两个分量分别用datadata和和* *nextnext表示，该如何书写？表示，该如何书写？p方式方式1： 直接表示为直接表示为 node.data；node.next=方式方式2：p指向结点首地址，然后指向结点首地址，然后 p-data=; p-next= ; 方式方式3： p指向结点首地址，然后指向结点首地址，然后 (*p).data=； (*p).nextb60-12单链表的存储结构描述typedef structtypedef struct Node Node /结点类型定义结点类型定义 ElemType ElemType data data； structstruct Node N

9、ode * * next next；Node,Node,* *LinkListLinkList；/LinkList/LinkList为结构指针类型为结构指针类型60-13设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针, ,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。p-dataai的值的值p-nextai+1的地址的地址链表不具备的特点是链表不具备的特点是 。 A A、可随机访问任何一个元素、可随机访问任何一个元素 B B、插入、删除操作不需要移动元素、插入、删除操作不需要移动元素 C C、无需事先估计存储空间大小、无需事先估计存储空间

10、大小 D D、所需存储空间与线性表长度成正比、所需存储空间与线性表长度成正比 练习：练习：60-14静态链表静态链表 用数组模拟可利用空间表 0 1 2 3 4 5 6 7 8 9 3 8 1 -1 6 cur(游标) a2 a1 a4 a3 data # define MAXSIZE 10 /链表的最大长度typedef struct ElemType data;int cur;componet, SLinkListMAXSIZE;第第1 1个元素的下标：个元素的下标： SLinkList0.curSLinkList0.cur60-15单链表上的基本运算1 1 建立单链表建立单链表2 2 单

11、链表查找单链表查找3 3 单链表插入单链表插入4 4 单链表删除第单链表删除第i i个结点个结点60-16建立单链表（带头结点）1) 头插法建表（逆序）头插法建表（逆序）操作步骤：操作步骤： 建立一个建立一个“空表空表”； 输入数据元素输入数据元素an， 建立结点并插入；建立结点并插入； 输入数据元素输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1 依次类推，直至输入依次类推，直至输入a1为止。为止。ss60-17头插法建表算法Linklist CreateFromHeadLinklist CreateFromHead()() LinkList L;Node LinkL

12、ist L;Node * *s;ints;int flag=1; flag=1;/标志标志flagflag初值为初值为1 1 L=(Linklist)malloc(sizeof(Node L=(Linklist)malloc(sizeof(Node););/分配头结点分配头结点 L-next=NULL;L-next=NULL; while(flag while(flag) ) /输入输入“$”$”时时, flag, flag置置0, 0, 建表结建表结束束 c=getchar c=getchar(); (); if(c if(c!=$) !=$) /为新结点分配存储空间为新结点分配存储空间 s

13、=(Node s=(Node* *)malloc(sizeof(Node)malloc(sizeof(Node); s-data=c;); s-data=c; s-next=L-next; L-next=s;s-next=L-next; L-next=s; /链接链接 else flag=0;else flag=0; return L return L； 60-18r c c1 1 s sLc cn n s srr 2) 尾插法建表：设尾指针r建立一个建立一个“空表空表”, r 指向头结点指向头结点;输入数据元素输入数据元素C1, 建立结点并链接建立结点并链接, r指向该结点；指向该结点；输入

14、数据元素输入数据元素C2, 建立结点并建立结点并链接链接, r指向该结点；指向该结点；输入数据元素输入数据元素Cn, 建立结点并建立结点并链接链接, r指向该结点；指向该结点；c c2 2 s sr 60-19尾插法建表算法Linklist CreateFromTailLinklist CreateFromTail() () /新结点加到链表末尾新结点加到链表末尾 LinkList L;Node LinkList L;Node * *r r, ,* *s;ints;int flag =1; flag =1;/flag/flag初值初值 L=(Node L=(Node * *)malloc(si

15、zeof(Node)malloc(sizeof(Node); ); /分配头结点分配头结点 L-next=NULL; L-next=NULL; r=L;r=L; /r/r始终指向链表的表尾始终指向链表的表尾 while(flagwhile(flag) ) /输入输入“$”$”时时flagflag为为0 0，建表结，建表结束束 c=getchar c=getchar();(); if(c if(c!=$)!=$) s=(Node s=(Node* *)malloc(sizeof(Node);s)malloc(sizeof(Node);s-data=c;-data=c; r-next=s; r=s

16、r-next=s; r=s /链接链接 else flag=0; else flag=0; r-next=NULL;r-next=NULL; return L return L； 60-20单链表查找（带头结点）1) 按序号查找按序号查找 算法描述：设带头结点的单链表的长度算法描述：设带头结点的单链表的长度为为n, 要查找表中第要查找表中第i个结点个结点, 则需要从单链表则需要从单链表的头指针的头指针L出发出发, 从头结点（从头结点（L-next）开始顺）开始顺着链域扫描着链域扫描, 用指针用指针p指向当前扫描到的结点指向当前扫描到的结点,初值指向头结点初值指向头结点 (p=L), 用用j做记

17、数器做记数器, 累计当累计当前扫描过的结点数前扫描过的结点数(初值为初值为0), 当当j=i 时时, 指针指针p所指的结点就是要找的第所指的结点就是要找的第i个结点。个结点。60-21L 线性表的操作 Get (L, i)在单链表中i=3时,Get的实现过程:211830754256pppj1 2 3P-data=3060-22 因此，查找第因此，查找第 i 个数据元素的基本个数据元素的基本操作为：操作为：移动指针，比较移动指针，比较 j 和和 i 。 令指针令指针 p 始终始终指向指向线性表中第线性表中第 j 个数据元素。个数据元素。 单链表是一种单链表是一种顺序存取顺序存取的结构的结构,

18、为为找第找第 i 个数据元素个数据元素, 必须先找到第必须先找到第 i-1个个数据元素。数据元素。60-23按序号查找算法实现/ /* *带头结点，找第带头结点，找第i i个结点个结点, ,找到返回指向它的指针找到返回指向它的指针; ;否则返回空否则返回空* */ /Node Node * * Get(LinkList L, int Get(LinkList L, int i) i)练习：练习： Node *p； p=L；j=0； / 从头结点开始扫描 while (p-next!=NULL)&(jnext； j+； / 扫描下一结点 if（i= =j）return p； / 找到了第

19、i个结点 else return NULL； / 找不到,i0或in60-242) 2) 按值查找按值查找算法描述：按值查找是指在单链表中算法描述：按值查找是指在单链表中查找是否有结点值等于查找是否有结点值等于e e的结点，若有的话，的结点，若有的话，则返回首次找到的其值为则返回首次找到的其值为e e的结点的存储位的结点的存储位置，否则返回置，否则返回NULLNULL。查找过程从单链表的头。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点指针指向的头结点出发，顺着链逐个将结点的值和给定值的值和给定值e e作比较。作比较。60-25按值查找算法实现/ /* *带头结点，查找其结点值等于

20、带头结点，查找其结点值等于keykey的结点，若找到的结点，若找到则返回该结点的位置则返回该结点的位置p p，否则返回，否则返回NULL NULL * * / /Node Node * *Locate( LinkList L,ElemTypeLocate( LinkList L,ElemType key) key) Node *p; p=L-next; / 从表中第一个结点比较 while (p!=NULL) if (p-data!=key) p=p-next; else break; / 找到结点key，退出循环 return p;练习：练习：60-26ai-13. 单链表插入操作单链表插入

21、操作 InsList(L, i, e)的实现的实现： 有序对有序对 改变为改变为 和和 eaiai-1 可见可见, 插入结点需要修改第插入结点需要修改第 i-1 个结点的个结点的指针和新结点的指针。指针和新结点的指针。在单链表第在单链表第i i个结点之前插入结点的步骤为个结点之前插入结点的步骤为: :pres1)1)找到单链表的第找到单链表的第i-1i-1个结点并由指针个结点并由指针prepre指示。指示。2)2)然后申请一个新结点并由指针然后申请一个新结点并由指针s s指示。指示。3)3)将将prepre指示结点的指针值赋给指示结点的指针值赋给s s指示结点的指针域。指示结点的指针域。 (

22、(将第将第i i个结点链接到新结点上个结点链接到新结点上) )4)4)然后修改然后修改prepre指示结点的指针域指示结点的指针域, , 使它等于使它等于s s。 ( (新结点链接到第新结点链接到第i-1i-1个结点上个结点上) )插入到第i个位置（带头结点）60-27int InsList(LinkList L,int i,ElemTypeint InsList(LinkList L,int i,ElemType e) e) /在单链表在单链表L L第第i i个结点前插入值为个结点前插入值为e e的新结点的新结点 Node Node * *pre,pre,* *s; pre=L; ints;

23、 pre=L; int k=0; k=0; /先找到第先找到第i-1i-1个结点的存储位置个结点的存储位置, ,让让PrePre指向它指向它 while(pre-next!=NULL&kwhile(pre-next!=NULL&ki-1)next;-next; k=k+1; k=k+1; if(k if(k!=i-1) return 0; !=i-1) return 0; s=(Node s=(Node* *)malloc(sizeof(Node)malloc(sizeof(Node); ); /申请新结点申请新结点 s-data=e; s-data=e; /将将e e赋给赋给

24、s s指示的数据域指示的数据域 s-next=pre-next; pre-next=s;s-next=pre-next; pre-next=s; /链接链接 return 1;return 1; 60-28 s=(Node s=(Node* *)malloc(sizeof(Node)malloc(sizeof(Node); ); /申请新结点申请新结点 s-data=e; s-data=e; /将将e e赋给赋给s s的数据域的数据域 s-next=pre-next; pre-next=s; s-next=pre-next; pre-next=s; /链接链接ai-1 eaiai-1pres6

25、0-29在链表的插入操作中，结点插入的位置可能有四种情况。 设Head是头指针，s是插入结点的存储地址。(1) 原来链表为空表，即Head=NULL，则插入结点为表首结点，表示为Head=s；s-next=NULL；(2) 插入位置在表中第一个结点Head之前，则插入结点为新的表头，表示为s-next=Head；Head=s；插入到第i个位置（无头结点）60-30(3) 插入位置在表的中间，为q结点之后，p结点之前，表示为q-next=s；s-next=p； (4) 插入位置在链尾，即新结点s作为原表尾结点p之后的新表尾，表示为p-next=s；s-next=NULL；60-31删除第i个结点

26、（带头结点）操作为操作为: :找到线性表中第找到线性表中第i-1i-1个结点个结点* *p,p,修改其指针域修改其指针域让它指向第让它指向第i+1i+1个结点。释放第个结点。释放第i i个结点的空间。个结点的空间。ai-1aiai+1ai-1r= p-next; p-next= r-next;r= p-next; p-next= r-next; free(rfree(r););pr60-32int DelList(LinkList L,int i,ElemTypeint DelList(LinkList L,int i,ElemType * *e)e)/删除单链表删除单链表L L中第中第i i

27、个元素个元素, ,并保存其值到变量并保存其值到变量* *e e中中 Node Node * *p,p,* *r; p=L; intr; p=L; int k =0; k =0; while(p while(p-next!=NULL & knext!=NULL & knext; k=k+1; p=p-next; k=k+1; if(k if(k!=i-1) !=i-1) /即循环因即循环因p-next=NULLp-next=NULL而跳出而跳出 return 0;return 0; r=p-next; p-next=r-next;r=p-next; p-next=r-next;

28、/删除结点删除结点 free(rfree(r); ); / / 释放被删除结点所占空间释放被删除结点所占空间 return 1;return 1; 60-33根据被删除结点在链表中的位置，删除操作有如下四种情况：(1) 链表中只有一个结点，该结点就是被删除的结点，其操作为Head=NULL；或 Head=Head-next；(2) 被删除的结点是链中第一个结点，其操作为 Head=Head-next；删除指定值的结点（无头结点）60-34(3) 被删除的结点在链的中间，其中删除结点的地址为r，前趋结点的地址为p，其操作为p-next=r-next；(4) 被删除的结点在链尾，其中删除结点的地址

29、为r，前趋结点的地址为p，其操作为p-next=NULL；或 p-next=r-next；下图给出了线性表删除算法的框图。 60-35线性链表删除算法框图开始循环查找值为KEY的结点是否找到？是否第一个结点?删除中间或链尾结点删除结点送空间表结束输出无此结点修改链首YYNN60-36删除算法：DELETE(head，key)/* 在head为入口的链表中删除值为key的结点 */ r=head；p=r； /* 设置前趋结点的地址 */ while(r!=NULL)&(r-data!=key) p=r； r= r-next； /* 查找删除结点的位置 */60-37if(r=NULL)

30、printf(无此结点)；return；else if(head=r) head=r-next；/* 删除头结点 */ else p-next=r-next；/*删除链中间和链尾结点 */ free(r)；60-383 循环链表 最后一个结点的指针域的指针又指回最后一个结点的指针域的指针又指回第一个结点（或头结点）的链表第一个结点（或头结点）的链表 a1 a2 . an 和单链表的差别: 判别链表中尾结点的条件不再是“后继指针是否为空”，而是“后继指针是否为头指针”。60-39rear L空链表空链表a1ai-1aian L设头指针的一般形式设头指针的一般形式 a1ai-1aian 设尾指针的

31、一般形式设尾指针的一般形式 rear-next带头结点的循环带头结点的循环单链表示意图单链表示意图60-40通过查询，确定关键字值KEY不在链中，该结点插入的位置和插入的操作有如下几种情况：(1) 若表空(Head=NULL)，则插入结点后是只有一个结点的循环链表。(2) 若表非空，则分为三种情况： 插入的位置是在第一个结点，即原表的第一个结点成为结点插入后新表的第二个结点，同时为了保持循环链表的结构特征，在形成新的入口后，链表中最末一个结点的链指针应修正指向新的入口结点。循环链表的插入操作（无头结点）60-41 插入的位置是在最末一个结点之后，那么，最末一个结点的指针指向插入的结点，插入结点

32、的指针仍指向首结点。 插入的位置是在链的中间，那么可通过插入位置的前趋结点的指针，完成新结点的插入。下图所示为四种插入操作的示意图。 60-42循环链表的插入操作HeadxxHead(c)(d)(a)Headx(b)Headx60-43 下图给出了循环链表删除关键字值为KEY的结点的算法框图。循环链表的删除操作（无头结点）60-44循环链表删除算法框图开始调用查找子程序被删除记录是否在表中？被删除记录是否在表首？表中是否只有一个记录？查循环链表最末一个记录删除指定的记录，修正循环链表入口最末一个记录链的指针指向新的入口 删除指定的记录， 修正有关链指针删除指定的记录，表空被删记录不在表中被删除

33、记录送空链表结束NYYNNY60-45 必须注意，在循环链表中，要充分考虑到可能出现被删除结点位置不同的各个边界条件。若被删除结点在链首，则必须修改入口Head，而且还要考虑到链表中最末一个记录的指针要指向结点删除后的新入口，该情况的操作示意图如下图所示；特殊情况下，被删除结点是第一个且仅只有这一个结点，那么循环链表入口应设置为空，Head=NULL；其他情况与单链表的删除结点的算法相似。60-46循环链表删除首结点(a) 删除结点之前；(b) 删除结点之后ijkHeadjkHead(a )(b )60-47例例 有两个带头结点的循环单链表有两个带头结点的循环单链表LALA、LBLB，编，编写

34、算法，将两个循环单链表合并为一个循环单写算法，将两个循环单链表合并为一个循环单链表，其头指针为链表，其头指针为LALA。算法思想：算法思想：先找到两个链表的尾，并分别由指先找到两个链表的尾，并分别由指针针p p、q q指向它们，然后将第一个链表的尾与第指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个二个表的第一个结点链接起来，并修改第二个表的尾表的尾q q，使它的链域指向第一个表的头结点。，使它的链域指向第一个表的头结点。练习：练习：60-48LinkList merge(LinkList LA,LinkListLinkList merge(LinkList LA,L

35、inkList LB) LB)/ /* *此算法将两个循环单链表的首尾连接起来此算法将两个循环单链表的首尾连接起来* */ / Node Node * *p, p, * *q; p=LA; q=LB;q; p=LA; q=LB; while(p while(p-next!=LA) p=p-next;-next!=LA) p=p-next; /找到找到LALA的表尾的表尾 while(qwhile(q-next!=LB) q=q-next;-next!=LB) q=q-next; /找到找到LBLB的表尾的表尾 p-next=LB-next;p-next=LB-next; /使使LALA尾指针指

36、向尾指针指向LBLB第第1 1个结点个结点 q-next=LA;q-next=LA; /使使LBLB的尾指针指向表的尾指针指向表LALA的头结点的头结点 free(LBfree(LB);); /释放释放LBLB的头结点空间的头结点空间 return(LAreturn(LA);); 60-49 4 双向链表双向链表typedef structtypedef struct Node Node /结点类型定义结点类型定义 ElemType ElemType data data； structstruct Node Node * * next next； structstruct Node Node

37、* * prior; prior;Node,Node,* *LinkListLinkList；/LinkList/LinkList为结构指针类型为结构指针类型后继指针域后继指针域prior data next前驱指针域前驱指针域数据域数据域60-50双向链表的结构Head60-51双向链表的结构有以下特点（无头结点）：(1) 若Head为空(NULL)，则双向链表为空。 (2) 在双向链表中，若结点p有p-Lnext=NULL则该结点是链的第一个结点；若结点p有p-Lnext=p-Rnext=NULL 则该结点p是链的第一个结点且该链仅有这个结点p。 (3) 在双链表中，若结点p有p-Rnext=NULL则该结点是链的最末一个结点。60-52(4) 在双向链表中，若结点p是表中任意结 点 的 地 址 ， 则 该 结 点 的 前 趋 结 点 是pLnext，后继结点的地址是pRnext，对结点p也可以表示为p= p-Rnext-Lnext= p-Lnext-Rnext这个表达式非常直观地反映了双向链表结构的本质特点，即无论是