数据结构与算法设计PPT (7).pdf
第第2 2章章 线性表线性表2.32.3 线性表链式存储结构线性表链式存储结构 链式存储结构的特点 链表的插入 链表的删除 插入删除运算总结主要内容线性表顺序存储结构特点 存储空间一般不能自主扩充 如果需要增加存储容量，那需要重新申请大的空间，并把数据移动到新空间上。扩充空间的效率很低。插入和删除时需要移动元素实现 效率很低，平均情况下需要移动表长一半的数据元素采用链表可以解决这些问题采用链表可以解决这些问题 方法-具有关系的数据元素可以不用相邻存储-可用指针指示数据元素之间的关系-插入和删除可采用更改链接关系的方式进行 这就是链式存储结构的思想 链式存储结构没有存储上的限制(只受Heap空间容量大小的限制)解决的方法解决的方法 单链表最简单的链表，又称线性链表 特点 每个元素(表项)用结点(Node)存储 元素之间的关系通过指向后继的指针来表示 指针与并不是数据元素的数据成分，是表示关系的存储代价 头指针是找到所有元素结点的关键单链表存储数据元素存储数据元素存储后继结点存储后继结点存储地址存储地址单链表结点单链表的存储映映像通过头指针可以找到链表上的所有结点的存储位置HeapHeap线性表链式存储结构 存储空间可以自主扩充 插入和删除可以通过改变指针做到 不再具有随机存取能力，只能按照头指针依次顺序查找数据元素 关系的表示需要占用存储空间链表中第一个结点和最后一个结点的位置很重要单链表的类定义多个类表达一个概念多个类表达一个概念(单链表单链表)。链表结点链表结点(ListNodeListNode)类类链表链表(ListList)类类链表游标链表游标(IteratorIterator)类类定义方式定义方式复合方式复合方式嵌套方式嵌套方式class class List;/复合类定义复合类定义classclassListNode/链表结点类链表结点类friend classfriend classL List;/链表类为其友元类链表类为其友元类private:private:intintdata;/结点数据结点数据,整型整型ListNode*link;/结点指针结点指针;class class List/链表类链表类public:public:/链表公共操作链表公共操作private:private:ListNode*first,*last;/表头和表尾指针表头和表尾指针;单链表的复合类定义单链表的复合类定义class class List /链表类定义链表类定义(嵌套方式嵌套方式)public:public:/链表操作链表操作private:private:classclassListNode /嵌套链表结点类嵌套链表结点类public:public:int int data;ListNode*link;ListNode*first,*,*last;/表头和表尾指针表头和表尾指针;单链表的嵌套类定义单链表的嵌套类定义单链表中的插入与删除 插入 第一种情况：在第一个结点前插入newnodelink=first;first=newnode；（插入前）（插入后）firstnewnodenewnodefirst(插入前)(插入后)第二种情况：在链表中间插入newnodelink=plink;plink=newnode；newnodepnewnodep第三种情况：在链表末尾插入newnodelink=plink;plink=last=newnode；(插入前)(插入后)newnodenewnodelastplastp 查找插入位置i之前的第i-1个结点的指针 根据查找结果判断插入位置是否合法-不合法返回 获取新结点，将元素装入结点 判断-在头部插入，进行处理-在中间插入，进行处理-在尾部插入，进行处理插入算法思想插入算法思想int int List:Insert(constconst intintx,const int const int i)/在链表第在链表第i i个结点处插入新元素个结点处插入新元素x xListNode*p=first;int;int k=0;while while(p!=NULL&k i-1)p=plink;k+;/找第找第i i-1 1个结点个结点if if(p=NULL&first!=NULL)coutcout“无效的插入位置无效的插入位置!n”;return return 0;ListNode*newnode=newnewListNode(x,NULL);/创建新结点创建新结点,其数据为其数据为x x,指针为指针为0 0从从0 0开始开始if if(first=NULL|i=0)/插在表前插在表前newnodelink=first;if if(first=NULL)last=newnode;first=newnode;else else /插在表中或末尾插在表中或末尾newnodelink=plink;if if(plink=NULL)last=newnode;plink=newnode;return return 1;删除删除第一种情况第一种情况:删除表中第一个元素删除表中第一个元素第二种情况第二种情况:删除表中或表尾元素删除表中或表尾元素在单链表中删除含在单链表中删除含a ai i的结点的结点仅已知待删除结点的指针是否可以完成删除操作？查找删除位置i之前的第i-1个结点的指针 根据查找结果判断删除位置是否合法-不合法返回 判断-在头部删除，进行处理-在中间或尾部删除，进行处理删除算法思想删除算法思想intintList:Remove(intinti)/在链表中删除第在链表中删除第i i个结点个结点Node*p=first,*q;int;int k=0;while while(p!=NULL&k i-1)p=plink;k+;/找第找第i i-1 1个结点个结点if if(p=NULL|plink=NULL)coutcout“无效的删除位置无效的删除位置!n”;”;return return 0;if if(i=0)/删除表中第删除表中第 1 1 个结点个结点q=first;/q q 保存被删结点地址保存被删结点地址p=first=firstlink;/修改修改firstfirst else else /删除表中或表尾元素删除表中或表尾元素q=plink;plink=qlink;/重新链接重新链接 if if(q=last)last=p;/可能修改可能修改lastlastk=qdata;deletedeleteq;/删除删除q qreturnreturnk;插入删除总结插入运算：（1）在链表头之前插入（2）在链表中间插入（3）在链表末尾插入删除运算：（1）删除第一个结点（2）删除某一个中间结点（3）删除最后一个顶点
