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

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章,线性表、堆栈和队列,第四章 线性表、堆栈和队列,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,神经衰弱,线性表定义：,一个线性表是由零个或多个具有,相同类型,的结点组成的,有序集合,。,用（,a,0,，,a,1,，,，,a,n-1,）,来表示一个线性表。当,n0,时，,a,0,称为表的,始结点,，,a,n-1,称为表的,终结点,，当,n=0,时，线性表中有零个结点，称为,空表,。,线性表的逻辑结构：,线性结构,线性表记为,(a,0,a,1,a,n-1,)n 0,(),空表,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,顺序存储结构,顺序存储：,用一组,连续,的存储空间,依次,存储线性表的元素。,实现顺序存储的最有效方法是使用一维数组。例如：线性表（,a,0,，,a,1,，,a,n-1,),。,可以使用一个数组,an,来存放此线性表。,包含,4,个结点的线性表,A4,在内存中的表示，其中每个结点占,2,个连续的字节，第一个结点,A0,的首地址为,302,图,4.1,线性表的顺序存储,线性表,A2,308,306,304,302,A0,A1,A3,例,：线性表（,a,0,，,a,1,，,a,n-1,),。,可以使用一个数组,an,来存放此线性表。,Loc(ak)=Loc(a0)+k*c,a,0,a,1,a,n-1,a,k,b+c,b+k*c,b,b+(n-1)*c,0,1,n-1,k,空闲区,特点：,其逻辑顺序与物理顺序,相同,。,顺序存储，随机存取,顺序存储的线性表的基本运算,1,、,插入,例,在顺序表（,12,13,21,24,28,30,42,77,）,中，插入元素,25,。,问题：此时，线性表的逻辑结构,发生什么变化？,位置关系发生变化,长度增,1,序号 元素,3,4,1,5,2,7,8,6,12,13,21,24,28,30,42,77,插入,25,序号 元素,3,4,1,5,2,7,8,6,12,13,25,21,24,28,30,42,77,9,在下标为,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.).,时间复杂性分析：,插入操作的基本运算是：,元素移动,D,n,中有多少种可能的输入呢？,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,）,中，删除元素,24,。,问题：此时，线性表的逻辑结构,发生什么变化？,位置关系发生变化,长度减,1,序号 元素,3,4,1,5,2,7,8,6,12,13,21,24,28,30,42,77,删除,24,序号 元素,3,4,1,5,2,7,6,12,13,21,28,30,42,77,删除下标为,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.),时间复杂性分析：,删除操作的基本运算是：,元素移动,D,n,中有多少种可能的输入呢？,n,种（,n,个位置可以发生删除）,设每种输入发生的频率相等：,1/n,则期望复杂性为：,E(n)=(n-1)/n+1/n+0/n,=,（,n-1,）,/2,结论,：,线性表的顺序存储结构,优点,：空间利用率高，简单、易于实现，可以,随机访问,表中任一元素，存取速度快。,缺点,：插入和删除结点，要调整一批节点的地址。,问题：,由于线性表中元素的数目可以改变，因此定义数组时要做如何的考虑呢？,定义足够大的数组。,4.2.2,链接存储结构,单链表,1,、单链表的定义,2,、单链表的基本操作,3,、单链表结点类,(Node),4,、单链表的构造,5,、链表类（,LinkedList,）,4.2.2,链接存储结构,单链表,1,、单链表的定义,链式存储：,用一组,任意,存储单元存储线性表的数据元素。,例,将线性表（,a,3,，,a,4,，,a,5,),以链表的形式存,储在内存中。,a,5,500,a,3,100,002,a,4,002,500,单链表的,结点结构,：,单链表的定义：,每个结点只含有,一个链接域,的 链表叫单链表,。,data,next单链表的存储映像,特点：,逻辑顺序与物理顺序可以相同也可 以不同。,链表有,头节点、尾节点、头指针,(head),。,判断表尾的条件：,p,next=NULL,空表的条件：,head=NULL,a,5,a,3,a,4,4.2.2,链接存储结构,单链表,1,、单链表的定义,2,、单链表的基本操作,3,、单链表结点类,(Node),4,、单链表的构造,5,、链表类（,LinkedList,）,在链表中，删除一个结点或插入一个结点，只需改变一个或两个相关结点的指针，不对其它结点产生影响。,插入：,FAT,HAT,p,GAT,s,s next=p next;,p next=s;,删除：,q=p next;,FAT,HAT,p,GAT,q,p next=q next;,4.2.2,链接存储结构,单链表,1,、单链表的定义,2,、单链表的基本操作,3,、单链表结点类,(Node),4,、单链表的构造,5,、链表类（,LinkedList,）,(1),Node,类声明：,template,class Node,private:,Node *next;,public:,T data;,/,构造函数,Node,(const T&item,Node *,ptrnext,=NULL);,/,返回指向当前结点的后继结点的指针,Node *,NextNode,(void,)const;,/,在当前结点之后插入指针,p,所指结点,void,InsertAfter,(Node,*p);,/,删除当前结点的后继结点,Node *,DeleteAfter,(void,);,;,(2),Node,类的实现,构造函数,template,Node:,Node,(const T&item,Node *,ptrnext,）：,data(item),next(ptrnext,),返回当前结点的,next,域的值,template,Node *,Node :,nextNode,(void)const,return next,；,在当前结点之后插入结点,p,/,ADL,描述,算法,InsertAfter,（,thisp,）,IA1,将当前结点的,next,域值赋给,P,的,next,域,next,（,p,）,next,（,this,）,.,IA2,将,P,赋给当前结点的,next,域,next,（,this,）,p.,FAT,HAT,this,GAT,p,在当前结点之后插入结点,p,/C+,描述,template,void Node:,InsertAfter,(Node,*p),p,next=,next,;,next=p;,FAT,HAT,this,GAT,p,删除当前结点的后继结点,/,ADL,描述,算法,DeleteAfter,（,this.,tempptr,）,DA1 this,的,next,域值,=NULL,？,IF next,（,this,）,=NULL THEN,tempptr,NULL,.,ELSE,（,tempptr,next,（,this,）,.,next,（,this,）,next,（,tempptr,）,.,）,FAT,HAT,this,GAT,tempptr,删除当前结点的后继结点,/C+,描述,template,Node*Node :,DeleteAfter,(void,),if(next=NULL),return NULL;,Node *,tempptr,=next;,next=,tempptr,next;,return,tempptr,;,FAT,HAT,this,GAT,tempptr,4.2.2,链接存储结构,单链表,1,、单链表的定义,2,、单链表的基本操作,3,、单链表结点类,(Node),4,、单链表的构造,5,、链表类（,LinkedList,）,在,Node,类基础上,构造单链表,1,）创建新结点,2,）表头插入结点,3,）遍历链表,4,）表尾插入结点,1,）创建一个,data,为,item,next,为,nextptr,的结点,算法,GetNode,（,item,，,nextptr,.,NewNode,）,GN1,为新结点申请空间,NewNode,AVAIL .,GN2,为结点诸域赋值,data,（,NewNode,）,item.next,（,NewNode,）,nextptr,.,item,NewNode,nextptr,#include,#include“,stdlib.h,”,template,Node*,GetNode,(const,T&item,Node*,nextptr,=NULL),Node*,newNode,;,newNode,=new Node(item,nextptr,);,if(,newNode,=NULL),cerr,“Memory allocation failure,！”,=0;i-),head=,GetNode,(ai,head,);,代码段二：,Node*head=NULL;,for(i=n-1;i=0;i-),InsertFront,(head,ai,);,3),遍历链表,遍历：按一定次序访问所有节点，且每个节点恰被访问一次。,算法,PrintList,（,head,）,/,输出头指针为,head,的链表,每输出,5,个元素换行,PL 1,取表头，计数器初始化,currptr,head.count,0,.,a,c,b,head,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,a,c,b,head,遍历链表,/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,取头指针,currptr,head.,a,c,b,head,currptr,IR2,currptr,=NULL,？,IF,currptr,=NULL THEN,InsertFront,（,head,，,item,）,head=NULL,currptr,=NULL,head,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,）,.,）,a,c,b,head,currptr,currptr,newNode,item,NULL,表尾插入结点,/C+,template,void,InsertRear,（,Node*&head,const T&item),Node*,currptr,=head;,if(,currptr,=NULL),InsertFront(head,item,);,else,while,(currptr,NextNode,()!=NULL),currptr,=,currptr,NextNode,(),；,Node*,newNode,;,newNode,=,GetNode(item,);,currptr,InsertAfter(newNode,);,例,4.1,构造一个有,n,个结点的单链表，第,i,个结点的数据为给定数组,an,中,ai-1,的值。,代码段三：,Node*head=NULL,；,for(i=0;i,n;i,+),InsertRear,(head,ai,);,4.2.2,链接存储结构,单链表,1,、单链表的定义,2,、单链表的基本操作,3,、单链表结点类,(Node),4,、单链表的构造,5,、链表类（,LinkedList,）,定义一种链表类,LinkedList,，将链表的基本操作视为链表类的成员函数，并将其封装在类中。,类,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&item,）,;/,表头插入,void,InsertRear,（,const T&item,）,;/,表尾插入,/,返回当前结点的,data,域值,T&Data,（,void,）,;,例,4.2,按表,L1,在前，表,L2,在后的次序，实现两者的连接。,template,void,JointLists,（,LinkedList,&L1,，,LinkedList,&L2,）,/,先令两个表当前指针指向各自表头结点,L1.Reset,（）L2.Reset,（）,;,while,（,!L2.EndOfList,（）,L1.InsertRear,（,L2.Data,（,）,;,L2.Next,（）,;,单链表总结,优点：插入、删除操作方便；共享空间好。,缺点：随机访问困难；,(,从任一结点出发，只能访问其后的结点；,只能从头结点开始，才能扫描表中全部结点,),4.2.3,循环,链表,1,循环链表的定义和结构,定义：,在单链表中，使其最后一个结点的指针又指回到第一个结点，则这样的链表叫循环链表。,单链表表头结点：第一个结点,循环链表表头结点：,哨位结点,(header),header,x,n,x,1,判断表尾的条件：,单链表：p next=NULL,循环链表：,p next=Header,x,n,x,1,p,Header,判断空表的的条件,:,单链表：,Head=NULL,循环链表：,Header,next,Header,header,2.,循环链表结点类,CNode,的定义,声明,template,class,CNode,private,：,CNode,*,next,;,public:,T,data,;,CNode,(void);/,生成哨位结点,CNode,(const T&item):data(item),next(this),void,InsertAfter,(,CNode,*p);,CNode,*,DeleteAfter,(void,);,CNode,*,NextNode,(void,)const;,;,3,、实现,/,删除当前结点的后继结点,ADL,描述,算法,DeleteAfter,（,this.,tempptr,）,DA1,链表为空？,IF,next,（,this,）,=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,),.,),x,n,x,1,header,this,x,1,header,this,4.2.4,双向循环,链表,1,问题的提出,在循环链表中访问结点,p,的前趋结点,tempptr,next(p).,WHILE,next(tempptr)p,DO,tempptr,next(tempptr,).,x,n,x,1,header,2,双向循环链表的结构,结点结构：,链表的结构,left,data,right,。,L,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,void,InsertRight,(,DNode,*p);,void,InsertLeft,(,DNode,*p);,DNode,*,DeleteNode,(void,);,DNode,*,NextNodeLeft,(void)const;,DNode,*,NextNodeRight,(void,)const实现,构造函数,template,Node:,D,Node,(const,T&item,）：,data(item),left(this),right(this),this,item,在当前结点,(this),之后插入结点,P,left,（,right,（,this,）,P.,right,（,P,）,right,（,this,）,.,left,（,P,）,this.,right,（,this,）,P.,P,4,3,2,1,t,his,在当前结点,(this),之后插入结点,P,算法,InsertRight,（,this,，,P,）,IR1,令当前结点的右结点的左指针指向,Node,（,Pleft,（,right,（,this,）,P.,IR2,令,Node,（,P,）,的右指针指向当前结点的右结点,right,（,P,）,right,（,this,）,.,IR3,令,Node,（,P,）,的左指针指向当前结点,left,（,P,）,this.,IR4,令当前结点的右指针指向,Node,（,P,）,right,（,this,）,P,P,2,1,3,4,在当前结点,(this),之前插入结点,P,left,（,P,）,left,（,this,）,right,（,left,（,this,）,P.,right,（,P,）,this.,left,（,this,）,P.,this,在当前结点,(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,令当前结点的左指针指向,Node,（,P,）,left,（,this,）,P,删除当前结点,(this),算法,DeleteNode,（,this,）,DN1,令当前结点的左结点的右指针指向当前结点的右结点,right,（,left,（,this,）,right,（,this,）,.,DN2,令当前结点的右结点的左指针指向当前结点的左结点,left,（,right,（,this,）,left,（,this,）,this,练习题：,1.,对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，那么应选用何种存储结构？试说明理由。若线性表的总数不稳定，且经常进行插入和删除操作，那么应选用何种存储结构？试说明理由。,2.,在链表中查找,data,域值为,x,的结点,算法Find(head,x.currptr,),F1,取头指针,currptr,head.,F2,查找,WHILE,(,currptrNULL,AND,data(currptr,)x),DO,currptr,next(currptr,).,3.,单链表应用,:,一元多项式及其相加,在多项式的链表表示中每个结点增加了一个数据成员,link,，,作为链接指针。,优点：,多项式的项数可以动态地增长，不 存在存储溢出问题。,插入、删除方便，不移动元素。,coef,Link,Exp,多项式链表的相加,AH,=1-10,x,6,+2,x,8,+7,x,14,BH,=-,x,4,+10,x,6,-3,x,10,+8,x,14,+4,x,18,作 业,1,、已知长度为,n,的线性表,A,(a,1,a,2,.a,n,),采用顺序存储结构，请写一算法，将线性表转换为,A,(a,n,.a,2,，,a,1,),，要求转换过程中用尽可能少的存储空间。,2,、编写算法，在头指针为,head,的单链表中，删除域值为,x,的结点。,3,、,68,页,4-1,