一键复制
无论是身处学校还是步入社会，大家都尝试过写作吧，借助写作也可以提高我们的语言组织能力。相信许多人会觉得范文很难写？这里我整理了一些优秀的范文，希望对大家有所帮助，下面我们就来了解一下吧。
数据结构小结篇一
【实验目的】
学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。
【实验内容】
1.顺序表的实践
1)建立4个元素的顺序表s=sqlist[]={1，2，3，4，5}，实现顺序表建立的基本操作。
2)在sqlist []={1，2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。
3)在sqlist []={1，2，3，4，9，5}中删除指定位置（i=5）上的元素9，实现顺序表的删除的基本操作。2.单链表的实践
3.1)建立一个包括头结点和4个结点的（5，4，2，1）的单链表，实现单链表建立的基本操作。
2)将该单链表的所有元素显示出来。
3)在已建好的单链表中的指定位置（i=3）插入一个结点3，实现单链表插入的基本操作。
4)在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。
【实验步骤】
1.打开vc++。
2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。
3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
【实验心得】
线性是我们学习数据结构中，碰到的第一个数据结构。学习线性表的重点掌握顺序表和单链表的各种算法和时间性能分析。线性表右两种存储方式即顺序存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于顺序表的插入删除运算，其平均时间复杂度均为0（n）.通过这次的学习，掌握的太熟练，主要是课本上的知识点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次实验我找到了自己的不足之处，以后会努力的。
实验二：栈的表示与实现及栈的应用
【实验目的】
（1）掌握栈的顺序存储结构及其基本操作的实现。（2）掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3）掌握用递归算法来解决一些问题。【实验内容】
1.编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。
2.编写递归程序，实现n！的求解。3.编写递归程序，实现以下函数的求解。
n,n0,1fib(n) fib(n1)fib(n2),n1
4.编写程序，实现hanoi塔问题。【实验步骤】 1.打开vc++。
2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。
3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
【实验心得】
通过这次的学习我掌握了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（botton）；栈又称为后进先出（last in first out）的线性表,简称lifo结构，因为它的修改是按后进先出的原则进行的。
加上这个实验，我已经学了线性表（顺序表，单链表）和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后知识的总要基础。
实验三：二叉树的建立及遍历
【实验目的】
（1）掌握利用先序序列建立二叉树的二叉链表的过程。（2）掌握二叉树的先序、中序和后序遍历算法。【实验内容】
1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立如下图所示的二叉树。
并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开vc++。
2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。
3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
【实验心得】
这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次实验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些判断条件，总体来说，本次试验不太好做，期间出现了很多逻辑错误，变量初始化的问题等，不过经过仔细排查最后都一一解决了。
实验四：查找与排序
【实验目的】
（1）掌握折半查找算法的实现。（2）掌握冒泡排序算法的实现。【实验内容】
1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49 【实验步骤】 1.打开vc++。
2.建立工程：点file->new，选project标签，在列表中选win32 console application，再在右边的框里为工程起好名字，选好路径，点ok->finish。至此工程建立完毕。
3.创建源文件或头文件：点file->new，选file标签，在列表里选c++ source file。给文件起好名字，选好路径，点ok。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
（1）查找算法的代码如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {
elemtype *elem;
int length;}sstable;status initlist(sstable &st){ int i,n;
=
(elemtype*)
malloc(elemtype));
if(!)return(overflow);
printf(“输入元素个数和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i<=n;i++){
(maxnum*sizeof
scanf(“%d”,&[i]);}
= n;
return ok;} int seq_search(sstable st,elemtype key){
int i;
[0]=key;
for(i=;[i]!=key;--i);
return i;} int binarysearch(sstable st,elemtype key){
int mid,low,high,i=1;
low=1;
high=;
while(low<=high)
{
mid=(low+high)/2;
if([mid]==key)
return mid;
else if(key<[mid])< p="">
high=mid-1;
else
}
return 0;} void main(){ sstable st;initlist(st);
elemtype key;int n;printf(“ key= ”);
scanf(“%d”,&key);
printf(“nn”);
/*printf(“after seqsearch:: ”);
n=seq_search(st,key);
printf(“position is in %d nn”,n);*/
printf(“after binary search::”);
n=binarysearch(st,key);
low=mid+1;if(n)printf(“position is in %d nn”,n);else
} 实验结果如下所示：
（2）排序算法的代码如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {
elemtype *elem;
int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;
(elemtype));
if(!)return(overflow);
printf(“输入元素个数和各元素的值:”);
scanf(“%dn”,&n);
for(i=1;i<=n;i++){
scanf(“%d”,&[i]);}
= n;
return ok;} void sort(sstable st){
int i,j,t;
for(i=1;i<;i++)< p="">
for(j=i+1;j<=;j++)
if([i]>[j]){ t=[i];=
(elemtype*)
malloc
(maxnum*sizeof
}
} [i]=[j];[j]=t;void display(sstable st){ int i;
for(i=1;i<=;i++){
printf(“%d
”,[i]);}
} void main(){
sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 实验结果如下所示：
【实验心得】
通过这次实验,我明白了程序里的折半查找和冒泡查找.其实排序可以有很多种，但是其目的应该都是为了能够在海量的数据里迅速查找到你要的数据信息，折半查找是种比较快的方式，但前提是要是有 序的排序才可以。对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量，low表示区域下界，high表示上界，中间位置mid=(low+high)/2.而冒泡查找则是从小到大的排序.
数据结构小结篇二
一、基本概念
1、数据元素是数据的基本单位。
2、数据项是数据不可分割的最小单位。
3、数据结构的
逻辑结构（抽象的，与实现无关）
物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系
4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出 正确性：能按设计要求解决具体问题，并得到正确的结果。
有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。确定性：算法中每条指令的含义必须明确，不允许由二义性
可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。
输入：一个算法的输入可以包含零个或多个数据。输出：算法有一个或多个输出
5、算法设计的要求：
（1）正 确 性：算法应能满足设定的功能和要求。（2）可 读 性：思路清晰、层次分明、易读易懂。
（3）健 壮 性：输入非法数据时应能作适当的反应和处理。
（4）高 效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。（5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。
二、线性表
1、线性表 list：最常用且最简单的数据结构。含有大量记录的线性表称为文件。
2、线性表是n个数据元素的有限序列。
线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。
3、顺序表——线性表的顺序存储结构 特点
a)逻辑上相邻的元素在物理位置上相邻。b)随机访问。
2)表长为n时，线性表进行插入和删除操作的时间复杂度为o（n），插入一个元素时大约移动表中的一半元素，删除一个元素时大约移动表中的（n-1）2。
4、线性表的链式存储结构 1)类型定义
简而言之，“数据 + 指针”
2)不带头结点的空表判定为 l= =null 带头结点的空表判定为 l->next= =null 循环单链表为空的判定条件为 = =l 线性链表的最后一个结点的指针为null 头结点的数据域为空，指针域指向第一个元素的指针。
5、顺序表和单链表的比较
6、顺序存储：优点：存储密度大，可随机存储
缺点：大小固定；不利于增减节点;存储空间不能充分利用；容量难扩充 链式存储：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限制 缺点：增加了存储空间的开销；不可以随机存储元素
三、栈与队列
1、栈
栈：限定仅在表尾进行插入或删除操作的线性表。栈顶：表尾端 栈底：表头
栈是先进后出的线性表。
插入栈顶元素称为入栈，删除栈顶元素称为出栈。
类似于顺序表，插入和删除操作固定于表尾。
3、队列
先进先出的线性表。队尾入队 对头出队
允许插入的一端叫做队尾 允许删除的一端叫做对头
4、链队列
1.树的定义
树（tree）：是 n（n≥0）个有限数据元素的集合。在任意一棵非空树t中：
（1）有且仅有一个特定的称为树根（root）的结点，根结点无前趋结点；
（2）当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的集合t1，t2，„，tm，其中每一个集合ti（1≤ i ≤m）本身又是一棵树，并且称为根的子树。2.基本术语：
结点的度数：结点的非空子树（即后缀）个数叫作结点的度数
树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否则称作分支结点。
结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1 孩子和双亲： 树的深度：
树的度数：树中度数最大的结点度数叫作树的度数 树林：是由零个或多个不相交的树所组成的集合。3.二叉树性质：
1)二叉树的第i层上至多有2i-1个结点。2)深度为k的二叉树至多有2k-1个结点。满二叉树：深度为k，有2k-1个结点。
完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。
3)叶子结点n0，度为2的结点为n2，则n0 = n2+1。考虑结点个数：n = n0 + n1 + n2 考虑分支个数：n-1 = 2n2 + n1 可得n0 = n2+1
5.遍历二叉树（先序dlr、中序ldr、后序lrd）方法与c语言描述
由二叉树的递归定义可知，一棵二叉树由根结点（d）、根结点的左子树（l）和根结点的右子树（r）三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。一般有三种方法：先序(前序)遍历dlr（根左右）、中序遍历ldr（左根右）、后序遍历lrd（左右根）。
7.树和森林
树的存储结构
双亲表示法，孩子表示法，孩子兄弟表示法。特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。
赫夫曼编码(前缀码)向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。
五、图 1．
完全图：有12 n(n-1)条变得无向图
有向完全图：具有n（n-1）条弧的有向图。权：与图的边或弧相关的数。
顶点v的度：和v相关联的边的数目。
入度：以顶点v为头的弧的数目 出度：以顶点v为尾的弧的数目 回路或环：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
边(弧)多则需要存储空间多。
·十字链表：
十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。
·邻接多重表 3.图的遍历
1)深度优先（dfs）搜索
访问方式：从图中某顶点v出发： a）访问顶点v；
b）从v的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，结束。2)广度（宽度，bfs）优先搜索 a）访问顶点v ；
b）访问同v相邻的所有未被访问的邻接点w1,w2, „wk；
c）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；
4.生成树和最小生成树
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有dfs生成树和bfs生成树。
1)最小生成树
·kruskal算法
一句话，“不构成环的情况下，每次选取最小边”。
-网
用顶点表示活动，边表示活动的优先关系的有向图称为aov网。
拓扑排序：对aov网络中顶点构造拓扑有序序列的过程。拓扑排序的方法(1)在有向图中选一个没有前驱的顶点且输出之(2)从图中删除该顶点和所有以它为尾的弧 6.关键路径
aoe网，关键路径
aoe网(activity on edge)——带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。
关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径。7.最短路径
(1)迪杰斯特拉算法
求一个顶点到其他各顶点的最短路径。
算法：(a)初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞；
(b)从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
(c)修改最短路径：计算u的邻接点的最短路径，若(v,„,u)+(u,w)<(v,„,w)，则以(v,„,u,w)代替。
(d)重复(b)-(c)，直到求得v到其余所有顶点的最短路径。特点：总是按照从小到大的顺序求得最短路径。
六、查找
1.查找分为：静态查找表、动态查找表、哈希查找表 2.静态查找表：对查找表只作查找操作的查找表。动态查找表：查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表。
3.顺序查找：顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既 适用于顺序表，也适用于链表。
4.二分法（折半）查找：是一种效率较高的查找方法，但前提是表中元素必须 按关键字有序（按关键字递增或递减）排列。
5.索引顺序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块 效率最高
6.动态查找表：二叉排序树查找：二叉排序树的生成
二叉排序树(二叉查找树)：或者是一颗空树。或者如下1若它的左子树不空，则左子树上所有的结点的值均小于他的根结点的值。2若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树。
7.哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法，数字分析法
冲突解决方法：开放定址法、拉链法、公共溢出区法
七、排序 1.插入类排序： ·直接插入排序
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。·折半插入排序 ·希尔排序 基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量的记录组成一个子序列。2.交换类排序 ·起泡排序
也称冒泡法，每相邻两个记录关键字比大小,大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数）。·快速排序
在当前无序区r[1..h]中任取一个数据元素作为比较的“基准”(不妨记为x)，用此基准将当前无序区划分为左右两个较小的无序区：r[1..i-1]和r[i+1..h]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准x则位于最终排序的位置上，即r[1..i-1]≤≤r[i+1..h](1≤i≤h)，当r[1..i-1]和r[i+1..h]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。3.选择类排序 ·简单选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。·堆排序
堆排序是一树形选择排序，在排序过程中，将r[1..n]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。4.归并类排序 ·二路归并排序 5.基数类排序 ·基数排序
主要特点不需要进行关键字间的比较。多关键字排序：
最高为优先（msd法）从主关键字开始排序，再从次高位排序，一次类推，最后将所有子序列依次连接在一起成为一个有序序列。
最低位优先（lsd法）从最次位关键字开始排序，在对高一位的进行排序，直到成为一个有序序列。
选取排序方法需要考虑的因素：(1)待排序的元素数目n；(2)元素本身信息量的大小；
(3)关键字的结构及其分布情况；
(4)语言工具的条件，辅助空间的大小等。
小结：
(1)若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3)若n较大，则应采用时间复杂度为o(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要o(nlog2n)的时间。
数据结构小结篇三
一周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在设计过程中，和同学们相互探讨，相互学习，相互监督。我学会了运筹帷幄，学会了宽容，学会了理解，也学会了做人与处世，这次课程设计对我来说受益良多。
课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．“千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础。我这次设计的科目是数据结。
数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。作为一门独立的课程在国外是从20xx年才开始设立的。20xx年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。通过这次模具设计，我在多方面都有所提高。
一、编译工具visualc++ 很多程序在结构上是独立的，但是本此设计的程序功能不是零散的，它有一个连接是的程序是一个整体，怎样达到这种统一体呢？因为这个输出连接是贯穿始终的。说到这，就应该说以下我所应用的调试工具，也就是运行环境visualc++，可以充分利用windows的支持剪贴版和英文的特点。正是在实现循环链表的程序中充分利用这个特点，才能制作出全汉化的初始化画面。
二、巩固和温习了c语言
在界面设置中使用函数调用while。其中文本显示颜色和背景颜色都可以任意按照自己的喜好，任意改变，但改变的时候必须采用标准英文大写，同时在制作显示菜单的窗口，大小根据菜单条数设计。最后采用printf输出程序设计界面。
这次的程序软件基本上运行成功，可以简单的建立链式循环链表，并进行输出，及循环语句的运用和选择语句的控制。由于时间和知识上的限制，使得程序规模相对较小，即功能还不很全面，应用也不很普遍。原来c语言可是涉及很多知识，而不是枯燥无聊的简单的代码部分而已，利用c语言方面的知识，我们可以设计出更完善的软件。
三、积累了宝贵的经验
我这次课程设计代码中主要使用了链表的循环和遍历这两中操作。循环链表(circularlinkedlist)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由null改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。类似地，还有多重链的循环链表。在循环单链表中，表中所有结点被链在一个环上，多重循环链表则是将表中的结点链在多个环上。为了使某些操作实现起来方便，在循环单链表中也可设置一个头结点。这样，空循环链表仅由一个自成循环的头结点表示。所谓遍历(traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
这次课程设计我选中的题目是个人资料的管理。编写了一个可以简易使用的个人资料管理系统，可以进行资料的输入和管理。虽然在我的程序中有一部分是从网上搜索得来的，但我已经竭力将所获得的信息变成自己的资源，动手上机操作，在了解和看懂的基础上有所改变和创新，但是在的程序软件中还有部分的不足，需要加以更新。仅管，我并没能很好的利用所学数据结构的知识，但我也尽了自己最大的努力用我所学来完成这次的课程设计。同时，通过这次课程设计，我认识到了自己动手实践的弱势，特别是在编程方面，知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。
四、对以后的学习充满了信心和期待
通过这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这也是一笔很大的资源。在以后的时间中，我们应该利用更多的时间去上机实验，加强自学的能力，多编写程序，相信不久后我们的编程能力都会有很大的提高能设计出更多的更有创新的作品。
数据结构小结篇四
数据结构参考题目
一、选择
1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）
a.栈 b.队列 c.树 d.图 2.下面程序段的时间复杂度为（）for(i=0;i
c.都是非空串 d.串的长度相等且对应的字符相同 5．若以s和x分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）
xx sx sx xx 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）a.0 b.1 c.48 d.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）
a.插入排序 b.冒泡排序 c.快速排序 d.归并排序
8.已知散列表的存储空间为t[0..16]，散列函数h（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：t[5]=39，t[6]=57和t[7]=7，则下一个关键字23插入的位置是（）
a.t[2] b.t[4] c.t[8] d.t[10] 9.如果将矩阵an×n的每一列看成一个子表，整个矩阵看成是一个广义表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为dout，则所有顶点的入度之和为（）
-1 +1 d.n 11．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）a线性结构 b.树形结构 c.线性结构和树型结构 d.线性结构和图状结构
12．栈的插入和删除操作在()进行。
a．栈顶 b.栈底 c.任意位置 d指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）a.24 b.71 c.48 d.53 14．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．关于栈和队列的说法中正确的是（）
a．栈和队列都是线性结构 b.栈是线性结构，队列不是线性结构 c.栈不是线性结构，队列是线性结构 d.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）a．顺序存储比链式存储少占空间 b.顺序存储比链式存储多占空间
c.顺序存储和链式存储都要求占用整块存储空间 d.链式存储比顺序存储难于扩充空间
17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）a.q→next=s；p→next=s； b.q→next=s；s→next=p； c.q→next=s；q→next=p； d.q→next=s；s→next=q；
18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为h(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1 b.2 c.3 d.4 19．执行下面程序段时，s语句被执行的次数为：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）
a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．关于串的叙述中，正确的是（）a．空串是只含有零个字符的串 b.空串是只含有空格字符的串
c.空串是含有零个字符或含有空格字符的串
d.串是含有一个或多个字符的有穷序列
23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）
a．front==rear
b.(front+1)%m==rear
+1==front
d.(rear+1)%m==front 24．设有二维数组
1a［n］［n］表示如下：23456，则a［i］［i］（0≤i≤n-1）的d.i2/2 值为（）
a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度为h的完全二叉树中，结点数最多为（）
ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）
-1 c.n(m-1)d.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）a.n b.n-1 c.n+1 d.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）a.矩阵中非全零元素的行数等于图中的顶点数
b.第i行上与第i列上非零元素总和等于顶点vi的度数 c.矩阵中的非零元素个数等于图的边数
d.第i行上非零元素个数和第i列上非零元素个数一定相等
29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为h(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）a.1 b.2 c.3 d.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）
a.36，44，49，55，81，88 b.44，36，49，55，81，88 c.44，36，49，81，55，88 d.44，36，49，55，88，81
二、填空题
1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。
3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。
5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。
9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。
10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）
11.数据的存储结构是数据的逻辑结构的存储映象（）。
12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。
13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。
16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（）
19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。
27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。
28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。
30.将插入和删除限定在表的同一端进行的线性表是队列（）。
三、画图题
1.请根据下列二元组画出相应的数据结构
k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构
k={a,b,c,d,e,f,g,h,i,j} r={,, k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）} 四、运算题 1．已知一个图的顶点集v和边集h分别为： v＝{0，1，2，3，4，5，6，7} e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。 2.一个线性表为b=（12，23，45，57，20，03，78，31，15，36），设散列表为ht[0..12]，散列函数为h（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 平均查找长度：（写出计算过程） 3．已知一个图的顶点集v和边集h分别为： v＝{0，1，2，3，4，5，6，7} e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发） ____ __，___ _，___ ___，__ ____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果： 前序： 中序： 后序： 5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。 五、编程题 1.请编写一个算法，实现十进制整数与二进制数的转换。void shi_to_er(unsigned x){ 2.写出二分法查找的算法： int search_bin(keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。linklist *invertlink(linklist *h){ 数据结构】二叉排序树的建立，查找，插入和删除实践题 /*sy53.c*/ #include typedef struct node{ keytype key; struct node *lchild,*rchild; }bstnode; typedef bstnode *bstree; bstree createbst(void); void searchbst(bstree t,keytype key); void insertbst(bstree *tptr,keytype key); void delbstnode(bstree *tptr,keytype key); void inorderbst(bstree t); main() {bstree t; char ch1,ch2; keytype key; printf(“建立一棵二叉排序树的二叉链表存储n”); t=createbst(); ch1='y'; while(ch1=='y' || ch1=='y') {printf(“请选择下列操作：n”); printf(“1------------------更新二叉排序树存储n”); printf(“2------------------二叉排序树上的查找n”); printf(“3------------------二叉排序树上的插入n”); printf(“4------------------二叉排序树上的删除n”); printf(“5------------------二叉排序树中序输出n”); printf(“6------------------退出n”); scanf(“n%c”,&ch2); switch(ch2) {case '1':t=createbst();break; case '2':printf(“n请输入要查找的数据：”); scanf(“n%d”,&key); searchbst(t,key); printf(“查找操作完毕。n”);break; case '3': printf(“n请输入要插入的数据：”); scanf(“n%d”,&key); insertbst(&t,key); printf(“插入操作完毕。n”);break; case '4': printf(“n请输入要删除的数据：”); scanf(“n%d”,&key); delbstnode(&t,key); printf(“删除操作完毕。n”);break; case '5': inorderbst(t); printf(“n二叉排序树输出完毕。n”);break; case '6':ch1='n';break; default:ch1='n'; } } } bstree createbst(void) {bstree t; keytype key; t=null; printf(“请输入一个关键字(输入0时结束输入)：n”);scanf(“%d”,&key); while(key) {insertbst(&t,key); printf(“请输入下一个关键字(输入0时结束输入)：n”);scanf(“n%d”,&key); } return t; } void searchbst(bstree t, keytype key) { bstnode *p=t; while(p) {if(p->key==key) {printf(“已找到n”); return; } p=(key key)? p->lchild:p->rchild; } printf(“没有找到n”); } void insertbst(bstree *t,keytype key) {bstnode *f,*p; p=(*t); while(p) {if(p->key==key) {printf(“树中已有key不需插入n”); return; } f=p; p=(key key)?p->lchild:p->rchild; } p=(bstnode*)malloc(sizeof(bstnode)); p->key=key; p->lchild=p->rchild=null; if((*t)==null)(*t)=p; else if(key }/*insertbst*/ void delbstnode(bstree *t,keytype key) {bstnode *parent=null, *p, *q,*child; p=*t; while(p) {if(p->key==key)break; parent=p; p=(key key)?p->lchild:p->rchild; } if(!p){printf(“没有找到要删除的结点n”);return;} q=p; if(q->lchild && q->rchild) for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild; if(!parent)*t=child; else {if(p==parent->lchild) parent->lchild=child; else parent->rchild=child; if(p!=q) q->key=p->key; } free(p); } void inorderbst(bstree t){ if(t!=null) {inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);} }数据结构小结篇五
