北理工数据结构实验报告

《数据结构与算法设计》实验报告——实验一学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固线性表的相关操作；2.熟悉VC环境，加强编程、调试的练习；3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作；4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。

二、实验内容1、采用单向环表实现约瑟夫环。

请按以下要求编程实现：①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。

环表中的结点编号依次为1，2，……，m。

②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。

三、程序设计1、概要设计为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。

（1）、单向环表的抽象数据类型定义为：ADT Joseph{数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={ <ai-1,ai>|ai∈D,i=1,2,……,n}基本操作：create(&L,n)操作结果：构造一个有n个结点的单向环表L。

show(L)初始条件：单向环表L已存在。

操作结果：按顺序在屏幕上输出L的数据元素。

Josephf( L,m,s,n)初始条件：单向环表L已存在， s>0,n>0，s<m。

操作结果：返回约瑟夫环的计算结果。

}ADT Joseph（2）、主程序流程主程序首先调用create(&L,n)函数，创建含有m个节点的单向环表L，然后调用show(L)函数，顺序输出链表中的数据，最后调用Josephf( L,m,s,n)函数，依次输出报的数。

（3）、函数调用关系图2、详细设计(1)、数据类型设计typedef int ElemType; //定义元素类型typedef struct Lnode{ElemType data;struct Lnode *next;}Lnode,*Linklist; //定义节点类型，指针类型（2）、操作算法程序实现：void create(Linklist &L,int m){//生成一个具有m个结点的单向环表，环表中的结点编号依次为1，2，……，m Linklist h,p;L=(Linklist)malloc(sizeof(Lnode));L->data = 1;h=L;for(int i=2;i<=m;i++){p = (Linklist)malloc(sizeof(Lnode));p->data = i; //生成新节点，数据为节点编号h->next = p;h = p; //插入链表}h->next = L; //形成循环链表}void show(Linklist L,int m){//从第一个节点开始依次输出节点编号printf("The numbers of the list are: \n"); //提示用户Linklist h;h=L;for(int i=1;i<=m;i++){printf("%d ",h->data);h = h->next;}printf("\n");}void Josephf(Linklist &L,int m,int s,int n){//实现约瑟夫环Linklist h,q;h = L;q = L;while(h->data != s) //定位开始的节点h = h->next;while(q->next!=h) //定位在开始位置的上一个节点q = q->next;for(int j=1;j<=m;j++){int i=1;while(i<n){q=q->next;i++;}printf("%d ",q->next->data); //依次输出报号为n的节点q->next = q->next->next; //删除已输出节点}printf("\n");}（3）、主程序的代码实现：int main(){int s,m,n;Linklist L;printf("请输入节点数m：\n");scanf("%d",&m);create(L,m); //建立循环链表show(L,m); //输出链表数据printf("请输入起始位置s：\n");scanf("%d",&s);printf("请输入报的数n：\n");scanf("%d",&n);Josephf(L,m,s,n); //输出所报数字return 0;}四、程序调试分析1.引用标识符&不符合C语言语法，应使用C++;2.为了实现循环链表，建立时应该不设头结点且第一个节点就存储编号数据；3.删除节点时要定位到前一个指针，所以在定位开始位置后还要再定位到前一个指针；4.输出时要注意增加“ ”（空格）和“\n”（换行），使输出易于辨识。

数据结构实验报告实验总结本次数据结构实验主要涉及线性表、栈和队列的基本操作以及链表的应用。

通过实验，我对这些数据结构的特点、操作和应用有了更深入的了解。

下面对每一部分实验进行总结。

实验一：线性表的基本操作线性表是一种常见的数据结构，本实验要求实现线性表的基本操作，包括插入、删除、查找、遍历等。

在实验过程中，我对线性表的结构和实现方式有了更清晰的认识，掌握了用数组和链表两种方式实现线性表的方法。

实验二：栈的应用栈是一种后进先出（LIFO）的数据结构，本实验要求利用栈实现简单的括号匹配和后缀表达式计算。

通过实验，我了解到栈可以方便地实现对于括号的匹配和后缀表达式的计算，有效地解决了对应的问题。

实验三：队列的应用队列是一种先进先出（FIFO）的数据结构，本实验要求利用队列实现银行排队和迷宫求解。

通过实验，我对队列的应用有了更加深入的了解，了解到队列可以解决需要按顺序处理的问题，如排队和迷宫求解等。

实验四：链表的应用链表是一种常用的数据结构，本实验要求利用链表实现学生信息管理系统。

通过实验，我对链表的应用有了更深入的了解，了解到链表可以方便地实现对于数据的插入、删除和修改等操作，并且可以动态地调整链表的长度，适应不同的需求。

通过本次实验，我掌握了线性表、栈、队列和链表的基本操作，并了解了它们的特点和应用方式。

同时，通过实际编程的过程，我对于数据结构的实现方式和效果有了更直观的认识，也锻炼了自己的编程能力和解决问题的能力。

在实验过程中，我遇到了一些问题，如程序逻辑错误和内存泄漏等，但通过调试和修改，最终成功解决了这些问题，对自己的能力也有了更多的信心。

通过本次实验，我深刻体会到了理论与实践的结合的重要性，也对于数据结构这门课程有了更加深入的理解。

总之，本次数据结构实验给予了我很多有益的启发和收获，对于数据结构的概念、特点和应用有了更深入的理解。

在以后的学习中，我会继续加强对数据结构的学习和研究，不断提高自己的编程能力和解决问题的能力。

一、实验背景数据结构是计算机科学中一个重要的基础学科，它研究如何有效地组织和存储数据，并实现对数据的检索、插入、删除等操作。

为了更好地理解数据结构的概念和原理，我们进行了一次数据结构实训实验，通过实际操作来加深对数据结构的认识。

二、实验目的1. 掌握常见数据结构（如线性表、栈、队列、树、图等）的定义、特点及操作方法。

2. 熟练运用数据结构解决实际问题，提高算法设计能力。

3. 培养团队合作精神，提高实验报告撰写能力。

三、实验内容本次实验主要包括以下内容：1. 线性表（1）实现线性表的顺序存储和链式存储。

（2）实现线性表的插入、删除、查找等操作。

2. 栈与队列（1）实现栈的顺序存储和链式存储。

（2）实现栈的入栈、出栈、判断栈空等操作。

（3）实现队列的顺序存储和链式存储。

（4）实现队列的入队、出队、判断队空等操作。

3. 树与图（1）实现二叉树的顺序存储和链式存储。

（2）实现二叉树的遍历、查找、插入、删除等操作。

（3）实现图的邻接矩阵和邻接表存储。

（4）实现图的深度优先遍历和广度优先遍历。

4. 算法设计与应用（1）实现冒泡排序、选择排序、插入排序等基本排序算法。

（2）实现二分查找算法。

（3）设计并实现一个简单的学生成绩管理系统。

四、实验步骤1. 熟悉实验要求，明确实验目的和内容。

2. 编写代码实现实验内容，对每个数据结构进行测试。

3. 对实验结果进行分析，总结实验过程中的问题和经验。

4. 撰写实验报告，包括实验目的、内容、步骤、结果分析等。

五、实验结果与分析1. 线性表（1）顺序存储的线性表实现简单，但插入和删除操作效率较低。

（2）链式存储的线性表插入和删除操作效率较高，但存储空间占用较大。

2. 栈与队列（1）栈和队列的顺序存储和链式存储实现简单，但顺序存储空间利用率较低。

（2）栈和队列的入栈、出队、判断空等操作实现简单，但需要考虑数据结构的边界条件。

3. 树与图（1）二叉树和图的存储结构实现复杂，但能够有效地表示和处理数据。

《数据结构与算法统计》实验报告——实验三学院：班级：学号：姓名：一、实验目的1 熟悉VC环境，学会使用C++解决关于二叉树的问题。

2 在上机、调试的过程中，加强对二叉树的理解和运用。

3 锻炼动手编程和独立思考的能力。

二、实验内容遍历二叉树。

请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。

三、程序设计1、概要设计为实现上述程序功能，首先需要二叉树的抽象数据结构。

⑴二叉树的抽象数据类型定义为：ADT BinaryTree {数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D=Φ，则R=Φ，称BinaryTree为空二叉树；若D≠Φ，则R={H}，H是如下二元关系；（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ；（3）若D1≠Φ，则D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的关系H1 ⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr ⊆H；H={<root,x1>,<root,xr>,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作：CreatBiTree(BiTree &T)操作结果：按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTree T,int (*visit)(char e))初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：先序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。

InOrderTraverse(BiTree T,int (*visit)(char e))初始条件：二叉树T已经存在，visit是对结点操作的应用函数操作结果：中序遍历二叉树T ，对每个结点调用visit函数仅一次；一旦visit（）失败，则操作失败。

《数据结构与算法统计》实验报告学院：班级：学号：姓名：一、实验目的1.熟悉VC++6.0环境，学习使用C++实现链表的存储结构；2.通过编程，上机调试，进一步理解线性表、链表的基本概念。

二、实验内容归并顺序表（选作）。

请按以下要求编程实现：①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。

②将链表linka和linkb归并为linkc，linkc仍然为升序排列。

归并完成后，linka和linkb为空表。

输出linkc。

③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。

例如：linka输入为：10 20 30 40 50 0linkb输入为：15 20 25 30 35 40 45 50 0归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50删除重复后的linkc为：10 15 20 25 30 35 40 45 50三、程序设计1、概要设计说明程序的主要功能，主程序的流程以及各个程序模块之间的调用关系，给出主要流程图。

应用单链线性表寄存数字序列。

⑴单链线性表的抽象数据类型线性表的定义如下：ADT LinkList {数据对象：D = { ai | ai ∈ElemSet, i=1,…,n，n≥0 }数据关系：R1 = { <ai-1, ai> | ai-1,ai ∈D, i=2, …,n }基本操作：Creat(LinkList &L)操作结果：构造单链线性表L。

MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)初始条件：单链线性表La，Lb，Lc已经存在。

操作结果：归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。

Delete(LinkList &L)初始条件：链表L已经存在。

《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：06111001学号：**********姓名：宝竞宇一、实验目的掌握栈的建立，输入，删除，出栈等基本操作。

应用栈解决实际问题。

二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。

例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计1、概要设计抽象数据类型定义：两个栈结构，分别用来储存数据和计算符号宏定义：函数“成功”，“失败的返回值”在主程序程序中先依次输入各表达式，存入相应各栈，然后，调用“判断函数”来判断计算符的优先次序，然后再利用计算函数来计算，表达式值。

其中还有，取栈顶元素函数，存入栈函数。

2、详细设计数据类型实现：struct t{ char dat[200];int top;}prt;入栈函数：存入数组，栈顶指针上移void pushd(long int a){ prd.dat[prd.top++]=a;}出栈：取出对应值，栈顶指针下移long int popd( ){ return prd.dat[--prd.top];}比较优先级：建立数组，比较返回大于小于号。

计算函数：以字符型输入，运算符号，用switch来分支计算判断，返回计算数值long int operation ( long int x, long int y, char a){ s witch(a){ case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y )return x/y;else{ printf("Divide 0.\n");return 0;}case '%': return (long int) fmod(x,y);case '^': if (y>=0 ) return (long int) pow(x,y);else return (0);default: printf("Error No. 3\n");return 0;}}主程序：在主程序内，以字符串的形式输入表达式，然后分别调用函数存入各相应栈，然后用数组判断，比较运算符的优先顺序。

数据结构课程实验报告一、实验目的。

本次实验旨在通过对数据结构课程所学知识的应用，加深对数据结构相关算法和数据操作的理解，提高学生的编程能力和实际应用能力。

二、实验内容。

1. 实现顺序表、链表、栈、队列等数据结构的基本操作；2. 设计并实现数据结构相关算法，如查找、排序等；3. 进行实验数据的输入、输出和结果展示；4. 对实验结果进行分析和总结。

三、实验过程。

1. 针对顺序表、链表、栈、队列等数据结构，首先进行了相关操作的实现。

在实现过程中，需要考虑数据结构的特点和操作规则，确保操作的正确性和高效性。

2. 针对数据结构相关算法，如查找、排序等，设计并实现了相应的算法。

在实现过程中，需要考虑算法的时间复杂度和空间复杂度，确保算法的效率和稳定性。

3. 进行了实验数据的输入、输出和结果展示。

通过编写测试用例，对实现的数据结构和算法进行了测试，验证其正确性和可靠性。

4. 对实验结果进行了分析和总结。

通过对实验数据和测试结果的分析，总结了实验中遇到的问题和解决方法，以及实验的收获和体会。

四、实验结果。

经过实验测试，实现的数据结构和算法均能正确运行并得到预期的结果。

通过实验，加深了对数据结构相关知识的理解，提高了编程能力和实际应用能力。

五、实验总结。

本次实验使我对数据结构相关知识有了更深入的理解，同时也提高了我的编程能力和实际应用能力。

在未来的学习和工作中，我将继续努力，不断提升自己的能力，为将来的发展打下坚实的基础。

六、实验感想。

通过本次实验，我深刻感受到了数据结构在实际应用中的重要性，也意识到了自己在数据结构方面的不足之处。

在今后的学习和工作中，我将更加努力地学习和应用数据结构知识，不断提高自己的能力，为未来的发展做好充分的准备。

七、参考文献。

1. 《数据结构与算法分析》。

2. 《C语言程序设计》。

3. 《数据结构课程实验指导书》。

以上就是本次数据结构课程实验的报告内容，希望能对大家有所帮助。

感谢您的阅读！。

数据结构实验报告及心得体会一、引言数据结构是计算机科学中的重要基础课程，通过实验环节的学习，我们能够更好地掌握和应用数据结构的概念、算法和操作。

本报告旨在总结和分享我们进行的数据结构实验，并提出相应的心得体会。

二、实验一：线性表的实现与应用1. 实验目的本实验旨在通过实现和应用线性表的基本操作，掌握线性表的存储结构和算法。

2. 实验内容我们选择了顺序表和链表两种线性表的实现方式，并实现了插入、删除和查找等基本操作。

通过实验，我们发现顺序表适用于元素个数较少、频繁查找的情况，而链表适用于插入和删除操作较多、元素个数不确定的情况。

3. 实验心得通过实验一，我们深刻认识到数据结构的不同实现方式对算法的影响。

选择合适的数据结构可以提高算法效率，提高程序的性能。

同时，我们也意识到了在实际应用中，根据问题的具体特点选择不同的数据结构才能得到最优解。

三、实验二：栈与队列的应用本实验旨在通过实现和应用栈和队列的基本操作，掌握栈和队列的特性及其在实际应用中的作用。

2. 实验内容我们分别实现了顺序栈、链式栈、顺序队列和链式队列，并实现了入栈、出栈、入队和出队等基本操作。

我们发现栈适用于实现回溯算法、递归算法等，而队列适用于广度优先搜索、线程池等场景。

3. 实验心得通过实验二，我们进一步理解了栈和队列在实际编程中的运用。

它们提供了方便的数据结构，帮助我们解决了许多实际问题。

同时，实验过程中，我们也发现了栈溢出的问题，意识到了合理管理栈空间的重要性。

四、实验三：树与二叉树的实现与应用1. 实验目的本实验旨在通过实现和应用树和二叉树的基本操作，掌握树和二叉树的存储结构和算法。

2. 实验内容我们实现了树和二叉树的基本操作，包括创建、插入、删除和遍历等。

通过实验，我们发现树在表示具有部分层次结构的问题时更合适，而二叉树在表示递归结构时更加方便。

通过实验三，我们深入理解了树和二叉树的特性及其应用。

树和二叉树是许多高级数据结构的基础，熟练掌握它们的操作对于解决实际问题非常重要。

实验四图书管理系统姓名：任子龙学号：1120140167 班级：05111451一。

需求分析（1）问题描述有一个小型书库保管了大量图书，关于图书有大量信息需要处理，这些信息包括图书的分类、书名、作者名、购买日期、价格等。

现要求编写一个程序以便于对图书的管理。

（2）基本要求：a．建立图书信息.b．提供查找功能，按照多种关键字查找需要的书籍。

例如按书名查找,输入书名后，将显示出该图书的所有信息，或显示指定信息。

c．提供排序功能，按照多种关键字对所有的书籍进行排序，例如按出版日期进行排序。

d．提供维护功能，可以对图书信息进行添加、修改、删除等功能。

(3）数据结构与算法分析将每一本书看作是一个基本单元。

由于涉及添加、修改操作,这里使用了链表作为数据存储结构；同时，考虑到排序功能，尝试使用双向链表。

其中，每本书作为一个结点，数据域包含char 型变量，指针域含有左右指针left和right。

二.概要设计1。

抽象数据类型的定义为实现上述功能，程序中使用了双向链表，只需要定义一种数据类型：typedef struct book{char number[10]；char title[20］；char author［10］；char date[15];char price[10］;struct book ＊right；struct book *left;｝BK；注意结点的指针域有left和right两个。

2.本程序包含两个模块（1）主程序模块主函数只包含了Menu_select（)函数。

目的是进入主菜单界面，进行功能选择；直到输入操作码0，退出系统；（2）双向链表单元模块——实现书籍信息的链式存储的抽象数据类型.各函数之间的调用关系：三。

详细设计1。

结点类型typedef struct book{char number［10]；char title［20]；char author［10];char date［15］；char price［10];struct book ＊right；struct book *left;｝BK;2.子函数（1）功能菜单调用函数Menu_select()使用户进入主菜单界面，进行功能选择；先进入无限循环，输入操作码进行系统管理工作，直到输入操作码0,退出系统；（2）各种功能函数Initialize()//初始化图书系统信息;Insert()//添加新的图书信息;Sort（)//对图书进行排序,本程序可以实现按“图书编号”、“出版日期"、“图书价格”多种关键字进行排序；Search()//实现对图书的查找功能，本程序可以实现按“图书编号"、“出版日期”、“图书价格”多种关键字进行查找；deletebook（)//删除无效的图书信息；Print_book（)//打印全部图书信息。