数据结构与C语言程序设计复习.doc

200120001999 线性 结构next 值（5）线性表的归并（12） 两个栈模拟队列 （12）树型 结构遍历序列 二叉树〈=〉森林 树的基本概念 在二叉树上求结点的 祖先三次树前后序确定树（5） 中序线索树上求后序后继 （20） 判断二叉树相似（8）按层次顺序遍历二叉 树（12） 先序+中序建立二叉 树（12）图状 结构关键路径 （逆）邻接表的生成图的深度优先，广度 优先，最小生成树 （12）集合：查找 排序 外排最佳归并树的虚段 平衡二叉树 二叉排序树 ASL 分析Hash 表平均查找长度公式 （5） B-树的深度定义（5） 各类排序复杂度（8） 排序时间复杂度证明（8) 有序表查找长度证明（8） 置换-选择排序（8） 删除二叉树结点（12）Hash 表的删除 （12） 二叉排序树，平衡二 叉树（7） 内部排序第一趟结果 （9） 堆定义、堆排序与其 它排序的比较（8） 置换-选择排序（4）算法设计 与分析递归方程求解递归方程求解程序题2/10 35’3/12 40’5/10 60’数据结构逻辑结构存储结构操作线 性 结 构树 型 结 构图 状 结 构集合顺 序 存 储 结 构链 式 存 储 结 构虚拟存储结构数组指针所占比例总结所考知识点分布：线性结构：KMP 算法中 next 数组的值 线性表的归并 两个栈模拟队列 栈的输出序列 栈、队列基本操作的时间复杂度树： 二叉树和树的定义 二叉树的前序、中序、后序、层次遍历 哪些遍历序列可唯一决定二叉树 二叉树的结点查找 二叉树的相似判断 求二叉树结点的祖先结点 中序线索二叉树及中序遍历线索二叉树 在中序线索二叉树上求其他序的前驱、后继 Huffman 树的构造 森林（树）与二叉树的转换图： 图的深度优先、广度优先遍历 生成树 最小生成树的 Kruskal 算法 （逆）邻接表的生成 拓扑排序 关键路径 最短路径 Dijkstra 算法、Floyd 算法查找： 有序表 ASL 证明 索引排序表的查找 二叉排序树的插入、删除、ASL 分析 平衡二叉树的插入、删除、 B-树的定义、深度、插入 Hash 表的构造、查找、删除及 ASL 分析排序： 各类排序的时间空间复杂度分析 稳定性分析 基于比较的排序在最坏情况下能达到的最好的时间复杂度证明各类排序的第一趟排序结果 堆的定义 置换选择排序的初始归并段构造 初始归并段平均长度的证明 最佳归并树的虚段算法设计与分析： 递归方程求解例题分析例：假设有两个按元素值非递减有序排列的线性表 A 和 B，均以单链表 作存储结构，请编写算法将表 A 和表 B 归并成一个按元素非递减有 序（允许值相同）排列的线性表 C，并要求利用原表（即表 A 和表 B）的结点空间存放表 C。

void MergeList_L(LinkList pb=Lb->next; Lc=pc=La; //用 La 的头结点作为 Lc 的头结点 while(pa pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放 Lb 的头结点 }//MergeList_L例：已知两个单链表 A 和 B 分别表示两个集合，其元素递增排列，请 编写算法求 C=AB，要求 C 按元素递增排列，并利用原表（即表 A 和表 B）的结点空间存放表 C void Join(Linklist pb=lb->next;lc=la;pc=la; while(papa=pa->next;free(p);} else if(pa->data>pb->data) {p=pb;pb=pb->next;free(p);}else{pc->next=pa;pc=pa;pa=pa->next;p=pb;pb=pb->next;free(p);} } pc->next=nil; while(pa){p=pa;pa=pa->next;free(p);} while(pb){p=pb;pb=pb->next;free(p);} free(lb); }例：带头结点的单链表的逆置用类似栈的方式实现 struct link *inverse（head） struct link *head； {struct link *p1， *p2， *p；p1=head->next;if (p1!=nil) { p2=p1->next; p1->next=nil; //处理链尾 while (p2!=nil) {p=p2->next; //保存下一个结点 p2->next=head->next; head->next=p2; //插入链头 p2=p; //循链向下 } } } 用队列和递归实现 if not empty(head) { dlqueue(head,x);reverse(head);enqueue(head,x);}例：用一个数组存放两个栈，一个从左端开始增长，一个从右端开始增长。

Stack1 Stack2 … … …bottom1 top1 top2 bottom2栈 1 增长 栈 2 增长 （1）实现双栈 DualStack，其声明如下： const int MaxDualStackSize = 100 class DualStack{private: int top1 , top2 ; DataType stackStorage[MaxDualStackSize];Public:DualStack(void);void Push(DataType elt,int n); //往栈 n 中压入 eltDataType Pop(int n); //从栈 n 中弹出DataType Peak(int n); //取栈 n 的栈顶元素 Int StackEmpty(int n); //栈 n 为空否？Int StackFull(int n); //栈 n 已满否？void ClearStack(int n); //清空栈 n};void DualStack::push(DataType elt, int n) { if(StackFull(n)) return(“stack overflow!“); else{if(n==1){ StackStorage[top1]=elt; top1++;} if(n==2){ StackStorage[top2]=elt; top2--;} } } int DualStack::StackFull(int n) {return (top2+1==top1);}（2）利用双栈 DualStack 模拟一个队列，写出入队和出队 的算法。

Void enqueue(Dual Stack Q, DataType a ) { if(!Q.StackFull(1)) Q.push(a,1); else return(“overflow“); }DataType dlqueue(DualStack Q) DataType a; {if(!(Q.StackEmpty(1)else {while(!Q.StackEmpty(1)) Q.push(Q.pop(1),2);a=Q.pop(2);}return(a); } else return(“Infeasible“);} 前序+中序决定二叉树 main() {Datatype preorder[n],inorder[n]; Struct link *BT; If (n>0) BT=creat(0,n-1,0,n-1); Return(BT); } struct link * creatBT(int prestart, int preend, int instart, int inend) {p=(struct link *)malloc(sizeof(struct link)); p->lchild=null;p->rchild=null; p->data=preorder[prestart]; if (prestartinstart) p->lchild=creatBT(prestart+1,prestart-instart+i,instart,i-1); if (irchild=creatBT(prestart-instart+i+1,preend,i+1,inend); } return(p); }按层次遍历二叉树 void Traverse_level(Bitree bt) {Initqueue(Q); Enqueue(Q,bt); while (!QueueEmpty(Q)) {v=Dlqueue(Q); visit(Q); if(!v->lchild)Enqueue(Q,v->lchild); if(!v->rchild)Enqueue(Q,v->rchild); } }在二叉排序树中删除所有结点值lchild=T; p=T; while(!p)if (p->datalchild=p->rchild;q=p;p=p->rchild;delete(q 及 q 的左子树);//要用非递归的遍历具体实现}else{f=p;p=p->lchild;}哈希表的删除 hashtable del_hashtable (hashtable if ( hash[t]= = null) return (“infeasible”);else if (hash[t]= =K) hash[t]=hash[t]->next;else { found=0;q=hash[t];p=hash[t]->next;while ((!found)q->next=p->next;}else{q=p; p=p->next;}if(!found) return (“infeasible”);}return(hash); } 数据结构与数据结构与 C C 语言程序设计答案语言程序设计答案一一. 是非题（是非题（2’2’ 1010））（（ ））1 1、、队列逻辑上是一个表头和表尾既能插入又能删除的线队列逻辑上是一个表头和表尾既能插入又能删除的线 性表。

性表 （（√））2 2、任何一个递归过程都可以转换成非递归过程任何一个递归过程都可以转换成非递归过程 ））3 3、、 与与 n n 个键值的集合个键值的集合{k1,k2,…,kn}{k1,k2,…,kn}相对应的堆是唯一相对应的堆是唯一 的 ））4 4、、在索引顺序表上实现分块查找，在等概率查找情况下，在索引顺序表上实现分块查找，在等概率查找情况下， 其查找长度只与表中元素个数有关，而与每块中元素其查找长度只与表中元素个数有关，而与每块中元素 个数无关个数无关 ））5 5、、所谓加权无向图所谓加权无向图 G G 的最小生成树的最小生成树 T T 就是将就是将 G G 中各结点中各结点 间的最短路径作为边所构造出来的间的最短路径作为边所构造出来的 G G 的子图 ））6 6、、在在 1010 万个随机排列的数据中，要选出万个随机排列的数据中，要选出 5 5 个最小的数，个最小的数， 采用快速排序比采用采用快速排序比采用 ShellShell 排序、堆排序及各种直接排序、堆排序及各种直接 排序法都快排序法都快 ））7 7、、B B 树查找算法的时间复杂性为树查找算法的时间复杂性为 O O（（n n）） 。

（（ ））8 8。