下载文档原格式
数据结构C语言版实验教案一、实验目的1. 掌握数据结构基本概念和原理。
2. 培养使用C语言进行数据结构编程的能力。
3. 加深对数据结构在实际问题中的应用的理解。
二、实验内容1. 线性表的实现与操作。
2. 栈和队列的实现与操作。
3. 链表的实现与操作。
4. 树与二叉树的实现与操作。
5. 图的实现与操作。
三、实验环境1. 计算机硬件：Pentium（或更高）处理器。
2. 操作系统：Windows 7/8/10 或Linux。
3. 编程语言：C语言。
4. 开发工具：Code::Blocks 或Visual Studio。
四、实验要求1. 每个实验至少编写一个C程序实现数据结构的基本操作。
2. 每个实验要求有详尽的代码注释，以便于理解。
五、实验评价1. 代码质量：代码规范、易读、无明显错误。
2. 实现功能：正确实现数据结构的基本操作。
3. 实验报告：内容详实，能反映实验过程和收获。
六、实验一：线性表的实现与操作1. 实验目标：理解线性表的概念，掌握线性表的顺序存储结构及其基本操作。
2. 实验内容：实现一个简单的线性表结构体。
编写函数实现线性表的插入、删除、查找等基本操作。
设计测试用例验证线性表操作的正确性。
七、实验二：栈和队列的实现与操作1. 实验目标：理解栈和队列的概念，掌握它们的顺序存储结构及其基本操作。
2. 实验内容：实现一个简单的栈结构体。
编写函数实现栈的压入、弹出等基本操作。
实现一个简单的队列结构体。
编写函数实现队列的入队、出队等基本操作。
设计测试用例验证栈和队列操作的正确性。
八、实验三：链表的实现与操作1. 实验目标：理解链表的概念，掌握单链表和双向链表的存储结构及其基本操作。
2. 实验内容：实现一个简单的单链表结构体。
编写函数实现单链表的插入、删除、查找等基本操作。
实现一个简单的双向链表结构体。
编写函数实现双向链表的插入、删除、查找等基本操作。
设计测试用例验证链表操作的正确性。
九、实验四：树与二叉树的实现与操作1. 实验目标：理解树和二叉树的概念，掌握二叉树的存储结构及其基本操作。
实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。
实验主要步骤：1、分析、理解给出的示例程序。
2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。
3、修改程序：（1）增加插入结点的功能。
（2）将建立链表的方法改为头插入法。
程序代码:#include"stdio.h"#include"string.h"#include"stdlib.h"#include"ctype.h"typedef struct node //定义结点{char data[10]; //结点的数据域为字符串struct node *next; //结点的指针域}ListNode;typedef ListNode * LinkList; // 自定义LinkList单链表类型LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表ListNode *LocateNode(); //函数，按值查找结点void DeleteList(); //函数，删除指定值的结点void printlist(); //函数，打印链表中的所有值void DeleteAll(); //函数，删除所有结点，释放内存ListNode * AddNode(); //修改程序：增加节点。
用头插法，返回头指针//==========主函数==============void main(){char ch[10],num[5];LinkList head;head=CreatList(); //用头插入法建立单链表，返回头指针printlist(head); //遍历链表输出其值printf(" Delete node (y/n):"); //输入"y"或"n"去选择是否删除结点scanf("%s",num);if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){printf("Please input Delete_data:");scanf("%s",ch); //输入要删除的字符串DeleteList(head,ch);printlist(head);}printf(" Add node ? (y/n):"); //输入"y"或"n"去选择是否增加结点scanf("%s",num);if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){head=AddNode(head);}printlist(head);DeleteAll(head); //删除所有结点，释放内存}//==========用尾插入法建立带头结点的单链表===========LinkList CreatListR1(void){char ch[10];LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点ListNode *s,*r,*pp;r=head;r->next=NULL;printf("Input # to end "); //输入"#"代表输入结束printf("\nPlease input Node_data:");scanf("%s",ch); //输入各结点的字符串while(strcmp(ch,"#")!=0) {pp=LocateNode(head,ch); //按值查找结点，返回结点指针if(pp==NULL) { //没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode));strcpy(s->data,ch);r->next=s;r=s;r->next=NULL;}printf("Input # to end ");printf("Please input Node_data:");scanf("%s",ch);}return head; //返回头指针}//==========用头插入法建立带头结点的单链表===========LinkList CreatList(void){char ch[100];LinkList head,p;head=(LinkList)malloc(sizeof(ListNode));head->next=NULL;while(1){printf("Input # to end ");printf("Please input Node_data:");scanf("%s",ch);if(strcmp(ch,"#")){if(LocateNode(head,ch)==NULL){strcpy(head->data,ch);p=(LinkList)malloc(sizeof(ListNode));p->next=head;head=p;}}elsebreak;}return head;}//==========按值查找结点，找到则返回该结点的位置，否则返回NULL========== ListNode *LocateNode(LinkList head, char *key){ListNode *p=head->next; //从开始结点比较while(p!=NULL && strcmp(p->data,key)!=0) //直到p为NULL或p->data为key止p=p->next; //扫描下一个结点return p; //若p=NULL则查找失败，否则p指向找到的值为key的结点//==========修改程序：增加节点=======ListNode * AddNode(LinkList head){char ch[10];ListNode *s,*pp;printf("\nPlease input a New Node_data:");scanf("%s",ch); //输入各结点的字符串pp=LocateNode(head,ch); //按值查找结点，返回结点指针printf("ok2\n");if(pp==NULL) { //没有重复的字符串，插入到链表中s=(ListNode *)malloc(sizeof(ListNode));strcpy(s->data,ch);printf("ok3\n");s->next=head->next;head->next=s;}return head;}//==========删除带头结点的单链表中的指定结点=======void DeleteList(LinkList head,char *key){ListNode *p,*r,*q=head;p=LocateNode(head,key); //按key值查找结点的if(p==NULL ) { //若没有找到结点，退出printf("position error");exit(0);}while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next;r=q->next;q->next=r->next;free(r); //释放结点}//===========打印链表=======void printlist(LinkList head)ListNode *p=head->next; //从开始结点打印while(p){printf("%s, ",p->data);p=p->next;}printf("\n");}//==========删除所有结点，释放空间===========void DeleteAll(LinkList head){ListNode *p=head,*r;while(p->next){r=p->next;free(p);p=r;}free(p);}实验结果：Input # to end Please input Node_data:batInput # to end Please input Node_data:catInput # to end Please input Node_data:eatInput # to end Please input Node_data:fatInput # to end Please input Node_data:hatInput # to end Please input Node_data:jatInput # to end Please input Node_data:latInput # to end Please input Node_data:matInput # to end Please input Node_data:#mat, lat, jat, hat, fat, eat, cat, bat, Delete node (y/n):yPlease input Delete_data:hatmat, lat, jat, fat, eat, cat, bat,Insert node (y/n):yPlease input Insert_data:putposition :5mat, lat, jat, fat, eat, put, cat, bat, 请按任意键继续. . .示意图：headheadhead心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。
数据结构C语言版实验教案一、实验目的1. 理解数据结构的基本概念和原理。
2. 掌握C语言在数据结构中的应用和实现。
3. 培养动手实践能力和团队协作精神。
二、实验内容1. 线性表的实现与操作：顺序存储结构、链式存储结构。
2. 栈和队列的实现与操作。
3. 线性排序算法实现与分析。
4. 树与二叉树的实现与操作。
5. 图的实现与操作。
三、实验环境1. 编程语言：C语言。
2. 开发工具：Visual Studio、Code::Blocks等。
3. 操作系统：Windows、Linux或Mac OS。
四、实验步骤1. 实验准备：了解实验内容，阅读相关教材和资料，明确实验目标和任务。
2. 设计实验方案：根据实验内容，设计相应的数据结构和算法。
3. 编写实验代码：按照实验方案，用C语言编写代码。
4. 调试和测试：运行代码，检查功能是否符合预期，发现问题并及时修改。
五、实验评价1. 代码质量：代码结构清晰，注释详细，可读性强。
2. 功能实现：实验要求的功能全部实现，且运行稳定。
3. 算法效率：分析并优化算法，提高程序运行效率。
4. 实验报告：内容完整，包括实验目的、内容、步骤、总结等。
5. 团队协作：积极参与讨论，与团队成员共同解决问题。
六、实验一：线性表的实现与操作1. 实验目的：掌握顺序存储结构线性表的实现。
掌握链式存储结构线性表的实现。
熟悉线性表的基本操作，如插入、删除、查找等。
2. 实验内容：实现一个顺序存储结构线性表。
实现一个链式存储结构线性表。
实现线性表的插入、删除、查找等操作。
3. 实验步骤：设计顺序存储结构线性表的数据类型和操作函数。
实现链式存储结构线性表的数据类型和操作函数。
编写测试代码，验证线性表操作的正确性。
4. 实验评价：线性表结构设计合理，代码清晰。
能够正确实现线性表的基本操作。
测试代码全面，能够验证操作的正确性。
七、实验二：栈和队列的实现与操作1. 实验目的：理解栈和队列的基本概念。
掌握栈和队列的顺序存储结构实现。
数据结构实验指导书（C语言版）2017年9月目录1、顺序表的实现 (1)2、链栈的实现 (3)3、前序遍历二叉树 (5)4、图的深度优先遍历算法 (7)5、散列查找 (9)1、顺序表的实现1. 实验目的⑴掌握线性表的顺序存储结构；⑵验证顺序表及其基本操作的实现；⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。
2. 实验内容⑴建立含有若干个元素的顺序表；⑵对已建立的顺序表实现插入、删除、查找等基本操作。
3. 实现提示定义顺序表的数据类型——顺序表结构体SeqList，在SeqList基础上实现题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。
简单起见，本实验假定线性表的数据元素为int型，要求学生：（1）将实验程序调试通过后，用模板类改写；（2）加入求线性表的长度等基本操作；（3）重新给定测试数据，验证抛出异常机制。
4. 实验程序在编程环境下新建一个工程“顺序表验证实验”，并新建相应文件，文件包括顺序表结构体SeqList的定义，范例程序如下：#define MaxSize 100 /*假设顺序表最多存放100个元素*/typedef int DataType; /*定义线性表的数据类型，假设为int型*/typedef struct{DataType data[MaxSize]; /*存放数据元素的数组*/int length; /*线性表的长度*/} SeqList;文件包括建立顺序表、遍历顺序表、按值查找、插入操作、删除操作成员函数的定义，范例程序如下：int CreatList(SeqList *L, DataType a[ ], int n){if (n > MaxSize) {printf("顺序表的空间不够，无法建立顺序表\n"); return 0;} for (int i = 0; i < n; i++)L->data[i] = a[i];L->length = n;return 1;}void PrintList(SeqList *L){for (int i = 0; i < L->length; i++)printf("%d ", L->data[i]); /*输出线性表的元素值，假设为int型*/ }int Locate(SeqList *L, DataType x){for (int i = 0; i < L->length; i++)if (L->data[i] == x) return i+1; /*返回序号*/return 0; /*退出循环，说明查找失败*/ }int Insert(SeqList *L, int i, DataType x){if (L->length >= MaxSize) {printf("上溢错误，插入失败\n"); return 0;} if (i < 1 || i > L->length + 1) {printf("位置错误，插入失败\n"); return 0;} for (int j = L->length; j >= i; j--) /*j表示元素序号*/L->data[j] = L->data[j - 1];L->data[i - 1] = x;L->length++;return 1;}int Delete(SeqList *L, int i, DataType *ptr){if (L->length == 0) {printf("下溢错误，删除失败\n"); return 0;} if (i < 1 || i > L->length) {printf("位置错误，删除失败\n"); return 0;} *ptr = L->data[i - 1]; /*取出位置i的元素*/for (int j = i; j < L->length; j++) /* j表示元素所在数组下标*/L->data[j - 1] = L->data[j];L->length--;return 1;}在定义了顺序表的存储结构SeqList并实现了基本操作后，程序中就可以使用SeqList 类型来定义变量，可以调用实现基本操作的函数来完成相应的功能。
数据结构C语言版实验教案一、实验目的1. 理解数据结构的基本概念和原理。
2. 掌握C语言的基本语法和编程技巧。
3. 培养实际操作能力和问题解决能力。
二、实验内容1. 线性表的实现与操作。
2. 栈和队列的实现与操作。
3. 链表的实现与操作。
4. 树和图的实现与操作。
5. 排序和查找算法的实现与优化。
三、实验环境1. 操作系统：Windows或Linux。
2. 编程语言：C语言。
3. 编译器：GCC或Clang。
4. 开发工具：Visual Studio或Code::Blocks。
四、实验步骤1. 了解实验要求，阅读相关教材和资料。
2. 分析实验问题，设计实验方案。
3. 编写实验代码，进行调试和测试。
4. 分析实验结果，总结实验经验和教训。
5. 完成实验报告，提交实验代码和报告。
五、实验评价1. 代码规范性和可读性。
2. 实验问题的解决能力和创新性。
4. 实验操作的熟练程度和团队合作能力。
六、线性表的实现与操作1. 实验目的：学习线性表的基本概念。
掌握线性表的顺序存储结构和存储结构。
学会实现线性表的基本操作，如插入、删除、查找和打印。
2. 实验内容：实现一个简单的线性表。
实现线性表的插入和删除操作。
实现线性表的查找和打印操作。
3. 实验环境：同上。
4. 实验步骤：设计一个线性表的数据结构。
编写实现线性表操作的函数。
编写测试线性表操作的程序。
调试并运行程序，验证操作的正确性。
5. 实验评价：同上。
七、栈和队列的实现与操作1. 实验目的：理解栈和队列的基本概念和特点。
掌握栈和队列的顺序存储结构和存储结构。
学会实现栈和队列的基本操作，如入栈、出栈、入队、出队等。
2. 实验内容：实现一个简单的栈。
实现一个简单的队列。
实现栈和队列的综合应用，如数制转换等。
3. 实验环境：同上。
4. 实验步骤：设计栈和队列的数据结构。
编写实现栈和队列操作的函数。
编写测试栈和队列操作的程序。
调试并运行程序，验证操作的正确性。
5. 实验评价：同上。
数据结构实验C语言版数据结构实验C语言版第一章实验目的1.熟悉C语言编程环境。
2.掌握数据结构中常用的线性结构和非线性结构。
3.学习使用C语言实现常见的数据结构操作。
4.培养解决实际问题的思维能力。
第二章实验内容1.线性表1.1 顺序表1.1.1 初始化顺序表1.1.2 在顺序表中插入元素1.1.3 删除顺序表中的元素1.1.4 查找顺序表中的元素1.1.5 显示顺序表中的元素1.2 链表1.2.1 初始化链表1.2.2 在链表中插入节点 1.2.3 删除链表中的节点 1.2.4 查找链表中的节点1.2.5 显示链表中的节点2.栈和队列2.1 栈2.1.1 初始化栈2.1.2 入栈操作2.1.3 出栈操作2.1.4 获取栈顶元素2.1.5 判断栈是否为空 2.2 队列2.2.1 初始化队列2.2.2 入队操作2.2.3 出队操作2.2.4 获取队头元素2.2.5 判断队列是否为空3.树和图3.1 二叉树3.1.1 创建二叉树3.1.2 前序遍历二叉树3.1.3 中序遍历二叉树3.1.4 后序遍历二叉树3.1.5 层序遍历二叉树3.2 图3.2.1 创建图3.2.2 深度优先搜索遍历图3.2.3 广度优先搜索遍历图3.2.4 最短路径算法3.2.5 最小树算法第三章实验步骤1.确定实验目标和需求。
2.根据实验内容，编写C语言程序。
3.调试和运行程序，验证程序的正确性。
4.根据实验结果进行分析和总结。
第四章实验结果与分析1.线性表的操作结果分析。
2.栈和队列的操作结果分析。
3.树和图的操作结果分析。
附件：________源代码文件法律名词及注释：________1.版权：________指对作品享有的本质的、来自著作权法的权益。
2.许可证：________指权利人向他人授予合法使用作品的权利的法律文件。
3.商标：________指与一种商品及其生产者和经销者有关的特定名称、标识或符号。
4.注册商标：________指在商标局进行了合法登记并取得专有权的商标。
数据结构(C语言版) 实验报告实验报告1·实验目的本实验的目的是通过使用C语言实现各种数据结构，包括链表、栈、队列和树等，以加深对这些数据结构的理解，并学习其基本操作和应用场景。
2·实验环境和工具●操作系统：Windows 10●开发工具：Code::Blocks●编程语言：C语言3·实验内容3·1 链表3·1·1 定义链表结点的结构体3·1·2 创建链表3·1·3 插入结点3·1·4 删除结点3·1·5 遍历链表3·1·6 查找链表中的某个结点3·2 栈3·2·1 定义栈的结构体3·2·2 初始化栈3·2·3 入栈操作3·2·4 出栈操作3·2·5 判断栈是否为空3·2·6 获取栈顶元素3·3 队列3·3·1 定义队列的结构体3·3·2 初始化队列3·3·3 入队操作3·3·4 出队操作3·3·5 判断队列是否为空3·3·6 获取队头元素3·4 树3·4·1 定义树的结构体3·4·2 创建树3·4·3 插入结点3·4·4 删除结点3·4·5 遍历树3·4·6 查找树中的某个结点4·实验结果通过实验，我们成功实现了链表、栈、队列和树的基本操作，并对其进行了测试，验证了其正确性和效果。
5·总结与讨论本次实验使我对数据结构有了更深的理解，通过实际编写代码，加深了对链表、栈、队列和树等数据结构的认识。
数据结构C语言版实验教案一、实验目的1. 理解数据结构的基本概念和原理。
2. 掌握C语言编程的基本技巧。
3. 培养实际动手能力和解决实际问题的能力。
二、实验环境2. 操作系统：Windows 2000 / XP / 7 / 10。
3. 编程语言：C语言。
4. 开发工具：Code::Blocks 或Visual Studio。
三、实验内容1. 线性表的顺序存储结构实现。
2. 链式存储结构实现。
3. 栈和队列的实现。
4. 线性表的排序算法实现。
5. 查找算法实现。
四、实验要求1. 每个实验都需要编写相应的C程序代码，并进行调试和运行。
2. 每个实验都需要提交实验报告，包括实验目的、实验环境、实验内容、实验步骤、实验结果和实验心得等。
3. 每个实验都需要在实验报告中附上相应的程序代码和运行结果截图。
五、实验评价1. 实验报告的完整性：包括实验目的、实验环境、实验内容、实验步骤、实验结果和实验心得等。
2. 程序代码的规范性：包括代码的结构、注释、变量命名等。
3. 程序运行的正确性：包括程序的执行结果、运行效率等。
4. 实验报告的书面表达和逻辑性：包括实验报告的书写格式、语言表达、逻辑性等。
六、实验一：线性表的顺序存储结构实现1. 实验目的：学习线性表的概念。
掌握线性表的顺序存储结构。
学会使用C语言实现线性表的基本操作。
2. 实验内容：编写C程序实现线性表的创建、插入、删除、遍历等基本操作。
3. 实验步骤：定义线性表的数据结构和基本操作函数。
编写主函数，进行线性表的操作演示。
调试并运行程序。
4. 实验报告要求：提交实验代码和运行结果截图。
七、实验二：链式存储结构实现1. 实验目的：学习链式存储结构的概念。
掌握链表的创建和基本操作。
学会使用C语言实现单链表和双向链表。
2. 实验内容：编写C程序实现单链表和双向链表的创建、插入、删除、遍历等基本操作。
3. 实验步骤：定义链表的数据结构和基本操作函数。
编写主函数，进行链表的操作演示。
数据结构（C语言版）实验指导预备实验C语言的函数、数组、指针和结构体知识一、实验目的1、复习C语言中函数、数组、指针、结构体与共用体等的概念。
2、熟悉利用C语言进行程序设计的一般方法。
二、实验内容1、调试程序：输出100以内所有的素数（用函数实现）。
#include<stdio.h>int isprime(int n){ /*判断一个数是否为素数*/int m;for(m=2;m*m<=n;m++)if(n%m==0) return 0;return 1;}int main(){ /*输出100以内所有素数*/int i; printf("\n");for(i=2;i<100;i++)if(isprime(i)==1) printf("%4d",i);return 0;}运行结果：2、调试程序：对一维数组中的元素进行逆序排列。
#include<stdio.h>#define N 10int main(){int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp;printf("\nthe original Array is:\n ");for(i=0;i<N;i++)printf("%4d",a[i]);for(i=0;i<N/2;i++){ /*交换数组元素使之逆序*/temp=a[i];a[i]=a[N-i-1];a[N-i-1]=temp;}printf("\nthe changed Array is:\n");for(i=0;i<N;i++)printf("%4d",a[i]);return 0;}运行结果：3、调试程序：在二维数组中，若某一位置上的元素在该行中最大，而在该列中最小，则该元素即为该二维数组的一个鞍点。
数据结构C语言版实验报告《数据结构 C 语言版实验报告》一、实验目的本次实验旨在通过使用 C 语言实现常见的数据结构，加深对数据结构基本概念和操作的理解，提高编程能力和问题解决能力。
二、实验环境操作系统：Windows 10编程环境：Visual Studio 2019三、实验内容1、线性表顺序表的实现链表的实现（包括单向链表、双向链表）2、栈和队列栈的实现（顺序栈、链栈）队列的实现（顺序队列、循环队列、链队列）3、数组和字符串数组的基本操作字符串的操作（字符串的存储、字符串的比较、字符串的连接等）4、树和二叉树二叉树的遍历（前序、中序、后序）二叉树的创建和基本操作5、图图的存储（邻接矩阵、邻接表）图的遍历（深度优先遍历、广度优先遍历）四、实验步骤1、线性表顺序表的实现定义顺序表的数据结构，包括数组和表的长度等。
实现顺序表的初始化、插入、删除、查找等操作。
编写测试程序，对顺序表的各种操作进行测试。
链表的实现定义单向链表和双向链表的数据结构，包括节点结构体。
实现链表的创建、插入、删除、查找等操作。
编写测试程序，验证链表操作的正确性。
栈的实现定义顺序栈和链栈的数据结构。
实现栈的入栈、出栈、栈顶元素获取等操作。
进行栈的操作测试。
队列的实现定义顺序队列、循环队列和链队列的数据结构。
实现队列的入队、出队、队头队尾元素获取等操作。
对队列的操作进行测试。
3、数组和字符串数组的操作实现数组的初始化、元素访问、数组元素的修改等。
测试数组的基本操作。
字符串的操作定义字符串的存储方式。
实现字符串的比较、连接、复制等操作。
编写测试用例，验证字符串操作的准确性。
二叉树的遍历采用递归方式实现二叉树的前序、中序、后序遍历。
输出遍历结果进行验证。
二叉树的创建和基本操作构建二叉树的数据结构。
实现二叉树的节点插入、删除等操作。
5、图图的存储分别用邻接矩阵和邻接表来存储图。
实现图的初始化操作。
图的遍历用深度优先遍历和广度优先遍历算法对图进行遍历。
《数据结构与算法》实验指导书一、实验课程教学目的和要求《数据结构与算法》是一门实践性很强的课程，光靠读书和做习题是不能提高实践能力的。
《数据结构与算法》的实验与程序设计语言课程中的实验不同，后者更多的强调语言方面的功能实现，而前者更接近实际，需要同学们自己分析问题，设计模型和算法，再上机调试完成。
《数据结构与算法》的实验的目的主要有两个：1）深化理解书本上的理论知识，将书本的知识变“活”（为已掌握，为已活用）；2）理论和实践相结合，学会将相关的数据结构和算法应用于解决实际问题，培养数据结构的应用能力和软件工程所需要的实践能力。
《数据结构与算法》的实验类型1）验证性实验—主要是验证教材中已有的数据结构和算法。
2）设计性实验—针对具体问题，应用某一个知识点，自己设计数据结构和算法，培养对数据结构的简单运用能力。
3）综合性实验—针对具体问题，应用某几个知识点，自己设计数据结构和算法，培养对数据结构的综合运用能力。
《数据结构与算法》的实验安排《数据结构与算法》实验的一般步骤1）需求分析：要对简单的问题描述进行详细的分析，充分理解问题，明确问题要求做什么，有什么数据，边界条件……。
2）概要设计：针对问题描述中涉及到数据定义抽象数据类型，设计数据结构和算法模型。
本部分不必考虑实现的细节。
3）详细设计：设计具体的存储结构（用C++或C语言）。
此外，还要设计对象或函数间的调用关系及输入输出。
4）上机调试（运行代码，修正语法及逻辑错误）5）结果与总结《数据结构与算法》的实验要求：1）完成实验预习；2）完成并上交实验报告；3）完成电子设计文档预习/实验报告的格式要求：1）实验名称2）实验目的3）实验内容及要求4）概要设计：ADT5）详细设计：C++类或C函数6）调试分析：7）结果与总结实验一: 顺序表的操作一、实验目的：1）掌握线性表的顺序存储结构与算法实现；3）掌握顺序表的逻辑插入方法。
二、实验内容及要求：实现对有序的顺序表L进行保序插入的(C++或C)算法提示：主函数构建n个整数的顺序表L并调用输出函数；调用保序插入函数实现插入操作并调用输出函数输出。
实验二: 单链表的操作一、实验目的：1）掌握线性表的链接存储结构与算法实现；2）掌握线性表的逻辑插入/删除操作方法。
二、实验内容及要求：设计算法将一个带头结点的单循环链表A（值为整数）分解为两个具有相同结构的链表B和C，其中B表中结点为A表中值为奇数的结点，而C表中结点为A 表中值为偶数的结点（要求利用原表结点）。
提示：B表头结点利用A表头结点；为C表产生一个头结点。
从A的首元结点检查每个结点应插入B表还是C表，从而从A表取下，做相应的插入操作。
结点结构： struct Node{ int data;Node *next;};实验三：括号匹配问题一、实验目的：1）掌握栈和队列的存储结构；2）掌握栈和队列的操作特性；3）掌握栈和队列基本操作的实现。
二、实验内容及要求：括号匹配问题在算述表达式中，可能出现嵌套的大、中、小括号，设计一个算法，可以判断给定的表达式串中的括号是否是匹配的。
要求：首先，分别先定义一个栈和一个队；其次，将表达式串中的各种括号字符依次入队（其它字符不予考虑）；最后利用栈来判断队中的括号是否是匹配的。
无论是什么括号，最后出现的左括号，必须与其后最先出现的右括号匹配，这符合栈的后进先出的特点，故我们可以用栈和进行匹配性判断。
根据要求，串(括号) 队栈操作接口：bool match(char *s)主要操作：队，栈初始化括号字符入队出队为左括号：进栈出队为右括号：弹栈匹配？实验四：对称矩阵的压缩存储一、实验目的：1）掌握对称矩阵的压缩存储方法；2）掌握对称矩阵的压缩存储的寻址方法。
二、实验内容：1) 建立一个n×n的对称矩阵；2) 将对称矩阵用一维数组存储三、实现提示：首先建立一个n×n的对称矩阵A并初始化矩阵的元素。
对称矩阵只须存储下三角部分，即将一个n×n的对称矩阵用一个大小为n×(n+1)/2的一维数组SA来存储，则对称矩阵中的元素aij(i≥j)在SA中的下标k与i、j的关系为k=i×(i+1)/2+j，元素aij(i<j)在SA中的下标k与i、j的关系为k=j×(j+1)/2+i。
实验五：二叉树的操作一、实验目的：1）掌握二叉树的二叉链表存储结构；2）掌握二叉树的建立方法；3）掌握二叉树的遍历操作的算法实现。
二、实验内容及要求：1) 利用扩展二叉树的先序遍历序列建立一个含有n个结点的二叉树，采用二叉链表存储；2) 进行各种遍历（先序，中序，后序，层序）该二叉树；求二叉树中叶子结点的个数; 求二叉树t的深度; 交换二叉树t的所有左右孩子并以中序遍历输出。
3) 遍历算法分别用递归和非递归算法。
实验六：图的操作一、实验目的：1）掌握图的存储结构；2）掌握构造邻接矩阵的方法；3）掌握图的遍历算法的算法实现。
二、实验内容及要求：按给定的任一连通无向图构造邻接矩阵，再进行深度优先遍历和广度优先遍历。
实验七：查找一、实验目的：1）掌握顺序查找技术和拆半查找技术；2）掌握查找的算法实现；二、实验内容及要求：1、产生n个随机整数用顺序查找的方法进行查找操作，并统计查找的次数。
2、给定n个有序整数用折半查找的方法进行查找操作，并统计查找的次数。
要求分别用初始化函数，顺序查找函数，折半查找函数及输出函数来完成。
实验八：排序一、实验目的：1）深刻理解各种排序算法的设计思想；2）掌握各种排序算法的执行过程；3）掌握各种排序算法的设计实现。
二、实验内容及要求：产生n个随机整数分别采用直接插入排序、希尔排序、冒泡排序、直接选择排序和快速排序的方法进行排序。
要求分别采用各排序函数和输出函数来完成。
参考实验：/*----------------------有序顺序表的保序插入算法----------------------*/#include"stdio.h"#define MaxSize 100void show_array(int data[],int size);void insert_array(int data[],int size);void main(){int data[MaxSize];int length=0; //构造一个空表int a[]={4,8,10,12,20,23,25,30,34}; //构造一个长度为n的有序顺序表（本程序中n=9）for(int i=0;i<9;i++)data[i]=a[i];length=9;show_array(data,length); //调用输出函数insert_array(data,length); //调用插入函数}void show_array(int data[],int length) //定义输出函数{int i;for(i=0;i<length;i++)printf("%2d ",data[i]);printf("\n");}void insert_array(int data[],int length) //定义插入函数{int i,j,a;if(length==MaxSize)printf("上溢\n");else{printf("请输入要插入到顺序表中的元素\n");scanf("%d",&a);for(i=0;i<length;i++) //寻找插入元素在有序顺序表中的位置if(data[i]>=a)break;for(j=length;j>i;j--) //将最后一个元素至第i个元素后移一位data[j]=data[j-1];data[i]=a; //插入元素length++;show_array(data,length);}}/*------------------将循环单链表分解为同构的两个链表------------------*/#include"stdio.h"#include"stdlib.h"#include"process.h"void main(){struct Node //定义单链表结点{int data;struct Node *next;};struct Node *head,*head1,*rear,*p,*q,*s,*A,*B,*C;int i,n;head=(struct Node *)malloc(sizeof(struct Node)); //申请两个结点，分别用head和A指向该结点if(head==NULL) exit(1);p=(struct Node *)malloc(sizeof(struct Node));if(A==NULL) exit(1);head->next=p; //构造头结点puts("please enter intger:"); //构造有n个数据的单循环链表A（本程序中n=8）scanf("%d",&(p->data));n=8;for(i=1;i<n;i++){p->next=(struct Node *)malloc(sizeof(struct Node)); //申请空间，用A所指结点的next指向该空间if(p->next==NULL) exit(1);p=p->next;puts("please enter intger:");scanf("%d",&(p->data));}p->next=head; //重置循环A=head;printf("A链表为：\n");p=head->next; //输出单循环链表Awhile(p!=head){printf("%2d ",p->data);p=p->next;}head1=(struct Node *)malloc(sizeof(struct Node)); //构造一个空的单循环链表if(A==NULL) exit(1);head1->next=head1;rear=head1; //设置尾指针C=head1;B=A;p=head;q=head->next; //p指向head，q指向第一个结点while(q!=head) ////将A分解为两个相同结构的链表B和C{if((q->data)%2!=0) //B表中结点为A表中值为奇数结点{p=p->next; //p,q分别指向下个结点q=q->next;}else //C表中结点为A表中值为偶数结点{p->next=q->next; //将q从链表中摘下s=q; //s指向qrear->next=s; //将s插入链表Cs->next=head1; //重置循环rear=s; //重置尾指针q=p->next; //q指向下个结点}}printf("\nB链表为：\n");p=head->next; //输出链表B while(p!=head){printf("%2d ",p->data);p=p->next;}printf("\nC链表为：\n");q=head1->next; //输出链表C while(q!=head1){printf("%2d ",q->data);q=q->next;}printf("\n");}/*---------------------判断表达式中括号是否匹配---------------------*/#include"stdio.h"bool match(char *s);void main(){char str[30]; //定义一个字符串puts("please enter a string:\n");gets(str);if(match(str)==true)puts("\n匹配\n");elseputs("\n不匹配\n");}bool match(char *str) //定义判断字符串是否匹配的函数{char s;char stack[20],queue[30]; //定义一个空栈和空队int top,front,rear;top=-1;front=rear=0;while(*str!='\0'){if(*str=='('||*str==')'||*str=='['||*str==']'||*str=='{'||*str=='}') {rear=(rear+1)%20; //入队queue[rear]=*str;}str++;}while(front!=rear){front=(front+1)%20; //出队s=queue[front];if(s=='('||s=='['||s=='{'){top++; //入栈stack[top]=s;}else{switch(s){case ')':if(stack[top]=='(') top--;else top=1;break; //小括号匹配，弹栈，否则，top=1，表达式括号不匹配case ']':if(stack[top]=='[') top--;else top=1;break; //大括号匹配，弹栈，否则，top=1，表达式括号不匹配case '}':if(stack[top]=='{') top--;else top=1;break; //花括号匹配，弹栈，否则，top=1，表达式括号不匹配}}}if(top==-1)return true;elsereturn false;}/*------------------------对称矩阵的压缩存储------------------------*/#include"stdio.h"#define N 10void Matrix(int A[][N],int n,int SA[]);void main(){int A[N][N],SA[N*(N+1)/2],i,j,k,a;Matrix(A,N,SA); //调用压缩存储函数printf("\n请输入寻址A矩阵中元素的下标 i,j:\n"); //寻址A矩阵中的任一元素scanf("%d%d",&i,&j);if(i<j) //本程序中存储对称矩阵下三角形，A[i][j]=A[j][i] {a=i;i=j;j=a;}k=i*(i+1)/2+j;printf("\n元素A[%d][%d]=A[%d][%d]=%d\n",i,j,j,i,SA[k]); }void Matrix(int A[][N],int n,int SA[]){int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=i+j; //生成对称矩阵元素for(i=0;i<n;i++)for(j=0;j<=i;j++)SA[i*(i+1)/2+j]=A[i][j]; //压缩存储}/*----------------------二叉树实验----------------------*/ #include<iostream>using namespace std;template<class T>struct BINODE{BINODE<T> *lchild;T data;BINODE<T> *rchild;}; //构造二叉树的结点template<class T>struct element{BINODE<T> *ptr;int flag;}; //定义后序遍历非递归函数中栈元素类型BINODE<char> *first,*root,*q,*temp,stack[20],queue[20]; element<char> s[20];int count=0;template<class T>class BiTree{public:void creat(BINODE<T> *&root) //定义建立二叉树的函数{char ch;cin>>ch;if(ch=='#') root=NULL; //建立一棵空树else{root=new BINODE<T>; //生成一个结点root->data=ch;creat(root->lchild); //递归建立左子树creat(root->rchild); //递归建立右子树}}//各种遍历的非递归算法void preorder(BINODE<T> *root) //定义前序遍历函数{int top=-1; //采用顺序栈，并假定不会发生上溢while(root!=NULL || top!=-1){while(root!=NULL){cout<<root->data;stack[++top]=*root;root=root->lchild;}if(top!=-1){root=&stack[top--];root=root->rchild;}}}void inorder(BINODE<T> *root) //定义中序遍历函数{int top=-1; //采用顺序栈，并假定不会发生上溢while(root!=NULL || top!=-1){while(root!=NULL){stack[++top]=*root;root=root->lchild;}if(top!=-1){root=&stack[top--];cout<<root->data;root=root->rchild;}}}void postorder(BINODE<T> *root) //定义后序遍历函数{int top=-1; //采用顺序栈，并假定不会发生上溢while(root!=NULL || top!=-1){while(root!=NULL){top++;s[top].ptr=root;s[top].flag=1;root=root->lchild;}while(top!=-1 && s[top].flag==2){root=s[top--].ptr;cout<<root->data;if(top==-1);root=NULL;}if(top!=-1){s[top].flag=2;root=s[top].ptr->rchild;}}}void levelorder(BINODE<T> *root) //定义层序遍历函数{int front,rear; //采用顺序队，并假定不会发生上溢front=rear=0;if(root==NULL) return;queue[++rear]=*root;while(front!=rear){q=&queue[++front];cout<<q->data;if(q->lchild!=NULL) queue[++rear]=*(q->lchild);if(q->rchild!=NULL) queue[++rear]=*(q->rchild);}}//各种遍历的递归算法void dgpreorder(BINODE<T> *root) //定义前序遍历递归函数{if(root==NULL) return; //递归调用的结束条件else{cout<<root->data; //访问根结点的数据域dgpreorder(root->lchild); //前序递归遍历root的左子树dgpreorder(root->rchild); //前序递归遍历root的右子树}}void dginorder(BINODE<T> *root) //定义中序遍历递归函数{if(root==NULL) return; //递归调用的结束条件else{dginorder(root->lchild); //中序递归遍历root的左子树cout<<root->data; //访问根结点的数据域dginorder(root->rchild); //中序递归遍历root的右子树}}void dgpostorder(BINODE<T> *root) //定义后序遍历递归函数{if(root==NULL) return; //递归调用的结束条件else{dgpostorder(root->lchild); //后序递归遍历root的左子树dgpostorder(root->rchild); //后序递归遍历root的右子树cout<<root->data; //访问根结点的数据域}}//求叶子结点数、深度、交换左右子树算法void countleaf(BINODE<T> *root,int &count) //定义求叶子结点的函数//前序遍历根指针为root的二叉树以计算叶子数count，假定count 的初值为0;{if(root!=NULL){if(root->lchild==NULL && root->rchild==NULL)count++; //若root所指的结点是叶子，则计数器加1; countleaf(root->lchild,count); //累计左子树上的叶子数; countleaf(root->rchild,count); //累计右子树上的叶子数; }}int depth(BINODE<T> *root) //定义求深度的函数{int hl,hr;if(root==NULL) return 0;else{hl=depth(root->lchild);hr=depth(root->rchild);return (hl>hr?hl:hr)+1;}}void exchange(BINODE<T> *root) //定义交换左右子树的函数{if(root){exchange(root->lchild);exchange(root->rchild);temp=root->lchild; //交换左右子树root->lchild=root->rchild;root->rchild=temp;}}};void main(){BiTree<char> my;cout<<"请依次输入拓展二叉树的前序遍历序列:\n";my.creat(root);first=root;cout<<"以下为非递归算法的各种遍历序列:\n"; cout<<"二叉树的前序遍历序列为:";my.preorder(first);cout<<"\n二叉树的中序遍历序列为:";my.inorder(first);cout<<"\n二叉树的后序遍历序列为:";my.postorder(first);cout<<"\n二叉树的层序遍历序列为:";my.levelorder(first);cout<<"\n以下为递归算法的各种遍历序列:\n"; cout<<"二叉树的前序遍历序列为:";my.dgpreorder(first);cout<<"\n二叉树的中序遍历序列为:";my.dginorder(first);cout<<"\n二叉树的后序遍历序列为:";my.dgpostorder(first);my.countleaf(first,count);cout<<"\n叶子结点的个数:"<<count;cout<<"\n二叉树的深度为:"<<my.depth(first); my.exchange(first);cout<<"\n交换后的中序遍历序列为:";my.inorder(first);cout<<"\n";}。
