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

《数据结构与C语言程序设计复习.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构逻辑结构存储结构操作线性结构树型结构图状结构集合顺序存储结构链式存储结构虚拟存储结构数组指针200120001999线性结构next值（5）线性表的归并（12）两个栈模拟队列（12）树型结构遍历序列二叉树〈=〉森林树的基本概念在二叉树上求结点的祖先三次树前后序确定树（5）中序线索树上求后序后继（20）判断二叉树相似（8）按层次顺序遍历二叉树（12）先序+中序建立二叉树（12）图状结构关键路径（逆）邻接表的生成图的深度优先，广度优先，最小生成树（12）集合：查找排序外排最佳归并树的虚段平衡二叉树二叉排序树ASL分析Hash表平均查找长度公式（5）B-树的

2、深度定义（5）各类排序复杂度（8）排序时间复杂度证明（8)有序表查找长度证明（8）置换-选择排序（8）删除二叉树结点（12）Hash表的删除（12）二叉排序树，平衡二叉树（7）内部排序第一趟结果（9）堆定义、堆排序与其它排序的比较（8）置换-选择排序（4）算法设计与分析递归方程求解递归方程求解程序题所占比例2/1035’3/1240’5/1060’总结所考知识点分布：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。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)//已知单链线性表La和Lb的元素按值非递减排列。//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减

5、排列。{pa=La->next;pb=Lb->next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa->data<=pb->data){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=AÇB，要求C按元素递增排列，并利用原表（即表A和表B）的

6、结点空间存放表C。voidJoin(Linklist&la,linklist&lb,linklist&lc){pa=la->next;pb=lb->next;lc=la;pc=la;while(pa&&pb){if(pa->datadata){p=pa;pa=pa->next;free(p);}elseif(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;whi

7、le(pa){p=pa;pa=pa->next;free(p);}while(pb){p=pb;pb=pb->next;free(p);}free(lb);}例：带头结点的单链表的逆置用类似栈的方式实现structlink*inverse（head）structlink*head；{structlink*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->ne

8、xt=p2;//插入链头p2=p;//