《数据结构教程 第2章 线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构教程 第2章 线性表.ppt（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院第二章第二章第二章第二章 线性表线性表线性表线性表 线性表线性表 顺序表顺序表 单链表单链表 线性链表的其他变形线性链表的其他变形 单链表的应用：多项式及其运算（不做要求）单链表的应用：多项式及其运算（不做要求）静态链表静态链表本章的基本内容是：本章的基本内容是：数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院线性表：线性表：简称表，是简称表，是n（n0）个具有）个具有相同类型相同类型的数据的数据元素的元素的有限序有限序列列。线性表的长度：线性表的长度：线性表中数据元素的个数
2、。线性表中数据元素的个数。空表：空表：长度等于零的线性表，长度等于零的线性表，记为：记为：L=()。非空表非空表记为：记为：L（a1,a2,ai-1,ai,an)2.1 2.1 线性表线性表线性表线性表2.1.1 线性表的概念线性表的概念其中，其中，ai（1in）称为数据元素）称为数据元素，称为，称为结点结点或表项或表项；下角标下角标 i 表示该元素在线性表中的位置或序号表示该元素在线性表中的位置或序号。数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院a1a3a4ana2线性表的图形表示线性表的图形表示线性表线性表（a1,a2,ai-1,ai,an)的图形表
3、示如下：的图形表示如下：2.1 2.1 线性表线性表线性表线性表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院a1a3a4ana2线性表的特性线性表的特性1.有限性：线性表中数据元素的个数是有穷的。有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素顺序性：线性表中相邻的数据元素ai-1和和ai之间存在之间存在序偶关系序偶关系(ai-1,ai)，即，即ai-1是是ai的前驱，的前驱，ai是是ai-1的后继；的后继；a1 无前驱，无前驱，an无后继，其它
4、每个元素有且仅有一个前无后继，其它每个元素有且仅有一个前驱和一个后继。驱和一个后继。2.1 2.1 线性表线性表线性表线性表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院线性表的抽象数据类型定义（见线性表的抽象数据类型定义（见P44）ADT LinearList isObjects:n个原子表项的一个有限序列。数据类型为个原子表项的一个有限序列。数据类型为T。Function:creat()int length()int search(T&x)int Locate(int i)T*getData(int i)void setData(int i,T&x)b
5、ool Insert(int i,T&x)bool Remove(int i,T&x)bool IsEmpty()bool IsFull()void CopyList(LinearList&L)void sort()end LinearList2.1 2.1 线性表线性表线性表线性表进一步说明进一步说明:（1 1）线性表的基本操作）线性表的基本操作根据实际应用而定；根据实际应用而定；（2）复杂的操作可以通）复杂的操作可以通过基本操作的组合来实现；过基本操作的组合来实现；数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院templateClass LinearL
6、IstPublic:LinearList();LinearList();virtual int Size()const=0;virtual int Length()const=0;virtual int Search(T&x)const=0;virtual int Locate(int i)const=0;virtual T*getData(int i)const=0;virtual void setData(int i,T&x)const=0;virtual bool Insert(int i,T&x)const=0;virtual bool Remove(int i,T&x)const=0
7、;virtual bool IsEmpty()const=0;virtual bool IsFull()const=0;virtual void sort()const=0;virtual bool input()const=0;virtual bool output()const=0;virtual bool LinearList operator=(LinearList&L)const=0;2.1.2 线性表类定义线性表类定义2.1 2.1 线性表线性表线性表线性表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院2.2 顺序表顺序表2.2.1 2.2.1
8、 顺序表的定义和特点顺序表的定义和特点例：例：（34,23,67,43）34236743 4存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素定义定义：把线性表中的所有表项按照其逻辑顺序：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。的一块连续的存储空间中。数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院特点：特点：（1 1）在顺序表中，各个表项的逻辑顺序与其存放的）在顺序表中，各个表项的逻辑顺序与其存
9、放的物理顺序一致。物理顺序一致。（2 2）对顺序表中所有表项，既可以进行顺序访问，）对顺序表中所有表项，既可以进行顺序访问，也可以进行随机访问。也可以进行随机访问。2.2 顺序表顺序表2.2.1 2.2.1 顺序表的定义和特点顺序表的定义和特点数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例：例：（34,23,67,43）34236743存储空间的起始位置存储空间的起始位置 4用什么属性来描述顺序表？用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的容量（最大长度）顺序表的当前长度顺序表的当前长度2.2 顺序表顺序表2.2.1 2.2.1 顺序表的定
10、义和特点顺序表的定义和特点数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例：例：（34,23,67,43）34236743 4如何实现顺序表的内存分配？如何实现顺序表的内存分配？顺序表顺序表一维数组一维数组2.2 顺序表顺序表2.2.1 2.2.1 顺序表的定义和特点顺序表的定义和特点数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院如何求得任意元素的存储地址？如何求得任意元素的存储地址？0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度一般情况下，一般情况下，(a1，a2，,ai-1，
11、ai,an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)2.2 顺序表顺序表2.2.1 2.2.1 顺序表的定义和特点顺序表的定义和特点数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空闲空闲 长度长度Loc(ai)=Loc(a1)+(i-1)c随机存取随机存取：在在O(1)时间内存取数据元素时间内存取数据元素一般情况下，一般情况下，(a1，a2，,ai-1，ai,an)的顺序存储：的顺序存储：cLoc(ai)Loc(a1)2.2 顺序表顺序表2.2.1 2.2.1 顺序表的定义
12、和特点顺序表的定义和特点数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 顺顺序序表表类类的的声声明明（见见P46）const int MaxSize=100;template /模板类模板类class SeqList:public LinearListprotected:T*data;int maxSize;int last;void reSize(int newSize);public:SeqList(int sz=defaultSize);/构造函数构造函数;SeqList(SeqList&L);/复制构造函数复制构造函数 SeqList()delet
13、e data;/析构函数析构函数 SeqList operator=(SeqList&L);2.2 顺序表顺序表2.2.2 2.2.2 顺序表的类定义及其操作顺序表的类定义及其操作数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院操作接口：操作接口：SeqList(intint szsz)算法描述：算法描述：SeqList :SeqList(int sz)if(sz0)maxSize=sz;last=-1;/置表的实际长度为空置表的实际长度为空 data=new TmaxSize;/创建顺序表存储数组创建顺序表存储数组 if(data=NULL)/动态分配失败
14、动态分配失败 cerr“存储分配错误！存储分配错误！”endl;exit(1);顺序表的实现顺序表的实现构造函数构造函数2.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院操作接口：操作接口：SeqList(SeqListSeqList&L)顺序表的实现顺序表的实现复制构造函数复制构造函数算法描述：算法描述：SeqList :SeqList(SeqList&L)/复制构造函数，用参数表中给出的已有顺序表初始化新建的顺序表。复制构造函数，用参数表中给出的已有顺序表初始化新建的顺序表。maxSize=L.size();last=L.length(
15、)-1;data=new TmaxSize;/创建顺序表存储数组创建顺序表存储数组 if(data=NULL)/动态分配失败动态分配失败 cerr“存储分配错误！存储分配错误！”endl;exit(1);for(int i=1;i=MaxSize合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序号）指的是元素的序号）顺序表的实现顺序表的实现插入插入 435122442a1a2a3a40 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件2.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术
16、学院template bool SeqList:Insert(int i,T&x)if(last=maxSize-1)return false;if(ilast+1)return false;for(intint j=last;j=i;j=last;j=i;j-)-)dataj+1=dataj;datai=x;last+;return true;算法描述算法描述C+描述描述顺序表的实现顺序表的实现插入插入基本语句基本语句？2.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院最好最好情况（情况（i=n+1）：）：基本语句执行基本语句执行0次，时
17、间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（i=1）：）：基本语句执行基本语句执行n+1次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：）：时间复杂度为时间复杂度为O(n)。时间性能分析时间性能分析顺序表的实现顺序表的实现插入插入+-+=11)=1(niiinp+-+=11)=1(11niinn2n=O(n)2.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院操作接口：操作接口：bool remove(int i,T&x)删除前：删除前：(a1,ai-1,ai,ai+1,an)删除后：删除后：(a1,a
18、i-1,ai+1,an)顺序表的实现顺序表的实现删删 除除ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化2.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例：（例：（35,33,12,24,42），），删除删除i=2的数据元素。的数据元素。仿照顺序表的插入操作，完成：仿照顺序表的插入操作，完成：1.分析边界条件；分析边界条件；2.分别给出伪代码和分别给出伪代码和C+描述的算法；描述的算法；3.分析时间复杂度。分析时间
19、复杂度。顺序表的实现顺序表的实现删删 除除 535a1a2a3a40 1 2 3 4422412334a51224422.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算法描述：算法描述：template int SeqList:search(T&x)const for(int i=0;i=last;i+)if(datai=x)return i+1;return 0;顺序表的实现顺序表的实现搜索和定位搜索和定位操作接口：操作接口：int Locate(int i)const int search(T&x)const时间复杂度时间复杂度？2.
20、2 顺序表顺序表template int SeqList:Locate(int i)const if(i=1&i=last+1)return i;else return 0;数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院2.2.3 顺序表的性能分析顺序表的性能分析 （主要分析搜索、插入和删除）（主要分析搜索、插入和删除）搜索算法的时间代价用数据比较次数来衡量：搜索算法的时间代价用数据比较次数来衡量：平均比较次数为平均比较次数为:(n+1)/2。插入和删除的时间代价主要看循环内的数据移动次插入和删除的时间代价主要看循环内的数据移动次数数：插入操作平均移动：插
21、入操作平均移动：n/2个表项；个表项；删除操作平均移动：删除操作平均移动：(n-1)/2个表项。个表项。2.2 顺序表顺序表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院2.2.4 顺序表的应用顺序表的应用2.2 顺序表顺序表void union(SeqList&LA,SeqList&LB)/合并顺序表合并顺序表LALA和和LBLB，结果存于结果存于LALA，重复元素只留一个重复元素只留一个 int n=LA.length(),m=LB.length(),i,k,x;for(i=1;i=m;i+)x=LB.getData(i);k=LA.Search(x)
22、;if(k=0)LA.Insert(n,x);n+;void Intersection(SeqList&LA,SeqList&LB)/求顺序表求顺序表LALA和和LBLB中的共有元素，结果存于中的共有元素，结果存于LALA int n=LA.length(),m=LB.length(),i=1,k,x;while(i=n)x=LA.getData(i);k=LB.Search(x);if(k=0)LA.Remove(i,x);n-;else i+;将顺序表作为集合的典型运算将顺序表作为集合的典型运算并和交并和交数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院
23、顺序表的优缺点顺序表的优缺点 顺序表的优点：顺序表的优点：无需为表示结点间的逻辑关系而增加额外的存储空无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率高；间，存储利用率高；随机存取：可以快速地存取表中任一位置的元素。随机存取：可以快速地存取表中任一位置的元素。顺序表的缺点：顺序表的缺点：插入和删除操作需要移动大量元素；插入和删除操作需要移动大量元素；表的容量难以确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充；造成存储空间的造成存储空间的碎片碎片。2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院单链表：单链表：是一种最
24、简单的链表表示，也叫做线性链表。是一种最简单的链表表示，也叫做线性链表。存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素。的存储单元存放线性表的元素。2.3.1 单链表的概念单链表的概念静态存储分配静态存储分配 顺序表顺序表事先确定容量事先确定容量 链链 表表动态存储分配动态存储分配 运行时分配空间运行时分配空间 连续连续不连续不连续零散分布零散分布2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院0200020803000325存储特点：存储特点：1.逻辑次序和物理次序逻辑次序和物理次序 不一定相同。不一定相同。2.元素
25、之间的逻辑关系元素之间的逻辑关系 用指针表示。用指针表示。例：例：(a1,a2,a3,a4)的存储示意图的存储示意图 a10200 a20325 a30300 a4 2.3 单链表单链表2.3.1 单链表的概念单链表的概念数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院0200020803000325 a10200 a20325 a30300 a4 结点结点数据域数据域指针域指针域单链表是由若干结点构成的；单链表是由若干结点构成的；单链表的结点只有一个指针域。单链表的结点只有一个指针域。data：存储数据元素存储数据元素next：存储指向后继结点的地址存储指
26、向后继结点的地址 data next单链表的结点结构：单链表的结点结构：数据域数据域指针域指针域2.3 单链表单链表2.3.1 单链表的概念单链表的概念数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 data links=new Node;sNode如何引用数据元素如何引用数据元素？s-data;*s.data;data如何引用指针域如何引用指针域？links-link;2.3 单链表单链表2.3.1 单链表的概念单链表的概念数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院0200020803000325 a10200
27、a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表重点在数据元素之间的逻辑关系的重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。表示，所以，将实际存储地址抽象。什么是存储结构什么是存储结构？2.3 单链表单链表2.3.1 单链表的概念单链表的概念数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=NULL空表空表头指针：头指针：指向第一个结点的地址。指向第一个结点的地址。尾标志
28、：尾标志：终端结点的指针域为空。终端结点的指针域为空。2.3 单链表单链表2.3.1 单链表的概念单链表的概念数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院单链表的存储映像单链表的存储映像free(a)可利用存储空间可利用存储空间a0a2a1a3 freefirst(b)经过一段运行后的单链表结构经过一段运行后的单链表结构2.3 单链表单链表2.3.1 单链表的概念单链表的概念数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院n多个类表达一个概念(单链表)。u 链表结点(ListNode)类u 链表(List)类n数据结构
29、设计方法u 复合类u 嵌套类u 基类和派生类u 用struct定义ListNode类2.3 单链表单链表2.3.2 单链表的类定义单链表的类定义数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 class List;/链表类定义（复合类方法）class ListNode /链表结点类 friend class List;/链表类为其友元类 private:int data;/结点数据,整型整型 ListNode*link;/结点指针;class List /链表类 private:ListNode*first;/表头指针;2.3 单链表单链表2.3.2 单链
30、表的类定义单链表的类定义数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院class List /链表类定义(嵌套类方法)private:class ListNode /嵌套链表结点类 public:int data;ListNode*link;ListNode*first;/表头指针public:/链表操作;2.3 单链表单链表2.3.2 单链表的类定义单链表的类定义数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院链表类和链表结点类定义链表类和链表结点类定义(基类与派生类方法基类与派生类方法)class ListNode
31、/链表结点类protected:int data;ListNode*link;class List:public class ListNode /链表类,继承链表结点类的数据和操作 private:ListNode*first;/表头指针;2.3 单链表单链表2.3.2 单链表的类定义单链表的类定义数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院用用structstruct定义定义ListNodeListNode类类struct ListNode /链表结点类 int data;ListNode*link;class List /链表类,直接使用链表结点类的
32、数据和操作 private:ListNode*first;/表头指针;2.3 单链表单链表2.3.2 单链表的类定义单链表的类定义数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院n插入u 第一种情况：在第一个结点前插入第一种情况：在第一个结点前插入 newnode-link=first;first=newnode;（插入前）（插入前）（插入后）（插入后）a1a2 firstxnewnodexnewnodea1firsta22.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技
33、术学院信息技术学院x (插入前插入前)()(插入后插入后)n插入u第二种情况：在链表中间插入第二种情况：在链表中间插入 newnode-link=current-link;current-link=newnode；newnodeai+1aicurrentxnewnodecurrent2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表aiai+1数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 n插入u第三种情况：在链表末尾插入第三种情况：在链表末尾插入 newnode-link=current-link;current-link=new
34、node；2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表an(插入前插入前)()(插入后插入后)xnewnodeanxnewnodecurrentcurrent 数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院bool List:Insert(int&x,int i)/在链表第在链表第 i i 个结点之后插入新元素个结点之后插入新元素 x x，i i为为0 0，则在第一个结点之前。，则在第一个结点之前。if(first=NULL|i=0)ListNode*newNode=new LinkNode(x);if(newNode=NULL
35、)cerrlink=first;first=newNode;/插入的为第一个结点插入的为第一个结点 else LinkNode*current=first;for(int k=1;klink;if(current=NULL&first!=NULL)/非空表切链太短非空表切链太短cerr“无效的插入位置无效的插入位置!n”;return false;2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表 else /插入在链
36、表的中间插入在链表的中间LinkNode*newNode=new LinkNode(x);if(newNode=NULL)cerrlink=current-link;current-link=newNode;return true;数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院n n删除删除uu第一种情况第一种情况第一种情况第一种情况:删除表中第一个元素删除表中第一个元素删除表中第一个元素删除表中第一个元素uu第二种情况第二种情况第二种情况第二种情况:删除表中或表尾元素删除表中或表尾元素删除表中或表尾元素删除表中或表尾元素在单链表中删除含在单链表中删除含a
37、i的结点的结点ai-1ai-1aiaiai+1ai+1currentdel删除前删除前删除后删除后2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院bool List:Remove(int i,int&x)/在链表中删除第 i 个结点 ListNode*del,*current;if(i link;else current=first;for(int k=1;k link;2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学
38、南京中医药大学信息技术学院信息技术学院 if(current=NULL|current-link=NULL)/空表或链太短空表或链太短 cerr link;/删除表中或表尾元素 current-link=del-link;x=del-data;delete del;/取出被删结点中的数据值 return true;2.3.3 单链表中的插入和删除单链表中的插入和删除2.3 单链表单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院0200020803000325 a10200 a20325 a30300 a4 firsta1a2an非空表非空表first=
39、NULL空表空表空表和非空表不统一，缺点？空表和非空表不统一，缺点？如何将空表与非空表统一如何将空表与非空表统一？2.3 单链表单链表2.3.4 带附加头结点的单链表带附加头结点的单链表数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院头结点：头结点：在在单链表的第以一个元素结点之前附设一个单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。类型相同的结点，以便空表和非空表处理统一。非空表非空表firsta1a2an空表空表first2.3 单链表单链表2.3.4 带附加头结点的单链表带附加头结点的单链表数据结构（数据结构（C+版）版
40、）南京中医药大学南京中医药大学信息技术学院信息技术学院template struct LinkNode T data;LinkNode*link；LinkNode(LinkNode*ptr=NULL)link=ptr;/仅初始化指针成员的构造函数仅初始化指针成员的构造函数 LinkNode(const T&item,LinkNode*ptr=NULL)data=item;link=ptr;/初始化数据与指针成员的构造函数初始化数据与指针成员的构造函数;template class List:public LinearListpublic:List()first=new LinkNode;Lis
41、t(const T&x)first=new LinkNode(x);2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 List(List&L);List()makeEmpty();void makeEmpty();int Length()const;LinkNode*getHead()return first;void setHead(LinkNode*p)first=p;LinkNode*Search(T x);LinkNode*Locate(int i);T*getData(int i);voi
42、d setData(int i,T&x);bool Insert(int i,T&x);bool Remove(int i,T&x);protected:LinkNode*first;/链表的头指针链表的头指针;2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院成员函数的实现成员函数的实现输入函数输入函数input()头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面。算法描述：算法描述：first=new Node;first-link=NULL;数组数组a3512243342
43、初始化初始化first 2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面。数组数组a3512243342算法描述：算法描述：s=new Node;s-data=a0;s-link=first-link;first-link=s;插入第一个元素结点插入第一个元素结点first35s2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版）版）南
44、京中医药大学南京中医药大学信息技术学院信息技术学院头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面。数组数组a3512243342算法描述：算法描述：s=new Node;s-data=a1;s-link=first-link;first-link=s;依次插入每一个结点依次插入每一个结点12sfirst352.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院template void List:InputFront(T
45、endTag)LinkNode*newNode;T val;first=new Node;first-lin=NULL;if(first=NULL)cerr“存存 储储 分分 配配 错错 误误！”val;while(val!=endTag)newNode=new LinkNode(val);if(newNode=NULL)cerr“存存 储储 分分 配配 错错 误误！”link=first-link;first-link=newNode;cinval;2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版
46、）版）南京中医药大学南京中医药大学信息技术学院信息技术学院尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。算法描述：算法描述：first=new Node;last=first;数组数组a3512243342初始化初始化firstlast2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。算法描述：算法描述：s=new Node;s-d
47、ata=a0;first-link=s;last=first;数组数组a3512243342插入第一个元素结点插入第一个元素结点firstlast35slast2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。算法描述：算法描述：s=new Node;s-data=a1;first-link=s;last=first;数组数组a3512243342依次插入每一个结点
48、依次插入每一个结点firstlast35last12slast2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。算法描述：算法描述：last-link=NULL;数组数组a3512243342最后一个结点插入后最后一个结点插入后firstlast35last42slast2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类成员函数的实现成员函数的实现输入函数
49、输入函数input()数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院2.3 单链表单链表2.3.5 单链表的模板类单链表的模板类template void List:InputRear(T endTag)LinkNode*newNode,*last;T val;first=new Node;first-lin=NULL;if(first=NULL)cerr“存存 储储 分分 配配 错错 误误！”val;last=first;while(val!=endTag)newNode=new LinkNode(val);if(newNode=NULL)cerr“存存
50、 储储 分分 配配 错错 误误！”link=newNode;last=newNode;cinval;last-link=NULL;成员函数的实现成员函数的实现输入函数输入函数input()数据结构（数据结构（C+版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院启示：算法设计的一般过程启示：算法设计的一般过程算法设计的一般步骤：算法设计的一般步骤：第一步：确定第一步：确定入口入口（已知条件）、（已知条件）、出口出口（结果）；（结果）；第二步：根据一个小实例画出第二步：根据一个小实例画出示意图示意图；第第三三步步：正正向向思思维维：选选定定一一个个思思考考问问题题的的起起点点，逐逐步步