数据结构课件第2章线性表.ppt

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

1、第二章线性表,题目一：狐狸逮兔子实验【问题描述】围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到号洞找，第二次隔个洞（即3号洞）找，第三次隔个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？,学习目标掌握线性表的顺序存储结构及具体操作实现；掌握线性表的单、双向链接存储结构及具体操作实现；掌握算法时间复杂度分析。,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,an）,

2、特点：1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个“最后元素”；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,简言之，线性结构反映结点间的逻辑关系是 的。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,一对一(1:1),线性表,2.1 线性表的类型定义,2.3 线性表类型的实现 链式映象,2.2 线性表类型的实现 顺序映象,2.1线性表的类型定义,2.1 线性表的基本概念,、线性表它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由n（n0)个相同类型数据元素a0,a1,an-1组成的线

3、性结构。,（a0,a1,ai-1，ai,ai1，,an-1）,线性表的逻辑结构：,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,（A,B,C,D,Z）,例2 分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析：数据元素都是同类型（字母），元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性！,例1 分析26 个英文字母组成的英文表是什么结构。,抽象数据类型线性表的定义如下：,ADT List,数据对象：,D ai|ai ElemSet,

4、i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT List,InitList(&L),操作结果：,构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList(&L),初始条件：操作结果：,线性表 L 已存在。,销毁线性表 L。,ListEmpty(L),ListLength(L),PriorElem(L,cur_e,&pre_e),NextElem(L,cur_e,&next_e),GetElem(L,i,&e),LocateElem(L,e,compare(),ListTrav

5、erse(L,visit(),引用型操作:,ListEmpty(L),初始条件：操作结果：,线性表L已存在。,若L为空表，则返回TRUE，否则FALSE。,（线性表判空）,ListLength(L),初始条件：操作结果：,线性表L已存在。,返回L中元素个数。,（求线性表的长度）,PriorElem(L,cur_e,&pre_e),初始条件：操作结果：,线性表L已存在。,若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。,（求数据元素的前驱）,NextElem(L,cur_e,&next_e),初始条件：操作结果：,线性表L已存在。,若cur_e

6、是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。,（求数据元素的后继）,GetElem(L,i,&e),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)。,用 e 返回L中第 i 个元素的值。,（求线性表中某个数据元素）,LocateElem(L,e,compare(),初始条件：操作结果：,线性表L已存在，e为给定值，compare()是元素判定函数。,返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。,（定位函数）,ListTraverse(L,visit(),初始条件：操作结果：

7、,线性表L已存在，Visit()为某个访问函数。,依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。,（遍历线性表）,加工型操作,ClearList(&L),PutElem(&L,i,&e),ListInsert(&L,i,e),ListDelete(&L,i,&e),ClearList(&L),初始条件：操作结果：,线性表L已存在。,将L重置为空表。,（线性表置空）,PutElem(&L,i,&e),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)。,L中第i个元素赋值同e的值。,（改变数据元素的值）,ListInsert(&L,i,e),

8、初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)+1。,在L的第i个元素之前插入新的元素e，L的长度增1。,（插入数据元素）,ListDelete(&L,i,&e),初始条件：操作结果：,线性表L已存在且非空，1iLengthList(L)。,删除L的第i个元素，并用e返回其值，L的长度减1。,（删除数据元素）,利用上述定义的线性表 可以实现其它更复杂的操作,例 2-2,例 2-3,例 2-1,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,例 2-1,要求对线性表作如下操作：扩大

9、线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,1从线性表LB中依次察看每个数据元素;,2依值在线性表LA中进行查访;,3若不存在，则插入之。,GetElem(LB,i)e,LocateElem(LA,e,equal(),ListInsert(LA,n+1,e),操作步骤：,GetElem(Lb,i,e);/取Lb中第i个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之,void union(List,fo

10、r(i=1;i=Lb_len;i+),/union,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合。,例 2-2,集合 B,集合 A,从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,void union(List/union,GetElem(Lb,i,e);/取Lb中第 i 个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和 e 相同的数据元素，则插入之,for(i=1;i=Lb_

11、len;i+),InitList(La);/构造(空的)线性表LA,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例如：如果集合 B，（2，3，3，5，6，6，6，8，12）,对集合 B 而言，值相同的数据元素必定相邻；,如果构造一个纯集合 A，对集合 A 而言，数据元素依值从小至大的顺序插入。,因此，数据结构改变了，解决问题的策略也相应要改变。,void purge(List i+)/purge,GetElem(L

12、b,i,e);/取Lb中第i个数据元素赋给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La中不存在和 e 相同的数据元素，则插入之,线性表的存储结构是指为它开辟的计算机存储空间、存储空间的联系以及所采用的程序实现方法。线性表的存储结构主要有如下两类：,(1)顺序存储结构(2)链式存储结构,2.2 线性表类型的实现 顺序映像,1、用一组地址连续的存储单元 依次存放线性表中的数据元素（逻辑关系相邻,物理位置相邻。）,a1 a2 ai-1 ai an,线性表的起始地址称作线性表的基地址,(1)逻辑上相邻的数据元素，其物理

13、上也相邻；(2)若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出。,设首元素a0的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为：LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a0)+L*i,对上述公式的解释如图所示,2、线性表顺序存储特点：,地址 内容 元素在表中的位序,0,i,1,n-1,空闲区,i+1,L,b=LOC(a0),b+L,b+iL,b+(n-1)L,b+(MaxSize-1)L,LOC(ai)=LOC(a0)+L*i,3、线性表的顺序存储结构示意图,4、顺序映像的 C 语言描述,

14、typedef struct SqList;/俗称 顺序表,#define LIST_INIT_SIZE 80/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量,ElemType*elem;/存储空间基址,int length;/当前长度,int listsize;/当前分配的存储容量/(以sizeof(ElemType)为单位),5、线性表的基本操作在顺序表中的实现,InitList(&L)/结构初始化,LocateElem(L,e,compare()/查找,ListInsert(&L,i,e)/插入元素,ListDelete(&L,i)/

15、删除元素,Status InitList_Sq(SqList&L)/构造一个空的线性表/InitList_Sq,算法时间复杂度：,O(1),L.elem=(ElemType*)malloc(LIST_ INIT_SIZEsizeof(ElemType);if(!L.elem)exit(OVERFLOW);,L.length=0;L.listsize=LIST_INIT_SIZEreturn OK;,定位：判断某个元素是否存在，存在给出其位置，否则为0,e=,38,i,1,2,3,4,1,8,50,可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。,int LocateElem_Sq(

16、SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回 0/LocateElem_Sq,O(ListLength(L),算法的时间复杂度为：,i=1;/i 的初值为第 1 元素的位序p=L.elem;/p 的初值为第 1 元素的存储位置,while(i=L.length,if(i=L.length)return i;else return 0;,(*compare)(*p+,e),int LocateElem_Sq(SqList L,ElemType e,)p

17、=L.elem;for(i=1;i=L.length;i+)if(*p+=e)return i;else return 0;/LocateElem_Sq,时间复杂性：(找到)最好 1次 O(1)最坏 n次 O(n)平均 n/2次 O(n),(找不到)最好 n+1次 O(n)最坏 n+1次 O(n)平均 n+1次 O(n),线性表操作 ListInsert(&L,i,e)的实现：,首先分析:,插入元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an),Status ListInsert_Sq(SqList&L,int i,ElemType

18、e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq,算法时间复杂度为:,O(ListLength(L),q=,元素右移,例如：ListInsert_Sq(L,5,66),L.length-1,0,87,56,42,66,q=/插入e,线性表操作 ListDelete(&L,i,&e)的实现：,首先分析：,删除元素时，线性表的逻辑结构发生什么变化？,(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an),ai+1,an,表的长度减少,Status ListDelete_Sq(SqList&L,in

19、t i,ElemType&e)/ListDelete_Sq,for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减1return OK;,算法时间复杂度为:,O(ListLength(L),p=/表尾元素的位置,if(i L.length)return ERROR;/删除位置不合法,元素左移,L.length-1,0,87,56,p=,例如：ListDelete_Sq(L,5,e),例：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。,（a1,a2,ai-1，ai,ai

20、+1，,an）,常见做法：从前往后扫描，见到0元素则与尾部非0元素互换；,从后往前扫描，见到0元素则后面元素统统前移；,从前往后扫描，见到0元素先计数，再将后续的一个非0元素前移，全部扫完后再把后续部分（长度为0元素的个数）清0。,深圳华为公司来某校招聘面试题,解：void SortA(SeqList*L)int i=0,zerosum=0;if(L-lenghth=0)return(0);/空表则结束 else for(i=0;ilenghth-1;i+)if(L-elemi0)L-elemi-zerosum=L-elemi;else zerosum+;for(i=L-lenghth-zer

21、osum;ilenghth;i+)L-elemi=0;/表的后部补0,6、其它一些操作实现,1、清空操作 void ClearList(SqList&L),L.length=0;删除L中所有元素，使之成为一个空表,2.判空操作,bool ListEmpty(SqList&L),return(L.length=0);/if（L.length=0）/return true;/else return false;若L为空表，返回真，否则返回假,3、有关查表的操作 1.遍历一个线性表 void TraverseList(SqList&L),for(int i=0;iL.length-1;i+)cout

22、L.elemi;coutendl;依次访问L中每一个元素一次,2.查找指定序号的元素 ElemType GetElem(SqList&L,int pos),if(posL.length)cerrpos is out range!endl;exit(1);return L.elempos-1;/注意序号与下标的不同,7、顺序表操作的效率分析,算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）

23、；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,时间效率分析:,推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次；若在a1后面插入，要后移n-1个元素，后移次数为n-1;若在an-1后面插入，要后移1个元素；若在尾结点an之后插入，则后移0个元素；所有可能的元素移动次数合计：0+1+n=n(n+1)/2,故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n),共有多少种插入形式?连头带尾有n+1种!,同理可证：顺序表删除一元素的时间效率

24、为:T（n)=(n-1)/2 O(n),插入效率：,删除效率：,教材P25有对执行效率的推导：（与课本略有区别）,即插入、删除算法的平均时间复杂度为 O(n),链式存储结构,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：,2.3 线性表类型的实现 链式映像,链表（linked list）：,是用动态申请存储空间，并通过指针来链接结点，按照线性表的前驱关系把一个个结点链接起来。链表所需要的存储空间可以根据线性元素的多少而动态地改变。,存储方式

25、：,用任意存储空间单元来存放线性表的各个元素，为了能体现元素之间的逻辑关系（线性），在存放每个元素的同时，也存放相关元素的信息（相关元素的存储地址），即用指针来表示元素之间的逻辑关系。存放一个元素占用的空间为：,用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,例：请画出26个英文字母表的链式存储结构。,该字母表在内存中链式存放的样式举例如下：,解：该字母表的逻辑结构为：（a,b,y,z）,链表存放示意图如下：,单链表、双链表、多链表、循环链表：结

26、点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。,循环链表示意图：,head,头结点,头指针,头指针,空指针,线性表为空表时，头结点的指针域为空,头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a的结点。,答：,讨论1.在链表中设置头结点有什么好处？,讨论2.如何表示空表？,头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以

27、为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。,答：,无头结点时，当头指针的值为空时表示空表；,有头结点时，当头结点的指针域为空时表示空表。,头结点不计入链表长度！,Typedef struct LNode ElemType data;/数据域 struct Lnode*next;/指针域 LNode,*LinkList;*LinkList;是指针型的LNode结构类型的替代,二、结点和单链表的 C 语言描述,LinkList L；/L 为单链表的头指针,三、单链表操作的实现,GetElem(L,i,e)/取第i个

28、数据元素,ListInsert(&L,i,e)/插入数据元素,ListDelete(&L,i,e)/删除数据元素,ClearList(&L)/重置线性表为空表,CreateList(&L,n)/生成含 n 个数据元素的链表,线性表的操作 GetElem(L,i,&e)在单链表中的实现:,j,1,2,3,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 I。,单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。,令指针 p 始终指向线性表中第 j 个数据元素。,Status GetElem_L(LinkList L,int i,ElemType&

29、e)/L是带头结点的链表的头指针，以 e 返回第 i 个元素/GetElem_L,算法时间复杂度为:,O(ListLength(L),p=L-next;j=1;/p指向第一个结点，j为计数器,while(p/顺指针向后查找，直到 p 指向第 i 个元素/或 p 为空,if(!p|ji)return ERROR;/第 i 个元素不存在e=p-data;/取得第 i 个元素return OK;,线性表的操作 ListInsert(&L,i,e)在单链表中的实现：,有序对 改变为 和,Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单

30、链表的头指针，本算法/在链表中第i 个结点之前插入新的元素 e/LinstInsert_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while(p/i 大于表长或者小于1,s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;,s,p,线性表的操作ListDelete(&L,i,&e)在链表中的实现:,有序对 和 改变为,在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。,q=p-next;p-next=q-n

31、ext;e=q-data;free(q);,p,q,Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点/ListDelete_L,算法的时间复杂度为:,O(ListLength(L),p=L;j=0;while(p-next/删除位置不合理,q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;,操作 ClearList(&L)在链表中的实现:,void ClearList(/ClearList,free(p);,算法时间复杂度：

32、,O(ListLength(L),如何从线性表得到单链表？,链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。,实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,先挖“坑”,后种“萝卜”！,新手特别容易忘记！,L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表p=L;for(i=1;inext=(LinkList)malloc(sizeof(LNode);p=p-next；/让指针变量P指向后一个结点cinp-data;/输入数据p-

33、next=NULL;/单链表尾结点的指针域要置空！,void CreateList_L(LinkList&L,int n)/顺序输入 n 个数据元素，建立带头结点的单链表要一个个慢慢链入,例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。,操作步骤：,一、建立一个“空表”；,二、输入数据元素an，建立结点并插入；,三、输入数据元素an-1，建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L,算法的时间复杂度为:,O(L

34、istlength(L),L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表,for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);cinp-data;/输入元素值 p-next=L-next;L-next=p;/插入,作业：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出完整的C/C+语言程序。,四、用单链表实现线性表上其它的操作,1.初始化单链表 void InitList(LNode*/O(1),3.删除单链表中结点，使之成为空表,void ClearLis

35、t(LNode*/O(n),4.得到单链表的长度,int ListSize(LNode*HL)/带头结点 P=HL-next;int i=0;while(P!=NULL)i+;P=P-next;return i;/O(n),5.得到单链表中第pos个结点中的元素,ElemType GetElem(LNode*HL,int pos)if(posnext;while(P!=NULL)i+;if(i=pos)break;P=P-next;if(P!=NULL)return P-data;else cerrpos is out range!endl;exit(1);/O(n),6.遍历一个单链表,vo

36、id TraverseList(LNode*HL)P=HL-next;while(P!=NULL)coutdatanext;coutendl;O(n),7.查找具有给定值的第一个元素,bool Find(LNode*HL,ElemType O(n),五、单链表的操作效率分析,（1）查找：因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,时间效率分析,（2）插入和删除：因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为 O(1)。,但是，如果要在单链表中进行在某结点前插或删除操作，因为要从头查找前驱结点，所以一般情况下，单链表插入和删除操作的

37、时间复杂度是 O(n)（同顺序表）。,1.双向链表,六、其它形式的链表,typedef struct DuLNode ElemType data;/数据域 struct DuLNode*prior;/指向前驱的指针域 struct DuLNode*next;/指向后继的指针域 DuLNode,*DuLinkList;,双向链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。,最后一个结点的指针域的指针又指回第一个结点的链表,a1 a2.an,2.循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,双向循环链表,空表,非空表,

38、a1 a2.an,双向链表的操作特点：,“查询”和单链表相同。,“插入”和“删除”时需要同时修改两个方向上的指针。,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入,删除,p-next=p-next-next;p-next-prior=p;,p,七、静态链表,静态链表：在数组中增加一个（或两个）指针域，这些指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的指针又称仿真指针。,静态单链表的类型定义如下：#define MAXSIZE 1000/预分配最大的元素个数（连续空间ty

39、pedef struct DataType data;/数据域 int next;/指示域 component,SLinkListMAXSIZE;/这是一维结构型数组,例 2：一线性表 S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？,data,01234561000,next,说明1：假设S为SLinkList型变量，则SMAXSIZE 为一个静态链表；S0.next则表示第1个结点在数组中的位置。,说明2：如果数组的第i个分量表示链表的第k个结点，则：Si.data表示第k个结点的数据；Si.next 表示第k+1个结点(即k的直接后继)的位置。,i,头结点,

40、说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。,例如：在线性表 S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：,S7.next=S3.next；,Step2:将QIAN的游标换为新元素LIU的下标：,S3.next=7,Step1:将QIAN的游标值存入next的游标中：,头结点,LIU,6,7,7,本章小结,线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。,2.线性表,逻辑结构：“一对一”或“1:1”存储结构：顺序、链式运 算：修改、

41、插入、删除查找和排序另述,3.顺序存储,特征：逻辑上相邻，物理上也相邻；优点：随机查找修改快 O(1)缺点：插入、删除慢 O(n),改进方案：链表存储结构,循环链表的特点：从任一结点出发均可找到表中其他结点,双向链表的特点：可方便找到任一结点的前驱,静态链表的特点：不用指针也能实现链式存储和运算,4.链式存储,特征：逻辑上相邻，物理上未必相邻；优点：插入、删除快 O(1)缺点：随机查找修改慢 O(n),5.几种特殊链表的特点：,顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链

42、式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。,顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。,作业：试用C/C+语言编写一个算法，将一循环单链表就地逆置。,操作前：（a1,a2,ai-1，ai,ai+1，,an）,操作后：（an,ai+1，ai,ai-1，,a2,a1）,q=head;p=head-next;/有头结点while(p!=head)/循环单链表 r=p-next;p-next=q;/前驱变后继 q=p;p=r;/准备处理下一结点head-next=q;/以an为首,q=head;p=head-next;/有头结点while(p!=head)/循环单链表 s=q;q=p;p=p-next;q-next=s;/准备处理下一结点p-next=q;/以an为首,（要求同学们根据下面算法的核心语句，编写一个完整算法）算法的核心语句 A 或 B,