书签分享收藏举报版权申诉 / 90

立即下载

当前位置：首页 > 教育专区 > 大学资料 > 九江学院《数据结构》第02章线性表.ppt

九江学院《数据结构》第02章线性表.ppt

上传人：wuy****n92

文档编号：91225758

上传时间：2023-05-24

格式：PPT

页数：90

大小：553KB

( 4.5 )

《九江学院《数据结构》第02章线性表.ppt》由会员分享，可在线阅读，更多相关《九江学院《数据结构》第02章线性表.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、退出主目录下一页第二章线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 顺序表与链表的比较主目录下一页上一页退出本章要点n 线性表(Linear List)：由n(n)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)。记作：(a1，a2，an)n 这里的数据元素ai(1i n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。2.1 线性表的类型定义主目录下一页上一页退出本章要点例1、26个英文字母组成的字母表（A，B，C,Z）例2、某校

2、从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）2.1 线性表的类型定义主目录下一页上一页退出本章要点例3、学生健康情况登记表如下：2.1 线性表的类型定义姓名学号性别年龄健康情况王小林 790631 男 18 健康陈红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱.主目录下一页上一页退出本章要点例4、一副扑克的点数（2，3，4，J，Q，K，A）2.1 线性表的类型定义从以上例子可看出线性表的逻辑特征是：在非空的线性表中，有且仅有一个开始结点a1，它没有直

3、接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2i n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。主目录下一页上一页退出本章要点n 线性表的特点n 同一性：线性表中所有元素的性质相同n 有序性：除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱，最后一个数据元素无后继n 有穷性：数据元素在表中的位置只取决于它自身的序号，序号不可能无穷，故元素个数不可能无穷

4、2.1 线性表的类型定义主目录下一页上一页退出本章要点抽象数据类型（ADT）的表示ADT数据对象：结构关系：基本操作：ADT/（参数表）操作前提：操作结果：2.1 线性表的类型定义主目录下一页上一页退出本章要点线性表的抽象数据类型定义ADT LinearList数据元素:D=ai|aiD0,i=1,2,n,n0,D0为某一数据对象结构关系:S=|ai,ai+1 D0,I=1,2,n-1基本操作:(1)InitList(L)/初始化操作前提:L为未初始化线性表操作结果:将L初始化为空表(2)DestroyList(L)/删除表操作前提:线性表L已存在操作结果:将L销毁(3)Cl

5、earList(L)/内容清空操作前提:线性表L已存在操作结果:将表L置为空表主目录下一页上一页退出本章要点(4)EmptyList(L)/判空操作前提:线性表L已存在操作结果:如果L为空表则返回真,否则返回假(5)ListLength(L)/求长度操作前提:线性表L已存在操作结果:如果L为空表则返回0,否则返回表中的元素个数(6)Locate(L,e)/检索操作前提:表L已存在,e为合法元素值操作结果:如果L中存在元素e,则将“当前指针”指向e所在位置并返回真,否则返回假(7)GetData(L,i)/取元素操作前提:表L已存在,且i值合法,即1iListLength(L)操作结果:

6、返回线性表L中第i个元素的值线性表的抽象数据类型定义主目录下一页上一页退出本章要点(8)InsList(L,i,e)/插入(前插)操作前提:表L已存在,e为合法元素值且1iListLength(L)+1操作结果:将表L中第i个位置插入新的数据元素e,L的长度加1(9)DelList(L,i,&e)/删除操作前提:表L已存在且非空,1iListLength(L)操作结果:删除表L的第i个数据元素,并用e返回其值,L的长度减1ADT LinearList线性表的抽象数据类型定义主目录下一页上一页退出本章要点2.2.1 顺序表存储结构把线性表的结点按逻辑顺序依次存放在一组地址连续

7、的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l 2.2线性表的顺序表示和实现主目录下一页上一页退出本章要点元素an.元素ai.元素a2元素a1bb+mb+(i-1)*mb+(maxlen-1)*m存储地址内存状态Loc(元素i)=b+（i-1)*m首地址

8、起始地址基地址每个元素所占用的存储单元个数顺序存储结构示意图(顺序表)：2.2.1顺序表的存储结构主目录下一页上一页退出本章要点元素a1元素a2.元素ai+1.01i 可用C语言中的一维数组来描述:#defineM100/*定义M为常数100，M的值作为数组的最大容量*/intVM;/*V是数组的名字，假设数组中的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*mVVViVm-12.2.1顺序表的存储结构主目录下一页上一页退出本章要点n 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表

9、的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。2.2.1顺序表的存储结构主目录下一页上一页退出本章要点#define MAXSIZE 100/*线性表可能达到的最大长度为100*/typedef int elemtype;typedef struct elemtype elemMAXSIZE;/*线性表占用的数组空间*/int len;/*线性表实际长度，这里记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置1*/Sqlist;2.2.1顺序表的存储结构主目录下一页上一页退出本章要点#define MAXSIZE

10、100typedef struct elemtype elemMAXSIZE;int len;Sqlist;2.2.1顺序表的存储结构主目录下一页上一页退出本章要点在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.elemi-1。2.2.2顺序表上实现的基本操作主目录下一页上一页退出本章要点n 顺序表的初始化顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中 len 指针置为0，表示

11、表中没有数据元素。算法如下：2.2.2顺序表上实现的基本操作主目录下一页上一页退出本章要点 Sqlist*init_Sqlist()Sqlist*L;L=(Sqlist*)malloc(sizeof(Sqlist);L-len=0;return L;n 设调用函数为主函数，主函数对初始化函数的调用如下：main()Sqlist*L;L=Init_Seqlist();顺序表的初始化主目录下一页上一页退出本章要点n 按序号查找n 注意：元素标号与数组的下标之间的关系元素an.元素ai.元素a2元素a1Elem0Elem1Elemi-1Elemn-12.2.2顺序表上实现的基本操作主

12、目录下一页上一页退出本章要点n Locate（L，x）：查找顺序表中是否含有与x值相同的元素ai-1.a2a1alenai+1aix按内容查找主目录下一页上一页退出本章要点ai-1.a2a1alenai+1aix按内容查找主目录下一页上一页退出本章要点ai-1.a2a1alenai+1aix如果x和ai-1相同，则找到并停止查找；否则按照前面的步骤继续下去按内容查找主目录下一页上一页退出本章要点ai-1.a2a1alenai+1aix如果此时仍然没有找到，返回错误并停止n 有关算法及程序在“查找”一章中介绍按内容查找主目录下一页上一页退出本章要点n in

13、t Location_Sqlist(Sqlist*L,elemtype x)int i=0;while(ilen&L-elemi!=x)i+;if(i=L-len)return-1;else return i;/*返回的是存储位置*/按内容查找主目录下一页上一页退出本章要点以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第i(1in+1)个位置上，插入一个新结点x，使长度为n的线性表(a1，ai-1，ai，an)变成长度为n+1的线性表(a1，ai-1，x，ai，an)2.2.2顺序表上实现的基本操作主目录下一页上一页退出本章要点.a2a1an.ai

14、+1ai01i-1iai-1.a2a1alenai+1aixai-1.a2a1 aiai+1alength alen ai+1aixn-1插入运算主目录下一页上一页退出本章要点n 顺序表上完成这一运算通过以下步骤进行：(1)将aian 顺序向下移动，为新元素让出位置；(2)将 x 置入空出的第i个位置；(3)修改表长。插入运算主目录下一页上一页退出本章要点int InsList(Sqlist*L,int i,int x)/*在线性表V中第i 个元素之前插入x，i 的合法值为 1 i L-len+1*/int k;if(iL-len+1)printf(“Locate Error!

15、”);return 0;/*位置i值不合法*/if(L-len=MAXSIZE)printf(Filled!);return(ERROR);for(k=L-len-1;k=i-1;k-)L-elemk+1=L-elemk;/*插入位置后的元素依次右移*/L-elemi-1=x;/*插入x*/L-len+;/*表长加1*/return 1;注意数组元素从0开始插入运算主目录下一页上一页退出本章要点main()/*顺序表插入的主函数*/Sqlist*a;Sqlist m;int n,x,k;scanf(“%d”,&(m.len);a=&m;for(i=0;i=m.len-1;i+)scan

16、f(“%d”,&(m.elemi);/*数组赋初值*/printf(“input n,x:”);scanf(“%d%d”,&n,&x);k=InsList(a,n,x);if(k=1)printf(nOK!);/*执行函数调用*/else printf(nERROR!);插入运算主目录下一页上一页退出本章要点本算法中注意以下问题：n(1)顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。n(2)要检验插入位置的有效性，这里 i的有效范围是：1=i=n+1，其中 n 为原表长。n(3)注意数据的移动方

17、向。插入运算主目录下一页上一页退出本章要点分析算法的复杂度：这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是ni1。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关,而 i 的取值范围为：1=i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；n 当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。插入运算主目录下一页上一页退出本章要点由于插入可能在表中任何位置上进行，因此需分析算法的平

18、均复杂度在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。故 Eis(n)=pi(n-i+1)不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)=(n-i+1)/(n+1)=n/2 插入运算主目录下一页上一页退出本章要点也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶

19、的。因此算法的平均时间复杂度为O(n)。插入运算主目录下一页上一页退出本章要点2、删除线性表的删除运算是指将表的第i(1in)个结点删除，使长度为n的线性表：(a1，ai-1，ai，ai+1，an)变成长度为n-1的线性表(a1，ai-1，ai+1，an)2.2.2顺序表上实现的基本操作主目录下一页上一页退出本章要点ai-1.a2a1alenai+1aiai-1.a2a1aiai+1alengthai+1alengthai+1ai+1alen.a2a1an.ai+1ai01i-1in-1删除运算主目录下一页上一页退出本章要点序号元素0 a01 a12 a2 i-1

20、 ai-1i aii+1 ai+1 num anum 在长度为num的顺序表List，删除第i(1ilen+1)个数据元素，需将第i至第len+1个数据元素的存储位置（num-i+1）依次前移，并使顺序表的长度减1，返回TRUE值，若i1或inum+1，则无法删除，返回FALSE值，如下图所示。0 a01 a12 a2 ai-1i ai+1i+1 ai+2 num anum i-1 删除运算主目录下一页上一页退出本章要点int DelList(Sqlist*L,int i,int*e)/*在线性表V中删除第i 个元素，用e接收返回值*/int k;if(iL-len)printf(Lo

21、cate Error!n);return 0;*e=L-elemi-1;for(k=i;klen;k+)L-elemk-1=L-elemk;/*被删除元素之后的元素左移*/L-len-;/*表长减1*/return 1;删除运算主目录下一页上一页退出本章要点本算法注意以下问题：n（1）删除第i个元素，i的取值为 1=ilen的值为0，条件（iL-len）也包括了对表空的检查。n（3）删除 ai 之后，该数据将不存在，如果需要可先取出 ai，再做删除。删除运算主目录下一页上一页退出本章要点该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。n 若i=n，则由

22、于循环变量的初值大于终值，前移语句将不执行，无需移动结点；n 若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。n 删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n)=pi(n-i)删除算法的时间性能分析：删除运算主目录下一页上一页退出本章要点n 式中，pi表示删除表中第i个结点的概率。在等概率的假设下，p1=p2=p3=pn=1/n 由此可得：Ede(n)=(n-i)/n=(n-1)/2 即

23、在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。删除运算主目录下一页上一页退出本章要点3、顺序表的应用例：将有序线性表La=2,4,6,7,9，Lb=1,5,7,8，合并为Lc=1,2,4,5,6,7,7,8,9。分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要先将Lc置为空表，然后将La或Lb中的元素逐个插入到Lc中即可。设两个指针i和j分别指向La和Lb中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到Lc中的元素c为c=，当时；，当时，很显然，指针i和j的初值均为1，在所指元素插入Lc后，i，j在

24、La或Lb中顺序后移。2.2.2顺序表上实现的基本操作主目录下一页上一页退出本章要点线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。也就是说定位操作可以直接实现。高级程序设计语言提供的数组数据类型可以直接定义顺序存储结构的线性表，使其程序设计十分方便。顺序表存储结构的特点主目录下一页上一页退出本章要点但是，顺序存储结构也有一些不方便之处，主要表现在：（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间。（2）插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作

25、和删除操作时需移动大量数据。这对于插入和删除操作频繁的线性表、以及每个数据元素所占字节较大的问题将导致系统的运行速度难以提高。（3）顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。主目录下一页上一页退出本章要点线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另

26、一种存储方式，链式存储结构，简称为链表(Linked List)。2.3.1 线性表的链式表示(线性链表)和实现主目录下一页上一页退出本章要点链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构 2.3.1 线性链表主目录下一页上一页退出本章要点其中：data域是数

27、据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表（Single Linked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用表示)。data link 2.3.1 线性链表主目录下一页上一页退出本章要点 110 130 135 160头指针 head 165 170 2

28、00 205 hat 200.cat 135eat 170.mat Nullbat 130fat 110 jat 205lat 160 165 2.3.1 线性链表例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示意图如右：主目录下一页上一页退出本章要点bat cat eat mat 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。head 2.3.1 线性链表主目录下一页上一页退出本章要点typedef char elemtype;typedef struct node e

29、lemtype data;struct node*next;NODE，*NODEPTR;NODE*p；用C语言描述的单链表结构定义如下：2.3.1 线性链表主目录下一页上一页退出本章要点注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即p=(NODE*)malloc(sizeof(NODE);函数malloc分配了一个类型为NODE的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p)；释放所指的结点变量空间。n 注意：指针变量P和（其值为结点地址）结点变量*P之间的关系。2.3.1 线性链表主目

30、录下一页上一页退出本章要点a1a2an a3L.带头结点的单链表头结点头指针相关概念n 头结点在第一个结点之前附设的一个结点，该结点的数据域可以存储附加信息，也可以什么都没有n 头指针永远指向头结点的指针n 空链表L 2.3.1 线性链表主目录下一页上一页退出本章要点一、建立单链表假设线性表中结点的数据类型是字符型，我们逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的常用方法有如下两种：头插法建表尾插法建表 2.3.1 线性链表主目录下一页上一页退出本章要点bab axPPS在P所指向的结点之后插入新的结点xS单链表的插入s-next=p-

31、next;p-next=s;主目录下一页上一页退出本章要点Lsa1La1Lsa2该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。snext=head-next;head-next=s;头插法建表主目录下一页上一页退出本章要点 NODEPTR createfromhead()char ch;NODEPTR head;NODE*p;head=(NODEPTR)malloc(sizeof(NODE);head-next=NULL;ch=getchar();while(ch!=n）p=(NODE

32、*)malloc(sizeof(NODE);pdata=ch;pnext=head-next;head-next=p;ch=getchar();return(head);头插法建表主目录下一页上一页退出本章要点头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。尾插法建表主目录下一页上一页退出本章要点尾插法建表 LrLS头指针头结点a1增加一个结点La1 a2Srr主目录下一页上一页退出本章要点If(c!=$)s=(N

33、ODE*)malloc(sizeof(NODE);/*用来创建一个新结点*/s-data=c;r-next=s;/*r永远指向链表的最后一个结点*/r=s;elseflag=0;/*设置的标志变量，表示建表结束，当输入“$”时结束建表*/r-next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/尾插法建表主目录下一页上一页退出本章要点bab ax anaia1a2PPai-1xLS二、插入运算主目录下一页上一页退出本章要点 anaia1a2Pai-1LInsLinkList(NODE*p,int x)/*在P所指向的结点之后插入新的结点*/NODE*s

34、;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;return OK;二、插入运算主目录下一页上一页退出本章要点 anaia1a2Pai-1LInsLinkList(NODE*p,int x)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;return OK;S二、插入运算主目录下一页上一

35、页退出本章要点 anaia1a2Pai-1xLInsLinkList(NODE*p,int x)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;return OK;S二、插入运算主目录下一页上一页退出本章要点 anaia1a2Pai-1xLInsLinkList(NODE*p,int x)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(siz

36、eof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;return OK;S二、插入运算主目录下一页上一页退出本章要点 anaia1a2Pai-1xLInsLinkList(NODE*p,int x)/*在P所指向的结点之后插入新的结点*/NODE*s;/*定义指向结点类型的指针*/s=(NODE*)malloc(sizeof(NODE);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;return OK;二、插入运算主目录下一页上一页退出本章要点DelLinkList(NODE*p)/*删除p指

37、针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/三、删除运算主目录下一页上一页退出本章要点ai-1a1aiai+1L pDelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/q三、删除运算主目录下一页上一页退出本章要点a

38、i-1a1aiai+1L pDelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/三、删除运算主目录下一页上一页退出本章要点ai-1a1aiai+1L pqDelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q

39、);/*删除并释放结点*/三、删除运算主目录下一页上一页退出本章要点ai-1a1aiai+1L pqDelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/三、删除运算主目录下一页上一页退出本章要点ai-1a1aiai+1L pDelLinkList(NODE*p)/*删除p指针指向结点的后一个结点*/NODE*q;if(p-next!=NULL)q=p-next;/*q指向p的

40、后继结点*/p-next=q-next;/*修改p结点的指针域*/free(q);/*删除并释放结点*/三、删除运算主目录下一页上一页退出本章要点按内容查找：设含有表头结点的单链表的头指针为L,沿着链表的开始往后找结点x，若找到，则返回该结点在链表中的位置，否则返回空地址按序号查找：设含有表头结点的单链表的头指针为L，沿着链表的开始位置往后找并且从1开始计数，若数量等于i时，则返回该位置具体的值，否则可以返回错误提示信息四、线性链表的查找操作主目录下一页上一页退出本章要点Node*lbcz(Node*h,intx)Node*p;p=h-next;while(p!=NULL&p-

41、data!=x)p=p-next;return(p);anaia1a2ai-1L按内容查找主目录下一页上一页退出本章要点Node*lbcz(Node*h，inti)Node*p;intk=1;p=h-next;while(p!=NULL&knext;K+;return(p);按内容查找主目录下一页上一页退出本章要点循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也

42、可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。2.3.2 循环链表主目录下一页上一页退出本章要点循环链表：首尾相接的链表。将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。a1a2an a3L.带头结点的单链表a1a2ana3L.循环单链表 2.3.2 循环链表主目录下一页上一页退出本章要点 a1 an.head非空表空表在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)2.3.2 循环链表主目录下一页上一页退出本章要点在很多实际问题中，表的操作常常是

43、在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext)next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。2.3.2 循环链表主目录下一页上一页退出本章要点若已知某结点的指针为p，其后继结点的指针则为p-next，而找其前驱则只能从该链表的头指针开始,顺着各

44、结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n),如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，用这种结点组成的链表称为双向链表。双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。2.3.3 双向链表主目录下一页上一页退出本章要点设指

45、针p指向某一结点，则双向链表结构的对称性可用下式描述：(pprior)next=p=(pnext)prior即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放在它的后继结点*(pnext)的直接前趋指针域中。2.3.3 双向链表主目录下一页上一页退出本章要点在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点，提高运算效率。data next priorL1 2 3struct DNodeElemType data;struct DNode*prior,*next;；带头结点的双向链表 2.3.3 双向链表主目录下一

46、页上一页退出本章要点双向链表的前插运算int DlinkIns(struct DNode*L,int i,ElemType e)L1 2 3PSeS-prior=P-prior;P-prior-next=S;S-next=P;P-prior=S;2.3.3 双向链表主目录下一页上一页退出本章要点L1 2 3双向链表的删除操作int DlinkDel(struct DNode*L,int i,ElemType*e)PP-next-prior=p-prior;P-prior-next=P-next；注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指

47、针。上述两个算法的时间复杂度均为O(1)。2.3.3 双向链表主目录下一页上一页退出本章要点n 区别n动态链表由指针实现的，表中的结点空间的分配和回收（即释放）都是由系统提供的标准函数malloc和free动态实现的链表n静态链表用游标指示器代替指针实现的链表n 静态链表的结构n也是由数据域和指针域组成n指针域不再是指针，而是在一个数组中的相对位置（游标指示器）n结点不是动态生成的，而是数组静态分配的 2.3.4 动态链表与静态链表主目录下一页上一页退出本章要点n 顺序存储的三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的

48、存储开销。(3)顺序表具有按元素序号随机访问的特点。n 顺序存储的两个缺点：(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。n 链表的优缺点恰好与顺序表相反。2.4 顺序表和链表的比较主目录下一页上一页退出本章要点n 在实际中怎样选取存储结构呢？通常有以下几点考虑：、基于存储的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对MAXSIZE要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或

49、存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于的。2.4 顺序表和链表的比较主目录下一页上一页退出本章要点、基于运算的考虑在顺序表中按序号访问ai的时间性能是O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度

50、考虑显然后者优于前者。2.4 顺序表和链表的比较主目录下一页上一页退出本章要点、基于环境（语言）的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。2.4 顺序表和链表的比较主目录下一页上一页退出本章要点n 基于空间的考虑n 空间的利用率和存储密度n 存储密度结点数据本身所占的存储量/结点结构所占的存储总量n 基于时间的考虑n 实现某一操作的时间n 基于语言

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

11.9 金币

版权申诉 word格式文档无特别注明外均可编辑修改；预览文档经过压缩，下载后原文更清晰！ 立即下载

配套讲稿：: 如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
特殊限制：: 部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
关键词：: 数据结构九江学院 02 线性

淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。

限制150内

关于本文

本文标题：九江学院《数据结构》第02章线性表.ppt
链接地址：https://www.taowenge.com/p-91225758.html