河南科技大学 数据结构.docx

1数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。2线性表：线性表是具有相同属性的数据元素的一个有限序列。3稀疏矩阵：稀疏矩阵是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。4栈：栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。5数据类型：数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种综合描述。6数据结构：数据结构是指数据以及相互之间的联系。7链接存储：在链接存储中，每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息，其存储结点的结构为：dataP1p2.pm其中data表示值域，用来存储一个元素，p1,p2,.,pm(m1)均为指针域，8队列：队列简称队，它也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。9堆：堆分为小根堆和大根堆两种。对于一个小根堆，它是具有以下特性的一棵完全二叉树：（1）若树根结点存在左孩子，则根结点的值（或某个域的值）小于等于左孩子结点的值（或某个域的值）；（2）若树根结点存在右孩子，则根结点的值（或某个域的值）小于等于右孩子结点的值（或某个域的值）。（3）以左右孩子为根的子树又各是一个堆。（4）大根堆的定义与上述类似，只要把小于等于改为大于等于就可以了。简答题一、中缀表达式如何转换为后缀表达式课本89页几道例题二、算法的定义及具有哪些特性算法定义就是解决特定问题的方法。五个特性：1、有穷性：一个算法必须在执行有穷步之后结束。2、确定性：算法中每一步都必须有确切的含义。3、可行性：算法中每一步都必须是可行的，即算法中每一步都能够通过手工或机器可以接受的有限次操作在有限时间内实现。4、输入：一个算法可以有0个1个或多个输入量，在算法被执行前提供给算法。5、输出：一个算法执行结束后至少有一个输出量，它是利用算法对输入量进行运算和处理的结果。三、树的性质1树中的结点数等于所有的结点的度数加1；2度为k的数中第i层上至多有ki-1个结点（i1）；3深度为h的k叉树至多有（kh-1）/(k-1)个结点；4具有n个结点的k叉树的最小深度为logk(n(k-1)+1)（k为底数）四、什么是二叉搜索数：二叉搜索数又称二叉排序树，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树：（1）若它左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；（2）若它的右子树非空，则右子树上所有节点的关键字均大于（若允许具有相同的关键字的结点存在，则大于等于）根结点的关键字；（3）左、右子树本身又各是一棵二叉搜索树五、什么是图、子图、完全图、路径、回路、连通、网1图是一种复杂的非线性数据结构。2设有两个图G=(V,E)和G(V,E)，若V是V的子集，即VV，且E是E的子集，即EE，则称G是G的子图。3若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。4在一个图G中，从顶点v到顶点v的一条路径是一个顶点序列vi1，vi2，vim，其中v=vi1，v=vim，若此图是无向图，则（vij-1，vij）E(G)，（2jm）；若此图是有向图，则E(G)，（2jm）。5若一条路径上的前后两端点相同，则被称为回路。6在有向图G中，若从顶点vi到vj有路径，则称从vi到vj是连通的。7边上带有权的图称作带权图，也常称作网。六、一般从哪几个方面对算法进行评价？正确性，健壮性，可读性，简单性，时间复杂度，空间复杂度。七、给出广义表，画出树：课本118页最上面的广义表，对应的树为图5-1八、二叉树的性质：1二叉树上终端结点数等于双分支结点数加1；2二叉树上第i层上至多有2i-1个结点（i1）；3深度为h的二叉树至多有2h-1（2的h次方减1）个结点；4对完全二叉树中编号为i的结点（1in，n1，n为结点数）有：(1) 若in/2，即2in，则编号为i的结点为分支结点，否则为叶子结点。表达式x表示对x进行向下取整。(2) 若n为奇数，则树中每个分支结点都既有左孩子，又有右孩子；若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。(3) 若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，则右孩子结点的编号为2i+1，即遵循对一般二叉树的编号规则。(4) 除树根结点外，若一个结点的编号为i，则它的双亲结点的编号为n/2,也就是说，当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子，当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。此点也适合于一般二叉树。5具有n个(n0)结点的完全二叉树的深度为log2(n+1)或log2n+1。九、二叉树有几种遍历递归算法？并写出算法。前序遍历算法void Preorder(struct BTreeNode* BT) if(BT!=NULL) printf(%c ,BT-data);Preorder(BT-left);Preorder(BT-right); 中序遍历算法void Inorder (struct BTreeNode* BT) if (BT!=NULL) Inorder(BT-left);printf(%c ,BT-data);Inorder(BT-right);后序遍历递归算法void Postorder(struct BTreeNode* BT) if(BT!=NULL) Postorder(BT-left); Postorder(BT-right); printf(%c ,BT-data); 十、什么是哈夫曼树？写出它的具体算法哈夫曼(Huffman)树又称作最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。算法如下：(1) 根据与n个权值w1,w2,wn对应的n个结点构成具有n棵二叉树的森林F=T1,T2,Tn，其中每棵二叉树Ti(1in)都只有一个权值为wi的根结点，其左、右子树均为空；(2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和；(3) 从F中删除构成新树的那两棵树，同时把新树加入F中；(4) 重复(2)和(3)步，直到F中只含有一棵树为止，此树便是哈夫曼树。十一、什么是栈，栈顶，栈顶元素，栈底，进栈，出栈1栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。2人们把对栈进行运算的一端称为栈顶。3栈顶的第一个元素被称为栈顶元素。4相对地，把另一端称为栈底。5向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素。6从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。普里姆算法void Prim(adjmatrix GA,edgeset CT,int a,int n) int i,j,k,min,t,m,w;struct edgeElem x;for(i=0;in;i+) if(ia) CTi-1.fromvex=a; CTi-1.endvex=i; CTi-1.weight=GAai; for(k=1,kn;k+) min=MaxValue; m=k-1; for(j=k-1;jn-1;j+) if(CTj.weightmin) min=CTj.weight; m=j; x=CTk-1; CTk-1=CTm; CTm=x; j=CTk-1.endvex; for(i=k;in-1;i+) t=CTi.endvex; w=GAjt; if(wlen=HBT-MaxSize) ElemType *p; p=realloc(HBT-heap, 2*HBT-MaxSize*sizeof(ElemType); if(!p) printf(存储空间用完!n); exit(1); HBT-heap=p; HBT-MaxSize=2*HBT-MaxSize; HBT-heapHBT-len=x; HBT-len+;i=HBT-len-1; while(i!=0) int j=(i-1)/2; if(x=HBT-heapj) break; HBT-heapi=HBT-heapj; i=j; HBT-heapi=x; 克鲁斯卡尔算法void Kruskal(edgeset GE,edgeset C,int n)int i,j,k,d;int m1,m2;adjmatrix s;for(i=1;in;i+)for(j=0;jn;j+)if(i=j) sij=1;else sij=0;k=1;d=0;while(kn)for(i=0;in;i+) if(siGEd.fromvex=1) m1=i;if(siGEd.endvex=1) m2=i);if(m1!=m2) Ck-1=GEd;k+;for(j=0;jn,j+) sm1j=sm1j | sm2j;sm2j=0;d+P187图的遍历深度优先搜索遍历void dfs1(adjmatrix GA, int i, int n)/*从初始点vi出发深度优先搜索由邻接矩阵GA表示图*/ int j;printf(%d ,i); visitedi=1; for(j=0; jn; j+) if(GAij!=0 & GAij!=MaxValue & !visitedj) dfs1(GA,j,n); (以邻接矩阵)广度优先搜索遍历的过程p189void bfs1(adjmatrix GA, int i, int n) struct QueueSq Q; InitQueue1(&Q);printf(%d ,i); visitedi=1; EnQueue(&Q,i); while(!EmptyQueue(&Q) int j;int k=OutQueue(&Q); for(j=0; jadjvex; if (!vistedj) printf(%d ,j); visitedj=1; EnQueue(&Q,j); p=p-next; 162初始化堆void InitHeap(struct HeapSq* HBT,int MS) if(MSheap=malloc(MS*sizeof(ElemType); if(!HBT-heap) print(“内存空间用完，退出n”); exit(1); HBT-MaxSize=MS; HBT-len=0; 157 从二叉搜索树中删除等于给定值x的结点，若删除成功则返回1，否则返回0。 int Delete(struct BTreeNode* BST, ElemType x);152（二叉树的应用）二叉搜索树（查找） ElemType* Find(struct BTreeNode* BST, ElemType x) /*从二叉搜索树中查找等于给定值x的元素*/if(BST=NULL) return NULL; else if(x=BST-data) return &(BST-data); else if(xdata) return Find(BST-left,x); else return Find(BST-right,x); 向二叉树中插入元素 void Insert(struct BTreeNode* BST, ElemType x) /*向二叉搜索树中插入一个元素x*/ if(*BST=NULL) struct BTreeNode* p=malloc(sizeof(struct BTreeNode); p-data=x; p-left=p-right=NULL; *BST=p; else if(xdata) Insert(&(*BST)-left),x);else Insert(&(*BST)-right),x); 142从树中查找结点值ElemType* FindGTree(struct GTreeNode* GT, ElemType x) if(GT=NULL) return NULL; else ElemType* p;int i;if(GT-data=x) return &(GT-data);for(i=0; iti,x) return p; return NULL; 140树的运算 出树的先根遍历算法： void PreRoot(struct GTreeNode* GT) int i;if(GT!=NULL) printf(%c ,GT-data); for(i=0; iti); 二叉树后根遍历void PostRoot(struct GTreeNode* GT) int i;if(GT!=NULL) for(i=0; iti); printf(%c ,GT-data); 二叉树树的按层遍历void LayerOrder(struct GTreeNode* GT) struct GTreeNode* p;int i;struct GTreeNode* qMQ;int front=0, rear=0;if(GT!=NULL) rear=(rear+1)% MQ; qrear=GT; while (front!=rear) front=(front+1)% MQ; p=qfront; printf(%c ,p-data);for(i=0; iti!=NULL) rear=(rear+1)% MQ; qrear=p-ti; 139建立树130建立二叉树132求二叉树深度的递归算法如下： int BTreeDepth(struct BTreeNode* BT) if(BT=NULL) return 0; else int dep1=BTreeDepth(BT-left); int dep2=BTreeDepth(BT-right); if(dep1dep2) return dep1+1; else return dep2+1; 132 二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回空值ElemType* FindBTree(struct BTreeNode* BT, ElemType x)if(BT=NULL) return NULL; else if(BT-data=x) return &(BT-data); else ElemType* p; if(p=FindBTree(BT-left,x) return p; if(p=FindBTree(BT-right,x) return p; return NULL; 129二叉树按层遍历算法（非递归） void Levelorder(struct BTreeNode* BT) struct BTreeNode* p; struct BTreeNode* qQueueMaxSize; int front=0, rear=0; if(BT!=NULL) rear=(rear+1)% QueueMaxSize; qrear=BT; while (front!=rear) front=(front+1)% QueueMaxSize; p=qfront; printf(%c ,p-data);if(p-left!=NULL) rear=(rear+1)% QueueMaxSize; qrear=p-left; if(p-right!=NULL) rear=(rear+1)% QueueMaxSize; qrear=p-right; 队列106初始化队列一用于存储队列的固定大小的动态存储空间，假定动态存储空间的大小为10。 void InitQueue(struct QueueSq* Q) /*置队列空间初始最大长度为10*/Q-MaxSize=10; Q-queue=malloc(10*sizeof(ElemType); Q-front=Q-rear=0; 第二种情况是分配由参数指定大小的动态存储空间。实用中使用任一种初始化算法均可。 void InitQueue(struct QueueSq* Q, int ms) if(msMaxSize=ms; Q-queue=malloc(ms*sizeof(ElemType); if(!Q-queue) printf(内存空间用完!n); exit(1); Q-front=Q-rear=0; 2向队列插入元素 void EnQueue(struct QueueSq* Q, ElemType x) if(Q-rear+1)%Q-MaxSize=Q-front) againMalloc(Q); Q-rear=(Q-rear+1)%Q-MaxSize;Q-queueQ-rear=x; againMalloc()算法的具体定义如下： void againMalloc(struct QueueSq* Q)ElemType *p;p=realloc(Q-queue, 2*Q-MaxSize*sizeof(ElemType); if(!p) printf(存储空间用完!n); exit(1); Q-queue=p; if(Q-rear!=Q-MaxSize-1) int i;for(i=0; irear; i+) Q-queuei+Q-MaxSize=Q-queuei;Q-rear+=Q-MaxSize; Q-MaxSize=2*Q-MaxSize; 3从队列中删除元素并返回 ElemType OutQueue(struct QueueSq* Q) if(Q-front=Q-rear) printf(队列已空，无法删除!n); exit(1); Q-front=(Q-front+1)%Q-MaxSize; return Q-queueQ-front; 110向链队中插入一个元素 void EnQueue(struct QueueLk* HQ, ElemType x) struct sNode* newp;newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(内存动态空间用完，退出运行!n); exit(1); newp-data=x; newp-next=NULL; if(HQ-rear=NULL) HQ-front=HQ-rear=newp; else HQ-rear=HQ-rear-next=newp; 3从队列中删除一个元素 ElemType OutQueue(struct QueueLk* HQ) struct sNode* p; ElemType temp; if(HQ-front=NULL) printf(队列为空无法删除!n); exit(1); temp=HQ-front-data; p=HQ-front; HQ-front=p-next; if(HQ-front=NULL) HQ-rear=NULL; free(p); return temp; 86把十进制整数转换为二至九之间的任一进制数输出void Transform(long num, int r) struct StackSq a; InitStack(&a); while(num!=0) int k=num % r; Push(&a,k); num/=r; while(!EmptyStack(&a) printf(%d,Pop(&a); printf(n); 从键盘上输入一批整数，然后按照相反的次序打印出来。#include#include typedef int ElemType; struct StackSq ElemType *stack; int top; int MaxSize; ; #include顺序栈操作.c void main() struct StackSq a; int x; InitStack(&a); printf(输入一批整数，直到输入终止标志-1为止!n);scanf(%d,&x); while(x!=-1) Push(&a,x); scanf(%d,&x); while(!EmptyStack(&a) printf(%d ,Pop(&a); printf(n); 假定从键盘上输入为 78 63 45 82 91 34 -1则输出为 34 91 82 45 63 7878初始化栈S为空 首先给出第一种置空的算法。 void InitStack(struct StackSq* S) /*置栈空间初始最大长度为10*/S-MaxSize=10; S-stack=malloc(10*sizeof(ElemType); S-top=-1; 79新元素进栈，即把它插入到栈顶 void Push(struct StackSq* S, ElemType x) if(S-top=S-MaxSize-1) againMalloc(S); S-top+; S-stackS-top=x; 80删除栈顶元素并返回值 ElemType Pop(struct StackSq* S) if(S-top=-1) printf(栈空，无元素出栈!n); exit(1); S-top-; return S-stackS-top+1; 读取栈顶元素ElemType Peek(struct sNode* HS) if(*HS=NULL) printf（栈空，无栈顶结点!n）;exit(1);return （*HS）-data;82向链栈中插入一个元素 void Push(struct sNode* HS, ElemType x) struct sNode *newp;newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(内存动态空间用完，退出运行!n); exit(1); newp-data=x; newp-next=*HS; *HS=newp; 83从链栈中删除一个元素并返回它 ElemType Pop(struct sNode* HS) struct sNode* p; ElemType temp;if(*HS=NULL) printf(栈空无法删除!n); exit(1); p=*HS; *HS=p-next;temp=p-data; free(p); return temp; .清除链栈为空 void ClearStack(struct sNode* HS) struct sNode *cp， *np; cp=*HS; while(cp!=NULL) np=cp-next; free（cp）; cp=np; *HS=NULL; 69广义表长度的递归算法如下： int LenthGList(struct GNode* GL) if(GL!=NULL) return 1+LenthGList(GL-next); else return 0; 70求一个广义表深度的算法： int DepthGList(struct GNode* GL) int max=0; while(GL!=NULL) if(GL-tag=1) int dep=DepthGList(GL-sublist); if(depmax) max=dep; GL=GL-next; return max+1; 稀疏矩阵初始化运算 稀疏矩阵的存储类型不同，其初始化过程也不同，对于SMatrix类型的对象，初始化过程为： void InitMatrix1(struct SMatrix* M) M-m=0; M-n=0; M-t=0; 对于LMatrix类型的对象，其初始化如下： void InitMatrix2(struct LMatrix* M) int i;M-m=0; M-n=0; M-t=0; for(i=1; ilmi=NULL; 对于CLMatrix类型的对象，初始化过程为： void InitMatrix3(struct CLMatrix* M) int i;M-m=0; M-n=0; M-t=0; for(i=1; irmi=NULL; for(i=1; icmi=NULL;稀疏矩阵的建立void InputMatrix1(struct SMatrix* M, int m, int n)int k=0; int row, col;ElemType val; M-m=m; M-n=n; printf(输入每个三元组:n);scanf(%d %d %d,&row,&col,&val); while(row!=0) k+; M-smk.row=row; M-smk.col=col; M-smk.val=val; scanf(%d %d %d,&row,&col,&val); M-t=k; 稀疏矩阵的输出2.清楚线性表L中的所有元素，即释放单链表中的所有结点，使之成为一个空表 void ClearList(struct sNode* HL) struct sNode *cp,*np; cp=*HL while(cp!=NULL) np=cp-next; Free(cp); Cp=np; *HL=NULL; 3.返回线性表L的长度，即单链表的长度 int SizeList(struct sNode* HL) int i=0; While(HL!=NUll) i+; HL=HL-next; return i; 5. 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 ElemType GetElem(struct sNode* HL, int pos) int i=0; if(posnext; if(HL!=NULL) return HL-data; else printf(pos值非法，退出运行!n); exit(1); 6.遍历一个单链表void TraverseList（struct sNode* HL） while(HL!=NULL) printf(“%5d”,HL-data); HL=HL-next; printf(“n”); 7.从单链表中查找给定值x的第一个元素，查找返回地址，否则返回NULL ElemType* FindList(struct sNode* HL,ElemType x) while (HL!=NULL) if(HL-data=x) return &HL-data; slse HL=HL-next; return NULL; 8.把单链表第pos个结点的值修改为x的值，修改成功返回1，否则返回0 int UpdatePosList(struct sNode* HL,int pos,ElemType x) int i=0; struct sNode* p=HL;while(p!=NULL) i+; if(pos=i) break; else p=p-next; if(pos=i) p-data=x;return 1; else return 0; 10.向单链表的末尾添加一个元素void InsertLastList(struct sNode* HL, ElemTypex)stuuct sNode *newp；newp=malloc(sizeof(struct sNode);if(newp=NULL) print(“内存用完，退出运行n”); exit(1);newp-data=x;newp-next=NULL;if(*HL=NULL) *HL=newp;else stru