数据结构第2章线性表单向链式存储.ppt

单链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。,2.3 线性表的链接存储结构及实现,单链表,存储特点：逻辑次序和物理次序 不一定相同。2.元素之间的逻辑关系 用指针表示。,2.3 线性表的链接存储结构及实现,例：(a1,a2,a3,a4)的存储示意图,单链表,a10200,a20325,a30300,a4,2.3 线性表的链接存储结构及实现,单链表,数据域,指针域,单链表是由若干结点构成的；单链表的结点必须有一个指针域。,data：存储数据元素next：存储指向后继结点的地址,struct node ElemType data;struct node*next;,2.3 线性表的链接存储结构及实现,如何申请一个结点？,s=new struct node;,s,s=new struct node;,2.3 线性表的链接存储结构及实现,s-data,如何引用数据元素？,如何引用指针域？,s-next,2.3 线性表的链接存储结构及实现,单链表,为了清楚起见，在讨论单链表的存储示意图时，通常将右图用下图表示。,2.3 线性表的链接存储结构及实现,单链表,头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。,2.3 线性表的链接存储结构及实现,单链表,空表和非空表不统一？如何将空表与非空表统一？,L中的地址值不相同,使L中的地址值相同,头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一，操作方便,2.3 线性表的链接存储结构及实现,带头结点的单链表,非空表,头结点,第一个结点,终端结点（尾结点）,由于单链表的存储空间是动态分配的，只要记住头指针，就能对单链表操作，所以单链表的类型描述只要考虑结点类型和指向结点的指针类型。,单链表类型的描述,2.3 线性表的链接存储结构及实现,typedef struct node ElemType data;struct node*next;Node,*LinkList;其中：Node等价于struct node LinkList等价于struct node*,单链表的实现按位查找,操作接口：int GetLinkList(LinkList L,int i,ElemType&x),核心操作（关键操作）：工作指针后移。从第1个结点出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。,2.3 线性表的链接存储结构及实现,L,a1,a2,an,ai,1.工作指针p初始化;累加器j置1;,2.1 工作指针p后移;2.2 累加器j加1;,2.循环直到p为空或p指向第i个结点,3.若p为空，则第i个元素不存在，抛出查找位置异常；否则查找成功，返回结点p的数据元素；,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述伪代码,int GetLinkList(LinkList L,int i,ElemType,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述C描述,不能,错,对,int GetLinkList(LinkList L,ElemType x,LinkList,2.3 线性表的链接存储结构及实现,单链表的实现按值查找,算法描述C描述,L,a1,an,x,p,p,p,如果找到了，p指向某个存在的结点，反之p为空,单链表的实现插入,操作接口：int InsertLinkList(LinkList L,int i,ElemType x);,2.3 线性表的链接存储结构及实现,如何实现结点ai-1、x和ai之间逻辑关系的变化？,算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;,插入位置的合理范围：1,n+1i=1 p指向头结点i=n+1 p指向尾结点,让p指向ai的直接前驱,注意分析边界情况表头、表尾。,单链表的实现插入,2.3 线性表的链接存储结构及实现,L,a1,an,ai,算法描述：s=new Node;s-data=x;s-next=p-next;p-next=s;,由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。,控制指针p移动的循环：while(p,j=0,j=n,当插入位置i合法，将指针变量移到第i-1个结点，j记住位置i-1。移动p的条件是：p!=NULL&ji-1,算法描述伪代码,1.工作指针p初始化；累加器j清零；2.查找第i-1个结点并使工作指针p指向该结点；3.若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，3.1 生成一个元素值为x的新结点s；3.2 将新结点s插入到结点p之后；,2.3 线性表的链接存储结构及实现,单链表的实现插入,int InsertLinkList(LinkList L,int i,ElemType x)p=L;j=0;while(p,2.3 线性表的链接存储结构及实现,算法描述C描述,单链表的实现插入,if(!p|ji-1)printf(“位置异常“);return 0;else/(p,，,基本语句？时间复杂度？,单链表的实现删除,操作接口：int DeleteLinkList(LinkList L,int i,ElemType,2.3 线性表的链接存储结构及实现,如何实现结点ai-1和ai之间逻辑关系的变化？,算法描述：q=p-next;x=q-data;p-next=q-next;delete q;,删除位置的合理范围：1,ni=1 p指向头结点i=n p指向尾结点的直接前驱,单链表的实现删除,2.3 线性表的链接存储结构及实现,算法描述：q=p-next;x=q-data;p-next=q-next;delete q;,注意分析边界情况表头、表尾。,控制指针p移动的条件：while(p-next,删除的结点必须存在，因此p-next不能为空。,j=0,j=n,算法描述伪代码,1.工作指针p初始化；累加器j清零；2.查找第i-1个结点并使工作指针p指向该结点；3.若p不存在后继结点，则抛出位置异常；否则，3.1 暂存被删结点和被删元素值；3.2 摘链，将结点p的后继结点从链表上摘下；3.3 释放被删结点；3.4 返回被删元素值；,2.3 线性表的链接存储结构及实现,单链表的实现删除,int DeleteLinkList(LinkList L,int i,ElemType,2.3 线性表的链接存储结构及实现,算法描述C描述,单链表的实现删除,if(!p-next|ji-1)printf(“位置异常”);return 0;else/(p-next,单链表的实现创建函数,操作接口：int creatLinkListf(LinkList&L,int n),头插法：将待插入结点插在头结点的后面。,算法描述：L=new Node;L-next=NULL;,2.3 线性表的链接存储结构及实现,35,12,24,33,42,例如,单链表的实现创建函数,操作接口：int creatLinkListf(LinkList,头插法：将待插入结点插在头结点的后面。,2.3 线性表的链接存储结构及实现,35,12,24,33,42,算法描述：s=new Node;scanf(,插入第一个元素结点,L,单链表的实现创建函数,操作接口：int creatLinkListf(LinkList,头插法：将待插入结点插在头结点的后面。,2.3 线性表的链接存储结构及实现,35,12,24,33,42,算法描述：s=new Node;scanf(,依次插入每一个结点,int creatLinkListf(LinkList,2.3 线性表的链接存储结构及实现,单链表的实现创建函数（头插）,算法描述：,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现创建函数,操作接口：int creatLinkListr(LinkList,算法描述：L=new Node;L-next=NULL;R=L;,35,12,24,33,42,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现创建函数,操作接口：int creatLinkListr(LinkList,算法描述：s=new Node;scanf(,35,12,24,33,42,插入第一个元素结点,尾插法：将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现创建函数,操作接口：int creatLinkListr(LinkList,算法描述：s=new Node;scanf(,35,12,24,33,42,依次插入每一个结点,35,int creatLinkListr(LinkList,2.3 线性表的链接存储结构及实现,单链表的实现创建函数(尾插),算法描述：,int creatLinkList(LinkList/调用插入函数,2.3 线性表的链接存储结构及实现,单链表的实现创建函数(用插入函数实现),算法描述：,单链表的实现销毁函数,销毁函数将单链表中所有结点的存储空间释放。,2.3 线性表的链接存储结构及实现,操作接口：int destroyLinkList(LinkList,L,a1,a2,an,ai,算法描述：q=p;p=p-next;delete q;,注意：保证链表未处理的部分不断开,单链表的实现销毁函数,int destroyLinkList(LinkList,2.3 线性表的链接存储结构及实现,算法描述：,启示：算法设计的一般过程,算法设计的一般步骤：第一步：确定入口（已知条件）、出口（结果）；第二步：根据一个小实例画出示意图；第三步：正向思维：选定一个思考问题的起点，逐步提出问题、解决问题；逆向思维：从结论出发分析为达到这个结论应该先有什么；正逆结合；第四步：写出具体算法，分析边界情况；第五步：进一步验证，手工运行。,存储分配方式比较,顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。,2.4 顺序表和单链表的比较,2.4 顺序表和单链表的比较,时间性能比较,按位查找：顺序表的时间复杂度为(1)，是随机存取；单链表的时间复杂度为(n)，是顺序存取。插入和删除：顺序表需移动表长一半的元素，时间复杂度为(n)单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间复杂度仅为(1),2.4 顺序表和单链表的比较,空间性能比较,空间性能是指某种存储结构所占用的存储空间的大小。,定义结点的存储密度：,2.4 顺序表和单链表的比较,空间性能比较,结点的存储密度：顺序表中每个结点的存储密度=1（只存储数据元素），没有浪费空间；单链表的每个结点的存储密度1（包括数据域和指针域），有指针的存储空间开销。整体结构：顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。,结论,若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。,2.4 顺序表和单链表的比较,总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。,