计算机组成原理真题解析.ppt

1、第四章 线性表、堆栈和队列,第四章 线性表、堆栈和队列 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称为表的终结点，

2、当n=0时，线性表中有零个结点，称为空表。 线性表的逻辑结构：线性结构,线性表的操作 （1）随机存取：存取下标为k的结点。 （2）插入：在下标为k的结点前（或后） 插入一个新结点 （3）删除：删除下标为k的结点。 （4）查找：寻觅具有特定域值的结点。 （5）归并、分拆、复制、计数、排序。,第四章 线性表、堆栈和队列 4.2 线性表的存储结构 4.2.1 顺序存储结构 4.2.2 链接存储结构单链表 4.2.3 循环链表 4.2.4 双向循环链表,4.2 线性表的存储结构,4.2 线性表的存储结构 4.2.1 顺序存储结构 顺序存储：用一组连续的存储空间依次存储线性表的元素。 实现顺序存储的最有

3、效方法是使用一维数组。例如 ：线性表（a0，a1 ， , an-1)。可以使用一个数组an来存放此线性表。,包含4个结点的线性表A4在内存中的表示，其中每个结点占2个连续的字节，第一个结点A0的首地址为302,例 ：线性表（a0，a1 ， , an-1)。可以使用一个数组an来存放此线性表。,Loc(ak)= Loc (a0) + k*c, 特点：其逻辑顺序与物理顺序相同。 顺序存储，随机存取,顺序存储的线性表的基本运算 1、插入 例 在顺序表（12,13,21,24,28,30,42,77） 中，插入元素 25。 问题：此时，线性表的逻辑结构 发生什么变化？ 位置关系发生变化 长度增1,在下

4、标为k的结点后插入一个新结点/ADL描述 算法 Insert(A,n,k,x) Insert1k是否合法 IF (kn) THEN PRINT(“overflow”) ELSE ( FOR i= n TO k+1 STEP -1 DO Ai+1 Ai. Ak+1 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,4

5、2,77） 中，删除元素 24。,问题：此时，线性表的逻辑结构 发生什么变化？ 位置关系发生变化 长度减1,删除下标为k的结点/ADL描述 算法 Delete(A,n,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, 结论： 线性表的顺

6、序存储结构优点：空间利用率高，简单、易于实现，可以随机访问表中任一元素，存取速度快。 缺点：插入和删除结点，要调整一批节点的地址。 问题：由于线性表中元素的数目可以改变，因此定义数组时要做如何的考虑呢？ 定义足够大的数组。,4.2.2 链接存储结构 单链表 1、单链表的定义 2、单链表的基本操作 3、单链表结点类(Node) 4、单链表的构造 5、链表类（LinkedList）,4.2.2 链接存储结构 单链表 1、单链表的定义 链式存储：用一组任意存储单元存储线性表的数据元素。,例 将线性表（a3，a4，a5 ),以链表的形式存 储在内存中。,002,500, 单链表的结点结构： 单链表的定

7、义：每个结点只含有一个链接域的 链表叫单链表。,单链表的存储映像, 特点：逻辑顺序与物理顺序可以相同也可 以不同。,链表有头节点、尾节点、头指针(head)。 判断表尾的条件：p next = = NULL 空表的条件：head = = NULL,4.2.2 链接存储结构 单链表 1、单链表的定义 2、单链表的基本操作 3、单链表结点类(Node) 4、单链表的构造 5、链表类（LinkedList）,在链表中，删除一个结点或插入一个结点，只需改变一个或两个相关结点的指针，不对其它结点产生影响。, 插入：, 删除：,4.2.2 链接存储结构 单链表 1、单链表的定义 2、单链表的基本操作 3、

8、单链表结点类(Node) 4、单链表的构造 5、链表类（LinkedList）,(1) Node类声明： template class Node private: Node * next; public: T data;,/ 构造函数 Node ( const T,(2) Node类的实现 构造函数 template Node : Node(const T next = p ; , 删除当前结点的后继结点 /ADL描述 算法 DeleteAfter（this . tempptr） DA1 this的next域值 = NULL？ IF next（this）= NULL THEN tempptr

9、NULL . ELSE（tempptr next（this）. next（this） next（tempptr） . ） ,删除当前结点的后继结点/C+描述 template Node * Node :DeleteAfter(void) if( next= = NULL) return NULL; Node * tempptr = next; next = tempptr next; return tempptr; ,4.2.2 链接存储结构 单链表 1、单链表的定义 2、单链表的基本操作 3、单链表结点类(Node) 4、单链表的构造 5、链表类（LinkedList）,在 Node类基础上

10、, 构造单链表 1）创建新结点 2）表头插入结点 3）遍历链表 4）表尾插入结点,1）创建一个data为 item, next为nextptr的结点 算法GetNode（item ，nextptr . NewNode） GN1 为新结点申请空间 NewNode AVAIL . GN2 为结点诸域赋值 data（NewNode） item. next（NewNode） nextptr. ,item,nextptr,# include # include “stdlib.h” template Node * GetNode(const T ,2）表头插入：在头指针为 head 的链表中，插入dat

11、a 域为 item 的新结点，并将其作为头结点。 算法InsertFront（head，item） IF1 调用函数GetNode GetNode（item，head. newNode）. IF2 head指向新结点 head newNode. ,template void InsertFront (Node * ,例4.1 构造一个有n个结点的单链表，第i个结点的数据为给定数组an中ai-1的值。,代码段一： Node *head=NULL； for( i=n-1;i=0;i-) head=GetNode(ai,head); 代码段二： Node *head=NULL; for( i=n-1

12、;i=0;i-) InsertFront(head,ai);,3) 遍历链表 遍历：按一定次序访问所有节点，且每个节点恰被访问一次。 算法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）.

13、 ）,currptr,currptr, 遍历链表/C+ template void printList（Node * head) Node * currptr = head; count = 0; while ( currptr != NULL ) cout ( currptr data） “ ” ； if( (count + ) % 5 = = 0 ) cout endl; currptr = currptr nextNode( )； ,4) 表尾插入结点 在头指针为head的链表尾部插入data域值为item的结点； 算法InsertRear（head ，item） IR1 取头指针 cu

14、rrptr 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（curr

15、ptr ，newNode）. ）,currptr,表尾插入结点/C+ template void InsertRear（Node * ,例4.1 构造一个有n个结点的单链表，第i个结点的数据为给定数组an中ai-1的值。,代码段三： Node *head=NULL； for( i=0;in;i+) InsertRear(head,ai);,4.2.2 链接存储结构 单链表 1、单链表的定义 2、单链表的基本操作 3、单链表结点类(Node) 4、单链表的构造 5、链表类（LinkedList）,定义一种链表类LinkedList ，将链表的基本操作视为链表类的成员函数，并将其封装在类中。,类L

16、inkedList所涉及到的数据成员： 头指针：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.2 按表L1在前，表L2在后的次序，实现两者的连接。 te

17、mplate void JointLists（LinkedList ,while（ ! L2.EndOfList（ ） ） L1.InsertRear（L2.Data（ ）; L2.Next（ ） ; ,单链表总结 优点：插入、删除操作方便；共享空间好。 缺点：随机访问困难； (从任一结点出发，只能访问其后的结点； 只能从头结点开始，才能扫描表中全部结点),4.2.3 循环链表 1 循环链表的定义和结构 定义：在单链表中，使其最后一个结点的指针又指回到第一个结点，则这样的链表叫循环链表。 单链表表头结点：第一个结点 循环链表表头结点：哨位结点(header),header,判断表尾的条件： 单

18、链表：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 T,3、实现 / 删除当前结点的后继结点 ADL描述 算法DeleteAfter（this. tempptr） DA1 链表为空？ IF next（th

19、is）= this THEN tempptr NULL .,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 问题的提出 在循环链表中访问结点p的前趋结点 tempptr next(p). WHILE next(tempptr)p DO tempptr next(tempptr).,2 双向循环链表的结构 结点结构： 链表的结构,Hea

20、der 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,实现 构造函数 template Node : DNode(const T& item）： data(item),left(this),right(this) ,item,在当前结点(

21、this)之后插入结点 P left（right（this） P . right（P） right（this）. left（P） this. right（this） P .,在当前结点(this)之后插入结点 P 算法InsertRight（this ，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）的右指针指向当前结点 right（P） this . IL4 令当前结点的左指