第2章线性表c2

《第2章线性表c2》由会员分享，可在线阅读，更多相关《第2章线性表c2（60页珍藏版）》请在文档大全上搜索。

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的数据元素；的数据元