自考数据结构导论02142第二章线性表ppt课件.ppt

《自考数据结构导论02142第二章线性表ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构导论02142第二章线性表ppt课件.ppt（110页珍藏版）》请在三一办公上搜索。

1、1,第二章 线性表,2,第2章 线性表,2.1 线性表的基本概念2.2 线性表的顺序存储2.3 线性表的链接存储2.4 其它运算在单链表上的实现2.5 其它链表2.6 顺序实现与连接实现的比较2.7 小结,3,4,本章总述,本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现；另外，简单介绍了串这种特殊的线性表的运算和存储实现。,线性表是一种最简单最常见的数据结构,5,本章重点 线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。本章难点 单链表上的算法设计。,6,字母表(A,B,C,D.Z)数字表(0,1,2,3,4,5,6,7,8,9),学生名单,7,问题：线性结

2、构的特点？,8,2.1 线性表的基本概念,线性表是由n（n0）个数据元素（结点）a1，a2，an组成的有限序列。 数据元素的个数n定义为表的长度, n=0时称为空表，记作（）或 将非空的线性表（n0）记作： L=（a1，a2，an） 数据元素ai（1in）只是个抽象符号，其具体含义在不同情况下可以不同。,9,线性表的基本术语：起始结点、终端结点、直接前驱、直接后继线性表长度，空表,L=（a1，a2，an）,注意：线性表中只有一个起始结点，一个终端结点，起始结点没有直接前驱，有一个直接后继。终端结点有一个直接前驱，没有直接后继。除此二结点外，每个结点都有且只有一个直接前驱和一个直接后继。,10,

3、线性表的逻辑结构特征,对于非空的线性表: 有且仅有一个起始结点a1，没有直接前驱，有且仅有一个直接后继a2； 有且仅有一个终端结点an，没有直接后继，有且仅有一个直接前驱an-1； 其余的内部结点ai（2in-1）都有且仅有一个直接前驱ai-1和一个直接后继ai+1。,11,线性表的基本运算,1，初始化 Initiate(L)2，求表长度 Length(L)3，取表元 Get(L,i)4，定位 Locate(L,x)5，插入 Insert(L,x,i)6，删除 Delete(L,i)区分引用型和加工型操作,12,2.2 线性表的顺序实现,定义 顺序表是线性表的顺序存储存储结构，即以一段连续内存

4、存放的线性表此时，内存的顺序性体现了数据间的逻辑关系线性表中相邻的结点在存储结构中仍相邻,13,假定有一组数据，数据间有顺序：12 10 5 78 56 45 32 88 71 11,此处数据间的顺序即表示数据间的逻辑关系即线性关系，这一组数据为线性表,0,1,2,3,4,5,6,7,8,9,11,12,10,5,78,56,45,32,88,71,线性表的顺序存储结构,14,假设已知a1地址为Loc(a1)，每个数据占c个单元则计算ai地址,Loc(ai) =,Loc(a1) +,c *(i-1),a1 a2 a3 a4 a5 a6 a7 a8 a9 a10,15,此处数据间的顺序即表示数据

5、间的逻辑关系即线性关系，这一组数据为线性表,0,1,2,3,4,5,6,7,8,9,顺序存储线性表时，需要存储：存储单元大小、数据个数,线性表大小：10线性表长度：7所存放数据的类型:,MaxSize,Length,DataType,16,a1,a2,an,0,1,length-1,1,2,n,内存,data数组下标,元素序号,maxsize-1,顺序表的结构体定义#define maxsize 100typedef struct datatype datamaxsize; int length; Seqlist;Seqlist L；问题：L有什么成员？,17,附讲： 结构体,结构体是一种构造

6、数据类型 用途：把不同类型的数据组合成一个整体-自定义数据类型 引入结构体的好处：加强数据项之间的联系,如学生的基本信息，包括学号、姓名、性别、年龄、班级、成绩等数据项。这些数据项描述了一个学生的几个不同侧面。,独立的变量表示：,结构体变量表示：,char no9; /学号char name20; /姓名char sex; /性别unsigned int age; /年龄unsigned int classno; /班级float grade; /成绩,18,1、结构体类型的定义,struct 结构体类型名 数据类型名1 成员名1； 数据类型名2 成员名2； 数据类型名n 成员名n；,stru

7、ct是关键字,不能省略,合法标识符可省:无名结构体,成员类型可以是基本型或构造型,以分号;结尾,例1：struct Student_Info char no9; /学号 char name20; /姓名 char sex; /性别 unsigned int age; /年龄 unsigned int classno; /班级 float grade; /成绩;,例2：struct Date int year; /年 int month; /月 int day; /日;,19,在结构体中数据类型相同的成员，既可逐个、逐行分别定义，也可合并成一行定义，就象一次定义多个变量一样。,struct St

8、udent_Info char no9; /学号 char name20; /姓名 char sex; /性别 unsigned int age; /年龄 unsigned int classno; /班级 float grade; /成绩;,struct Student_Info char no9, name20, sex; unsigned int age, classno; float grade; ;,struct Date int year; /年 int month; /月 int day; /日;,struct Date int year, month, day;,注意：结构类型

9、只是用户自定义的一种数据类型，用来定义描述结构的组织形式,不分配内存，只有用它来定义某个变量时，才会为该变量分配结构类型所需要大小的内存单元。所占内存的大小是它所包含的成员所占内存大小之和。,20,2、结构体变量的定义和引用,struct 结构体类型名 数据类型名1 成员名1； 数据类型名n 成员名n；struct 结构体类型名 变量名列表；,结构体变量的定义,间接定义法：先定义结构类型，再定义结构变量,21,2、结构体变量的定义和引用,struct 结构体类型名 数据类型名1 成员名1； 数据类型名n 成员名n； 变量名列表；,结构体变量的定义,直接定义法：定义结构体类型的同时定义结构体变量

10、,struct Student_Info char no9; /学号 char name20; /姓名 char sex; /性别 unsigned int age; /年龄 unsigned int classno; /班级 float grade; /成绩 student1, student2;,struct char no9; /学号 char name20; /姓名 char sex; /性别 unsigned int age; /年龄 unsigned int classno; /班级 float grade; /成绩 student1, student2;,或,无名结构体定义，变量

11、只能一次定义,22,结构体变量的引用,引用规则,结构体变量不能整体引用,只能引用变量成员,引用方式：,结构体变量名.成员名 /非指针型结构体变量的引用,可以将一个结构体变量赋值给另一个结构体变量,结构体嵌套时逐级引用,结构体指针-成员名 或 （*结构体指针）.成员名/指针型结构体变量的引用,成员(分量)运算符结合性:从左向右,成员(分量)运算符结合性:从左向右,结构体变量名.成员名.子成员名最低级子成员名,23,3、结构体变量的赋值,结构体变量初始化赋值,先定义结构体类型，再定义结构体变量时赋初值,注意：赋初值时， 中间的数据顺序必须与结构体成员的定义顺序一致，否则就会出现混乱。,struct

12、 Student_Info stu = 20020306, ZhangMing, M, 18, 1, 90;,struct Student_Info stu = 18, ZhangMing, M, 20020306, 1, 90;,24,3、结构体变量的赋值,结构体变量初始化赋值,定义结构体类型的同时，定义结构体变量并赋初值,struct Date int year, month, day; birthday = 1986, 12, 10;,struct int year, month, day; birthday = 1986, 12, 10;,或,struct Student_Info c

13、har no9; /学号 char name20; /姓名 char sex; /性别 unsigned int age; /年龄 unsigned int classno; /班级 float grade; /成绩 student = 20020306, ZhangMing, M, 18, 1, 90;,25,strcpy (stu1.no, stu.no); strcpy (stu1.name, stu.name);stu1.sex = stu.sex;stu1.age = stu.age;stu1.classno = stu.classno;stu1.grade = stu.grade;

14、,struct Student_Info stu; strcpy (stu.no, 20020306); strcpy (stu.name, ZhangMing);stu.sex = M;stu.age = 18;stu.classno = 1;stu.grade = 90;struct Student_Info stu1;stu1 = stu;,3、结构体变量的赋值,结构体变量在程序中赋值,如果在定义结构体变量时并未对其赋初始值，那么在程序中要对它赋值的话，就只能一个一个地对其成员逐一赋值，或者用已赋值的同类型的结构体变量对它赋值,memcpy (,26,结论顺序表是用一维数组实现的线性表，

15、数组下标可以看成是元素的相对地址逻辑上相邻的元素，存储在物理位置也相邻的单元中,顺序存储结构的特点1.线性表的逻辑结构与存储结构一致 2.可以对数据元素实现随机读取,27,图2-1 线性表顺序存储结构示意图,28,设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用L个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址是d，那么结点ai的存储地址LOC（ai）,LOC（ai）=d+(i-1)*L,29,若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100， 则第12个元素的存储地址是 。 A112

16、 B144 C148 0412,答案：B,30,基本运算在顺序表上的实现,插入、删除、定位,31,插入,线性表的插入运算是指在表的第i（1in+1）个位置上，插入一个新结点x，使长度为n的线性表：（a1，ai-1，ai，an）变成长度为n+1的线性表： （a1，ai-1，x，ai，an）, 当表空间已满，不可再做插入操作 当插入位置为非法位置，不可做正常插入操作,32,将表中位置为n ，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾该顺序表长度加1 下图为在位置3插入新结点x=66示意

17、图。,顺序表插入操作过程,L.length-1,0,注意位置和下标的区别,21,18,30,75,42,56,87,66,3,33,void InsertSeqList ( Seqlist *L，DataType x，int i ) int j; if ( i L.length + 1 ) exit(“位置错误”); if ( L.length = MaxSize ) exit(“溢出); for( j=L.length-1; j=i; j-) L.data j = L.dataj-1 ; L.data i-1 = x; L.length+;,假设L已指向某线性表，L是Seqlist类型指针,

18、34,假设线性表中含有n个数据元素，在进行插入操作时，有 个位置可插入在每个位置插入数据的概率是：在i位置插入时，要移动 个数据假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,插入算法的分析,n+1,1/(n+1),12,10,5,78,56,45,32,44,33,n-i+1,78,56,45,32,44,33,平均时间复杂度O(n),35,在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1,答案：A,36,2. 删除,线性表的删除运算是指将表的第i个结点删去，使长度为n的线性表 （a1，a

19、i-1，ai，ai+1，an）变成长度为n-1的线性表 （a1，ai-1，ai+1，an）,当要删除元素的位置i不在表长范围内（即i1或iL-length）时，为非法位置，不能做正常的删除操作,37,顺序表删除操作过程,1，若i=n，则只要删除终端结点，无须移动结点；2，若1in-1，则必须将表中位置 i+1，i+2，n的结点，依次前移到位置i，i+1，n-1上，以填补删除操作造成的空缺。 3，该表长度减1,仅当删除位置i=n时， 才无须移动结点，直接令表长度-1即可,38,顺序表删除操作过程,12,10,5,78,56,45,32,44,33,22,56,45,32,44,33,22,12,

20、10,5,78,56,45,32,44,33,22,56,45,32,44,33,22,lngth-1结束,j初值：删除位置ij终值：最后的前一个位置L.length,data = data ;,j-1,j,39,具体算法描述,void DeleteSeqList(SeqList *L,int i) int j; if( i L.length ) Error(“位置错误”); for( j = i ;j L.length ; j+ ) L.data j-1 =L.data j ; L.length-;,40,假设线性表中含有n个数据元素，在进行删除操作时，有 位置可删除在每个位置删除数据的概率

21、是：在i位置删除时，要移动 个数据假定在n个位置上删除元素的可能性均等，则平均移动元素的个数为：,删除算法的分析,n,1/n,12,10,78,56,45,32,5,44,33,22,n-i+1,56,45,32,44,33,22,长度：,10,9,41,在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：,平均时间复杂度O(n),42,习题：在长度为n的顺序表的第i(1in)个位置上删除一个元素，元素的移动次数为( ) A.n-i+1 B.n- i C.i D.i-1,答案：B,43,顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性

22、表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,分析结论,44,3. 定位(查找),定位运算LocateSeqlist(L,X)的功能是求L中值等于X的结点序号的最小值，当不存在这种结点时结果为0。,45,从第一个元素 a1 起依次和x比较，直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号；或者查遍整个表都没有找到与 x 相等的元素，返回0。,定位,L.length-1,0,46,定位,int locateSeqList (SeqList L, DataType x) i=1; while( (i=L.length) ,47,线性表的顺序存储结构必

23、须占用一片地址连续的存储单元。 ()线性表的顺序存储结构要比链式存储结构节省存储空间。 (),习题,若线性表采用顺序存储结构,线性表的长度等于表中元素的个数与每个元素所占内存单元之乘积。 ()在长度为n的顺序表的第i个位置插入一个数据元素，i的合法值为1iN。 ()删除长度为n的顺序表的第i个数据元素，i的合法值为1in。 (),48,无需为表示结点间的逻辑关系而增加额外存储空间可以方便地随机存取表中的任一结点,顺序表的优点,顺序表的缺点,插入和删除运算不方便，必须移动大量的结点顺序表要求占用连续的空间，存储分配只能预先进行，因此当表长变化较大时，难以确定合适的存储规模,49,2.3 线性表的

24、链接实现,链接方式存储的线性表简称为链表Link List链表的具体存储表示为： 用一组任意的存储单元来存放 链表中结点的逻辑次序和物理次序不一定相同。还必须存储指示其后继结点的地址信息,50,用一组地址任意的存储单元存放线性表中的数据元素,12,11,45,22,34,线性表中数据为（11，12，22，34，45）,head,51,单链表,data域-存放结点值的数据域 next域-存放结点的直接后继的地址（位置）的指针域（链域）所有结点通过指针链接而组成单链表NULL称为 空指针Head称为 头指针变量，存放链表中第一个结点地址,第52页,一个变量的地址称为该变量的“指针”。例如，地址20

25、00是变量的指针。如果有一个变量专门用来存放另一变量的地址（即指针）的，则它称为“指针变量”。,附讲2 ：指针,注：指针是一个地址，指针变量的值（即指针变量中存放的值）也是地址（即指针）。而指针变量是存放地址的变量。,第53页,如i_pointer为指针变量，则(*i_pointer)是i_pointer所指向的变量，如图所示。则：i=3;等价于 *i_pointer=3;这两个语句的含义是将3赋给指针变量i_pointer所指向的变量。,第54页,定义指针变量的一般形式为：类型说明符*指针变量名；其中：类型说明符指的是指针变量指向的变量的数据类型，“*”表示随后的变量是指针变量。下面都是合法

26、的定义：float *pointer_； char *pointer_； 可以用赋值语句使一个指针变量得到另一个变量的地址，从而使它指向该变量。例如：pointer_；pointer_；,定义一个指针变量,第55页,在定义指针变量时要注意两点：,第56页,指针变量的引用,注意:指针变量中只能存放地址（指针），不要将一个整数（或任何其他非地址类型的数据）赋给一个指针变量。,与指针变量有关的运算符：1.：其功能是返回操作数的内存地址。2.*：表示的是地址对应单元中的内容。,注:1.操作的对象为一个变量，而*操作的对象为一个变量的地址。2.对指针变量不能直接赋值：如：int *pp; pp=10;(

27、10是整数，不是地址)3.、*优先级相同，结合方向自右向左。,第57页,#include voidmain( )int ，； int*pointer_，*pointer_； 100；10； pointer_；/*把变量的地址赋给pointer_1 */ pointer_；/*把变量的地址赋给pointer_*/ printf（%d,%dn,）； printf（%d,%dn,*pointer_1,*pointer_2)； ,运行结果为：100，10100，10,例8. 通过指针变量访问整型变量。,58,单链表的一般图示法,由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来

28、表示链域中的指针，单链表就可以表示为下图形式。,带头结点的单链表空表和非空表,单链表中第一个结点内一般不存数据，称为 头结点利用头指针存放该结点地址，为什么要加设头结点？,59,在单链表中，增加头结点的目的是 A 。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现,练习,60,单链表的类型定义,struct node datatype data； struct node * next；Node，*LinkList;,数据域,指针域：存放该结点的直接后继结点的地址。,61,单链表的简单操作,单链表特点：起始节点又称为首结点，无前

29、驱，故设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。头指针名是head的链表可称为表head。终端结点又称尾结点，无后继，故终端结点的指针域为空，即NULL除头结点之外的结点为表结点为运算操作方便，头结点中不存数据,62,特别注意：Head是什么类型变量？ Head内存放的是什么？,Head,Head是链表的头指针，所以是指针类型变量。Head内存放的是头结点的地址。,63,1. 初始化,建立一个空的单链表L，InitiateLinkList（L）一个空的单链表是一个头指针和一个头结点构成的假设已定义指针变量t，令t指向一个头结点并令头结点的next为NU

30、LL注意：产生头结点时由malloc函数产生一个新节点,特别注意：malloc函数的使用格式及作用:动态分配内存函数malloc函数格式如下（数据类型*）malloc（sizeof（数据类型）如：int *p;p=（int *）malloc（sizeof（int）,64,1. 初始化,LinkList InitiateLinklist( ) LinkList head; head= ( linkList ) malloc( sizeof( struct node ) ); head-next=NULL; return head;,65,2. 求表长,在单链表存储结构中，线性表的长度等于单链表所

31、含结点的个数（不含头结点）,Head,66,0,j,1,2,3,head,4,5,67,2. 求表长,步骤：1，令计数器j为02，令p指向头结点3，当下一个结点不空时，j加1，p指向下一个结点4，j的值即为链表中结点个数，即表长度,68,int lengthLinkList (LinkList head) Node *p; p=head; j=0; while( p-next != NULL ) p=p-next; j+; return(j);,求表长,特别注意：p=p-next的作用,69,3. 读表元素,步骤：查找第i个结点1、令计数器j为02、令p指向头结点3、当下一个结点不空时，并且j

32、i时， j加1，p指向下一个结点4、如果j等于i，则p所指结点为要找的第i结点 否则，链表中无第i结点,0,j,1,2,3,head,4,5,70,3. 读表元素,Node GetlinkList( LinkList head, int i ) Node *p; p=head; int j=0; while ( (p-next!=NULL) ,71,已知指针p指向单链表中某个结点，则语句p -next=p -next-next的作用是_。,练习,答案：删除p的直接后继结点,72,4. 删除,算法思路（此算法描述删除第i个结点） 找到第i-1个结点；若存在继续，否则结束； 删除第i个结点，并释放

33、对应的内存 结束。,73,算法步骤,删除运算是将表的第i个结点删去。（1）找到ai-1的存储位置p（2）令p-next指向ai的直接后继结点（3）释放结点ai的空间，将其归还给存储池。,74,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,ai,ai+1,q = p-next; p-next = q-next; free(q);,p,q,75,void DeleteLinkList (LinkList head,int i) Node *q; if (i=1) p=head; else p=GetLinkList(head, i-1); if (

34、p！=NULL ,程序实现,76,5. 插入,插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。具体步骤： （1）找到ai-1存储位置p（2）生成一个数据域为x的新结点*s（3）令结点*p的指针域指向新结点（4）新结点的指针域指向结点ai。,77,s,p,假设在p所指结点后插入s所指结点,ai-1,ai,e,78,void InsertLinkList (LinkList head, Data x, int i) Node *p,*q; p=GetLinkList (head, i-1); if (p) /若p！=NULL s=()malloc(); s-da

35、ta=x; s-next=p-next; p-next=s; else printf(“error”);,程序实现,79,6. 定位,定位运算是对给定表元素的值，找出这个元素的位置。对于单链表，给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称为按值查找。具体步骤： 1、令p指向头结点2、令i=03、当下一个结点不空时，p指向下一个结点,同时i的值加14、直到p指向的结点的值为x。返回i+1的值。5、如果找不到结点值为x的话，返回值为0,80,定位运算算法描述,int LocateLinklist(LinkList head , DataType x) Node *p=head;

36、 p=p-next; int i=0; while (p!=NULL else return 0,81,1. 已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ A. s-next = p; p-next = s; B. s-next = p-next; p-next = s; C. s-next = p-next; p = s; D. p-next = s; s-next = p;,练习,答案：B,82,2. 在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_和_。,s-next-next=

37、p-next;p-next=s;,83,3. 若频繁地对线性表进行插入和删除操作，该线性表应该采用存储结构。 A散列 B顺序 C链式 D索引,答案 C,练习,84,4. 链表中所占用的存储单元地址一定是 A无序的 B连续的 C不连续的 D部分连续的,练习,答案 A,85,5. 在单链表中，增加头结点的目的是A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现,练习,答案 A,86,6. 在表达式中，符号p-next表示。 Ap所指的链结点的指针域(位置) Bp所指的链结点的指针域的内容 Cp所指的链结点的下一个链结点的地址,练习,

38、答案 C,87,2.4 其他运算在单链表上的实现,1，建立单链表步骤： 1）定义头指针，初始化单链表 2）输入数据 3）当输入数据不为 分配新节点内存，并存入数据 将新节点链入单链表中 再次输入数据，执行第3）步,Head,12,10,88,头插法,Head,10,12,始终将新增加的结点插入到头结点之后，第一个数据节点之前。,89,头插法,LinkList CreateLinkList1() Linklist head; Node * p; int x; head=malloc(sizeof(Node); head-next=NULL; scanf(%d”,90,尾插法,Head,12,10

39、,每次建立一个新结点，然后将新结点链接到表尾。,91,Linklist CreateLinkList2( ) head=( )malloc(sizeof(struct node) p=head; scanf(“%d”, ,92,2，清除单链表中值为x的重复结点分析： 清除单链表中值为x的重复结点步骤：1）找到值为x的第一个结点位置，p指向该结点2）从p所指结点开始向后查找， 若存在值为x的结点，令q指向x结点前一个 执行删除操作 继续查找直到链表末尾,93,2，清除单链表中所有重复结点逐步求精法分析： 整体步骤： 当未到达链表末尾时（ai不是终端结点时） 删除ai+1到an结点中值为ai的结点

40、 i+,i=1While（ ai 不是终端结点 ） 删除ai+1到an结点中值为ai的结点 i+ ,94,2，清除单链表中重复结点逐步求精法分析：进一步细化步骤： 当未到达链表末尾时（ai不是终端结点时） 删除ai+1到an结点中值为ai的结点 j=i while （jn） if( aj=ai) 删除aj j+ i+,95,进一步细化步骤： p=head-next /令p指向第一个数据节点 if （p=NULL） return； while（p-next!=NULL）/当p不是终端结点时 q=p; /从p开始向后找和p数据相等的结点 while（q-next!=NULL） if(q-next-

41、data = p-data ) /*删除q-next 所指结点*/ else q=q-next; p=p-next; /删除q-next 所指结点 r=q-next; q-next =q-next-next; free(r);,96,2.5 其它链表,循环链表 普通链表的终端结点的next值为NULL 循环链表的终端结点的next指向头结点,97,循环链表 普通链表的终端结点的next值为NULL 循环链表的终端结点的next指向头结点问题：对于普通链表 如何判断查找结点时找到末尾？ 如何判断普通链表为空？ 如何找到普通链表的尾结点对于循环链表 如何判断查找结点时找到末尾？ 如何判断循环链表为

42、空？ 如何找到循环链表的尾结点,98,如何找到普通链表的尾结点如何找到循环链表的尾结点在循环链表中附设一个rear指针指向尾结点适用于经常适用头尾结点的链表操作中,99,1. 若p为指向循环链表中某链结点的指针变量，判断循环链表是否只有一个结点的标志是。,练习,答案：p-next=p,100,2. 非空的循环单链表first的尾结点（由p所指向）满足： A. p-link = NULL; B. p = NULL; C. p-link = first; D. p = first;,练习,答案：C,101,2，双向循环链表在链表中设置两个指针域， 一个指向后继结点 一个指向前驱结点这样的链表叫做双

43、向链表,102,双向链表的结构体定义,双向链表的结点,struct dlnode datatype data; struct dlnode *prior, *next; ;,假设双向链表中p指向某节点则有 p-prior-next 与p-next-prior相等,103,双向链表中结点的插入,p,q,q-next = p-next; p-next = q;q-next-prior = q; q-prior = p;,104,双向链表中结点的删除,p-next = p-next-next;p-next-prior = p;,p,free(q);,q,q= p-next ;,105,1. 在非空双

44、向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对应的语句依次为：p-next=q；p-prior=q-prior；q-prior=p；。 Aq-next=p； Bq-prior-next=p； Cp-next-next=p； Dp-prior-next=p；,练习,答案：D,106,2.设某非空双链表，若要删除指针q所指向的结点，则需执行下述语句段：q-prior-nextq-next; _。,练习,答案：q-next-prior=q-prior,107,2.6 顺序实现与链式实现的比较,空间性能的比较,108,时间性能的比较,顺序表 读表元 定位（找x） 插入 删除,O（1）,O（n）,O（n）,O（n）,链表 读表元 定位（找x） 插入 删除,O（n）,O（n）,O（n）,O（n）,109,110,