计算机组成原理真题解析.ppt_第1页
计算机组成原理真题解析.ppt_第2页
计算机组成原理真题解析.ppt_第3页
计算机组成原理真题解析.ppt_第4页
计算机组成原理真题解析.ppt_第5页
已阅读5页,还剩80页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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 令当前结点的左指

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论