中原工学院数据结构复习重点,考点

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。(掌握单链表的增删改查算法)用C语言描述的单链表结点如下：TypedefcharElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;•b•c•d•ai=0i=1i=2i=3head头结点•a•d•c•b•∧•b采用尾插法建立单链表的过程4.插入元素操作分析：在线性表中“插入”一个元素时，使元素之间的关系ai-1,ai改变为ai-1,e和e,ai。由此，算法的基本思想就是，首先找到第i-1个结点，然后修改相应指针。①②5.删除元素操作分析：和插入类似，由于删除元素ai改变了元素之间的逻辑关系，使ai＋1不再是ai的后继，而是ai－1的后继：首先找到第i-1个结点，然后修改相应指针。例、在含有尾指针的循环链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。（循环链表）LinkListconnect(LinkListra，linklistrb){//ra、rb为两个表的尾指针LinkListp=ra-next;ra-next=(rb-next)-nextdeleterb-next;rb-next=p;returnrb;}通常称top为栈顶指针,base为栈底指针。顺序栈的类型定义如下：typedefcharSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;voidconversion(){InitStack(s);cinn;while(n){push(S,n%2);n=n/2;}while(!StackEmpty(S)){Pop(s,e);coute;}}使用堆栈实现十进制与二进制的转换3.4.2链队列1.链队列的定义队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。链队列的类型LinkQueue定义为如下：structQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;(3)入队StutasEnQueue(LinkQueue&Q,QElemTypee){//在当前队列的尾元素之后，插入元素e为新的队列尾元素p=newQNode;if(!p)exit(OVERFLOW);//存储分配失败p-data=e;p-next=NULL;Q.rear-next=p;//修改尾结点的指针Q.rear=p;//移动队尾指针returnOK;}(4)出队StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除当前队列Q中的头元素，用e返回其值，if(Q.front==Q.rear)//链队列中只有一个头结点returnERROR;p=Q.front-next;e=p-data;//返回被删元素Q.front-next=p-next;//修改头结点指针if(Q.rear==p)Q.rear=Q.front;deletep;//释放被删结点returnOK;}循环队列的类型定义。#defineMAXQSIZE100typedefcharQElemType;typedefStruct{QElemType*base;intfront;intrear;}SqQueue;如何判断队列“空”还是“满”。解决此问题的方法至少有三种：设标志位(上次的更新动作)：0-创建/删除，1-插入引入队列长度少用一个元素空间＊约定：当Q.front==(Q.rear+1)%MAXQSIZE时队满练习题1、设一个栈的入栈序列是ABCD，则借助一个栈所得的出栈序列不可能是（）。A.ABCDB.DCBAC.ACDBD.DABC2、设top为链栈(无头结点)的栈顶指针，则空栈的条件是（）。A.n==0B.top-next==0C.top==NULLD.top-next==NULL3、设栈的输入序列是1，2，...，n，若输出序列的第一个元素是n，则第i个输出元素是（）。A.n-i+1B.iC.n-iD.前面都不正确4、队列的工作方式是（）。A.可在队尾删除B.可在队头插入C.先进先出D.先进后出5、循环队列Q为空的条件是（）。A.MAXQSIZE==0B.Q.front==Q.rearC.Q.front==Q.rear-1D.Q.front==(Q.rear+1)%MAXQSIZE6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再插入两个元素后，rear和front的值分别为（）。A.1和5B.2和4C.4和2D.5和17、指出下列程序段的功能是什么？(1)voiddemo1(SqStacks){inti;intarr[64];intn=0;while(!StackEmpty(s))arr[n++]=pop(s);for(i=0;in;i++)push(s,arr[i]);}(2)voiddemo2(SqStacks,intm){SqStackt;inti;initstack(t);while(!StackEmpty(s))if((i=pop(s))!=m)push(t,i);while(!StackEmpty(t)){i=pop(t);push(s,i);}}ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先树的基本概念;二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，这是二叉树与树的最主要的差别。二叉树的5种基本形态：(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的5种形式例：若一个完全二叉树有1450个结点，则度为1的结点个数为，度为2的结点个数为，叶子结点的个数为，有个结点有左孩子，有个结点有右孩子；该树的高度为。(性质3、性质4以及完全二叉树的特征)答案：172472572572411练习2.二叉链表存储二叉树经常用二叉链表法A^BC^D^E^F^^G^^H^lchilddatarchild按先序遍历,其先序序列为：-+a*b-cd/ef按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-－＋*a/b-dcfe例1．统计二叉树中叶子结点的个数.voidCountLeaf(BiTreeT,int&count){//先序遍历二叉树，以count返回二叉树中叶子结点的数目if(T){if((!T-Lchild)&&(!T-Rchild))count++;//对叶子结点计数CountLeaf(T-Lchild,count);CountLeaf(T-Rchild,count);}例：已知先序序列{ABHFDECKG}和中序序列{HBDFAEKCG},构造二叉树过程如下：HBDFEKCGAEKCGABHDFKCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG6.4.1树的存储结构1.双亲表示：以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。6.4树与森林ABCDEFGdataparentABCDEFG-100011301234562.孩子表示法：(1)多重链表法（两种）(2)孩子链表法将每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，n个结点有n个孩子链表，n个头指针组成线性表。datachild1childd......d为树的度同构degreechild1childd......d为结点的度不同构dataABCDEFGABC∧DE∧F∧G∧1045631223∧45∧6∧孩子链表法示例结点结构datanextSiblingABCDEFGBCDGFEA3.孩子兄弟表示法除信息域外，再增加两个分别指向该结点的第一个孩子和下一个兄弟结点的指针firstChild1.树二叉树方法：树中所有相邻兄弟间加一连线；对树中的每个结点，只保留其与第一个孩子间的连线，删去它与其他孩子间连线；以树根为轴心，将整棵树顺时针旋转45度，使之结构层次分明。6.4.2森林与二叉树的转换树的遍历示例先根遍历：ABEHIJCDFGK后根遍历：HIJEBCFKGDAAFHBCDGIJEK森林的遍历示例先序遍历森林：ABCDEFGHIKJ中序遍历森林：BCEDAGFKIJH已知a,b,c,d,e,f,g,h出现的频率分别为：0.05,0.29,0.07,08,0.14,0.23,0.03,0.11,构造赫夫曼树并编码。并计算WPL练习例w={5,29,7,8,14,23,3,11}514297823311142978231135887151429233581111358191429238715113581929231487152929148715291135819234211358192342291487152958113581923422914871529581007.2图的存储结构•（1）邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵，其它0E(G)v,v或)v,(v若1,],[jijijiA例：G12413例：15324G2001100010111010101010101000011000000001100618360240120078400530750例1452375318642带权的无向图的邻接矩阵例:G1bdac例:aecbdG21234acdbdatafirstarc3241^^^^adjvexnextarc1234acdbdatafirstarc4212^^^adjvexnextarc5e435^15323^1234acdbvexdatafirstarc41^1^^3^adjvexnext邻接表逆邻接表•深度优先搜索过程67ACDEGBFIHACDEGBFIH1234589123456789前进回退深度优先生成树•广度优先搜索过程ACDEGBFIHACDEGBFH123456789123456789广度优先生成树I构造最小生成树方法•方法一：普里姆(Prim)算法•——加顶点法，时间复杂度O(n2)•从某顶点开始，找其相邻边中权值最小的边所连另一个顶点，再找与这两个顶点相邻边中权值最小的边所连第三个顶点，重复操作，扩展到所有顶点。252510504613228102514242216185046132504613210原图(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212iclosedge123456UV-Ukadjvexlowcost01,2,3,4,5,6adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcost50280100,51,2,3,4,602852540,5,41,2,