《数据结构与C语言程序设计复习》由会员分享，可在线阅读，更多相关《数据结构与C语言程序设计复习（31页珍藏版）》请在金锄头文库上搜索。
1、文档供参考，可复制、编制，期待您的好评与关注！ 数据结构逻辑结构存储结构操作线性结构树型结构图状结构集合顺 序存 储结 构链 式存 储结 构虚拟存储结构数组指针200120001999线性结构next值（5）线性表的归并（12）两个栈模拟队列（12）树型结构遍历序列二叉树=森林树的基本概念在二叉树上求结点的祖先三次树前后序确定树（5）中序线索树上求后序后继（20）判断二叉树相似（8）按层次顺序遍历二叉树（12）先序+中序建立二叉树（12）图状结构关键路径（逆）邻接表的生成图的深度优先，广度优先，最小生成树（12）集合：查找排序外排最佳归并树的虚段平衡二叉树二叉排序树 ASL分析Hash表平均查
2、找长度公式（5）B-树的深度定义（5）各类排序复杂度（8）排序时间复杂度证明（8)有序表查找长度证明（8）置换-选择排序（8）删除二叉树结点（12）Hash表的删除（12）二叉排序树，平衡二叉树（7）内部排序第一趟结果（9）堆定义、堆排序与其它排序的比较（8）置换-选择排序（4）算法设计与分析递归方程求解递归方程求解程序题所占比例2/10 353/12 405/10 60总结所考知识点分布：l 线性结构：KMP算法中next数组的值线性表的归并两个栈模拟队列栈的输出序列栈、队列基本操作的时间复杂度l 树：二叉树和树的定义二叉树的前序、中序、后序、层次遍历哪些遍历序列可唯一决定二叉树二叉树的结点
3、查找二叉树的相似判断求二叉树结点的祖先结点中序线索二叉树及中序遍历线索二叉树在中序线索二叉树上求其他序的前驱、后继Huffman树的构造森林（树）与二叉树的转换l 图：图的深度优先、广度优先遍历生成树最小生成树的Kruskal算法（逆）邻接表的生成拓扑排序关键路径最短路径Dijkstra算法、Floyd算法l 查找：有序表ASL证明索引排序表的查找二叉排序树的插入、删除、ASL分析平衡二叉树的插入、删除、B-树的定义、深度、插入Hash表的构造、查找、删除及ASL分析l 排序：各类排序的时间空间复杂度分析稳定性分析基于比较的排序在最坏情况下能达到的最好的时间复杂度证明各类排序的第一趟排序结果堆
4、的定义置换选择排序的初始归并段构造初始归并段平均长度的证明最佳归并树的虚段l 算法设计与分析：递归方程求解例题分析例：假设有两个按元素值非递减有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc)/已知单链线性表La和Lb的元素按值非递减排列。/归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。pa=La-next;pb=Lb-next;Lc=pc
5、=La; /用La的头结点作为Lc的头结点while(pa&pb)if(pa-datadata) pc-next=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=AB，要求C按元素递增排列，并利用原表（即表A和表B）的结点空间存放表C。void Join(Linklist &la, linklist & lb, linklist & lc)pa=la-
6、next;pb=lb-next;lc=la;pc=la;while(pa&pb)if(pa-datadata)p=pa;pa=pa-next;free(p);else if(pa-datapb-data) p=pb;pb=pb-next;free(p); elsepc-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);例：带头结点的单链表的逆置用类似栈的方式实现struc
7、t 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);例：用一个数组存放两个栈，一个从左端开始增长
8、，一个从右端 开始增长。 Stack1 Stack2 bottom1 top1 top2 bottom2 栈1增长 栈2增长（1） 实现双栈DualStack，其声明如下： const int MaxDualStackSize = 100class DualStack private:int top1 , top2 ;DataType stackStorageMaxDualStackSize; Public: DualStack(void); void Push(DataType elt,int n); /往栈n中压入elt DataType Pop(int n); /从栈n中弹出 DataT
9、ype 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!);elseif(n=1) StackStoragetop1=elt; top1+;if(n=2) StackStoragetop2=elt; top2-;int DualStack:StackFull(in
10、t 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)& &Q.StackEmpty(2)if(!Q.StackEmpty(2) a=Q.pop(2); else while(!Q.StackEmpty(1) Q.push(Q.p
11、op(1),2); a=Q.pop(2); return(a);else return(Infeasible);前序+中序决定二叉树main()Datatype preordern,inordern;Struct link *BT;If (n0)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
12、-data=preorderprestart;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
