数据结构复习重点难点(含编程参考).pdf
数据结构复习第一章 概论（1）数据结构内容（P 1）映像（2）逻辑结构分类（P 3）（3）存储结构分类（P 3）（4）时间复杂度（规模，计算表示）（P 8）第二章 线性表（1）顺序表（插入1 4、删除1 6 实现方法、时间复杂度）（2）链 表（表示19、插入24、删除25）（3）单向链表（表示、空链表）一程序设计、理解、填空（4）单循环链表（尾指针2 6）（5）双向链表（插入28改变四个指针域、删除时节点变化28）（6）顺序表和链表空间和时间比较（2 9）存储密度查找插入删除顺序表1。O(n)。链表 1O(n)0(1)。第三章 栈和队列（1）栈的定义与性质、空栈的判断（2）栈的表示方式（顺序、链栈）（3）栈的程序理解（数值转换）（4）进栈出栈（选择，判断栈的容量）（5）双向栈（P34）（6）队列的定义性质（7）循环队列（判断队列满、列队空、求队列中元素个数）第四章 串（1）空串和空白串（2）串的基本运算（P52定位、求子串、串的比较）（3）串的节点大小（P 5 4）（4）子串的定位第五章 多维数组广义表（1）二维数组的存储计算（行序、列序）（2）特殊矩阵（对称、上三角、下三角）（20090126）（3）三元组表（4）广义表（表头、表尾、长度、深度、画图）P67第六章 树(1)二叉树性质(72-73)(2)二叉树(遍历)(3)二叉树程序阅读与编程(高度、叶子结点个数)(4)森林、树、二叉树的转换(84-85)(5)树的存储结构(左孩子右兄弟8 8)(6)哈夫曼树生成、编码(译码)、带权最短路径(9 0)第七章 图(1)无向图和有向图1 0 1(2)图一邻接矩阵和邻接表一图(103-105)(3)图的遍历(DFS108、BFS)(4)最小生成树(普利姆118、克鲁斯卡尔)(5)有向图的拓扑序列(6)最短路径(迪杰斯特拉1 2 2)森林、树、二叉树的转换(84-85)1.将树转换成二叉树(1)加线：在兄弟之间加一连线(2)抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系(3)旋转：以树的根结点为轴心，将整树顺时针转452.将二叉树转换成树(1)加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来(2)抹线：抹掉原二叉树中双亲与右孩子之间的连线(3)调整：将结点按层次排列，形成树结构3.森林转换成二叉树(1)将各棵树分别转换成二叉树(2)将每棵树的根结点用线相连(3)以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构4.二叉树转换成森林(1)抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树(2)还原：将孤立的二叉树还原成树一转方法2第八章 排序（1）关键字的比较、记录移动（2）考试题型：选 择（堆排序）、程序填空（二分法，冒泡两种改进冒泡）、简答题/绘图（快速，堆排序）（3）各种排序方法比较直接插入希尔冒泡快速146（*）选择15 0堆排序(*)二路归并箱排序(*)161是否稳定性稳定不稳定稳定不稳定不稳定不稳定稳定稳定是否就地就地就地就地非就地就地就地非就地非就地最佳复杂度0(n)0(nlgn)最差复杂度0(n2)0(n2)0(nlgn)平均复杂度0(n2)0(n1,25)0(n2)0(n2)0(nlgn)备注监视哨二分法插入增量d两指针i、j两步先个位再十位题型二分法插入程序填空写序列选 择（大小）画图写序列第九章 查找顺序查找二分法(*)分块查找二叉排序树（*）B-树(*)散列表（*）平均查找0(n)0(Ig n)具体分析1740(n l g n)说明(n+1)/n*lg(n+l)-l每一块 个 数173定义、中序遍历散列函数冲突处理探测填充因子193题型平均查找长度选择题比较节点个数比较节点画图画 图（节点分裂）、结点个数182公 式191画 图（给出散列序列）线性探测、拉链法第十章 文件（1）相 关 定 义（2 0 6）（2）索引顺序文件分类（IS A M、V S A M）（3）多关键字文件倒排文件编程题：（1）单 链 表（两个链表链接、删除、查找、统计满足条件的节点个数）（2）二 叉 树（高度、叶子结点个数、总结点个数）附 录 1 链表相关程序/*基本的链式顺序表操作*/#include#include#include typedef int Elemtype;typedef struct Lnode(Elemtype data;struct Lnode*next;Lnode;Lnode*L;/*数据子域*/*指针子域*/*节点结构类型*/*函数声明*/Lnode*creat_L();void out_L(Lnode*L);void insert_L(Lnode*L,int i,Elemtype);Elemtype delete_L(Lnode*L,int i);int locat_L(Lnode Elemtype e);/*主函数*/void main()(int i,k,loc;Elemtype e,x；char ch;doprintf(nnn);printf(Hn L建立单链表)printf(Mn 2.插入元素”)；printf(nn 3 删除元素”)；printf(nn 4 渣找元素，f);printf(nn 0.结束程序运行)printf(nn=);printf(n 请输入您的选择(1,2,3,4,0)”)；scanf(n%d,&k);switch(k)case 1:L=creat_L();out_L(L);break;case 2:printf(nn 请输入插入位置：”)；scanf(n%dM,&i);printf(”n 请输入要插入元素的值：);scanf(”d”,&e);insert_L(L,i,e);out_L(L);break;case 3:printf(n请输入要删除元素的位置：);scanf(%d,&i);x=delete_L(L,i)；out_L(L);if(x!=-l)printf(n 删除的元素为：%dn,x);printf(n删除d后的单链表为：n,x);out_L(L);)else printf(n要删除的元素不存在！：);break;case 4:(printf(n请输入要查找的元素值：)；scanf(%d,&e);loc=locat_L(L,e);if(loc=-l)printf(n 未找到指定元素！);else printf(n已找到，元素位置是d,loc);break;/switch*/printf(n-);while(k=l&knext=NULL;p=h;printf(n请输入第一个数据元素：);scanf(%d,&x);while(x!=-999)s=(Lnode*)malloc(sizeof(Lnode);s-data=x;s-next=NULL;/*分配头结点*/*输入第一个数据元素*/*输入-9 9 9,结束循环*/*分配新节点*/p-next=s;p=s;printf(”n请输入下一个数据：(输入-9 9 9,表示结束)”)；scanf(n%d0,&x);/*输入下一个数据*/)return(h);/*creat_L*/*输出单链表中的数据元素*/void out_L(Lnode*L)Lnode*p;p=L-next;printf(nnn);while(p!=NULL)printf(%5dn,p-data);p=p-next;/*out_link*/*在第i个位置插入元素e*/void insert_L(Lnode*L,int i,Elemtype e)Lnode*s,*p;intj;p=L;j=0；while(p!=NULL&jnext;j+;if(p=NULLIIivl)printf(”n 插入位置错误!)else s=(Lnode*)malloc(sizeof(Lnode);s-data=e;s-next=p-next;p-next=s;)/*insert_L*/*删除第i个元素，返回其值刃delete_L(Lnode*L,int i)Lnode*p,*q;int j;Elemtype x;p=L;j=O;while(p-next!=NULL&jnext;j+;if(!p-nextllinext;x=q-data;p-next=q-next;free(q);return(x);/*delete_L*/*查找值为e的元素，返回它的位置*/int locat_L(Lnode*L,Elemtype e)Lnode*p;int j=l;p=L-next;while(p!=NULL&p-data!=e)p=p-next;j+;)if(p!=NULL)return(j);else return(-l);/*locat_L*/附录2 二叉树相关程序#include#include#define M 100typedefchar Etype;typedef struct BiTNode Etype data;struct BiTNode*lch,*rch;BiTNode,*BiTree;BiTree queM;int front=0,rear=0;/*函数原型声明*/BiTNode*creat_btl();BiTNode*creat_bt2();void preorder(BiTNode*p);void inorder(BiTNode*p);void postorder(BiTNode*p);void enqueue(BiTree);BiTree delqueue();void levorder(BiTree);int treedepth(B iTree);void prtbtree(BiTree,int);void exchange(BiTree);int leafcount(BiTree);void paintleaf(BiTree);BiTNode*t;int count=0;/*定义二叉树结点值的类*/*树节点结构*/*层次遍历二叉树*/*主函数*/void main()char ch;int k;do printf(nn);printf(n=主菜单=);printf(nn1.建立二叉树方法1）;printf(nn2.建立二叉树方法2）;printf(n3.先序递归遍历二叉树）printf(n4.中序递归遍历二叉树）printf(n5.后序递归遍历二叉树）printf(Mn6.层次遍历二叉树）printf(n 7.计算二叉树的高度”)；printf(n 8.计算二叉树中叶结点个数”)；printf(n 9.交换二叉树的左右子树)printf(n 10 打印二叉树)printf(n 0结束程序运行)；printf(n=);printf(n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10);scanf(%d,&k);switch(k)(case 1:t=creat_bt 1 ();break;/*调用性质 5 建立二叉树算法*/case 2:printf(n 请输入二叉树各结点的值:)；fflush(stdin);t=creat_bt2();break;/*调用递归建立二叉树算法*/case 3:if(t)printf(先序遍历二叉树:)；preorder(t);printf(n);else printf(二叉树为空！n);break;case 4:if(t)printf(中序遍历二叉树:)；inorder(t);printf(n);)else p r in tf(二叉树为空！n);break;case 5:if(t)printf(后序遍历二叉树)postorder(t);printf(n);)else p r in tf(二叉树为空!n);break;case 6:if(t)printf(层次遍历二叉树:)；levorder(t);printf(n);)else p r in tf(二叉树为空!n);break;case 7:if(t)printf(二叉树高度为：%d,treedepth(t);printf(n);else printf(二叉树为空!n);break;case 8:if(t)p r in tf(二叉树的叶子结点数为:dn”,leafcount(t);p r in tf(二叉树的叶结点为:);paintleaf(t);printf(n);)else printf(二叉树为空!n);break;case 9:if(t)printf(交换二叉树的左右子树:n)；exchange(t);prtbtree(t,O);printf(,nn);)else printf。二叉树为空!nn);break;case 10:if(t)printf(逆时针旋转90度输出的二叉树prtbtree(t,0);printf(n);else p r in tf(二叉树为空!n);break;case 0:exit(0);/*switch*/while(k=1&kdata=e;p-lch=NULL;p-rch=NULL;vfi=p；if(i=l)t=p;/*序号为1的结点是根*/elsej=i/2;if(i%2=0)vfj-lch=p;/*序号为偶数，作为左孩子*/else vj-rch=p;/*序号为偶数，作为右孩子*/)printf(”n请继续输入二叉树各结点的编号和对应的值:)；scanf(n%d,%cn,&i,&e);)return(t);/*creat_btl*/*模仿先序递归遍历方法，建立二叉树*/BiTNode*creat_bt2()BiTNode*t;Etype e;scanf(n%cn,&e);if(e=#)仁NULL;/*对于邪值,不分配新结点*/else t=(BiTNode*)malloc(sizeof(BiTNode);t-data=e;t-lch=creat_bt2();/*左孩子获得新指针值*/t-rch=creat_bt2();/*右孩子获得新指针值*/)return(t);/*creat_bt2*/*先序递归遍历二叉树*/void preorder(BiTNode*p)if(P)printf(u%3cn,p-data);preorder(p-lch);preorder(p-rch);)/*preorder*/*中序递归遍历二叉树*/void inorder(BiTNode*p)if(P)inorder(p-lch);printf(n%3cH,p-data);inorder(p-rch);/*inorder*/*后序递归二叉树*/void postorder(BiTNode*p)if(P)postorder(p-lch);postorder(prch);printf(n%3cM,p-data);)/*postorder*/*层次遍历二叉树*/void enqueue(BiTree T)if(front!=(rear+l)%M)(rear=(rear+1)%M;querear=T;)BiTree delqueue()if(front=rear)return NULL;front=(front+1)%M;return(quefront);void levorder(BiTree T)/*层次遍历二叉树*/BiTree p;if(T)enqueue(T);while(front!=rear)p=delqueue();printf(n%3cn,p-data);if(p-lch!=NULL)enqueue(p-lch);if(p-rch!=NULL)enqueue(p-rch);/*计算机二叉树的高度*/int treedepth(BiTree bt)int hl,hr,max;if(bt!=NULL)hl=treedepth(bt-lch);hr=treedepth(bt-rch);max=(hlhr)?hl:hr;retum(max+l);)else return(O);)/*逆时针旋转90度输出二叉树树形*/void prtbtree(BiTree bt,int level)(intj；if(bt)prtbtree(bt-rch,level+1);for(j=0;jdata);prtbtree(bt-lch,level+1);/*交换二叉树左右子树*/void exchange(BiTree bt)BiTree p;if(bt)(p=bt-lch;bt-lch=bt-rch;bt-rch=p;exchange(bt-lch);exchange(bt-rch);/*计算叶结点数*/int leafcount(BiTree bt)if(bt!=NULL)(leafcount(bt-lch);leafcount(bt-rch);if(bt-lch=NULL)&(bt-rch=NULL)count+;)return(count);/*输出叶结点*/void paintleaf(BiTree bt)if(bt!=NULL)if(bt-lch=NULL&bt-rch=NULL)printf(n%3cn,bt-data);paintleaf(bt-lch);paintleaf(bt-rch);
