[理学]第四章 线性表.ppt

第四章 线性表、堆栈和队列,Chapter 4 线性表、堆栈和队列 4.1 线性表的定义和基本操作 4.2 线性表的存储结构 4.3 堆栈和队列,4.1 线性表的定义和操作 4.1.1 线性表的定义 例1 英文字母表 （ A,B,C,Z ) 整数序列 （ 1,78,9,12,10) 例2 某班学生健康情况登记表。 学号 姓名 性别 年龄 健康情况 01 张军 男 18 一般 02 陈红 女 17 良好 03 陈军 男 19 良好 ,线性表定义：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。用（a0，a1，an-1）来表示一个线性表。当n0时，a0称为表的始结点，an-1称为表的终结点，当n=0时，线性表中有零个结点，称为空表。 线性表的逻辑结构：线性结构,线性表的操作 （1）随机存取：存取下标为k的结点 （2）插入：在下标为k的结点前（或后） 插入一个新结点x （3）删除：删除下标为k的结点。 （4）查找：寻觅具有特定域值的结点。 （5）归并、分拆、复制、计数、排序。,Chapter 4 线性表、堆栈和队列 4.1 线性表的定义和基本操作 4.2 线性表的存储结构 4.2.1 顺序存储结构 4.2.2 链接存储结构单链表 4.2.3 循环链表 4.2.4 双向循环链表 4.3 堆栈和队列,4.2 线性表的存储结构,4.2.1 顺序存储结构 顺序存储：用一组连续的存储空间依次存储线性表的元素。 特点：其逻辑顺序与物理顺序相同。 实现顺序存储的最有效方法是使用一维数组 。例 ：线性表（a0，a1 ，a2 , a3)。 可以使用一个数组an来存放此线性表。,图4.1是包含4个结点的线性表A4在内存中的表示，其中每个结点占2个连续的字节，第一个结点A0的首地址为302,Loc(ak)= Loc (a0) + k*c,特点：其逻辑顺序与物理顺序相同。 顺序存储，随机存取,线性表上实现的基本运算 1、插入 例 在线性表（12,13,21,24,28,30,42,77） 中下标为3的结点后，插入元素 25。 问题：此时，线性表的逻辑结构 发生什么变化？ 位置关系发生变化 长度增1,在下标为k的结点后插入一个新结点 /ADL描述 算法 Insert(A,k,x) Insert1k是否合法 IF (kn) THEN PRINT(“overflow”) ELSE ( FOR i= n TO k+1 STEP -1 DO Ai+1 Ai. Ai x. n n+1.). ,时间复杂性分析 插入操作的基本运算是： 元素移动 Dn中有多少种可能的输入呢？ n+1种（n+1个位置可以发生插入） 设每种输入发生的频率相等：1/（n+1） 则期望复杂性为： E(n)=(n+(n-1) + +1+0) /(n+1) =n/2,2、删除 例 在线性表（12,13,21,24,28,30,42,77） 中删除下标为3的元素 。,问题：此时，线性表的逻辑结构 发生什么变化？ 位置关系发生变化 长度减1,删除下标为k的结点 /ADL描述 算法 Delete(A,k) Delete1检查k是否合法 IF (kn) THEN PRINT(“error”) ELSE ( FOR i=k+1 TO n DO Ai-1 Ai. n n-1.) ,时间复杂性分析 删除操作的基本运算是： 元素移动 Dn中有多少种可能的输入呢？ n种（n个位置可以发生删除） 设每种输入发生的频率相等：1/n 则期望复杂性为： E(n)=(n-1) /n +1/ n +0/ n =（n-1）/2, 结论： 优点：线性表的顺序存储结构简单、易于实现，数据的存取操作采用随机存取，可以随机访问表中任一元素。 缺点：线性表的容量不容易扩充，不利于数据的合并与分离；插入、删除操作需要移动大量元素。 问题：由于线性表中元素的数目可以改变，定义数组时要做如何的考虑呢？ 定义足够大的数组,4.2.2 链接存储结构 单链表 1、单链表的定义 链式存储：用一组任意存储单元存储线性 表的数据元素。,单链表的结点结构： 链表的第一个结点被称为头结点，指向头结点 的指针被称为头指针。链表的最后一个结点被 称为尾结点。 单链表的定义：每个结点只含有一个指针域的 链表叫单链表。,单链表的存储映像, 特点：逻辑顺序与物理顺序可以相同也可 以不同。,优点： 插入、删除操作方便。 数据的合并与分离容易。 结点可以不连续存储 线性表可扩充,例 将线性表（a3，a4，a5 ),以链表的形式存储 在内存中。,002,500, 单链表的特性： 在链表中，利用指针域表示线性表的逻辑结 构。 链表有头节点、尾节点、头指针。,2.单链表插入、删除操作举例 插入：,插入操作演示,2. 单链表插入、删除操作举例 删除： 删除操作演示,链表结点类Node的ADT描述： ADT Node is Data data 用来保存结点信息的域 next 用来存放后继结点地址信息的域，即存放指 向后继结点的指针 Operations Constructor Initial value: 给出当前结点的data域值和next域值 Process: 对data域和next域进行初始化 NextNode: Input: 无 Precondition: 无 Process: 取next域值 Output: 返回next域值 Postcondition: 无,InsertAfter Input: 指向被插入结点的指针 Precondition: 无 Process: 在当前结点之后插入结点。 1将当前结点的next域值赋给新插入结点的next域 2将当前结点的next域值更新为新插入结点的地址 Output: 无 Postcondition: 当前结点的next域存放新插入结点的地址 DeleteAfter Input: 无 Precondition: 无 Process: 删除当前结点的后继结点。 将当前结点的后继结点的next域值赋给当前结点的next域 Output: 指向被删除结点的指针 Postcondition: 当前结点的next域值被更新 End ADT Node,3. 单链表基本操作算法 (1) Node类声明： template class Node private: Node * next; public: T data;,/ 构造函数 Node ( const T,(2) Node类的实现 构造函数 template Node : Node(const T& item , Node * ptrnext）： data(item),next(ptrnext) , 返回当前结点的 next 域的值 C+： template Node * Node : nextNode(void) const return next ; ADL: 算法NextNode(this.p) NextNode1取当前结点的下一个结点 p next(this). , 在当前结点之后插入结点 p /ADL描述 算法InsertAfter（this ，p ） IA1 将当前结点的next域值赋给P的next域 next（p） next（this）. IA2 将P赋给当前结点的next域 next（this） p . , 删除当前结点的后继结点 /ADL描述 算法 DeleteAfter（this . tempptr） DA1 this的next域值 = NULL？ IF next（this）= NULL THEN tempptr NULL ELSE（tempptr next（this）. next（this） next（tempptr）. ,tempptr,(3) 构造链表 /ADL描述 创建一个data域值为 item,next 域值为 nextptr的结点。 算法GetNode（item ，nextptr . newNode） GN1 为新结点申请空间 newNode AVAIL . GN2 为结点诸域赋值 data（newNode） item. next（newNode） nextptr. ,item,NewNode,nextptr, 在头指针为 head 的链表中，插入一个data 域为 item 的新结点作为该链表的表头结点。 算法InsertFront（head ， item） IF1 调用函数GetNode GetNode（item，head. newNode）. IF2 head指向新结点 head newNode. 表头插入结点演示,(4)遍历链表 遍历链表演示 算法 PrintList（head） /输出头指针为head的链表,每输出5个元素换行 PL 1 取表头，计数器初始化 currptr head . count 0 .,currptr,PL 2 遍历并输出链表结点的data值 WHILE（currptr NULL） DO （ PRINT（ data（currptr）. count count + 1. IF（MOD（count，5）= 0 ） THEN PRINT . currptr next（currptr）. ）,currptr,currptr,currptr,(5)表尾插入结点 表尾插入 结点演示 算法 InsertRear（ head ，item ） / 在头指针为head的链表尾部插入data域值 / 为item的结点； IR1 取头指针 currptr head .,currptr,IR2 currptr = NULL？ IF currptr = NULL THEN InsertFront（head ，item）,head=NULL currptr=NULL,item,head,NULL,IR2 currptr = NULL？ IF currptr = NULL THEN InsertFront（head ，item） ELSE （ WHILE（next（currptr） NULL） DO currptr next（currptr）. GetNote（item，NULL . newNode）. InsertAfter（currptr ，newNode）. ）,currptr,定义一种链表类，将链表的基本操作视为链表类的成员函数，即将其封装在类中。 6.链表类LinkedList 在链表类的定义中，有一个当前指针，称当前指针所指结点为当前结点，用Node（currptr）记。,类 LinkedList 的数据成员： 头指针：front 尾指针：rear 当前指针：currptr 当前结点的前驱结点指针：prevptr 链表中结点个数：size 当前结点在链表中的位置：position,/ 令当前指针指向表头 void Reset （ int pos = 0 ） ; / 令当前指针指向原当前结点的后继结点 void Next （ void ） ; / 判断当前指针是否指向表尾结点 int EndOfList （ void ） const ; / 插入一个data域值为item的结点 void InsertFront（const T,例4.1 按表L1在前，表L2在后的次序，实现两者的连接。 template 链表连接演示 void JointLists （ LinkedList ,while（ ! L2.EndOfList（ ） ） L1.InsertRear（ L2.Data（ ） ） ; L2.Next（ ） ; ,缺点： （1） 单链表虽然克服了顺序存储的缺点，但却不能进行随机访问，数据存取只能采用顺序存取方式。 （2）内存空间占用较多。 问题： 从单链表中某一个结点出发，能访问到它前面的结点吗？ 不能，只能访问到它后面的结点。 对单链表来说，只有从头结点开始才能扫描表中全部结点 . 作业68页4-1,4.2.3 循环链表 1. 循环链表的定义和结构 循环链表的定义：在单链表中，使其表尾结点的指针指向表头结点，这样的链表叫循环链表。 循环链表演示,单链表表头结点：第一个节点 循环链表表头结点：哨位节点 注意： 判断表尾的条件： 单链表： p next = = NULL 循环链表：p next = = header,header,判断空表的的条件: 单链表：head=NULL 循环链表：header next header,header,2. 循环链表结点类 CNode的定义 声明 template class CNode, private： CNode * next; public: T data; CNode (void); / 生成哨位结点 CNode (const Ts,s.InsertAfter(),实现 / 删除当前结点的后继结点 ADL描述： 算法DeleteAfter（this. tempptr） DA1 链表为空？ IF next（this）= this THEN tempptr NULL DeleteAfter函数的演示,ELSE ( IF next(this)header THEN (tempptr next(header). next(header) next(tempptr).) ELSE (tempptr next（this）. next(this) next(tempptr). ) ) ,4.2.4 双向循环链表 1. 问题的提出 在循环链表中访问当前结点的前趋结点 tempptr next(p). WHILE next(tempptr)p DO tempptr next(tempptr).,p,2 双向循环链表的结构 结点结构： 链表的结构：,header left =header right =header p right left = p left right = p,双向循环链表判空的条件：,header,3 循环双链表结点类DNode定义 声明 template class DNode private： DNode * left; DNode * right;,public: T data; DNode (void);/生成哨位节点 DNode (const T,实现 构造函数 tamplate Node : DNode(const T& item）： data(item),left(this),right(this) ,item,在当前结点(this)之后插入结点 p left（right（this） P . right（P） right（this）. left（P） this. right（this） P,在当前结点(this)之后插入结点 p 算法InsertRight（this ，P） / 在当前结点Node（this）的右边插入结点Node（P） IR1 令当前结点的右结点的左指针指向Node（P） left（right（this） P . IR2 令Node（P）的右指针指向当前结点的右结点 right（P） right（this）. IR3 令Node（P）的左指针指向当前结点 left（P） this. IR4 令当前结点的右指针指向Node（P） right（this） P 右插入演示,在当前结点(this)之前插入结点 p left（P） left（this） right（left（this） P. right（P） this . left（this）P .,在当前结点(this)之前插入结点 p 算法InsertLeft（this ，P） / InsertLeft用IL简记 IL1 令Node（P）的左指针指向当前结点的左结点 left（P） left（this）. IL2 令当前结点之左结点的右指针指向Node（P） right（left（this） P. IL3 令Node（P