数据结构实验4

数据结构实验报告实验第四章：实验: 简单查找算法一．需求和规格说明：查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。

由于自己能力有限，本想实现其他算法，但没有实现。

其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。

二．设计思想：开始的时候提示输入一组数据。

并存入一维数组中，接下来调用一系列查找算法对其进行处理。

顺序查找只是从头到尾进行遍历。

二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。

二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。

当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。

这里还使用了广义表输出二叉树，以使得更直观。

哈希表则是利用给定的函数式建立索引，方便查找。

三．设计表示：四．实现注释：其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。

应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。

在查找到数据的时候要想办法输出查找过程的相关信息，并统计。

这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。

为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。

折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。

在查找后对查找数据进行了统计。

二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。

苏州科技学院数据结构（C语言版）实验报告专业班级测绘1011学号10201151姓名XX实习地点C1 机房指导教师史守正目录封面 (1)目录 (2)实验一线性表 (3)一、程序设计的基本思想，原理和算法描述 (3)二、源程序及注释（打包上传） (3)三、运行输出结果 (4)四、调试和运行程序过程中产生的问题及采取的措施 (6)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (6)实验二栈和队列 (7)一、程序设计的基本思想，原理和算法描述 (8)二、源程序及注释（打包上传） (8)三、运行输出结果 (8)四、调试和运行程序过程中产生的问题及采取的措施 (10)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (10)实验三树和二叉树 (11)一、程序设计的基本思想，原理和算法描述 (11)二、源程序及注释（打包上传） (12)三、运行输出结果 (12)四、调试和运行程序过程中产生的问题及采取的措施 (12)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (12)实验四图 (13)一、程序设计的基本思想，原理和算法描述 (13)二、源程序及注释（打包上传） (14)三、运行输出结果 (14)四、调试和运行程序过程中产生的问题及采取的措施 (15)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (16)实验五查找 (17)一、程序设计的基本思想，原理和算法描述 (17)二、源程序及注释（打包上传） (18)三、运行输出结果 (18)四、调试和运行程序过程中产生的问题及采取的措施 (19)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (19)实验六排序 (20)一、程序设计的基本思想，原理和算法描述 (20)二、源程序及注释（打包上传） (21)三、运行输出结果 (21)四、调试和运行程序过程中产生的问题及采取的措施 (24)五、对算法的程序的讨论、分析，改进设想，其它经验教训 (24)实验一线性表一、程序设计的基本思想，原理和算法描述：程序的主要分为自定义函数、主函数。

数据结构实验实验内容和目的：掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。

学习基本的查找和排序技术。

让我们在实际上机中具有编制相当规模的程序的能力。

养成一种良好的程序设计风格。

实验教材：数据结构题集（C语言版）清华大学出版社2007年实验项目：实验一、栈和循环队列㈠、实验内容：①栈掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。

本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。

②循环队列掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。

本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。

㈡、实验代码①栈程序代码：#include <stdio.h>#include <malloc.h>#define Stack_Size 6#define ERROR 0#define OK 1typedef int SElemType;typedef struct SNode{SElemType data;struct SNode *next;}SNode,*LinkStack;int CreatTwo(LinkStack &head,int n){int i;SNode *p;head=(LinkStack)malloc(sizeof(SNode));head->next=NULL;printf("请输入数据(数字):\n");for(i=n;i>0;--i){p=(SNode *)malloc(sizeof(SNode));scanf("%d",&p->data);p->next=head->next;head->next=p;}return 1;}int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}int Push(LinkStack &top,SElemType e){SNode *q;q=(LinkStack)malloc(sizeof(SNode));if(!q){printf("溢出!\n");return(ERROR);}q->data=e;q->next=top->next;top->next=q;return(OK);}int Pop(LinkStack &top,SElemType &e){SNode *q;if(!top->next){printf("error!\n");return(ERROR);}e=top->next->data;q=top->next;top->next=q->next;free(q);return(OK);}void main(){ int e;LinkStack top;printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");while(1){switch(menu_select()){case 1:if(CreatTwo(top,Stack_Size))printf("Success!\n");break; case 2:printf("Push:\n");scanf("%d",&e);if(Push(top,e))printf("Success!\n");break;case 3:if(Pop(top,e))printf("Success!\n");printf("%d\n",e);break;case 4:LinkStack p;printf("所有栈里的元素:\n");p=top;while(p->next){p=p->next;printf("%7d",p->data);}printf("\n");break;case 5:return;}}}运行结果：②循环队列程序代码：#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef struct{int *elem;//队列存储空间int front;int rear;}SqQueue;//判断选择是否正确int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\n");elsebreak;}return sn;}//参数(传出)SqQueue &Q,循环队列(空)int InitQueue(SqQueue &Q){Q.elem=(int *)malloc(MAXSIZE*sizeof(int));if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;i<MAXSIZE;i++)Q.elem[i]=-1;return OK;}//返回Q的元素个数int QueueLength(SqQueue Q){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}//显示队列的元素void Display(SqQueue Q){for(int i=0;i<=QueueLength(Q);i++)if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);printf("\n");}//入队int EnQueue(SqQueue &Q,int e){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)return ERROR;Q.elem[Q.rear]=e;return OK;}//出队int DeQueue(SqQueue &Q,int &e){if(Q.front==Q.rear)return ERROR;e=Q.elem[Q.front+1];Q.elem[Q.front+1]=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;}void main(){SqQueue Q;InitQueue(Q);int elem,e;printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");while(1){switch(menu_select()){case 1:printf("请输入队列元素(以0结束):\n");scanf("%d",&elem);while(elem!=0){EnQueue(Q,elem);scanf("%d",&elem);}printf("队列为：\n");Display(Q);fflush(stdin);break;case 2:scanf("%d",&elem);EnQueue(Q,elem);printf("队列为：\n");Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf("队列为：\n");Display(Q);break;case 4:printf("\n队列的所有元素:\n");Display(Q);break;case 5:printf("%d\n",QueueLength(Q));break;case 6:return;}}}运行结果：实验二、数组㈠、实验内容：数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构图的实验报告数据结构图的实验报告引言：数据结构图是计算机科学中重要的概念之一。

它是一种用图形表示数据元素之间关系的数据结构，广泛应用于算法设计、程序开发和系统优化等领域。

本实验报告旨在介绍数据结构图的基本原理、实验过程和结果分析。

一、实验目的本次实验的主要目的是掌握数据结构图的基本概念和操作方法，以及通过实验验证其在解决实际问题中的有效性。

具体而言，我们将通过构建一个社交网络关系图，实现对用户关系的管理和分析。

二、实验方法1. 确定数据结构在本次实验中，我们选择了无向图作为数据结构图的基础。

无向图由顶点集和边集组成，每条边连接两个顶点，且没有方向性。

2. 数据输入为了模拟真实的社交网络，我们首先需要输入一组用户的基本信息，如姓名、年龄、性别等。

然后，根据用户之间的关系建立边，表示用户之间的交流和联系。

3. 数据操作基于构建好的数据结构图，我们可以进行多种操作，如添加用户、删除用户、查询用户关系等。

这些操作将通过图的遍历、搜索和排序等算法实现。

三、实验过程1. 数据输入我们首先创建一个空的无向图，并通过用户输入的方式逐步添加用户和用户关系。

例如，我们可以输入用户A和用户B的姓名、年龄和性别，并建立一条边连接这两个用户。

2. 数据操作在构建好数据结构图后，我们可以进行多种操作。

例如，我们可以通过深度优先搜索算法遍历整个图，查找与某个用户具有特定关系的用户。

我们也可以通过广度优先搜索算法计算某个用户的社交网络影响力，即与该用户直接或间接相连的其他用户数量。

3. 结果分析通过实验，我们可以观察到数据结构图在管理和分析用户关系方面的优势。

它能够快速地找到用户之间的关系，帮助我们了解用户的社交网络结构和影响力。

同时，数据结构图也为我们提供了一种可视化的方式来展示用户之间的关系，使得分析更加直观和易于理解。

四、实验结果通过实验，我们成功构建了一个社交网络关系图，并实现了多种数据操作。

我们可以根据用户的姓名、年龄和性别等信息进行查询，也可以根据用户之间的关系进行遍历和排序。

实验报告名称：
姓名：学号：专业班级：
日期：
实验4: 顺序循环队列基本操作一、实验目的
1．熟悉并能实现顺序循环队列的定义和基本操作。

2．了解用队列解决实际应用问题。

二、实验要求
1．进行队列的基本操作时要注意队列“先进先出”的特性。

2．复习关于栈操作的基础知识。

3．编写完整程序完成下面的实验内容并上机运行。

4．整理并上交实验报告。

三、实验内容
1．掌握队列的思想及其存储实现。

2．掌握队列的常见算法的程序实现：
(1.) 判断队列是否为空
(2.) 测试队列的长度
(3.) 取队头元素值
(4.) 向队列中插入一新元素
(5.) 删除队列中一元素
3．在主函数中设计一个简单的菜单，分别调试上述算法。

数据结构实验报告一、实验目的数据结构是计算机科学中非常重要的一门课程，通过本次实验，旨在加深对常见数据结构（如链表、栈、队列、树、图等）的理解和应用，提高编程能力和解决实际问题的能力。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

操作系统为 Windows 10。

三、实验内容1、链表的实现与操作创建一个单向链表，并实现插入、删除和遍历节点的功能。

对链表进行排序，如冒泡排序或插入排序。

2、栈和队列的应用用栈实现表达式求值，能够处理加、减、乘、除和括号。

利用队列实现银行排队系统的模拟，包括顾客的到达、服务和离开。

3、二叉树的遍历与操作构建一棵二叉树，并实现前序、中序和后序遍历。

进行二叉树的插入、删除节点操作。

4、图的表示与遍历用邻接矩阵和邻接表两种方式表示图。

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

四、实验步骤及结果1、链表的实现与操作首先，定义了链表节点的结构体：｀｀｀cppstruct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；｀｀｀插入节点的函数：｀｀｀cppvoid insertNode(ListNode& head, int val) ｛ListNode newNode ＝ new ListNode(val)；head ＝ newNode;｝ else ｛ListNode curr ＝ head;while （curr>next!＝ NULL) ｛curr ＝ curr>next;｝curr>next ＝ newNode;｝｝｀｀｀删除节点的函数：｀｀｀cppvoid deleteNode(ListNode& head, int val) ｛if （head ＝＝ NULL) ｛return;｝ListNode temp ＝ head;head ＝ head>next;delete temp;return;｝ListNode curr ＝ head;while （curr>next!＝ NULL ＆＆ curr>next>data!＝ val) ｛curr ＝ curr>next;｝if （curr>next!＝ NULL) ｛ListNode temp ＝ curr>next;curr>next ＝ curr>next>next;delete temp;｝｝｀｀｀遍历链表的函数：｀｀｀cppvoid traverseList(ListNode head) ｛ListNode curr ＝ head;while （curr!＝ NULL) ｛std:：cout ＜＜ curr>data ＜＜＂＂；curr ＝ curr>next;｝std:：cout ＜＜ std:：endl;｝｀｀｀对链表进行冒泡排序的函数：｀｀｀cppvoid bubbleSortList(ListNode& head) ｛if （head ＝＝ NULL ｜｜ head>next ＝＝ NULL) ｛return;｝bool swapped;ListNode ptr1;ListNode lptr ＝ NULL;do ｛swapped ＝ false;ptr1 ＝ head;while （ptr1-＞next!＝ lptr) ｛if （ptr1-＞data ＞ ptr1-＞next>data) ｛int temp ＝ ptr1-＞data;ptr1-＞data ＝ ptr1-＞next>data;ptr1-＞next>data ＝ temp;swapped ＝ true;｝ptr1 ＝ ptr1-＞next;｝lptr ＝ ptr1;｝ while （swapped)；｝｀｀｀测试结果：创建了一个包含 5、3、8、1、4 的链表，经过排序后，输出为 1 3 4 5 8 。

数据结构课程实验报告数据结构课程实验报告引言：数据结构是计算机科学中非常重要的一门课程，它研究了数据的组织、存储和管理方法。

在数据结构课程中，我们学习了各种数据结构的原理和应用，并通过实验来加深对这些概念的理解。

本文将对我在数据结构课程中的实验进行总结和分析。

实验一：线性表的实现与应用在这个实验中，我们学习了线性表这种基本的数据结构，并实现了线性表的顺序存储和链式存储两种方式。

通过实验，我深刻理解了线性表的插入、删除和查找等操作的实现原理，并掌握了如何根据具体应用场景选择合适的存储方式。

实验二：栈和队列的实现与应用栈和队列是两种常见的数据结构，它们分别具有后进先出和先进先出的特点。

在这个实验中，我们通过实现栈和队列的操作，加深了对它们的理解。

同时，我们还学习了如何利用栈和队列解决实际问题，比如迷宫求解和中缀表达式转后缀表达式等。

实验三：树的实现与应用树是一种重要的非线性数据结构，它具有层次结构和递归定义的特点。

在这个实验中，我们学习了二叉树和二叉搜索树的实现和应用。

通过实验，我掌握了二叉树的遍历方法，了解了二叉搜索树的特性，并学会了如何利用二叉搜索树实现排序算法。

实验四：图的实现与应用图是一种复杂的非线性数据结构，它由节点和边组成，用于表示事物之间的关系。

在这个实验中，我们学习了图的邻接矩阵和邻接表两种存储方式，并实现了图的深度优先搜索和广度优先搜索算法。

通过实验，我深入理解了图的遍历方法和最短路径算法，并学会了如何利用图解决实际问题，比如社交网络分析和地图导航等。

实验五：排序算法的实现与比较排序算法是数据结构中非常重要的一部分，它用于将一组无序的数据按照某种规则进行排列。

在这个实验中，我们实现了常见的排序算法，比如冒泡排序、插入排序、选择排序和快速排序等，并通过实验比较了它们的性能差异。

通过实验，我深入理解了排序算法的原理和实现细节，并了解了如何根据具体情况选择合适的排序算法。

结论：通过这些实验，我对数据结构的原理和应用有了更深入的理解。

《数据结构》实验指导及实验报告栈和队列实验四栈和队列⼀、实验⽬的1、掌握栈的结构特性及其⼊栈，出栈操作；2、掌握队列的结构特性及其⼊队、出队的操作，掌握循环队列的特点及其操作。

⼆、实验预习说明以下概念1、顺序栈：2、链栈：3、循环队列：4、链队三、实验内容和要求1、阅读下⾯程序，将函数Push和函数Pop补充完整。

要求输⼊元素序列1 2 3 4 5 e，运⾏结果如下所⽰。

#include#include#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define STACKINCREMENT 5 /*存储空间分配增量*/typedef int ElemType; /*定义元素的类型*/typedef struct{ElemType *base; /*定义栈底部指针*/ElemType *top; /*定义栈顶部指针*/int stacksize; /*当前已分配的存储空间*/}SqStack;int InitStack(SqStack *S); /*构造空栈*/int push(SqStack *S,ElemType e); /*⼊栈操作*/int Pop(SqStack *S,ElemType *e); /*出栈操作*/int CreateStack(SqStack *S); /*创建栈*/void PrintStack(SqStack *S); /*出栈并输出栈中元素*/int InitStack(SqStack *S){S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType)); if(!S->base) return ERROR;S->top=S->base;int Push(SqStack *S,ElemType e){if(S->top-S->base>=S->stacksize){S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType)); S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*S->top++=e;return 1}/*Push*/int Pop(SqStack *S,ElemType *e){if(S->top!=S->base){*e=*--S->top;return 1;}elsereturn 0;}/*Pop*/int CreateStack(SqStack *S){int e;if(InitStack(S))printf("Init Success!\n");else{printf("Init Fail!\n");return ERROR;}printf("input data:(Terminated by inputing a character)\n"); while(scanf("%d",&e))Push(S,e);return OK;}/*CreateStack*/while(Pop(S,&e))printf("%3d",e);}/*Pop_and_Print*/int main(){SqStack ss;printf("\n1-createStack\n");CreateStack(&ss);printf("\n2-Pop&Print\n");PrintStack(&ss);return 0;}●算法分析：输⼊元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？2、在第1题的程序中，编写⼀个⼗进制转换为⼆进制的数制转换算法函数（要求利⽤栈来实现），并验证其正确性。

数据结构课程实验报告目录1. 实验简介1.1 实验背景1.2 实验目的1.3 实验内容2. 实验方法2.1 数据结构选择2.2 算法设计2.3 程序实现3. 实验结果分析3.1 数据结构性能分析3.2 算法效率比较3.3 实验结论4. 实验总结1. 实验简介1.1 实验背景本实验是数据结构课程的一次实践性操作，旨在帮助学生加深对数据结构的理解和运用。

1.2 实验目的通过本实验，学生将学会如何选择合适的数据结构来解决特定问题，了解数据结构与算法设计的关系并能将其应用到实际问题中。

1.3 实验内容本实验将涉及对一些经典数据结构的使用，如链表、栈、队列等，并结合具体问题进行算法设计和实现。

2. 实验方法2.1 数据结构选择在实验过程中，需要根据具体问题选择合适的数据结构，比如针对需要频繁插入删除操作的情况可选择链表。

2.2 算法设计针对每个问题，需要设计相应的算法来实现功能，要考虑算法的效率和实际应用情况。

2.3 程序实现根据算法设计，编写相应的程序来实现功能，并进行调试测试确保程序能够正确运行。

3. 实验结果分析3.1 数据结构性能分析在实验过程中，可以通过对不同数据结构的使用进行性能分析，如时间复杂度和空间复杂度等，以便选择最优的数据结构。

3.2 算法效率比较实验完成后，可以对不同算法在同一数据结构下的效率进行比较分析，找出最优算法。

3.3 实验结论根据实验结果分析，得出结论并总结经验教训，为后续的数据结构和算法设计提供参考。

4. 实验总结通过本次实验，学生将对数据结构与算法设计有更深入的了解，并能将所学知识应用到实际问题中，提高自己的实践能力和解决问题的能力。