线性表CPPT学习教案

1、会计学1线性表线性表C1.1. 链表的表示链表的表示( (包括有关术语、包括有关术语、结构结构等）等）2.2. 链表的实现（建表、输出、修改、插入、删除）链表的实现（建表、输出、修改、插入、删除）补充：其它链表形式补充：其它链表形式循环链表循环链表双向链表双向链表静态链表静态链表提问：提问： 怎样读取结点数据域中的信息？怎样读取结点数据域中的信息？ 链表的操作要用指针链表的操作要用指针如用如用p-data仅两个动作：找位置仅两个动作：找位置和改地址！和改地址！第1页/共41页 线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储

2、及实现 顺序表和单链表的比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：第2页/共41页存储分配方式比较存储分配方式比较顺序表顺序表采用采用顺序存储顺序存储结构，即用一段地址结构，即用一段地址连续连续的的存储单元存储单元依次依次存储线性表的数据元素，数据元素之存储线性表的数据元素，数据元素之间的逻辑关系通过间的逻辑关系通过存储位置存储位置来实现。来实现。单链表单链表采用采用链式存储链式存储结构，即用一组结构，即用一组任意任意的存储的存储单元存放线性表的元素。用单元存放线性表的元素。用指针指针来反映数据元素之来反映数据元素之间的逻辑关系。

3、间的逻辑关系。第3页/共41页时间性能比较时间性能比较 时间性能时间性能是指实现基于某种存储结构的基本操作（即是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。算法）的时间复杂度。 按位查找：按位查找：顺序表的时间为顺序表的时间为(1)(1)，是随机存取；，是随机存取；单链表的时间为单链表的时间为( (n n) )，是顺序存取。，是顺序存取。插入和删除：插入和删除：顺序表平均需移动表长一半的元素，时间为顺序表平均需移动表长一半的元素，时间为( (n n) )；单链表不需要移动元素，在给出某个合适位置的指针单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为后，

4、插入和删除操作所需的时间仅为(1)(1)。第4页/共41页空间性能比较空间性能比较 空间性能空间性能是指某种存储结构所占用的存储空间的大小。是指某种存储结构所占用的存储空间的大小。 定义结点的存储密度：定义结点的存储密度： 数据域占用的存储量数据域占用的存储量整个结点占用的存储量整个结点占用的存储量存储密度存储密度第5页/共41页空间性能比较空间性能比较 结点的存储密度：结点的存储密度：顺序表顺序表中每个结点的中每个结点的存储密度为存储密度为1 1（只存储数据元（只存储数据元素），没有浪费素），没有浪费空间空间；单链表的每个结点的单链表的每个结点的存储密度存储密度11（包括数据域和指（包括数据

5、域和指针域），有指针的结构性开销。针域），有指针的结构性开销。整体结构：整体结构：顺序表需要预分配存储空间，如果预分配得过大，顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；造成浪费，若估计得过小，又将发生上溢；单链表不需要预分配空间，只要有内存空间可以分单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。配，单链表中的元素个数就没有限制。 第6页/共41页结论结论总之总之，根据实际问题的具体需要，根据实际问题的具体需要, ,加以综合平衡，才能加以综合平衡，才能终选定终选定比较适宜比较适宜的实现方法。的实现方法。第7页/共41页特点：

6、特点： 3从单链表中某结点从单链表中某结点p p出发如何找到其前驱？出发如何找到其前驱？heada1ai-1anaip讨论讨论1：第8页/共41页如：带头结点的如：带头结点的空空循环链表样式循环链表样式head注：将单链表的首尾相接，将终端结点的指针域由空注：将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成指针改为指向头结点，构成单循环链表单循环链表，简称，简称循环链循环链表表。结点结构定义：结点结构定义：/未变未变template class XLinkList;/前视定义前视定义,便于使用友元便于使用友元template class Node friend class L

7、inkList;/友元类友元类 private: datatype data; Node *next; data next第9页/共41页heada1ai-1anai循环链表循环链表插入插入xspxspxsp核心算法描述：核心算法描述：s=new Node; s-data=x; s-next=p-next; p-next=s;第10页/共41页template void XLinkList:Insert(int i, datatype x) Node *p; int j; p=head ; j=0; while (p-next!=head & jnext; j+; if (j!=i-1) th

8、row i不合法不合法; else Node *s; s=new Node; s-data=x; s-next=p-next; p-next=s; 循环链表循环链表插入实现插入实现与单链表的插入操作相比，差别是什么？与单链表的插入操作相比，差别是什么？第11页/共41页循环条件：循环条件：p!=NULLp!=headp-next!=NULLp-next!=head循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环注：注：第12页/共41页template void XLinkList:PrintList( )Node *p;p=head-next;while (p!

9、=head) coutdatanext;循环链表循环链表遍历算法实现遍历算法实现O(n)第13页/共41页reara1ai-1anai开始结点：开始结点：rear-next-next终端结点：终端结点：rear其它形式的循环链表如：带尾指针的循环链表其它形式的循环链表如：带尾指针的循环链表 一个存储结构设计得是否合理，取决于基于该一个存储结构设计得是否合理，取决于基于该存储结构的存储结构的运算是否方便运算是否方便，时间性能是否提高时间性能是否提高。 第14页/共41页如何求结点如何求结点p p的直接前驱，时间性能？的直接前驱，时间性能？heada1ai-1anaip如何快速求得结点如何快速求得

10、结点p p的后继？的后继？如何快速求得结点如何快速求得结点p p的前驱？的前驱？讨论讨论2：p-next 引入一个辅助指针变量引入一个辅助指针变量q,从首结点开始遍历，从首结点开始遍历，至至q-next=p找到直接前驱结点找到直接前驱结点;双向链表：双向链表：在单链表的每个结点中再设置一个指在单链表的每个结点中再设置一个指向其前驱结点的指针域。向其前驱结点的指针域。priordatanext第15页/共41页template class DLinkList;template class Node friend class DLinkList; private: type data; Node

11、*next,*prior;双向链表双向链表启示？启示？时空权衡时空权衡空间换取时间空间换取时间结点结构定义（类的声明）：结点结构定义（类的声明）：priordatanext常用双向循环链表，如空的常用双向循环链表，如空的双向循环链表为：双向循环链表为：ai-1第16页/共41页双向链表的操作双向链表的操作插入实现插入实现ai-1ai操作接口：操作接口： template void DLinkList:Insert(int i, type x)pxs注意指针修改的注意指针修改的相对相对顺序顺序核心语句：核心语句： DNode *s; s=new DNode; s-data=x; s-prior=

12、p; s-next=p-next; p-next-prior=s; p-next=s; 第17页/共41页双向链表的操作双向链表的操作删除实现删除实现操作接口：操作接口：template type DLinkList:Delete(int i)ai-1aiqai结点结点q q的指针是否需要修改？的指针是否需要修改？delete q; pDNode *q; int x;q=p-next; x=q-data; p-next=q-next;(q-next)-prior=p; delete q; 不需要！不需要！第18页/共41页答：能。答：能。用数组来表示单链表，用数组元素的下标来模拟单用数组来表示

13、单链表，用数组元素的下标来模拟单链表的指针，称为链表的指针，称为静态链表静态链表。数据元素由。数据元素由数据域数据域和和指示域指示域组成。组成。注：数据域含义与前面相同，注：数据域含义与前面相同，指示域指示域相当于前面的相当于前面的指针域。指针域。静态链表的插入与删除操作与普通链表一静态链表的插入与删除操作与普通链表一样，不需要移动元素，样，不需要移动元素，只需修改指示器只需修改指示器就可以了就可以了参考参考p79 data next数据数据域域指示指示域域第19页/共41页例如：线性表例如：线性表( (张，王，李，赵，吴张，王，李，赵，吴) )的静态链表存储的静态链表存储张张 2王王 3李李

14、 4赵赵 5吴吴 -1012345678 7 8 -1 1data next静态链表静态链表headavailhead：静态链表头指针静态链表头指针，为了方，为了方便插入和删除操作，通常静态链便插入和删除操作，通常静态链表表带头结点带头结点；avail：空闲链表头指针空闲链表头指针，空闲链空闲链表由于只在表头操作，所以表由于只在表头操作，所以不带不带头结点头结点；第20页/共41页例如：线性表例如：线性表( (张，王，李，赵，吴张，王，李，赵，吴) )的静态链表存储的静态链表存储张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data nextheadavailS

15、LinkList S;第21页/共41页在线性表在线性表( (张，王，李，赵，吴张，王，李，赵，吴) )中中“王王”之后插入之后插入“孙孙”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data next张张 2王王 6李李 4赵赵 5吴吴 -1012345678 8 -1 1data next王之后王之后插入孙插入孙headavailheadavail孙孙3avail第22页/共41页在线性表在线性表( (张，王，李，赵，吴张，王，李，赵，吴) )中删除中删除“赵赵”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data nex

16、t张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data next删除赵删除赵摘链摘链headavailheadavail5第23页/共41页在线性表在线性表( (张，王，李，赵，吴张，王，李，赵，吴) )中删除中删除“赵赵”张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data next张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data next删除赵删除赵归还空间归还空间headavailheadavail56第24页/共41页SLinkList S;注注:S0.next指示第指示第1个个结

17、点在表中的位置。结点在表中的位置。当当S0.next=1时时.则则S1.data为线性表第一为线性表第一个元素的值。个元素的值。Sk.next指示第指示第K+1个个结点在表中的位置。结点在表中的位置。则则SK.data为线性表第为线性表第K个元素的值。个元素的值。张张 2王王 3李李 4赵赵 5吴吴 -1012345678 7 8 -1 1data nextheadavail第25页/共41页/线性表的静态单链表存储结构定义线性表的静态单链表存储结构定义/SLinkList.h 声明类声明类SLinkList#ifndef SLinkList_H#define SLinkList_Hconst

18、 int maxsize=5;template class SLinkList;template class Node friend class SLinkList; private: type data; int next; /指示器指示器;第26页/共41页template class SLinkList public: SLinkList( ); /建立只有头结点的静态空链表建立只有头结点的静态空链表 SLinkList(type *a, int n); /建立有建立有n个元素的静态单链表个元素的静态单链表 SLinkList(); /析构函数析构函数,为空为空 int Length()

19、; /求静态单链表的长度求静态单链表的长度 type Get(int i); /取静态单链表中第取静态单链表中第i个结点的元素值个结点的元素值 int Locate(type x); /求静态单链表中值为求静态单链表中值为x的元素序号的元素序号 void Insert(int i, type x); /在静态单链表中第在静态单链表中第i个位置插入元素值为个位置插入元素值为x的结点的结点 type Delete(int i); /在静态单链表中删除第在静态单链表中删除第i个结点个结点 void PrintList( ); /遍历静态单链表，按序号依次输出各元素遍历静态单链表，按序号依次输出各元素

20、 void clear(); void Pdisplay();/遍历整个存储区域的内容遍历整个存储区域的内容 private: Int head; /静态单链表的头指针静态单链表的头指针 int avail; /可利用空间表的头指针可利用空间表的头指针 Node sllmaxsize;/存储区域存储区域;#endif第27页/共41页静态链表算法实现实例静态链表算法实现实例(1)在静态链表中实现在静态链表中实现定位函数定位函数算法如下：算法如下：template int SLinkList:Locate(T x) /在静态单链表在静态单链表S查找第查找第1个值为个值为x的元素的位置。的元素的位

21、置。/若找到，则返回位序，否则为若找到，则返回位序，否则为-1； int i; i=sllhead.next ; while(i !=-1& abs(strcmp(Si.data,x) i=Si.next;return i;/#include /#include math.h第28页/共41页(2)在静态链表中实现在静态链表中实现插入算法插入算法如下：如下：template void SLinkList:Insert(int i, T x) /在静态单链表中第在静态单链表中第i个位置插入元素值为个位置插入元素值为x的结点的结点 int p; int j; p=head; j=0; /指示器指示

22、器p初始化初始化 while (p!=-1 & ji-1) p=sllp.next; /指示器指示器p后移后移 j+; /找插入点找插入点 if (p=-1) throw i的位置不合法的位置不合法; else int s;/存储放新结点存储放新结点 s=avail; avail=sllavail.next;/从从avail链中删除链中删除 slls.data=x; /数据域为数据域为x slls.next=sllp.next; /插入到插入到head链中。链中。 sllp.next=s;与动态链表算法与动态链表算法相似相似, ,但其利用但其利用指示器实现指示器实现! !第29页/共41页在静

23、态链表中实现在静态链表中实现删除算法删除算法如下：如下：template T SLinkList:Delete(int i) int p; int j; p=head ; j=0; /指示器指示器p初始化初始化 while (p!=-1 & ji-1) /查找第查找第i-1个结点个结点 p=sllp.next; j+; if (p=-1 | sllp.next=-1) throw “i不合法不合法; else int q; int x; q=sllp.next; x=sllq.data; /暂存被删结点暂存被删结点 sllp.next=sllq.next; /摘链摘链 sllq.next=av

24、ail;/avail收回收回 avail=q; return x;与动态链表算法与动态链表算法相似相似, ,但其利用但其利用指示器实现指示器实现! !第30页/共41页相对于顺序表而言，静态链表有什么优点？相对于顺序表而言，静态链表有什么优点？ 优点：优点：在执行插入和删除操作时，在执行插入和删除操作时，只需修改游标只需修改游标，不需要移动表不需要移动表中的元素，从而改进了在顺序表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。中插入和删除操作需要移动大量元素的缺点。缺点缺点:(1):(1)表长难以确定表长难以确定； (2)(2)静态链表静态链表还需要维护还需要维护一个一个

25、空闲链空闲链； (3)(3)静态链表静态链表不能随机存取不能随机存取。 第31页/共41页、间接寻址、间接寻址方法之一：将数组和指针结合起来。方法之一：将数组和指针结合起来。数组数组中存储数据元素的单元改为中存储数据元素的单元改为存储指向该存储指向该元素的指针元素的指针 。0 1 2 i-1 n-1 Max-1 空闲空闲 长度长度 a1 ai an a2插入操作移动的不是元素而是指向元素的指针。当元素插入操作移动的不是元素而是指向元素的指针。当元素本身占用的空间较多时，比顺序表的插入操作快得多。本身占用的空间较多时，比顺序表的插入操作快得多。 第32页/共41页一元多项式的计算一元多项式的计算

26、第33页/共41页一元多项式的通式可表示为：一元多项式的通式可表示为：A xaxaxa xmemeemm().120120分析：分析：一元多项式在计算机内存储时，既可用一元多项式在计算机内存储时，既可用顺序表顺序表存储存储，又可用，又可用链表链表存储。但当多项式的存储。但当多项式的次数很高且零系数项很多次数很高且零系数项很多时，则更适于用链表存储（时，则更适于用链表存储（通常设计两个数据域和一个指针通常设计两个数据域和一个指针域域）。）。a0a1a2am-2am-1顺序表顺序表链表链表am-1 em-1am-2 em-2 a0 e0 或或0.0 -1 am-1 em-1 a0 e0第34页/共41页coefexpnextclass termpublic:float coef;/系数系数int exp;/指数指数;结点包含两个域结点包含两个域data和和next,并且并且data又包又包含两个域含两个域coef和和exp。如结点如结点e为：为：Node e;e第35页/共41页bxxx8310141063 142 81 0a8 143 1010 6b例：例：123814xxa运算规则：两多项式中运算规则：两多项式中指数相同的项指数相同的项对应对应系系数相加，数相加，若若和不为和不为0,则则构成多项式构成多项式c=(a+b)中的一项；中的一项；a和和b中所有指数不相