第一篇：数据结构学习(C)树(总结)
数据结构学习（C++）——树（总结）
happycock（原作）CSDN
才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而如果再讲B＋、B－，就不能不提到搜索，如果是胜者树就不能不提到排序。为此，把这部分放到后面。我前面所做的努力，只是让你有个基本概念，什么时候记得用树。树的两个基本用途，可以用物质和精神来比喻。
一个用途是做为数据储存，储存具有树结构的数据——目录、族谱等等。为了在实际上是线性的储存载体上（内存、磁盘）储存非线性的树结构，必须有标志指示出树的结构。因此，只要能区分根和子树，树可以采取各种方法来储存——多叉链表、左子女－右兄弟二叉链表、广义表、多维数组。由于操作的需求，储存方法并不是随意选取的。比如，在并查集的实现上，选取的是双亲链表。
一个用途是做为逻辑判断，此时会常常听到一个名词——判定树。最常用的结构是二叉树，一个孩子代表true，一个孩子代表false。关于多叉判定树，有个例子是求8皇后的全部解——这个连高斯都算错了（一共是92组解，高斯最开始说76组解），我们比不上高斯，但是我们会让computer代劳。
就像哲学界到现在还纠缠于物质和精神本源问题，实际上在树这里也是如此。有些情况下，并不能区分是做为储存来用还是做为判断来用，比如搜索树，既储存了数据，还蕴涵着判断。
和后面的图相比，树更基本，也更常用。你可以不知道最短路径怎么求，却每时每刻都在和树打交道——看看你电脑里的文件夹吧。
最后，附带一个求N皇后的全部解的程序。
#include
#define N 8
int layout[N];//布局
int key = 0;
int judge(int row, int col)//判断能否在（row，col）放下
{
int i;for(i = 0;i < row;i++){if(layout[i] == col)return 0;//同一列if(icol)return 0;//同一条主对角线} if(i + layout[i] == row + col)return 0;//同一条副对角线 return 1;
}
void lay(int row)//在row行上放Queen
{
int i;if(row == N)//放完N个Queen输出布局 {
}printf(“n%02d ”, ++key);for(i = 0;i < N;i++)printf(“%c%d ”, layout[i] + 'a', i + 1);} else {for(i = 0;i < N;i++)//在i列上放Queen} {} layout[row] = i;if(judge(row, i))lay(row + 1);
int main()
{
}
lay(0);return 0;
第二篇：数据结构C章节总结
第一章 绪论
数据结构：数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。数据结构被形式地定义为(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合.数据类型：一个值的集合和定义在这个值集上的一组操作的总称；数据运算：对数据施加的一种操作；数据结构和数据类型两个概念之间区别：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
逻辑结构：我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。
物理结构：抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。
数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称；数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据的最小单位。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据结构：是相互之间一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性。数据结构包括逻辑结构（线性结构，如线性表，栈，队，串，数组 和非线性结构如 树结构、图结构）、物理（存储）结构（集合、线性结构、树形结构和图状结构或网状结构）和数据运算如插入、删除、修改、排序、查找。数据结构中，与所使用的计算机无关的数据叫逻辑结构，数据结构在计算机内存中的表示是指数据的存储结构
四大类存储结构：顺序存储、链式存储、索引存储和散列存储。顺序存储包括数据存储（把逻辑上相邻的元素存储在地址连续的存储单位）和数据关系存储（通过连续的物理地址体现关系）；链式存储包括数据存储（把逻辑上相邻的元素存放在物理地址随意的存储单元）和数据关系存储（不仅存放数据本身还存放数据元素的物理地址）
抽象数据类型ADT：一个数学模型以及定义在该模型上的一组操作，包括_数据和操作_两个部分 算法的特性：有穷性（执行有穷步结束）、确定性（确切含义，不会产生二义性）、可行性、输入（零个或多个输入）和输出（一个或多个输出）
算法设计的要求：正确性、可读写、健壮性、效率与低存储量需求。
2、数据的逻辑结构是指图形结构_三种类型，树形结构和图形结构合称为非线性结构_。数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构４种。
17_称为存储结构.1821、算法的执行时间是
371、某算法的时间复杂度为O(n2),表明该算法的_____.2.算法分析的目的是问题规模之间的关系;算法分析的两个主要方面是空间复杂度和时间复杂度
5．在决定选取何种存储结构时，一般不考虑
A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.编程语言实现这种结构是否方便。
10．程序段i ＝ 0；while（i<=n）｛i = i * 3
12数据项的个数要相同，而且对应的数据项的类型要一致 1.数据结构是一门研究非数值计算的程序设计问题中计算机的系和运算等的学科。数据结构式相互之间存在一种或多种特定关系的数据元素的集合。10.数据的运算最常用的有5-1-
第二章 线性表
1.线性表:一个线性表是n个类型相同的数据元素的有限序列。线性表的顺序表示：用一组地址连
续的存储单元依次存储线性表的数据元素。顺序存储结构的特点：优，可随机存取表中任一元素，方便快捷；缺，再插入或删除时，需移动大量元素，数组的静态空间分配。
2.线性结构与非线性结构的不同点：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反
映结点间的逻辑关系是多对多的。
3.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较个结点,4.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行 5.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，删除一个
元素时大约要移动表中的(n-1)/2两种情况下求平均个元素。
6.设单链表中指针p指着结点m，指针f指着将要插入的新结点x，当x插在链表中最后一个结点
m之后时，只要先修改后修改p->link=f即可。
7.在一个长度为n的顺序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移i个元素前插入元素需移动
存储结构需要分配较大空间，插入和删除不需要移动元素的线性表
9、在双向链表存储结构中，删除p所指的结点时需修改指针p所指的结点的前趋结点（若存在）时需修改指针
1.在循环双链表的p所指结点之前插入s所指结点的操作是12.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_结点的双循环链表__存储方式最节省运算时间；某线性表最常用的操作是在最后一个结点之后插
入一个结点或删除第一个结点，故采用_仅有尾指针的单循环链表存储方式最节省运算时间；对
于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为用尾指针表示的循环单链表
14.15.16.17、不带头结点的单链表head为空的判定条件是 带头结点的~是
19、带头结点的双循环表L为空表的条件是。
20、非空的循环单链表head的尾结点(由p所指向)满足21.在一个长度为n(n>1)操作与链表的长度有关；与单链表相比，双链表的优点之一是顺序访问相邻结点更灵活
23线性表的链接存储中，元素之间的逻辑关系是通过链接指针决定的。
24、从顺序表中删除第i个元素时，首先把第i个元素赋给_针开始向后的所有元素均前移一个位置，最后使线性表的长度减1。
25,26、循环单链表L为空的条件是
27、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为。
28、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为，若p为一个数组a中的下标，则其后继结点的下标的a[p].next。
29、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点
时，需要进行的操作为a[j].next=a[i].next和a[i].next=j语句。
第三章 栈和队列
1.栈：是限定仅在表尾进行插入或删除操作的线性表。栈又称为先进后出LIFO的线性表。
2.判定一个栈ST（最多元素为m0）为空的条件是
2.栈的两种存储方法：一是顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存
放自栈底到栈顶的元素；二是栈的链式表示。
3.队列：队列是一种先进先出FIFO的线性表。允许插入的一端叫做队尾rear，允许删除的一段则
称为队头front
4.链队的出队入队操作：s入队,rear->next=s;rear=s;p出队：front->next=p->next
5.顺序队：插入元素：front不变，rear加1；删除元素：rear不变，front加1。判定一个顺序栈
st(最多元素为MaxSize)为空的条件是6.循环队列:空队满队都是rea=r=front为区分,规定循环队列中剩一个元素即为满队,front=rear+1
7.8.9.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行。
10.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时
应执行rear->next=s;rear=s;
11.若己知一个栈的进栈序列是1,2,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1 23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是是(qu->rear+1)%MaxSize==qu->front 列的元素个数是(rear-front+MaxSize)%MaxSize。 24.从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行5.栈顶指针 7.在链表qu中,判定只有一个结点的条件是设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为3。 9.设计一个判别表达式中左、右括号是否配对出现的算法，采用数据结构最佳 例：设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆 列车开出车站的所有可能的顺序。 答：至少有14种①全进之后再出情况,只有1种：4，3，2，1②进3个之后再出的情况，有 3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况,有5种，2,4,3,12,3,4,12,1, 3,4 2,1,4,32,1,3,4④进1个之后再出的情况,有5种，1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,3 第四章 串 1.串：由零个或多个字符组成的有限序列；串中字符的数目n称为串的长度，零个字符的串称为 空串。包含子串的串相应的称为主串，通常称字符在序列中的序号为该字符在串中的位置。 2．空串是，其长度等于度等于其包含的空格个数。组成串的数据元素只能是 单个字符。 4．一个字符串中称为该串的子串。 5.若串S= ‘software’,其子串的数目是字符串长度为n的字串的个数计算公式 :[n+(n-1)+...+ 1+1]） 60．串是一种特殊的线性表，其特殊性体现在61．设有两个串p和q，求q在p中首次出现的位置的运算称为 串：1。KMP算法，求NEXT函数值等。时间：O(n+m)。其中，模式匹配为O（n）；预处理为 O（m）；求两串的最长公共子串，时间为O（n）是不行的，至少要O（n2）。 第五章 数组（线性结构，元素受限，操作不限）和广义表 1.矩阵的压缩存储：是指为多个值相同的元只分配一个存储空间，对零元不分配空间。 2.树的存储结构： 一、双亲表示法：就是用一组连续空间存储树的结点，同时在每个结点中附设 一个指示器指示其双亲的结点在数组中位置。特点：找双亲容易，找孩子难； 二、孩子兄弟表示 法（又称二叉树和二叉链表表示法）链表结构中的两个链域分别指向该结点的的第一个孩子结点 和下一个兄弟结点。操作容易，破坏了树的层次 第六章 树和二叉树 1.树：树是由n个类型相同的元素构成的有限集。 2.二叉树的性质：在二叉树的第i层上至多有2i-1个结点；深度为k的二叉树最多有2k-1个结点； 叶子结点比度为2的结点个数多1。 3.遍历二叉树：先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）。前后序遍历确定 跟，中序遍历确定左右子树，依次判断，方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继 续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定.第七章图 一、图的定义和术语： 1、图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 2、有向图—有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有 向边（也称弧）的有限集合，弧是顶点的有序对，记为 3、无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v），并且（v,w）=(w,v) 4、n个顶点的有向图最大边数是n(n-1)； n个顶点的无向图最大边数是n(n-1)/26、权——与图的边或弧相关的数叫~；简单路径——序列中顶点不重复出现的路径叫~ 14、简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~ 16、连通图——图中任意两个顶点都是连通的叫~；连通分量——非连通图的每一个连通部分叫~ 18、强连通图——有向图中，如果对每一对Vi,VjÎV, Vi¹Vj,从Vi到Vj 和从Vj到 Vi都存在路径 1、深度优先搜索----从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点 出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被 访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止 深度遍历：V1-> V2->V4-> V8->V5->V3->V6->V72、广度优先遍历(BFS)——方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个 未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图 中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作 起点，重复上述过程，直至图中所有顶点都被访问为止 第九章 查找 1.静态查找——拆半查找：确定待查记录所在的范围，然后逐步缩小范围知道找到或找不到该记 录为止。假设low和high分别为待查元素所在范围的上下界，指针mid指示区域中间的位置，mid=[low+high]/2.此处low和high分别为位置而非数值。比较时与mid做比较，比mid大，low=mid+1，反之high=mid-1，mid重新计算。查找成功或失败最多比较关键字个数不超过[log2n]+1 例：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它 将依次与表中20，70，30，50 比较大小，查找结果是失败。 2.静态查找——顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，相等则查找成功，反之失败。平均查找长度：ASL=(n+1)/2 3.二叉排列树：或是一棵空树；或者是具有以下性质的二叉树：1.若它的左子树不空，则左子树 上所有结点的值均小于它的根结点的的值；2.若它的右子树不空，则右子树上所有借点得知均大 于它的根节点的值；3.它的左右子树上也分别为二叉排列树。 c数据结构实验报告 数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____XX40703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;XX年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目 数据结构(C语言版)实验报告 专业：计算机科学与技术、软件工程 学号:____XX40703061___________________ 班级:_________软件二班______________ 姓名:________朱海霞______________ 指导教师:___刘遵仁________________ 青岛大学信息工程学院 XX年10月 实验1 实验题目：顺序存储结构线性表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。 程序代码: #include #include #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int* elem; int length; int listsize; }Sqlist; int InitList_Sq(Sqlist &L){ =(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!)return-1; =0; =LIST_INIT_SIZE; return OK; } int ListInsert_Sq(Sqlist&L,int i,int e){ if(i+1)return ERROR; if(==){ int *newbase; newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int)); if(!newbase)return-1; =newbase; +=LISTINCREMENT; } int *p,*q; q=&(); for(p=&();p>=q;--p) *(p+1)=*p; *q=e; ++; return OK; } int ListDelete_Sq(Sqlist &L,int i,int e){ int *p,*q; if(i)return ERROR; p=&(); e=*p; q=+; for(++p;p *(p-1)=*p; --; return OK; } int main(){ Sqlist L; InitList_Sq(L);//初始化 int i,a={3,-5,6,8,2,-5,4,7,-9}; for(i=1;i ListInsert_Sq(L,i,a); for(i=0;i printf(“ %d”,); printf(“ ”);//插入9个数 ListInsert_Sq(L,3,24); for(i=0;i printf(“ %d”,); printf(“ ”);//插入一个数 int e; ListDelete_Sq(L,2, e); for(i=0;i printf(“ %d”,);//删除一个数 printf(“ ”); return 0; } 实验结果： 3，-5,6,8,2，-5,4,7，-9 3，-5,24,6,8,2，-5,4,7，-9 3,24,6,8,2，-5,4,7，-9 心得体会： 顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。 实验主要步骤： 3、分析、理解给出的示例程序。 4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。 5、修改程序： (1)增加插入结点的功能。 (2)建立链表的方法有“前插”、“后插”法。 程序代码: #include #include #define NULL 0 #define OK 1 #define ERROR 0 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; int InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode));L->next=NULL; return OK; } int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s; int j; p=L;j=0; while(p&&j p=p->next;++j; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode));s->data=e; s->next=p->next; p->next=s; return OK; } int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q; int j; p=L;j=0; while(p->next&&j p=p->next;++j; } if(!(p->next)||j return ERROR; q=p->next;p->next=q->next;e=q->data;free(q); return OK; } int main(){ LinkList L,p; char a={'A','C','E','F','H','J','Q','U'};int i,j; InitList_L(L); for(i=1,j=0;i p=L->next; while(p!=NULL){ printf(“%c ”,p->data);p=p->next;}//插入八个字符 printf(“;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：; 1、掌握栈的顺序存储结构和链式存储结构，以便在实; 2、掌握栈的特点，即后进先出和先进先出的原则; 3、掌握栈的基本运算，如：入栈与出栈 } }//插入八个字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B'); p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一个字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);return 0; 实验结果： A C E F H J Q U A B C E F H J Q U A B E F H J Q U 心得体会： 单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。 实验3 实验题目：栈操作设计和实现 实验目的： 1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈的特点，即后进先出和先进先出的原则。 3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。 实验要求： 回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 实验主要步骤 (1)数据从键盘读入; (2)输出要判断的字符串; (3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。 程序代码: #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define N 100 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;// 在栈构造之前和销毁之后，base的值为NULL int *top;// 栈顶指针 int stacksize;// 当前已分配的存储空间，以元素为单位 } SqStack; int InitStack(SqStack &S) { // 构造一个空栈S if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int)))) exit(OVERFLOW);// 存储分配失败 =; =STACK_INIT_SIZE; return OK; } int StackEmpty(SqStack S) { // 若栈S为空栈，则返回TRUE，否则返回FALSE if(==) return TRUE; else return FALSE; } int Push(SqStack &S, int e) { // 插入元素e为新的栈顶元素 if(>=)// 栈满，追加存储空间 { =(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!) exit(OVERFLOW);// 存储分配失败 =+; +=STACKINCREMENT; } *()++=e; return OK; } int Pop(SqStack &S,int &e) { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==) return ERROR; e=*--; return OK; } int main(){ SqStack s; int i,e,j,k=1; char ch = {0},*p,b = {0}; if(InitStack(s))// 初始化栈成功 { printf(”请输入表达式: “); gets(ch); p=ch; while(*p)// 没到串尾 Push(s,*p++); for(i=0;i if(!StackEmpty(s)){// 栈不空 Pop(s,e);// 弹出栈顶元素 b=e; } } for(i=0;i if(ch!=b) k=0; } if(k==0) printf(”NO!“); else printf(”输出:“) printf(”YES!“); } return 0; } 实验结果： 请输入表达式： abcba 输出：YES! 心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。 实验4 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 程序代码: 实验结果： 心得体会： 实验5 实验题目：图的遍历操作 实验目的： 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。 实验要求： 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。 实验主要步骤： 设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 1.邻接矩阵作为存储结构 #include”“ #include”“ #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs;//顶点表 int edges;//邻接矩阵，可看作边表 int n,e;//图中的顶点数n和边数e }MGraph;//用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//输入顶点数和边数 scanf(”%c“,&a); printf(”Input Vertex string:“); for(i=0;in;i++) { scanf(”%c“,&a); G->vexs=a;//读入顶点信息，建立顶点表 } for(i=0;in;i++) for(j=0;jn;j++) G->edges=0;//初始化邻接矩阵 printf(”Input edges,Creat Adjacency Matrix “); for(k=0;ke;k++){ //读入e条边，建立邻接矩阵 scanf(”%d%d“,&i,&j);//输入边(Vi，Vj)的顶点序号 G->edges=1;;G->edges=1;//若为;//=========定义标志向 量，为 全 局 变 量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1; G->edges=1;//若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 } } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度优先遍历的递归算法====== void DFSM(MGraph *G,int i) { //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 给出你的编码 //===========BFS：广度优先遍历======= void BFS(MGraph *G,int k) { //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 给出你的编码 //==========主程序main ===== void main() { int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph));//为图G请内存空间 CreatMGraph(G);//建立邻接矩阵 printf(”Print Graph DFS: “); DFS(G);//深度优先遍历 printf(” “); printf(”Print Graph BFS: “); BFS(G,3);//以序号为3的顶点开始广度优先遍历 printf(” “); } 2.邻接链表作为存储结构 #include”“ #include”“ #define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex;//邻接点域 struct node *next;//链域 申 }EdgeNode; typedef struct vnode{ //顶点表结点 char vertex;//顶点域 EdgeNode *firstedge;//边表头指针 }VertexNode; typedef VertexNode AdjList;//AdjList是邻接表类型 typedef struct { AdjList adjlist;//邻接表 int n,e;//图中当前顶点数和边数 } ALGraph;//图类型 //=========建立图的邻接表======= void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s;//定义边表结点 printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//读入顶点数和边数 scanf(”%c“,&a); printf(”Input Vertex string:“); for(i=0;in;i++)//建立边表 { scanf(”%c“,&a); G->adjlist.vertex=a;//读入顶点信息 G->adjlist.firstedge=NULL;//边表置为空表 } printf(”Input edges,Creat Adjacency List “); for(k=0;ke;k++){ //建立边表 scanf(”%d%d“,&i,&j);//读入边(Vi，Vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成边表结点 s->adjvex=j;//邻接点序号为j s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;//邻接点序号为i s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//将新结点*S插入顶点Vj的边表头部 } } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度优先遍历的递归算法====== void DFSM(ALGraph *G,int i) { //以Vi为出发点对邻接链表表示的图G进行DFS搜索 给出你的编码 //==========BFS：广度优先遍历========= void BFS(ALGraph *G,int k) { //以Vk为源点对用邻接链表表示的图G进行广度优先搜索 给出你的编码 //==========主函数=========== void main() { int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf(”Print Graph DFS: “); DFS(G); printf(” “); printf(”Print Graph BFS: “); BFS(G,3); printf(” "); } 实验结果： 1.邻接矩阵作为存储结构 2.邻接链表作为存储结构 心得体会： 实验6 实验题目：二分查找算法的实现 实验目的： 掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。 实验要求： 编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。 实验主要步骤： 1.建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。 2.给出算法的递归和非递归代码; 3.如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性? 程序代码 实验结果： 心得体会： 实验7 实验题目：排序 实验目的： 掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。 实验要求： 实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。 实验主要步骤： 程序代码 实验结果： 心得体会： 数据结构与算法课程论文综述 摘要 如何合理的组织数据、高效率的处理数据是扩大计算机应用领域、提高软件效率的关键。在软件开发过程中要求“高效地”组织数据和设计出“好的”算法，并使算法用程序来实现，通过调试而成为软件，必须具备数据结构领域和算法设计领域的专门知识。 《数据结构与算法》课程就是主要学习在软件开发中涉及的各种常用数据结构及其常用算法，在此基础上，学习如何利用数据结构和算法解决一些基本的应用问题。 课程主要内容 本学期一共学习了十章的内容，下面就这十章的内容作了详细的介绍。第一章：数据结构与算法概述 本章主要是对数据、数据类型、数据结构、算法及算法分析等基本概念的掌握，而如何合理地组织数据、高效地处理数据正是扩大计算机领域、提高软件效率的关键，所以对这些概念的理解就显得十分重要。 数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称，其基本单位是数据元素，而数据类型是一个同类值的集合和定义在这个值集上的一组操作的总称。在高级程序语言中定义一种数据类型时，编译程序编译系统就能获得如下信息：（1）、一组性质相同的值的集合；（2）、一个预订的存储体系；（3）、定义在这个值集合上的一组操作。数据结构是指数据元素之间的关系，它包括数据的逻辑结构、存储结构、一组运算集合；数据的逻辑结构分为线性结构和非线性结构。数据的存储方法有：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。接下来便是关于算法的有关概念，算法是为解决一个特定问题而采取的确定的有限步骤集合，它具有有穷性、确定性、可行性、输入和输出。关于算法的性能分析，分为时间性能分析和空间性能分析。第二章：顺序表及其应用 本章主要是对顺序表、顺序表的结构、数据类型、基本算法及相关应用的介绍。顺序表是一种简单而常用的数据结构，其应用范围较为广泛，包括查找问题、排序问题、字符处理问题等内容。第三章：链表及其应用 链表是一种简单、常用的数据结构，与顺序表相比，具有插入、删除结点不需要移动元素，不必事先估计存储空间大小等优点，操作较为灵活。它有六种基本运算：（1）、置空表（2）、求表长（3)、按序号取元素（4）、按值查找 (5)、插入（6）、删除。 单链表即链表的每个结点只有一个指针域，用来存储其直接后继的存储位置。但是这样就使得对结点前面的元素的操作很困难，所以就在每个结点增加一个指向其前驱结点的指针域，从而构成双向链表。同时由于每个结点的地址既存放在其前驱结点的后继指针中，又存放在其后继结点的前驱指针域中，所以双向链表的插入操作分为前插和后插。第四章：堆栈及其应用 首先要明白栈是一种受限制的线性结构，遵守“先进后出”的规则，其插入与删除操作都在栈顶进行。 其次根据顺序存储和链接存储，栈分为顺序栈和链栈。其中顺序栈栈是用地址连续的存储空间依次存储栈中数据元素，并记录当前栈顶数据元素的位置；基本算法包括置空栈、判栈空、判栈满、取栈顶元素、入栈和出栈。而链栈则使用链式存储堆栈的数据元素，并记录当前栈顶数据元素的位置；每个结点包括data数据域：用来存放数据元素的值，next指针域：用来存放其直接后继结点的存储地址，其基本运算和顺序栈相同。 最后是关于堆栈的应用：（1）、数值转换问题；由于在将十进制数N转换为d进制数时，最先得到的余数是d进制数的最低位，在显示结果时需要最后输出；而最后求得的余数是d进制数的最高位，需要最先输出。这与栈的“先入后出”性质相吻合，所以可用栈来存放逐次求得的余数，然后输出。（2）、括号匹配问题；当读取一个表达式时，一旦读到括号就进栈，而读到下一个括号时就与栈中括号比较，若相匹配，则出栈，否则继续读取表达式。到最后，如果栈为空栈，则说明括号匹配，否则括号不匹配。第五章：队列及其应用 首先和栈一样，要知道队列是一种受限制的线性结构，遵守“先进先出”的规则，其插入在队尾、删除在对头。 其次根据顺序存储和链式存储，队列也分为顺序队列和链队列。其中顺序队列是用地址连续的向量空间依次存储队列中的元素，同时记录当前对头元及队尾元素在向量中的位置。然后是链队列，即在存储器中占用任意的、连续或不连续的物理存储区域，使用动态结点空间分配；在这其中，值得注意的是链队列不存在队满的情况。 第六章：特殊矩阵、广义表及其应用 首先是关于矩阵的概念即存储方法； 1、二维数组中元素aij的地址为：（1）、以行序为主存储，Loc（aij）=Loc（a00）+[j*（m+1）+i]*d（2）、以列序为主存储，Loc（aij）=Loc（a00）+[i*（n+1）+j]*d，其中m为行数、n为列数、d为每个元素所占的存储单元的个数。 2、对称矩阵：即将下三角存储在一个一维数组sa[k]中，其中0≤k<(n+1)/2；当i≥j时，k=i*（i+1）/2+j，当i 3、三角矩阵：和对称矩阵的存储思路一样用一维数组sa[k]存储，若是上三角矩阵（下三角中元素均为常数c），则当i≥j时，k=i*（i+1）/2+j，当i 4、对角矩阵：同样存储在一维数组sa[k]中，k=2i+j 5、稀疏矩阵：即矩阵中非零元素个数远远小于矩阵元素个数，可用三元组表存储，将非零元素的值与其行号、列号存放在一起。 其次是关于广义表的概念；广义表是n（n≥0）个元素a1、a2、a3、„、an的有限序列，而ai或是原子或是一个广义表，所以广义表是递归定义。第七章：二叉树及其应用 首先关于二叉树的概念及其性质；二叉树是由n（n≥0）个结点组成的有限集合。在这其中有两种特殊的二叉树，满二叉树和完全二叉树。同时二叉树具有如下五个性质：（1）、在二叉树的第i层上至多有2（i-1）个结点（i>0）（2）、深度为k的二叉树至多有2（k）-1个结点（k>0）（3）、对任意一棵非空二叉树，若果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1（4）、有n个结点的完全二叉树（n>0）的高度为∟log2n」+1（5）、若对满二叉树或完全二叉树按照“从上到下，每层从左到右，根结点编号为1”的方式编号，则编号为i的结点，它的两个孩子结点编号分别为2i和2i+1，它的父节点编号为i/2。 其次是二叉树的存储结构分为顺序存储和链接存储。顺序存储是按在完全二叉树中的编号顺序，依次存储在一维数组中。这样的存储方式可以很方便地找到任一结点的父结点及左右孩子，但对于一般的二叉树会造成很大的空间浪费，且在插入或删除结点时需大量移动节点，不利于运算的实现。那么就引出了二叉树的链接存储，每个结点包括三个域，lchild指针域：记录该结点左孩子的地址、rchild指针域：记录该结点右孩子的地址、data域：存储该结点的信息。 接下来是二叉树的遍历及线索化，不仅要能对二叉树进行遍历、线索化操作，而且还要能够根据给出的遍历结果构造出二叉树。最后是二叉树的应用，例如哈夫曼树：为数据压缩提供了一种方法、二叉排序树：即中序遍历的结果是递增的有序序列。 第八章：树和森林及其应用 首先是关于树和森林的有关概念及存储结构；树或森林与二叉树之间有一个自然地一一对应关系，任何一个森林或一棵树可以唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。在这里，要会如何将树或森林转换成二叉树、二叉树转换成树或森林。对于树的顺序存储结构：双亲表示法，链接存储结构：（1）、孩子表示法（2）、孩子兄弟表示法，只需了解。 其次是树和森林的遍历，要知道树只有先序遍历和后序遍历、森林只有先序遍历和中序遍历，且（1）、树的先序遍历与二叉树的先序遍历相同（2）、树的后序遍历与二叉树的中序遍历相同（3）、森林的先序遍历和中序遍历分别与二叉树的先序遍历和中序遍历结果相同。 最后是树的一个典型应用——B树，它是一种平衡的多路查找树，学习是根据实例走一遍算法，理解算法即可。第九章：散列结构及其应用 散列结构是以存储结点中的关键字作为自变量，通过确定的函数H（即散列函数或哈希函数）进行计算，把所求的函数值作为地址存储该结点。 首先是散列函数有：（1）、直接定址法（2）、除留余数法（3）、数字分析法（4）、平方取中法（5）、折叠法 其次是冲突处理，由于散列函数很可能将不同的关键字计算出相同的散列地址，所以就需要为发生冲突的关键字结点找到一个“空”的散列地址。冲突处理的方法有 1、开放定址法：Hi=（H（key）+di）mod m，i=1,2,3，„，K（K≤m-1）例如（1）、线性探测再散列，取di=1,2,3，„，m-1（2）、二次探测再散列，取di=1（2），-1（2），2（2），-2（2），„（3）、伪随机探测再散列，取di=伪随机数； 2、链地址法：在散列表的每一个存储单元中增加一个指针域，把产生冲突的关键字以链表结构存放在指针指向的单元中。第十章：图及其应用 首先是图的有关概念；图是一种数据结构，可以用二元组表示，形式化定义为：Graph（V，VR），其中V={x|x∈dataobject}，R={VR}，VR={＜x，y＞ P（x，y）∧（x，y∈V）}。顶点的度、入度和出度，以顶点V为头的弧的数目称为V的入度，以顶点V为尾的弧的数目称为V的出度，而出度与入度之和即为顶点V的度。 其次是图的存储结构；（1）、邻接矩阵（2)、邻接表 最后的图遍历和图的典型应用；对于遍历图的深度优先算法或广度优先算法、最小生成树的普利姆算法或克鲁斯卡尔算法、最短路径的迪杰特斯拉算法和弗洛伊德算法以及有向无环图拓扑排序算法，都需要根据实例走一遍算法，从而掌握这些算法。 心得体会 最开始学习这门课时，我对它没有很深刻的认识，只是听说这门课比较难。学习起来会比较累。通过这一学期的学习也确实证实了这一点。在学习这门课的过程中自己也确实遇到了一些问题，主要是书本上的知识与老师的讲解都比较容易理解，但是当自己利用已学的知识编写程序时就感到非常的棘手，很多时候都是把大概的算法思想想出来后，又把书本上的程序抄写一遍来完成程序的编写。针对这一问题以后自己会尽量学习摆脱掉书本，自己慢慢学会独立编写程序。 结语 通过对数据结构与算法的整理和实际应用，我深刻了解到数据结构与算法的重要性，同时也加深了对它的认识和了解，了解到了数据结构与算法在生活、工作等生活各个方面的重要性和不可缺少性。我通过整理数据结构与算法的学习而获得的极大收获。我相信这次的学习会对我以后的学习和工作产生非常大的影响力。 参考文献 《数据结构与算法》（第二版）王昆仑 李红 主编 《数据结构》课程设计题目(程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include typedef struct _RingNode { int pos; struct _RingNode *next;}RingNode, *RingNodePtr; // 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 void CreateRing(RingNodePtr pHead, int count){ RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr =(RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead;// 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n){ RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr!= NULL) { if(i == n) { // 踢出环 printf(“n%d”, pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if(pPrev == pCurr) { // 最后一个 printf(“nKing is %d”, pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main(){ int n = 0, m = 0; RingNodePtr pHead = NULL; printf(“M(person count)= ”); scanf(“%d”, &m); printf(“N(out number)= ”); scanf(“%d”, &n); if(m <= 0 || n <= 0) { printf(“Input Errorn”); return 0; } // 建立链表 pHead =(RingNodePtr)malloc(sizeof(RingNode)); pHead->pos = 1; pHead->next = NULL; CreateRing(pHead, m);// 开始出圈 printf(“nKick Order: ”); KickFromRing(pHead, n); printf(“n”); system(“pause”); return 0;} //数组做： #include void SelectKing(int MonkeyNum, int CallNum); void main(){ int MonkeyNum; int CallNum; /* 输入猴子的个数 */ printf(“Monkey Num = ”); scanf(“%d”, &MonkeyNum); /* 输入M的值 */ printf(“Call Num = ”); scanf(“%d”, &CallNum); SelectKing(MonkeyNum, CallNum); } void SelectKing(int MonkeyNum, int CallNum){ int *Monkeys;// 申请一个数组，表示所有的猴子； int counter = 0;//计数，当计数为猴子个数时表示选到最后一个猴子了； int position = 0;// 位置，数组的下标，轮流遍历数组进行报数； int token = 0;// 令牌，将报数时数到M的猴子砍掉； // 申请猴子个数大小的数组，把桌子摆上。 Monkeys =(int *)malloc(sizeof(int)* MonkeyNum); if(NULL == Monkeys) { printf(“So many monkeys, system error.n”); return; } // 将数组的所有内容初始化为0，被砍掉的猴子设置为1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循环，直到选中大王 while(counter!= MonkeyNum) { // 如果这个位置的猴子之前没有砍掉，那么报数有效 if(Monkeys[position] == 0) { token++;// 成功报数一个，令牌+1，继续报数直到等于M // 如果报数到M，那么将这个猴子砍去 if(token == CallNum) { Monkeys[position] = 1;// 设置为1，表示砍去 counter++;// 计数增加 token = 0;// 设置为0，下次重新报数 // 如果是最后一个猴子，把它的位置打印，这个就是大王了 if(counter == MonkeyNum) { printf(“The king is the %d monkey.n”, position+1); } } } // 下一个猴子报数 position =(position + 1)%MonkeyNum; } // 释放内存，开头为所有猴子创建的桌子 free(Monkeys); return;} 题目2 ：字符逆转（学时：3） 从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。 #include struct node { struct node *prev; char c; struct node *next;};struct node *input(struct node *top);int main(void){ struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c=' ';bottom=input(top);p=bottom->prev;while(p!=NULL){ printf(“%c”,p->c); p=p->prev;} return 0;} struct node *input(struct node *top){ struct node *t;char x;while((x=getchar())!='n'){ top->c=x;t=(struct node *)malloc(sizeof(struct node));top->next=t;t->prev=top;t->next=NULL;t->c=' ';top=top->next; } } return top;题目3 ：工资核算（学时：3） 设有一个单位的人员工资有如下信息：name、department、base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。 #include char name[100];char department[100]; int basepay; int allowance; int total;}stuff[SIZE];main(){ FILE *fp; int i; printf(“Please enter name department basepay allowance：n”); for(i=0;i scanf(“%s %s %f %f”,&stuff[i].name,&stuff[i].department,&stuff[i].basepay,&stuff[i].allowance); if((fp=fopen(“paydata.dat”,“wb”))==NULL) { printf(“Can't open filen”); return 0;} for(i=0;i if(fwrite(&stuff[i],LENTH,1,fp)!=1) printf(“文件写入出错n”); fclose(fp); if((fp=fopen(“paydata.dat”,“rb”))==NULL) { } printf(“Can't open filen”); printf(“修改过后的结果：n”); for(i=0;i { fread(&stuff[i],LENTH,1,fp); stuff[i].total=stuff[i].basepay+100+stuff[i].allowance; printf(“%-10s%-10s %f %f %fn”,stuff[i].name,stuff[i].department,stuff[i].basepay+100,stuff[i].allowance,stuff[i].total); } fclose(fp);return 0;} 题目4：满足条件的有序表生成（学时：3） 已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。 #include int a[7],b[5],c[6],d[7]; int i,j,k,t,m;printf(“nPlease enter 7 numbers of A:”);for(i=0;i<7;i++)scanf(“%d”,&a[i]);for(j=0;j<6;j++) for(i=0;i<6-j;i++) if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers：n”);for(i=0;i<7;i++)printf(“%5d”,a[i]); printf(“nPlease enter 5 numbers of B:”); for(i=0;i<5;i++)scanf(“%d”,&b[i]);printf(“n”);for(j=0;j<4;j++)for(i=0;i<4-j;i++) if(b[i]>b[i+1]){t=b[i];b[i]=b[i+1];b[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<5;i++)printf(“%5d”,b[i]); printf(“nPlease enter 6 numbers of C:”); for(i=0;i<6;i++)scanf(“%d”,&c[i]); for(j=0;j<5;j++) for(i=0;i<5-j;i++) if(c[i]>c[i+1]){t=c[i];c[i]=c[i+1];c[i+1]=t;} printf(“the sorted numbers：n”);for(i=0;i<6;i++)printf(“%5d”,c[i]);printf(“n”); for(i=0;i<5;i++){ for(j=0;j<6;j++){ if(b[i]==c[j]){ for(k=0;k<7;k++){ if(b[i]==a[k]) } } } } a[k]=m; printf(“n”);k=0;for(i=0;i<7;i++) if(a[i]!=m){ } printf(“生成的有序表d为 ”);for(i=0;i printf(“%4d”,d[i]);d[k]=a[i];k++;printf(“n”);} 题目5：一元 多项式的减法（学时：6） 设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。 #include struct Polynode { int coef;int exp;Polynode *next;}Polynode,*Polylist;void Polycreate(Polylist head){ } void Polyadd(Polylist polya,Polylist polyb){ Polynode *p,*q,*tail,*temp;int sum;p=polya->next;Polynode *rear,*s;int c,e;rear=head;printf(“请输入多项式的系数项和指数项”);scanf(“%d,%d”,&c,&e);while(c!=0){ } rear->next=NULL;s=(Polynode*)malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf(“%d,%d”,&c,&e); q=polyb->next;tail=polya;while(p!=NULL&&q!=NULL){ if(p->exp sum=p->coef+q->coef;if(sum!=0){ } else { temp=p;p->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next;free(temp); } } } } p=p->next;free(temp);q=q->next;free(temp);else { } tail->next=q;tail=q;q=q->next;if(p!=NULL)tail->next=p;else tail->next=q;void Polysubstract(Polylist polya,Polylist polyb){ Polylist h=polyb;Polylist p=pb->next;Polylist pd;while(p){p->coef*=-1;p=p->next;} pd=Polyadd(pa,h);for(p=h->next;p;p=p->next)p->coef*=-1;return pd； } void PrintPolyn(Polyn P) void printfPolyn(Polynode *head){ Polynode *p=head->next;while(p){printf(“%dx^%d”,p->coef,p->exp);if(p->next)printf(“+”);p=p->next;} } int main(){ Polynode *La,Lb;La=Polycreate();Lb=Polycreate();PrintPolyn(La);printf(“/n”);PrintPolyn(Lb); } printf(“/n”);Polyadd(polya,polyb);printPolyn(polya);return 0; 题目6：床位分配（学时：6） 某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。 #include typedef struct Room { int roomlevel;int roomnum;int bednum;int peoplenum;int bed[N];int sex;char name[10];struct Room *next;}Room;Room *creat(int roomlevel,int room[],int bed[]){ Room *head,*p,*q; int i=1,j,h,num=1; head=(Room *)malloc(sizeof(Room));head->peoplenum=0;q=head;while(i<=roomlevel) { for(j=1;j<=room[i];j++) { p=(Room *)malloc(sizeof(Room)); p->roomlevel=i;p->roomnum=num++; p->sex=-1; for(h=0;h q->next=p; q=p;} i++;} p->next=NULL; p->peoplenum=0; return(head);} void Init(Room *head){ Room *p;int i;p=head;while(p!=NULL){ p->peoplenum=0; p->sex=-1; for(i=0;i p->bed[i]=0; p=p->next;} printf(“nn 操作成功} void Getin(Room *head){ Room *p;n”); int i,s,lev,age;char name[10];int number=0;int bednumber=0;printf(“nn 欢迎使用订房系统 nn”); printf(“请输入性别（1为男，2为女）：”); scanf(“%d”,&s);printf(“nn 请输入想入住的房间等级：”);scanf(“%d”,&lev);p=head->next;while(p!=NULL){ if((p->roomlevel==lev)&&((p->sex==s)||(p->sex==-1))){ } for(i=0;i if(p->bed[i]==0){ } if(number!=0)break;number=p->roomnum;bednumber=i+1;p->bed[i]=1;p->sex=s;p->peoplenum++;break; } p=p->next;if(number==0&&bednumber==0) else { head->peoplenum++; printf(“n订单已下，请输入客人信息: n”);printf(“n 满客 n”); printf(“名字:n”);scanf(“%s”,name); printf(“年龄 :n”);scanf(“%d”,&age); printf(“您的订单3:n”); printf(“名字 年龄 性别 到达时间 房间等级 房间号 床位号n”); if(s==1) printf(“%s %d male 11-19 %d %d %dn”,name,age,p->roomlevel,p->roomnum,bednumber); else printf(“%s %d formale 11-19 %d %d %d n”,name,age,p->roomlevel,p->roomnum,bednumber); } printf(“n”); } void Checkout(Room *head){ Room *p;int number,bednumber,i,s;printf(“欢迎使用退房系统：”);printf(“nn 请输入房间号：”);scanf(“%d”,&number);printf(“nn 请输入性别（1为男，0为女）：”);scanf(“%d”,&s);printf(“请输入床位号：”);scanf(“%d”,&bednumber);p=head->next;while(p!=NULL){ if(p->roomnum==number) for(i=0;i roomlevel;i++) if(i+1==bednumber){ p->bed[i]=0;p->peoplenum--;if(p->peoplenum<0) p->peoplenum=0; } } } if(p->peoplenum==0) p->sex=-1; printf(“您已退房，欢迎下次光临”);break;p=p->next;void Display(Room *head){ Room *p;int i=0;p=head->next;printf(“nn已订房间查询”);if(head->peoplenum==NULL){ printf(“所有等级房间空房”); return;} while(p->peoplenum!=NULL){ if(p->sex==1) printf(“n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：男”,p->roomnum,p->roomlevel,p->peoplenum); else printf(“n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：女”,p->roomnum,p->roomlevel,p->peoplenum); } void main(){ int n,k=1,i,roomlevel,room[10],bed[10],sum=0; Room *head; printf(“请输入房间等级数:n”);printf(“Roomlevel:”);scanf(“%d”,&roomlevel);for(i=1;i<=roomlevel;i++) { printf(“n %d等级房间数:”,i); } printf(“n”);p=p->next; while(i peoplenum) if(p->bed[i]==1) { printf(“，已住床位号：%d”,i+1); i++; } } scanf(“%d”,&room[i]);printf(“n %d房间内床位数:”,i); scanf(“%d”,&bed[i]);sum+=room[i]*bed[i];head=creat(roomlevel,room,bed); while(k==1) { printf(“ n欢迎光临 :n”); printf(“1:订房n2:退房n3:查询n4:退出系统n”); printf(“请输入您的选择:n”); scanf(“%d”,&n); switch(n) { case 1: Getin(head);break; case 2: Checkout(head);break; case 3: Display(head);break; case 4: k=0;break; default : printf(“Error！please input again:”);break; } } } 题目7：文本文件单词的检索及计数（学时：6） 要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。 #include }SW; void CreatTextFile(){ char filename[10],ch; FILE*fp; printf(“请输入所用的文件名:”);scanf(“n%s”,filename);fp=fopen(filename,“w”); printf(“请输入一段文字，以$号结束:n”);scanf(“%s”,&ch); while(ch!='$'){ fwrite(&ch,sizeof(ch),1,fp); } scanf(“%c”,&ch); } fclose(fp);void CountWord(){ FILE *fp;SW S,T;char ch;char filename[10]; int i=0,number=0; printf(“输入文本文件名：”); scanf(“%s”,filename);fp=fopen(filename,“r”); printf(“输入要统计计数的单词：”); scanf(“%s”,T.ch); while(!feof(fp)){ ch= fgetc(fp); if(ch==' ') { if(i!=0){ S.ch[i]=' ';i=0; } } } if(strcmp(S.ch,T.ch)==0)number++;else if(ch=='n'){ if(i!=0) } else { } S.ch[i]=ch;i++;{ S.ch[i]=' '; i=0; } if(strcmp(S.ch,T.ch)==0)number++;if(number==0)printf(“单词不在文本中 n”);else printf(“单词%s在文件%s中共出现了%d次:”,T.ch,filename,number); fclose(fp);} void SearchWord(){ FILE*fp;SW S,T;char filename[10]; int i,i_r,line,flag=0;char ch;printf(“n输入文本文件名：”); scanf(“%s”,filename);fp=fopen(filename,“r”);printf(“输入要统计计数的单词：”); scanf(“%s”,T.ch); i=i_r=0;line=1;while(!feof(fp)){ ch=fgetc(fp); if(ch==' ') { if(i!=0) { i_r++;S.ch[i]=' '; i=0; if(strcmp(T.ch,S.ch)==0){ printf(“%s单词第一次出现是在n”,T.ch,line,i_r); %d 行,%d列 flag=1; break; } } } else if(ch=='n') { if(i!=0) { i_r++;S.ch[i]=' '; if(strcmp(T.ch,S.ch)==0){ printf(“%s单词第一次出现是在n”,T.ch,line,i_r); flag=1; break; } i=0;i_r=0;line++; } else { line++;i_r=0; } } else { %d 行,%d列 S.ch[i]=ch;i++;} } if(flag==0) printf(“%s单词不在文本中n”,T.ch); fclose(fp);} int main(){ } CreatTextFile();CountWord();SearchWord(); 题目8：二叉树的遍历（学时：6） 二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。 #include b=NULL;else { b=(BTNode *)malloc(sizeof(BTNode)); b->data=ch; b->lchild=CreatBTree();//递归先序建立左子树 b->rchild=CreatBTree();//递归先序建立右子树 } return b;} void PreOrder(BTNode *b)//递归先序遍历二叉树函数 { if(b!=NULL) { printf(“%c ”,b->data); PreOrder(b->lchild); PreOrder(b->rchild); } } void InOrder(BTNode *b)//非递归中序遍历二叉树函数 { BTNode *stack[M],*p;int top=-1;if(b!=NULL){ p=b; while(top>-1||p!=NULL) { while(p!=NULL)//扫描p的所有左结点并入栈 { top++; stack[top]=p; } p=p->lchild;if(top>-1){ p=stack[top];//出栈访问结点 top--;printf(“%c ”,p->data); p=p->rchild;//扫描p的右结点 } } printf(“n”);} } void PostOrder(BTNode *b)//非递归后序遍历二叉树函数 { BTNode *stack[M],*p;int sign,top=-1;if(b!=NULL){ do { while(b!=NULL)// b所有左结点入栈 { top++; stack[top]=b; b=b->lchild; } p=NULL;// p指向栈顶前一个已访问结点 sign=1; //置b为已访问 while(top!=-1 && sign){ b=stack[top];//取出栈顶结点 if(b->rchild==p)//右孩子不存在或右孩子已访问则访问b { printf(“%c ”,b->data); top--;p=b;//p指向被访问的结点 } else { b=b->rchild;//b指向右孩子结点 sign=0;//置未访问标记 } } }while(top!=-1); printf(“n”);} } void change(BTNode *b) //左右子树交换(递归){ BTNode *r;r=(BTNode *)malloc(sizeof(BTNode));int f1=0,f2=0;if(b==0)return; //树为空时，跳出 if(b->lchild){ change(b->lchild); r->lchild=b->lchild; f1++; //有左子树，符号位不为空 } if(b->rchild){ change(b->rchild); r->rchild=b->rchild; f2++; //有右子树，符号位不为空 } if(f1==0)r->lchild=NULL; //否则，给中间变量赋空值 if(f2==0)r->rchild=NULL;if(f1||f2){ b->rchild=r->lchild; //左右子树交换 b->lchild=r->rchild;} } int max(int m,int n){ } if(m>n)return m;else return n;int count(BTNode *b) //计算树高(递归){ if(b==NULL) return 0;else return(1+max(count(b->lchild),count(b->rchild)));} int main() { BTNode *root = NULL; printf(“-----------------二叉树的遍历-----------------nn”); printf(“请按先序递归顺序创建二叉树(结束符 #):n”); root = CreatBTree(); printf(“n递归先序遍历结果:n”); PreOrder(root); printf(“n非递归中序遍历结果:n”); InOrder(root); printf(“非递归后序遍历结果:n”); PostOrder(root); printf(“n树高: %dn”,count(root));printf(“n左右子树交换位置:”); change(root); printf(“n递归先序遍历结果:n”); PreOrder(root); printf(“n非递归中序遍历结果:n”); InOrder(root); printf(“非递归后序遍历结果:n”); PostOrder(root); return 0; 题目9：创建二叉排序树（学时：3） 二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。 #include typedef struct node { int data;struct node *lchild ,*rchild;}BSTNode,*BSTTree; //二叉排序树的插入（递归算法）void InsertBST(BSTTree *BST , int key){ } if((*BST)==NULL){ } else if((*BST)->data>key)//如果待插入的元素比根结点元素值小 InsertBST(&((*BST)->lchild),key);//插入在根结点的左子树(*BST)=(BSTNode*)malloc(sizeof(BSTNode));(*BST)->data=key;(*BST)->lchild=NULL;(*BST)->rchild=NULL;else InsertBST(&((*BST)->rchild),key);//插入在根结点的右子树上 //创建一棵二叉排序树 BSTTree CreateBSTTree(){ } //中序遍历 void InOrder(BSTTree BST){ if(BST!=NULL){ } InOrder(BST->lchild);printf(“%5d”,BST->data);InOrder(BST->rchild);BSTTree bst=NULL;int x;while(1){ } return bst; scanf(“%d”,&x);if(x==00)break;InsertBST(&bst,x);} void main(){ BSTTree BST; printf(“建立二叉排序树，请输入序列:n”); BST=CreateBSTTree(); printf(“中序遍历后输出的该序列为:”);InOrder(BST); printf(“n”); } 题目10：霍夫曼编码应用（学时：3） 假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。 #include char ch; int parent,lchild,rchild;}HTNode; typedef struct{ char ch; char bits[n+1]; }CodeNode; typedef struct { char cha;int number;}COUNTER; int Init(HTNode ht[])//初始化函数，为每一个字母信息赋权值 { int i,s=1;COUNTER counter[27];char ch;printf(“请输入字符：n”);scanf(“%c”,&ch);counter[1].cha='A';counter[2].cha='B';counter[3].cha='C';counter[4].cha='D'; counter[5].cha='E';counter[6].cha='F';counter[7].cha='G';counter[8].cha='H';counter[9].cha='I';counter[10].cha='J';counter[11].cha='K';counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16].cha='P';counter[17].cha='Q'; counter[18].cha='R'; counter[19].cha='S';counter[20].cha='T';counter[21].cha='U';counter[22].cha='V';counter[23].cha='W';counter[24].cha='X';counter[25].cha='Y';counter[26].cha='Z';for(i=1;i<=26;i++)counter[i].number=0;while(ch!=' '){ switch(ch){ case 'A':counter[1].number++;break;case 'B':counter[2].number++;break;case 'C':counter[3].number++;break;case 'D':counter[4].number++;break;case 'E':counter[5].number++;break;case 'F':counter[6].number++;break;case 'G':counter[7].number++;break;case 'H':counter[8].number++;break;case 'I':counter[9].number++;break;case 'J':counter[10].number++;break;case 'K':counter[11].number++;break;case 'L':counter[12].number++;break;case 'M':counter[13].number++;break;case 'N':counter[14].number++;break;case 'O':counter[15].number++;break; case 'P':counter[16].number++;break; case 'Q':counter[17].number++;break;case 'R':counter[18].number++;break;case 'S':counter[19].number++;break;case 'T':counter[20].number++;break;case 'U':counter[21].number++;break;case 'V':counter[22].number++;break;case 'W':counter[23].number++;break;case 'X':counter[24].number++;break; } } case 'Y':counter[25].number++;break;case 'Z':counter[26].number++;break;} scanf(“%c”,&ch);for(i=1;i<=26;i++){ } s=s-1;return s;if(counter[i].number!=0){ } ht[s].weight=counter[i].number;ht[s].ch=counter[i].cha;s++; void select(HTNode ht[],int q,int *p1,int *p2)//select函数 { int i,j,x=0,y=0;for(j=1;j<=q;++j){ } if(ht[j].parent==0){ } x=j;break;for(i=j+1;i<=q;++i){ } for(j=1;j<=q;++j){ } for(i=j+1;i<=q;++i){ if(ht[i].weight //选出第二小结点 if(ht[j].parent==0&&x!=j){ } y=j;break;if(ht[i].weight //选出最小结点 } } } if(x>y){ } else { } *p1=x;*p2=y;*p1=y;*p2=x;void huffman_setup(HTNode ht[],int s){ int i,a;int p1,p2;a=2*s-1;for(i=1;i<=a;i++){ if(i<=s){ } else { ht[i].weight=ht[i].weight; } } } ht[i].weight=0;ht[i].parent=ht[i].lchild=ht[i].rchild=0;for(i=s+1;i<=a;++i) //建立赫夫曼树 { } select(ht,i-1,&p1,&p2);ht[p1].parent=i;ht[p2].parent=i;ht[i].lchild=p1;ht[i].rchild=p2;ht[i].weight=ht[p1].weight+ht[p2].weight;void huffman_show(CodeNode hc[],HTNode ht[],int s)//给字符编码 { char q[n];int i,p,c,f;q[s-1]=' ';for(i=1;i<=s;i++) { p=s-1;for(c=i,f=ht[i].parent;f;c=f,f=ht[f].parent){ } } if(ht[f].lchild==c){ } else { } q[--p]='1';q[--p]='0';strcpy(hc[i].bits,&q[p]);} hc[i].ch=ht[i].ch;//-----------------编码 void huffman_code(CodeNode hc[]){ int i=1;char ch,ah;printf(“请输入编码的信息：n”);scanf(“%c”,&ch);printf(“编码是：n”);while(ch!=' '){ ah=hc[i].ch;while(ch!=ah){ } i++;ah=hc[i].ch;printf(“%s”,hc[i].bits);scanf(“%c”,&ch);i=1; } } //-----------------解码 void huffman_read(HTNode ht[],int s)//根据编码来返回字母信息 { int i,j,t;char b;t=2*s-1;i=t;printf(“进行解码n”);fflush(stdin);scanf(“%c”,&b);printf(“解码后的信息是：n”);while(b!=' '){ if(b=='0')i=ht[i].lchild;else i=ht[i].rchild;if(ht[i].lchild==0){ } } } printf(“%c”,ht[i].ch);j=i;i=t;scanf(“%c”,&b);int main(){ int flag=1,choice;int s,i;HTNode ht[m];CodeNode hc[n];printf(“霍夫曼树：n”);s=Init(ht);huffman_setup(ht,s);huffman_show(hc,ht,s);for(i=1;i<=s;i++){ } while(flag){ printf(“%c---> %sn”,hc[i].ch,hc[i].bits); } } printf(“请输入您想要进行的操作：n 1 编码n 2 解码n 3 退出n”);fflush(stdin);scanf(“%d”,&choice);switch(choice){ case 1: huffman_code(hc);printf(“n”);break; case 2: } huffman_read(ht,s);printf(“n”);break; case 3: flag=0;return 0;题目11：关键路径寻找（学时：6） 对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。 #include第三篇：c数据结构实验报告
第四篇：数据结构学习总结
第五篇：数据结构经典题目及c语言代码总结
点击咨询 