《第2章_线性表.ppt》由会员分享，可在线阅读，更多相关《第2章_线性表.ppt（66页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章章 线性表线性表2.1 2.1 线性表的基本概念线性表的基本概念线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例应用举例应用举例12.1 线性表的基本概念线性表的基本概念、线性表、线性表它是一种最简单的线性结构。是一种可以在任它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由意位置进行插入和删除数据元素操作的，由n（n0)个相同类型数据
2、元素个相同类型数据元素a0,a1,an-1组成的线性结组成的线性结构。构。23（a0,a1,ai-1，ai,ai1，,an-1）线性表的逻辑结构：线性表的逻辑结构：n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线性终点 （A,B,C,D,Z）4学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男192003级电信级电信0301班班012003010704赵玉凤赵玉凤女
3、女182003级电信级电信0302班班012003010813王王泽泽男男192003级电信级电信0303班班012003010906薛薛荃荃男男192003级电信级电信0304班班012003011018王 春男 19 192003级电信级电信0305班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中
4、的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例例1分析分析26个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。、线性表抽象数据类型、线性表抽象数据类型 它包括两个方面：它包括两个方面：数据集合：数据集合：a0,a1,an-1 ai的数据类型为的数据类型为DataType 操作集合操作集合：(1)ListInitiate(L)初始化线性表初始化线性表 (2)ListInsert(L,i,x)插入数据插入数据元素元素 (3)ListLength(L)求当前数据求当前数据元素个数元素个数 (4)ListDelete(L,
5、i,x)删除数据删除数据元素元素 (5)ListGet(L,i,x)取数据元素取数据元素 等等53 3、线性表的存储结构、线性表的存储结构(1)顺序存储结构（顺序存储结构（P21P21）:它是使用一片它是使用一片地址连续地址连续的有的有限内存单元空间存储数据元素的一种计算机存储数限内存单元空间存储数据元素的一种计算机存储数据方法。据方法。特点：特点：(任意两个在逻辑上相邻的数据元素在物理位置任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻上也必然相邻)逻辑上相邻的元素，物理上也相邻。逻辑上相邻的元素，物理上也相邻。(2)(2)链式存储结构链式存储结构(P27P27):):它是把数据元素和指
6、针定义成它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。起来的一种计算机存储数据方法。特点：特点：任意两个在任意两个在逻辑上相邻逻辑上相邻的数据元素在的数据元素在物理上不物理上不一定相邻一定相邻，数据元素的逻辑次序是通过链中的指针，数据元素的逻辑次序是通过链中的指针链接实现的。链接实现的。62.2 线性表的顺序表示和实现线性表的顺序表示和实现7一一、顺序表的存储结构顺序表的存储结构二、二、顺序表的实现顺序表的实现三、三、顺序表的运算效率分析顺序表的运算效率分析一、一、顺序表的存储结构表示顺序表的存储
7、结构表示 1、顺序表顺序表：用一组用一组地址连续地址连续的存储单元依次存储线的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。表。它通常采用静态数组实现数据元素的存储。8可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即：VnVn的有效范围是从的有效范围是从 V0V0Vn-1Vn-1(1)逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位置，则其他元若已知
8、表中首元素在存储器中的位置，则其他元素存放位置亦可求出素存放位置亦可求出（利用数组利用数组VnVn的的下标下标）。）。9设首元素设首元素a0的存放地址为的存放地址为LOC(a0)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+LLOC(LOC(a aii)=LOC()=LOC(a a00)+L*i)+L*i对上述公式的解释如图所示对上述公式的解释如图所示2、线性表顺序存储特点：、线性表顺序存储特点：10a a0 0a a1 1a
9、 ai ia ai+1i+1a an-1n-1 地址地址 内容内容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空闲区空闲区i+1i+1Lb=LOC(a0)b+L Lb+i+iL Lb+(n-1)+(n-1)L Lb+(MaxSize-1)+(MaxSize-1)L LLOC(aLOC(aii)=LOC(a)=LOC(a00)+L*i)+L*i3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数，每个数组元素用相邻的组元素用相邻的个字节个字节存储。存储器按字节编址，存储。存储器按字节编址，设存储数组元素设存
10、储数组元素 的第一个字节的地址是的第一个字节的地址是，则则 的第一个字节的地址是多少？的第一个字节的地址是多少？11113LOC(M3)=98+53=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a0)+L*i例例112charV30;voidbuild()/*字母线性表的生成字母线性表的生成,即即建表操作建表操作*/inti;V0=a;for(i=1;i=n-1;i+)Vi=Vi-1+1;程序程序2-1用数组用数组V来存放来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z），写出在顺序结构上），写出在顺序结构上生成生成和和显示显示该该表的
11、表的C语言程序。语言程序。13voidmain()/*主函数主函数，字母线性表的，字母线性表的生成和输出生成和输出*/intn=26;/*n n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V V的的 实际下标实际下标*/build();display();voiddisplay()/*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/inti;for(i=0;i=i;j-)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1 核核心心语语句：句：17123456789121321242528304277123456
12、781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：3)3)删除删除实现步骤：实现步骤：将第将第i+1 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i 是否合法是否合法?18删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素for(j=i+1;jdata=aa;p-next=q q;方式方式3：p指向结点首地址，然后指向结点首地址，然后(*p).data=aa；(*p).nextq qaabq qp p33设设p p为指向链表的
13、第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址附附1：介绍介绍C的三个有用的库函数的三个有用的库函数/算符（都在算符（都在中）：中）：sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m)开辟开辟m m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p)释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。si
14、zeof(x)计算计算x x的长度的长度malloc(m)开开m m字节字节空间空间free(p)删除一个变量删除一个变量34问问1：自定义结构类型变量自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指针p）是多少？）是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node)/单位是字节单位是字节p(node*)malloc(m)free(p)/只能借助只能借助node的指针删除！的指针删除！P-data=P-data=a a;p-;p-next=qnex
15、t=q(程序程序2-2.c)单链表的建立和输出单链表的建立和输出例：用单链表结构来存放例：用单链表结构来存放26个英文字母组成的线个英文字母组成的线性表（性表（a，b，c，z）,请写出请写出C语言程序。语言程序。35实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要空间并及时赋值，后继结点的地址要提前提前送给前面的指针。送给前面的指针。先挖先挖“坑坑”,后种后种“萝萝卜卜”！36#include#include#include#includetypedefstructnodechardata;structnode
16、*next;node;将全局变量及函数提前说明：将全局变量及函数提前说明：node*p,*q,*head;/一般需要一般需要3 3个指针变量个指针变量intn;/数据元素的个数数据元素的个数intm=sizeof(node);/*/*结构类型定义好之后，结构类型定义好之后，每个每个nodenode类型类型的长的长度就固定了，度就固定了，m m求一次即可求一次即可*/37新手特别容易忘记！新手特别容易忘记！int i;head=(node*)malloc(m);/m=sizeof(node)前面已求出前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符第一个结点值
17、为字符ap-next=(node*)malloc(m);/为后继结点为后继结点“挖坑挖坑”！p=p-next；/让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1;/最后一个元素要单独处理最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build()/字母链表的生成字母链表的生成。要一个个慢慢链入要一个个慢慢链入38p=head;while(p)/当指针不空时循环（仅限于当指针不空时循环（仅限于无头结点无头结点的情况）的情况）printf(%c,p-data);p=p-next;/让指针不断让指针不断“顺
18、藤摸瓜顺藤摸瓜”讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？sum+;sum+;sum=0;sum=0;voiddisplay()/*字母链表的输出字母链表的输出*/void main()void main()build();build();display();display();二、单链表的操作实现二、单链表的操作实现定义单链表结点的结构体如下定义单链表结点的结构体如下:t typedef struct Node DataType data;struct Node*next;SLNode;、初始化、初始化void ListInitiate(SL
19、Node*head)*初始化*/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1);(*head)-next=NULL;/*置链尾标记NULL*/3940、求单链表中数据元素的个数、求单链表中数据元素的个数int ListLength(SLNode*head)int ListLength(SLNode*head)SLNode*p=head;SLNode*p=head;/*p/*p指向头结点指向头结点*/int size=0;int size=0;/*size/*size初始为初
20、始为0*/0*/while(p-next!=NULL)/*while(p-next!=NULL)/*循环计数循环计数*/p=p-next;p=p-next;size+;size+;return size;return size;、向单链表中、向单链表中插入插入一个元素一个元素41在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xqabp链表插入的核心语句：链表插入的核心语句：Step 1Step 1Step 1Step 1：q q q q-next=-next=p-nextp-next;Step 2Step 2Step 2Step 2：p-nextp-next=
21、q=q；p-nexts-next思考：思考：思考：思考：Step1Step1Step1Step1和和和和2 2 2 2能互换么？能互换么？能互换么？能互换么？X X 结点的生成方式：结点的生成方式：m=m=sizeof(SLNode);q=(SLNode*)malloc(m);q-data=X X;q-next=?bap插插插插 入入入入 X X 42 int ListInsert(SLNode*head,int i,DataType x)int ListInsert(SLNode*head,int i,DataType x)SLNode*p,*q;SLNode*p,*q;int j;int
22、j;p=head;p=head;j=-1;j=-1;while(p-next!=NULL&j next!=NULL&j next;j+;p=p-next;j+;if(j!=i-1)if(j!=i-1)printf(printf(插入位置参数错！插入位置参数错！););return 0;return 0;(2)(2)if(q=(SLNode*)malloc(sizeof(SLNode)=NULL)if(q=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1);exit(1);q-data=x;q-data=x;(3)(3)q-next=p-next;q-next
23、=p-next;p-next=q;(4)p-next=q;(4)return 1;return 1;注：此单链表是带头结点的注：此单链表是带头结点的单链表的单链表的插入插入操作实现（操作实现（P29算法算法2.9）、从、从 单链表中删除一个元素单链表中删除一个元素43在链表中删除某元素在链表中删除某元素b b的示意图如下：的示意图如下：c a bp删除动作的核心语句删除动作的核心语句（要借助辅助指针变量（要借助辅助指针变量q q）：）：q=p-next;/首先保存首先保存b b的指针，靠它才能找到的指针，靠它才能找到c c；p-next=q-next;/将将a a、c c两结点相连，淘汰两结点
24、相连，淘汰b b结点；结点；free(q)；/彻底释放彻底释放b b结点空间结点空间p-next思考：思考：省略省略free(q)语句语句行不行？行不行？(p-next)-nextq44int ListDelete(SLNode*head,int i,DataType*x)int ListDelete(SLNode*head,int i,DataType*x)SLNode*p,*s;SLNode*p,*s;int j;int j;(1)p=head;(1)p=head;j=-1;j=-1;while(p-next!=NULL&p-next-next!=NULL&while(p-next!=NU
25、LL&p-next-next!=NULL&j i-1)j next;p=p-next;j+;j+;if(j!=i-1)if(j!=i-1)printf(printf(“插入位置参数错！插入位置参数错！”););return 0;return 0;(2)(2)s=p-next;s=p-next;*x=s-data;x=s-data;(3)(3)p-next=p-next-next;p-next=p-next-next;free(s);free(s);return 1;return 1;单链表的单链表的删除删除操作实现（操作实现（P30算法算法2.10）5、单链表的操作效率分析、单链表的操作效率分
26、析（1）查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为查找的时间复杂度为 O(n)。45时间效率分析时间效率分析（2）插入和删除插入和删除因线性链表不需要移动元素，只要修改指针，仅就插入或删因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为除而言，时间复杂度为O(1)。但是，如果要在单链表中进行在某结点但是，如果要在单链表中进行在某结点前前插或删除操作，插或删除操作，因为要因为要从头查找前驱从头查找前驱结点，所以一般情况下，结点，所以一般情况下，单链表插单链表插入和删除操作入和删除操作的时间
27、复杂度是的时间复杂度是O(n)（同顺序表）。（同顺序表）。三、应用举例三、应用举例程序2-3编程实现：建立一个单链表，首先依次输入数据元素,10，然后删除数据元素，最后依次显示当前表中的数据元素。#include#include#include typedef int DataType;#include LinList.h4647void main(void)void main(void)SLNode*head;SLNode*head;int i,x;int i,x;ListInitiate(&head);ListInitiate(&head);for(i=0;i10;i+)for(i=0;i
28、10;i+)if(ListInsert(head,i,i+1)=0)if(ListInsert(head,i,i+1)=0)printf(printf(错误错误!n);return;!n);return;if(ListDelete(head,4,&x)=0)if(ListDelete(head,4,&x)=0)printf(printf(错误错误!n);!n);return;return;48 for(i=0;i ListLength(head);i+)for(i=0;i 0)50p=(struct slnode*)malloc(sizeof(struct slnode);/*p=(struc
29、t slnode*)malloc(sizeof(struct slnode);/*申请一个新结点申请一个新结点*/p-data=d;p-data=d;p-next=NULL;p-next=NULL;if(head=NULL)head=p;/*if(head=NULL)head=p;/*若链表为空，则将头指针指向当前结点若链表为空，则将头指针指向当前结点p*/p*/else q-next=p;/*else q-next=p;/*链表不为空时，则将新结点链接在最后链表不为空时，则将新结点链接在最后*/q=p;/*q=p;/*将指针将指针q q指向链表的最后一个结点指向链表的最后一个结点*/scan
30、f(scanf(“%d%d”,&d);,&d);scanf(scanf(“%d,%d%d,%d”,&x,&y);,&x,&y);s=(struct slnode*)malloc(sizeof(struct slnode);s=(struct slnode*)malloc(sizeof(struct slnode);s-data=y;s-data=y;q=head;p=q-next;q=head;p=q-next;while(p!=NULL)&(p-data!=x)q=p;p=p-next;/*while(p!=NULL)&(p-data!=x)q=p;p=p-next;/*查找元素为查找元素为
31、x x的的指针指针*/s-next=p;q-next=s;/*s-next=p;q-next=s;/*插入元素插入元素y*/y*/四、循环单链表四、循环单链表循环链表循环链表示意图：示意图：循环单链表是单链表的另一种形式，其结构特点是链表中循环单链表是单链表的另一种形式，其结构特点是链表中的最后一个结点的指针域不再是结束标记，而是指向整个链表的最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。的第一个结点，从而使链表形成一个环。问：带头结点的循环单链表的插入、删除算法如何写？问：带头结点的循环单链表的插入、删除算法如何写？51xheada0anheadhe
32、ad52例：例：试写一算法，实现顺序表的就地逆置，即利用原表试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（的存储空间将线性表（a1,a2,a1,a2,.,an.,an）逆置为（）逆置为（anan，an-1an-1，.,a1.,a1）。）。参考程序：参考程序：void void inverseinverse(SeqList*L)(SeqList*L)DataType DataType temp temp;int i;int i;for(int for(int i i=0;=0;i isize-1)/2;size-1)/2;i i+)+)/循环次数为表长的一半循环次数为表长的一半
33、temptemp=L-list=L-listi i;L-list;L-listi i=L-listL-size-=L-listL-size-i i-1;-1;L-listL-size-L-listL-size-i i-1=-1=temptemp;五、双向链表五、双向链表、双向链表的存储结构、双向链表的存储结构双向链表：双向链表：链表中每个结点除后继指针域和数链表中每个结点除后继指针域和数据域外还有一个前驱指针域。据域外还有一个前驱指针域。其其结点的结构结点的结构为：为：双向链表结点的结构体定义如下：双向链表结点的结构体定义如下：typedef struct Node DataType data
34、;struct Node*next;struct Node*prior;DLNode;53prior datanext54带头结点的双向循环链表的结构示意图。带头结点的双向循环链表的结构示意图。headsa0 a1 an 与单链表类同，双向链表分带头结点和不带头结与单链表类同，双向链表分带头结点和不带头结点两种，也分有循环和非循环两种结构。下面仅讨论点两种，也分有循环和非循环两种结构。下面仅讨论带头结点的双向循环链表。带头结点的双向循环链表。2 2、双向链表的操作实现、双向链表的操作实现55(1)前插前插设设p已指向第已指向第i元素，请在第元素，请在第i元素元素前前插入元素插入元素xx sai
35、-1 ai p指针域的变化指针域的变化：ai-1的后继从的后继从ai(指针是指针是p)变为变为x（指针是（指针是s):s-next=p;p-prior-next=s;ai的前驱从的前驱从ai-1(指针是指针是p-prior)变为变为x(指针是指针是s);s-prior=p-prior;p-prior=s;p指针域的变化指针域的变化：后继方向：后继方向：ai-1的后继由的后继由 ai(指针指针p)变为变为 ai+1(指针指针 p-next);p-prior-next=p-next ;前驱方向：前驱方向：ai+1 的前驱由的前驱由 ai(指针指针p)变为变为ai-1(指针指针 p-prior);p
36、-next-prior=p-prior;56(2)双向链表的删除操作双向链表的删除操作设设p指向第指向第i个元素，删除第个元素，删除第i个个元素元素ai-1 ai ai+1 例例:已已知知P P结结点点是是双双向向链链表表的的中中间间结结点点，试试从从下下列列提提 供供 的的 答答 案案 中中 选选 择择 合合 适适 的的 语语 句句 序序 列列。a a在在P P结点后插入结点后插入S S结点的语句序列是结点的语句序列是-。57b b在在P P结点前插入结点前插入S S结点的语句序列是结点的语句序列是-。c c删除删除P P结点的直接后继结点的语句序列是结点的直接后继结点的语句序列是-。d d
37、删除删除P P结点的直接前驱结点的语句序列是结点的直接前驱结点的语句序列是-。e e删除删除P P结点的语句序列是结点的语句序列是-。58(1)P-next=P-next-next;(10)P-prior-next=P;(1)P-next=P-next-next;(10)P-prior-next=P;(2)P-prior=P-prior-prior;(11)P-next-prior=P;(2)P-prior=P-prior-prior;(11)P-next-prior=P;(3)P-next=S;(12)P-next-prior=S;(3)P-next=S;(12)P-next-prior=S
38、;(4)P-prior=S;(13)P-prior-next=S;(4)P-prior=S;(13)P-prior-next=S;(5)S-next=P;(14)P-next-prior=P-prior(5)S-next=P;(14)P-next-prior=P-prior(6)S-prior=P;(15)Q=P-next;(6)S-prior=P;(15)Q=P-next;(7)S-next=P-next;(16)Q=P-prior;(7)S-next=P-next;(16)Q=P-prior;(8)S-prior=P-prior;(17)free(P);(8)S-prior=P-prior
39、;(17)free(P);(9)P-prior-next=p-next;(18)free(Q);(9)P-prior-next=p-next;(18)free(Q);解答：解答：a.(12)(7)(3)(6)3a.(12)(7)(3)(6)3必须在必须在1212和和7 7的后面，其余的顺序可变的后面，其余的顺序可变b.(13)(8)(4)(5)b.(13)(8)(4)(5)同上同上c.(15)(1)(11)(18)c.(15)(1)(11)(18)不可变不可变d.(16)(2)(10)(18)d.(16)(2)(10)(18)不可变不可变e.(9)(14)(17)e.(9)(14)(17)2.
40、4 2.4 静态链表静态链表静态链表：静态链表：在数组中增加一个（或两个）指针在数组中增加一个（或两个）指针域，这些指针域用来存放下一个（或上一个）域，这些指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组数据元素在数组中的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的构造的单链表（或双链表）。静态链表中的指针又称仿真指针。指针又称仿真指针。5960 静态单链表的类型定义如下：静态单链表的类型定义如下：静态单链表的类型定义如下：静态单链表的类型定义如下：#defineMAXSIZE1000/预分配最大的元素个数（连续空间预分配最大的元素个数（连续空间typede
41、fstructDataTypedata;/数据域数据域intnext;/指示域指示域component,SLinkListMAXSIZE;/这是一维结构型数组这是一维结构型数组例例1 1：软考题：软考题：L=23L=23，1717，4747，0505，31 31 若此分量定义为若此分量定义为指针型指针型，属于，属于动态链表（题目中是指针）动态链表（题目中是指针）；若此分量定义为若此分量定义为整型整型（通常存放下标），则属于（通常存放下标），则属于静态链表静态链表。Z Z47474747Y Y3131V V23232323X X1717U U050510010010010011911911911
42、910410410410410810810810811611611611611211211211261例例2：一：一线性表线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？，用静态链表如何表示？data1 1 1 1ZHAOZHAO3LILI5QIANQIAN6WUWU0ZHOUZHOU4SUNSUN20 01 12 23 34 45 56 610001000cur说明说明1 1：假设假设S S为为SLinkListSLinkList型变量，则型变量，则SMAXSIZESMAXSIZE 为一个静态链表；为一个静态链表；S0.nextS0.next则表示第则表示
43、第1 1个结点在数组中的个结点在数组中的位置。位置。说明说明2 2：如果数组的第如果数组的第i i个分量表示链表个分量表示链表的第的第k k个结点，则：个结点，则：Si.dataSi.data表示第表示第k k个结点的数据；个结点的数据；Si.nextSi.next 表示第表示第k+1k+1个结点个结点(即即k k的直的直接后继接后继)的位置。的位置。i头结点头结点头结点头结点62说明说明3 3：静态链表的插入与删除操作与普通链表一样，不需要移静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。动元素，只需修改指示器就可以了。例如：在线性表例如：在线性表S=(ZHA
44、O,QIAN,SUN,LI,ZHOU,WU)的的QIAN,SUN之间之间插入新元素插入新元素插入新元素插入新元素LIU，可以这样实现：，可以这样实现：SSSS7 7 7 7.next=S3.next.next=S3.next.next=S3.next.next=S3.next；Step2:Step2:将将QIANQIAN的游标换为新元素的游标换为新元素LIULIU的的下标：下标：S3.next=S3.next=S3.next=S3.next=7 7 7 7Step1:Step1:将将QIANQIAN的游标值存入的游标值存入nextnext的游的游标中：标中：data2SUNSUN4ZHOUZH
45、OU0WUWU6QIANQIAN5LILI3ZHAOZHAO1 1 1 10 01 12 23 34 45 56 610001000curi头结点头结点头结点头结点LIULIU6 67 77 7本章小结本章小结631.1.线性结构线性结构(包括表、栈、队、数组）的定义和特点包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。直接后继。2.2.线性表线性表逻辑结构逻辑结构：“一对一一对一”或或 “1:11:1”存储结构：存储结构：顺序、链式顺序、链式运运 算：算：修改、插入、删除修改、插入、删除 查找和排序另述
46、查找和排序另述 3.3.顺序存储顺序存储特征：特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点：优点：随机查找修改快随机查找修改快 O(1)O(1)缺点：缺点：插入、删除慢插入、删除慢 O(n)O(n)改进方案：改进方案：链表存储结构链表存储结构链表存储结构链表存储结构64循环链表的特点：循环链表的特点：从任一结点出发均可找到表中其他结点从任一结点出发均可找到表中其他结点从任一结点出发均可找到表中其他结点从任一结点出发均可找到表中其他结点双向链表的特点：双向链表的特点：可方便可方便找到任一结点的前驱找到任一结点的前驱找到任一结点的前驱找到任一结点的前驱静态链表的特点：静态链表的特
47、点：不用指针也能实现链式存储和运算不用指针也能实现链式存储和运算4.4.链式存储链式存储特征：特征：逻辑上相邻，物理上未必相邻；逻辑上相邻，物理上未必相邻；优点：优点：插入、删除快插入、删除快 O(1)O(1)缺点：缺点：随机查找修改慢随机查找修改慢 O(n)O(n)5.5.几种特殊链表的特点：几种特殊链表的特点：65讨论讨论1 1：顺序存储和链式存储的区别和优缺点？顺序存储和链式存储的区别和优缺点？顺序存储时，顺序存储时，逻辑上相邻的数据元素，其物理存放地址逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；也相邻。顺序存储的优点是存储密度大，存储空间利
48、用率高；缺点是插入或删除元素时不方便。缺点是插入或删除元素时不方便。链式存储时，链式存储时，相邻数据元素可随意存放，但所占存储空相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。使用灵活。缺点是存储密度小，存储空间利用率低。顺序表顺序表适宜于做适宜于做查找查找这样的静态操作；这样的静态操作；链表链表宜于做宜于做插插入、删除入、删除这样的动态操作。若这样的动态操作。若线性表的长度变化不大线性表的长度变化不大，且，且其主要操作是查找，则采用顺序表；若其主要操作是查找，则采用顺序表；若线性表的长度变化线性表的长度变化较大较大，且其主要操作是插入、删除操作，则采用链表。，且其主要操作是插入、删除操作，则采用链表。讨论讨论2：什么是指针？指针的作用？什么是指针？指针的作用？66 指针指针即变量的内存地址。即变量的内存地址。指针主要功能指针主要功能有二：有二：提供了一种快速访问数组单元的途径；提供了一种快速访问数组单元的途径；使使C C语言函数可以修改其调用的参数。语言函数可以修改其调用的参数。