第2章线性表c2

1、数据结构（C+版）2012辽宁科技大学软件学院1单链表：单链表：线性表的链接存储结构。线性表的链接存储结构。存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素。的存储单元存放线性表的元素。 2.3 线性表的链式存储线性表的链式存储单链表单链表静态存储分配静态存储分配 顺序表顺序表事先确定容量事先确定容量 链链 表表动态存储分配动态存储分配 运行时分配空间运行时分配空间 连续连续不连续不连续零散分布零散分布数据结构（C+版）2012辽宁科技大学软件学院20200020803000325存储特点：存储特点：1. 逻辑次序和物理次序不一定相同。逻辑次序和物理次序不一定相同。 2. 元

2、素间的逻辑关系用指针表示。元素间的逻辑关系用指针表示。 2.3 线性表的链式存储线性表的链式存储例：例：(a1, a2 ,a3, a4)的存储示意图的存储示意图单链表单链表 a10200 a20325 a30300 a4 firsta1a2an1.一般情况存储示意图一般情况存储示意图数据结构（C+版）2012辽宁科技大学软件学院3 2.3 线性表的链式存储线性表的链式存储单链表单链表data：存储数据元素：存储数据元素next：存储后继结点的地址：存储后继结点的地址 data next2. 单链表的结点结构单链表的结点结构(逻辑逻辑)数据域数据域指针域指针域每个结点有一个指针域所以称为每个结点

3、有一个指针域所以称为“单单链表链表”数据结构（C+版）2012辽宁科技大学软件学院4 2.3 线性表的链式存储线性表的链式存储单链表单链表3. C+ 实现（存储）实现（存储）template struct Node DataType data; Node *next; 数据结构（C+版）2012辽宁科技大学软件学院5指针变量、指针、指针所指向结点、结点指针变量、指针、指针所指向结点、结点设设P是一个指针变量是一个指针变量指针变量简称为指针指针变量简称为指针指针指针P P所指向结点简称为结点所指向结点简称为结点P P2.3 线性表的链式存储线性表的链式存储图2-10 指针和结点之间关系的示意图a

4、iai+1p*p*(p-next)an a1first数据结构（C+版）2012辽宁科技大学软件学院6s=new Node ; 2.3 线性表的链式存储线性表的链式存储单链表单链表 Nodes如何申请一个结点如何申请一个结点？ data nextS简化后简化后如何引用结点如何引用结点？s-data ;（*s）.data ;3. 引用指针域引用指针域？s-next;2. 引用数据元素引用数据元素？1. 结点结点(结构体结构体)： *s数据结构（C+版）2012辽宁科技大学软件学院7p=new Node ; p-data=10;q=new Node;q-data=20;p-next=q; 分析下列

5、语句的功能，并画出示意图分析下列语句的功能，并画出示意图 10 nextp结构体指针的定义及引用结构体指针的定义及引用1.如何利用如何利用p访问访问20？2.如何插入元素如何插入元素x在两结点之间？在两结点之间？ 20 nextq结论：结论：10，20互为前驱，后继互为前驱，后继10 p20 p-next-datas=new Node;s-next=p-next;p-next=s;数据结构（C+版）2012辽宁科技大学软件学院8 2.3 线性表的链式存储线性表的链式存储单链表单链表firsta1a2anfirst =NULL非空表非空表空表空表头指针：头指针：指向第一个元素（开始结点）所在结点

6、的指向第一个元素（开始结点）所在结点的 指针变量，指针变量，一般命名为一般命名为first尾标志：尾标志：最后一个元素（终端结点）的指针域为最后一个元素（终端结点）的指针域为空空1.1.无头结点的单链表无头结点的单链表数据结构（C+版）2012辽宁科技大学软件学院92.2.带头结点的单链表带头结点的单链表 头结点：头结点：在在第一个元素结点之前附设一个类型相同第一个元素结点之前附设一个类型相同 的结点，从而使大部分算法实现更简单。的结点，从而使大部分算法实现更简单。 2.3 线性表的链式存储线性表的链式存储单链表单链表非空表非空表firsta1a2an空表空表first除特殊说明外，一般均以带

7、头结点的链表除特殊说明外，一般均以带头结点的链表为例实现相关操作为例实现相关操作数据结构（C+版）2012辽宁科技大学软件学院10template class LinkList public: LinkList( )； LinkList( ); int Length( ); DataType Get(int i); int Locate(DataType x); void Insert(int i, DataType x); DataType Delete(int i); void PrintList( ); private: Node *first; /头指针头指针;单链表类的声明单链表类的

8、声明2.3 线性表的链式存储线性表的链式存储数据结构（C+版）2012辽宁科技大学软件学院11单链表的实现单链表的实现遍历链表遍历链表操作接口：操作接口： PrintList( )v核心操作（关键操作）：核心操作（关键操作）：工作指针工作指针P后移后移v如何后移？如何后移？2.3 线性表的链式存储线性表的链式存储firsta1a2anaip=p-next;pppppp数据结构（C+版）2012辽宁科技大学软件学院12template void LinkList:PrintList( ) p=first-next; while (p) /输出线性表结点的数据域输出线性表结点的数据域 coutda

9、ta; /指针后移指针后移 p=p-next; 2.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现遍历链表遍历链表算法描述算法描述C+描述描述p+能否完成指针后移？能否完成指针后移？a1a2pp+p-next数据结构（C+版）2012辽宁科技大学软件学院13单链表的实现单链表的实现求链表长度求链表长度操作接口：操作接口： int Length( )v操作：遍历的同时，计数器操作：遍历的同时，计数器+12.3 线性表的链式存储线性表的链式存储firsta1a2anaipj=0pj=1pj=ipj=2pj=n遍历结束遍历结束p数据结构（C+版）2012辽宁科技大学软件学院14temp

10、late void LinkList:PrintList( ) p=first-next; while (p) coutdata; p=p-next; 2.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现求链表长度求链表长度算法描述算法描述C+描述描述求链表长度求链表长度template int LinkList:length( ) p=first-next; count=0; while (p) p=p-next; count+; return count;遍历链表遍历链表数据结构（C+版）2012辽宁科技大学软件学院15单链表的实现单链表的实现按位查找按位查找操作接口：操作接口

11、： DataType Get(int i)2.3 线性表的链式存储线性表的链式存储firsta1a2anaipj=0pj=1查找成功查找成功pj=ipj=2pj=n查找失败查找失败pj=i数据结构（C+版）2012辽宁科技大学软件学院161. 工作指针工作指针p初始化初始化; 累加器累加器j初始化初始化;2.1 工作指针工作指针p后移后移;2.2 累加器累加器j加加1;2. 循环直到循环直到p为空或为空或p指向第指向第i个结点个结点3. 若若p为空，则第为空，则第i个元素不存在，抛出查找位置个元素不存在，抛出查找位置异常；否则查找成功，返回结点异常；否则查找成功，返回结点p的数据元素；的数据元

12、素；2.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现按位查找按位查找算法描述算法描述伪代码伪代码数据结构（C+版）2012辽宁科技大学软件学院17template DataType LinkList:Get(int i) p=first; j=0; / p=first-next; j=1; while (p & jnext; j+; if (!p) throw “无该位置元素无该位置元素; else return p-data; 2.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现按位查找按位查找算法描述算法描述C+描述描述数据结构（C+版）2012辽宁科技大学软件

13、学院182.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现按值查找按值查找template int LinkList:Locate(DataType x) p=first-next; j=1； while (p & p-data!=x) p=p-next; j+; if (!p) throw “无该值元素无该值元素; else return j; 数据结构（C+版）2012辽宁科技大学软件学院19单链表的实现单链表的实现插入插入操作接口：操作接口： void Insert(int i, DataType x) 2.3 线性表的链式存储线性表的链式存储1. 一般位置（中间）插入一般

14、位置（中间）插入pxsfirsta1ai-1anai算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;关键：找到关键：找到i-1位置位置数据结构（C+版）2012辽宁科技大学软件学院202. 边界边界情况情况表头表头(i=1)、表尾、表尾(i=n+1)。 单链表的实现单链表的实现插入插入2.3 线性表的链式存储线性表的链式存储firsta1anakpxs算法描述：算法描述：s=new Node; s-data=x;s-next=p-next; p-next=s;pxs由于单链表带头结点，由于单链表带头结点，表头、表中、表尾三种表头、表

15、中、表尾三种情况的操作语句一致。情况的操作语句一致。 数据结构（C+版）2012辽宁科技大学软件学院21算法描述算法描述伪代码伪代码 1. 工作指针工作指针p初始化；累加器初始化；累加器j清零；清零； 2. 查找第查找第i- -1个结点的地址个结点的地址p； 3. 若查找不成功，则插入位置不合理，抛出异常；若查找不成功，则插入位置不合理，抛出异常； 否则，否则， 3.1 生成一个元素值为生成一个元素值为x的新结点的新结点* *s； 3.2 将结点将结点* *s插入到结点插入到结点* *p之后；之后；2.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现插入插入数据结构（C+版）201

16、2辽宁科技大学软件学院22 template void LinkList:Insert( (int i, DataType x) ) p=first ; j=0; while ( (p & j-next; j+; 2.3 线性表的链式存储线性表的链式存储算法描述算法描述C+描述描述单链表的实现单链表的实现插入插入 if (idata=x; s-next=p-next; p-next=s; ，基本语句？时间复杂度？基本语句？时间复杂度？数据结构（C+版）2012辽宁科技大学软件学院23单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList( )算法描述：算法描述：templ

17、ate LinkList:LinkList( ) first=new Node; first-next=null; 2.3 线性表的链式存储线性表的链式存储初始化，生成头结点初始化，生成头结点first数据结构（C+版）2012辽宁科技大学软件学院24单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a , int n)头插法：头插法：将待插入结点插在将待插入结点插在头结点头结点的后面的后面 。算法描述：算法描述：first=new Node; first-next=null; 2.3 线性表的链接存储线性表的链接存储数组数组a3512243342

18、初始化初始化first数据结构（C+版）2012辽宁科技大学软件学院25单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。2.3 线性表的链接存储线性表的链接存储数组数组a3512243342算法描述：算法描述：s=new Node;s-data=a0;s-next=first-next;first-next=s; 插入第一个元素结点插入第一个元素结点first35s数据结构（C+版）2012辽宁科技大学软件学院26单链表的实现单链表的实现构造函数构造函

19、数操作接口：操作接口：LinkList( DataType a , int n)头插法：头插法：将待插入结点插在头结点的后面将待插入结点插在头结点的后面 。2.3 线性表的链接存储线性表的链接存储数组数组a3512243342算法描述：算法描述：s=new Node; s-data=ai;s-next=first-next;first-next=s; 依次插入每一个结点依次插入每一个结点12sfirst35数据结构（C+版）2012辽宁科技大学软件学院27template LinkList: LinkList(DataType a , int n) first=new Node; first-

20、next=null; for (i=0; idata=ai; s-next=first-next; first-next=s; 2.3 线性表的链接存储线性表的链接存储单链表的实现单链表的实现构造函数构造函数算法描述：算法描述：数据结构（C+版）2012辽宁科技大学软件学院28尾插法：尾插法：将待插入结点插在将待插入结点插在终端结点终端结点的后面。的后面。 2.3 线性表的链接存储线性表的链接存储单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：first=new Node; rear=first;数组数组a

21、3512243342初始化初始化firstrear数据结构（C+版）2012辽宁科技大学软件学院29尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储线性表的链接存储单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：s=new Node; s-data=a0;first-next=s;rear=s;数组数组a3512243342插入第一个元素结点插入第一个元素结点firstrear35srear数据结构（C+版）2012辽宁科技大学软件学院30尾插法：尾

22、插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储线性表的链接存储单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：s=new Node; s-data=ai;rear-next=s;rear=s;数组数组a3512243342依次插入每一个结点依次插入每一个结点firstrear35rear12srear数据结构（C+版）2012辽宁科技大学软件学院31尾插法：尾插法：将待插入结点插在终端结点的后面。将待插入结点插在终端结点的后面。 2.3 线性表的链接存储线性

23、表的链接存储单链表的实现单链表的实现构造函数构造函数操作接口：操作接口：LinkList(DataType a , int n)算法描述：算法描述：rear-next=null;数组数组a3512243342最后一个结点插入后最后一个结点插入后firstrear35rear42srear数据结构（C+版）2012辽宁科技大学软件学院32template LinkList: LinkList( (DataType a , int n) ) first=new Node; rear=first; for ( (i=0; idata=ai; rear-next=s; rear=s; rear-nex

24、t=NULL; 2.3 线性表的链接存储线性表的链接存储单链表的实现单链表的实现构造函数构造函数算法描述：算法描述：数据结构（C+版）2012辽宁科技大学软件学院33单链表的实现单链表的实现删除删除操作接口：操作接口： DataType Delete(int i); 2.3 线性表的链式存储线性表的链式存储p如何实现结点如何实现结点ai-1和和ai之间逻辑关系的变化？之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;q数据结构（C+版）2012辽宁科技大学软件学院34单链表的实现单链表

25、的实现删除删除2.3 线性表的链式存储线性表的链式存储算法描述：算法描述：q=p-next; x=q-data;p-next=q-next; delete q;注意分析注意分析边界边界情况情况P在表头、表尾位置上的情况在表头、表尾位置上的情况 pqpq表尾的特殊情况：表尾的特殊情况：被删结点被删结点q q不存在，不删除。不存在，不删除。 p-next=nullfirsta1ana2数据结构（C+版）2012辽宁科技大学软件学院35算法描述算法描述伪代码伪代码 1.工作指针工作指针p初始化；累加器初始化；累加器j清零；清零； 2. 查找第查找第i-1个结点并使指针个结点并使指针p指向该结点；指向

26、该结点； 3. 若若p不存在或不存在或p不存在后继，则抛出位置异常；不存在后继，则抛出位置异常； 否则，否则， 3.1 暂存被删结点及元素值；暂存被删结点及元素值； 3.2 删除，将删除，将*p的后继从链表上摘下；的后继从链表上摘下； 3.3 释放被删结点所占内存空间；释放被删结点所占内存空间； 3.4 返回被删结点的元素值；返回被删结点的元素值； 2.3 线性表的链式存储线性表的链式存储单链表的实现单链表的实现删除删除数据结构（C+版）2012辽宁科技大学软件学院36template DataType LinkList:Delete (int i) p=first ; j=0; while

27、(p & jnext; j+; 2.3 线性表的链式存储线性表的链式存储算法描述算法描述C+描述描述单链表的实现单链表的实现删除删除 if (!p | | !p-next) throw “位置位置”; else q=p-next; x=q-data; p-next=q-next; delete q; return x; 数据结构（C+版）2012辽宁科技大学软件学院37单链表的实现单链表的实现析构函数析构函数析构函数将单链表中所有结点的所占存储空间释放。析构函数将单链表中所有结点的所占存储空间释放。 2.3 线性表的链式存储线性表的链式存储操作接口：操作接口：LinkList( );first

28、a1a2anaipq算法描述：算法描述：q=p; /q指向待释放的结点指向待释放的结点p=p-next;/p指向下一个结点指向下一个结点Delete q; 释放释放q所指的结点空间所指的结点空间p注意：保证链表未处理的部分不断开注意：保证链表未处理的部分不断开 qp数据结构（C+版）2012辽宁科技大学软件学院38单链表的实现单链表的实现析构函数析构函数template LinkList: LinkList( ) p=first; while (p!=null) q=p; p=p-next; delete q; 2.3 线性表的链式存储线性表的链式存储算法描述：算法描述：template Li

29、nkList: LinkList( ) while (first!=null) q=first; first=first-next; delete q; 数据结构（C+版）2012辽宁科技大学软件学院39链表的其它操作链表的其它操作1. 在有序表的基础上插入元素，使序列仍有序在有序表的基础上插入元素，使序列仍有序2.将一个链表逆置将一个链表逆置3.设计算法实现将设计算法实现将2个有序表合并为一个有序表个有序表合并为一个有序表2.3 线性表的链式存储线性表的链式存储数据结构（C+版）2012辽宁科技大学软件学院40启示：算法设计的一般过程启示：算法设计的一般过程算法设计的一般步骤：算法设计的一般

30、步骤：第一步：确定第一步：确定入口入口（已知条件）、（已知条件）、出口出口（结果）；（结果）；第二步：根据一个实例画出第二步：根据一个实例画出示意图示意图；第三步：选定一个核心问题的特例分析，再推出一般；第三步：选定一个核心问题的特例分析，再推出一般；第四步：写出第四步：写出顶层顶层较抽象算法，分析较抽象算法，分析边界边界情况；情况；第五步：第五步：验证验证第四步的算法；第四步的算法；第六步：写出第六步：写出具体具体算法；算法；第七步：第七步：进一步进一步验证，手工运行。验证，手工运行。数据结构（C+版）2012辽宁科技大学软件学院412.3.2 循环链表循环链表循环链表循环链表firsta1

31、ai-1anaip从单链表中某结点从单链表中某结点ai出发如何找到其前驱？出发如何找到其前驱？将单链表的首尾相接，将终端结点的指针域由空指针将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成改为指向头结点，构成单循环链表单循环链表，简称，简称循环链表循环链表。pp数据结构（C+版）2012辽宁科技大学软件学院42循环链表循环链表空表和非空表的处理一致空表和非空表的处理一致附设头结点附设头结点first空循环链表空循环链表firsta1ai-1anai非空循环链表非空循环链表2.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院43循环条件：循环条件：p!=n

32、ull = = p!=firstp-next!=null = = p-next!=first循环链表循环链表循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环2.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院44firsta1ai-1anai循环链表循环链表插入插入xspxspxsp算法描述：算法描述：s=new Node; s-data=x; s-next=p-next; p-next=s;2.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院45 template void LinkList:Insert( (int

33、i, DataType x) ) if(i1) throw “位置小于位置小于1; p=first ; j=0; while ( (p!=first & j-next; j+; if (p= =first ) throw 位置位置; else s=new Node; s-data=x; s-next=p-next; p-next=s; 循环链表循环链表插入插入与单链表的插入操作相比，差别是什么？与单链表的插入操作相比，差别是什么？2.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院46如何查找开始结点和终端结点？如何查找开始结点和终端结点？循环链表循环链表firsta1a

34、i-1anai开始结点：开始结点：first-next 终端结点：终端结点：p-next =first 将单链表扫描一遍，时间为将单链表扫描一遍，时间为O(n)2.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院47reara1ai-1anai开始结点地址：开始结点地址：rear-next-next终端结点地址：终端结点地址：rear循环链表循环链表带尾指针的循环链表带尾指针的循环链表通常情况下，头指针没有什么作用通常情况下，头指针没有什么作用2.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院48reara2ai-1anai开始结点地址：开始结点地

35、址：rear-next终端结点地址：终端结点地址：rear循环链表循环链表改进的带尾指针的循环链表改进的带尾指针的循环链表一个存储结构设计得是否合理，取决于基于该存储一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。结构的运算是否方便，时间性能是否提高。 a12.3.2 循环链表循环链表数据结构（C+版）2012辽宁科技大学软件学院49如何求结点如何求结点p的直接前驱，时间性能？的直接前驱，时间性能？firsta1ai-1anaip为什么可以快速求得结点为什么可以快速求得结点p的后继？的后继？如何快速求得结点如何快速求得结点p的前驱？的前驱？2.3.2 循环链表

36、循环链表数据结构（C+版）2012辽宁科技大学软件学院50双链表：双链表：在在单链表的每个结点中再设置一个指向其前单链表的每个结点中再设置一个指向其前驱结点的指针域驱结点的指针域。双链表双链表结点结构：结点结构：priordatanextdata：数据域，存储数据元素；：数据域，存储数据元素；prior：指针域，存储该结点的前驱结点地址；：指针域，存储该结点的前驱结点地址；next：指针域，存储该结点的后继结点地址。：指针域，存储该结点的后继结点地址。2.3.3 双链表双链表数据结构（C+版）2012辽宁科技大学软件学院51template struct DulNode DataType da

37、ta; DulNode *prior, *next; 双链表双链表启示？启示？时空权衡时空权衡空间换取时间空间换取时间priordatanext结点结构的结点结构的C+实现：实现：2.3.3 双链表双链表数据结构（C+版）2012辽宁科技大学软件学院52双链表的操作双链表的操作插入插入s-prior=p; s-next=p-next;p-next-prior=s;p-next=s; ai-1ai操作接口：操作接口： void Insert(DulNode *p, DataType x); pxs注意指针修改的注意指针修改的相对相对顺序顺序在在S结点完全插入到表中之前，结点完全插入到表中之前，

38、p-next是访问到是访问到ai的唯一途径。的唯一途径。因此因此p-next的值必须最后修改，的值必须最后修改，否则找不到否则找不到ai,导致链表断开。导致链表断开。2.3.3 双链表双链表数据结构（C+版）2012辽宁科技大学软件学院53双链表的操作双链表的操作删除删除( (p-prior) )-next=p-next; ( (p-next) )-prior=p-prior; 操作接口：操作接口： DataType Delete(DulNode *p); ai-1aipai结点结点p的指针是否需要修改？的指针是否需要修改？delete p; 2.3.3 双链表双链表数据结构（C+版）2012

39、辽宁科技大学软件学院54存储分配方式比较存储分配方式比较顺序存储结构用一段地址顺序存储结构用一段地址连续连续的存储单元的存储单元依次依次存储存储 线性表的元素，元素之间的逻辑关系通过线性表的元素，元素之间的逻辑关系通过存储位置存储位置来来实现。实现。链接存储结构用一组链接存储结构用一组任意任意的存储单元存放线性表的的存储单元存放线性表的元素。用元素。用指针指针来反映元素之间的逻辑关系。来反映元素之间的逻辑关系。2.4 顺序表和单链表的比较顺序表和单链表的比较数据结构（C+版）2012辽宁科技大学软件学院552.4 顺序表和单链表的比较顺序表和单链表的比较时间性能比较时间性能比较 时间性能时间性能是指实现基于某种存储结构的基本操作（即是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。算法）的时间复杂度。 按位查找：按位查找：顺序表的时间为顺序表的时间为(1)，是随机存取；，是随机存取；单链表的时间为单链表的时间为(n)，是顺序存取。，是顺序存取。插入和删除：插入和删除：顺序表需移动表长一半的元素，时间为顺序表需移动表长一半的元素，时间为(n)；单链表不需要移动元素，在单链表不需要移动元素，在给