51CTO下载-数据结构实验报告大全(严蔚敏版).doc

《51CTO下载-数据结构实验报告大全(严蔚敏版).doc》由会员分享，可在线阅读，更多相关《51CTO下载-数据结构实验报告大全(严蔚敏版).doc（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计 算 机 课 程 实 验 报 告（2013 2014 年度第 一 学期）专业 软件工程 课程 数据结构 班级 一班 组别 第七组 教师 xxxx 电 子 信 息 工 程 学 院 制实验报告填写说明1. 填写一律用钢笔或圆珠笔填写，要求字迹工整，条理清晰。2. “实验题目”可以填写章节名称或用文字表述。3. “实验目的”要逐条列出，“实验内容”以简练的文字进行概括。4. “附注”处填写实验注意事项或调试过程，以及实验中出现的异常情况和解决方法。5. “教师批阅”处有课任老师填写评语，给出实验成绩，并作为平时成绩，参与期末成绩总评。目 录1. 线性表抽象数据类型的实现与应用 32. 栈和队列抽象

2、数据类型的实现与应用 153. 串的实现及其应用 304. 树抽象数据类型的实现与应用 355. 图抽象数据类型的实现与应用 466. 查找方法的实现 507. 排序方法的实现以及比较 54 2013年9月30日实验项目1：线性表的顺序存储以及相关操作实现实验目的：1.掌握数据结构中线性表的顺序存储结构以及操作;2.了解数据结构中线性表的顺序存储基本操作原理3.掌握数据结构中基本算法的设计方法. 4.掌握程序的基本测试方法。实验仪器：计算机、C语言版数据结构相关实验题集、编写程序软件实验规划：（包括函数说明、公共变量说明、测试说明等）公共变量声明：#include#include#define

3、 TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1 #define LIST_INIT_SIZE 200 /设置空间大小为200#define LISTINCREMENT 10 / 增加空间大小10typedef int DataType; typedef struct DataType dataLIST_INIT_SIZE ;/定义一个数组data，用来存放节点； int length;/定义一个长度 int listsize; / 顺序表的储存空间大小SqList; 程序中的主要函数及功能说明1. voi

4、d CreateList(SqList *L)/建立线性表，无返回值2. void Printlist(SqList L)/打印线性表，无返回值3. int LocateList(SqList L, DataType newelem)/查询元素的位置 ，查找元素是：newelem 返回值类型为：int型4. void InsertList(SqList *L, DataType newelem, int position);/插入线性表中元素，插入的位置是：position 插入的元素是：newelem。无返回值5. void DeleteList(SqList *L, DataType ne

5、welem);/删除线性表元素，删除的元素是newelem 并上一个元素依次移动 无返回值测试说明：1. 创建顺序表元素个数为5，元素分别是：6 9 8 7 4预期结果打印出6 9 8 7 4 。 2插入元素：1，插入位置：2 预期结果是：6 1 9 8 7 4 3：查找元素：4 预期结果：4 ； 4：删除元素：8 预期结果：6 1 9 7 4 小组各成员工作分配情况表：胡超：统一定义常量，结构体模版，函数格式（参数、返回值）；编写插入函数，检查编写函数。肖煜：编写创建线性表函数删除线性表中的元素和测试程序容明彬： 编写打印函数，编写查找函数。实验内容及步骤（或程序清单）：内容：此线性表采顺序

6、式存储，实现了建表、查找、插入、删除、打印等功能。#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define LIST_INIT_SIZE 200/设空间大小为200#define LISTINCREMENT 10typedef int DataType;typedef struct DataType dataLIST_INIT_SIZE ;/定义一个数组data，用来存放节点； int length;/定义一个长度 int listsize; / 顺序表的

7、储存空间大小SqList;int main(void) SqList L;/定义一个顺序表L； DataType newelen; int i, position;/ 定义元素的位置 char m; L.length = 0;/初始化顺序表的长度 do printf(n); printf(#顺序线性表功能菜单#n); printf(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxn); printf(x 1：建立线性表 x 4：线性表从小到大排序xn); printf(x 2：插入元素 x 5：查找元素 xn); printf(x 3：删除特定元素x 6：退出程

8、序 xn); printf(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxn); printf(n*请输入你的选择：); scanf(%c, &m); switch(m) case 1:printf(输入元素的个数n); CreateList(&L); Printlist(L); break; case 2:printf(n); Printlist(L); printf(输入要插入的元素位序：n); scanf(%d, &position); printf(请输入要插入的数据元素：n); scanf(%d, &newelen); InsertList(&L,

9、newelen, position); Printlist(L); break; case 3:printf(n); Printlist(L); printf(请输入要删除的特定数据元素：); scanf(%d, &newelen); DeleteList(&L, newelen); Printlist(L); break; case 4:printf(n); printf(没有实现排序); break; case 5:printf(n); Printlist(L); printf(输入要查找的值：); scanf(%d, &newelen); i = LocateList(L, newele

10、n); printf(所要查找的值在位序：%dn, i); break; case 6:break; default: printf(n); Printlist(L); printf(您输入的有误！); break; getchar(); while(m != 6); system(pause);void CreateList(SqList *L);/建立线性表int LocateList(SqList L, DataType newelem);/查询线性表中元素位置void InsertList(SqList *L, DataType newelem, int position);/插入线性

11、表中元素void DeleteList(SqList *L, DataType newelem);/删除线性表中的某一元素，并依次移动元素void Printlist(SqList L);/打印线性表 scanf(%d, &L-datai); L-length = n;int LocateList(SqList L, DataType newelem)/查找L中元素位置，并用打印函数输出 int i; i = L.length;/i等于线性表的长度 L.data1 = newelem;/将输入的新元素赋给线性表的存储空间的第一个元素while(L.datai!=newelem)/将新输入的元素

12、与线性表的元素比较，若不等就继续查找，否则返回元素的位序 i-; return i;/返回查找元素的位序void InsertList(SqList *L, DataType newelem, int position)/在L表中插入新的元素，newelem，若超过线性表的长度，中文提示错误 int i; if(position L-length+1)/插入位序小于1或超出线性表的长度，提示有误 printf(插入位置不对n); else for(i = L-length; i=position; i-) L-datai+1 = L-datai;/插入位置及之后的元素右移 L-dataposi

13、tion = newelem; / 将新的元素newelem插入到position之前的位置 L-length+; / 表的长度增1 return; void DeleteList(SqList *L, DataType newelem)/指定元素删除 int i,j=0; for(i=1; ilength; i+) if(L-datai != newelem) j +; L-dataj = L-datai;/从第一个元素开始，将删除元素不等的元素转移到另一个新数组中 L-length = j;void Printlist(SqList L)/输出函数，输出所有的元素 int i; print

14、f(线性表是： ); for (i=1; i=L.length; i+) printf( %d, L.datai)/线性表中元素逐个打印出; printf(n);附 注实验结果分析：1,空的链表初始化成功;2,创建链表并输入数据;3.显示链表内容，便于排错4，插入结点并显示;5,查找某结点内数据6,删除某结点;8:总结：1.若插入的位置是0，则插入不成功，要注意顺序表的存储空间是否足够插入新的元素，若不足，则应增加新的存储空间。2.查找是把新输入元素和顺序表中的元素比较。比较的顺序从后至前比较，找到相同的元素，则查找成功3.输入删除的元素，也是和已有的元素比较，找到相同的元素则删除该元素优点：

15、组员合作很好。缺点：没能成功实现排序功能，有待于提高。改进：第7组还需努力。教师批阅： 2013年9月30日实验项目1：线性表的链式存储以及相关操作实现实验目的：1.掌握数据结构中线性表的链式存储结构以及操作;2.了解数据结构中线性表基本操作原理3.掌握C语言中基本程序设计的方法. 4.掌握基本测试方法。实验仪器：计算机、C语言版数据结构相关实验题集、编写程序软件实验规划：（包括函数说明、公共变量说明、测试说明等）公共变量声明：#include #include #define OK 1#define ERROR 0typedef int Status;/定义Status为int类型typed

16、ef int ElemType;/定义ElemType为int类型typedef struct LNode int data; struct LNode *next;LNode, *LinkList; /定义LNode结构体；void CreateList_L(LinkList L, int n);/创建链表void printList_L(LinkList L, int n);/打印出链表内容Status GetElem_L(LinkList L,int i,ElemType e);/查找链表中的元素Status InsertList_L(LinkList L, int i, ElemTyp

17、e e);/插入链表Status DeleteList_L(LinkList L, int i, ElemType e);/删除链表中特定位置元素测试说明：1. 创建顺序表元素个数为6，元素分别是： 1 2 3 5 9 8预期结果打印出1 2 3 5 9 8 2插入元素：2，插入位置：4 预期结果是：1 2 3 7 5 9 8 3：查找元素：5 预期结果：7 4：删除元素：3 预期结果：7 小组各成员工作分配情况表：胡超：统一定义常量，结构体模版，函数格式（参数、返回值）；编写插入函数，检查编写函数。肖煜：编写创建线性表函数删除线性表中的元素和测试程序容明彬： 编写打印函数，编写查找函数。实验

18、内容及步骤（或程序清单）：#include #include #define OK 1#define ERROR 0typedef int Status;/定义Status为int类型typedef int ElemType;/定义ElemType为int类型typedef struct LNode int data; struct LNode *next;LNode, *LinkList; /定义LNode结构体；void CreateList_L(LinkList L, int n);/创建链表void printList_L(LinkList L, int n);/打印出链表内容Stat

19、us GetElem_L(LinkList L,int i,ElemType e);/查找链表中的元素Status InsertList_L(LinkList L, int i, ElemType e);/插入链表Status DeleteList_L(LinkList L, int i, ElemType e);/删除链表中特定位置元素int main(void) int n,i; LNode *L;/定义L指针，并申请空间，作为头指针 L = (LinkList)malloc(sizeof(LNode); char m; do printf(n); printf(#链表功能菜单#n); p

20、rintf(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxn); printf(x 1：建立链表 x 4：删除元素 xn); printf(x 2：查找元素 x 5： xn); printf(x 3：插入元素 x 6：退出程序 xn); printf(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxn); printf(n*请输入你的选择：); scanf(%c, &m); switch(m) case 1: printf(输入链表的大小); scanf(%d, &n); CreateList_L(L, n); printList_L(L, n);

21、 break; case 2: printf(查找的位置是：); scanf(%d, &i); int e = GetElem_L(L, i,e); printf(元素是：%dn, e); break; case 3: printf(插入的元素位置是 n); scanf(%d, &i); printf(插入的元素是：n); scanf(%d, &e); InsertList_L(L, i, e); printList_L(L, n+1); break; case 4: printf(删除的元素的位置n); scanf(%d, &i); DeleteList_L(L,i,e); printLis

22、t_L(L, n-1); break; case 5: printf( ); printList_L(L, n); break; case 6: break; default: printf(n); printList_L(L, n); printf(您输入的有误！); break; getchar(); while(m !=6); system(pause); return 0;void CreateList_L(LinkList L, int n)/逆位序输入n个元素的值，建立带头结点的单线性链表L. int i; LNode *p; L = (LinkList)malloc(sizeof

23、(LNode); L - next = NULL;/先建立一个带头结点的单链表 for(i = n; i0; -i) p = (LinkList)malloc(sizeof(LNode);/生成新结点 printf(输出元素的值：n); scanf(%d, &p-data);/输入元素的值 p - next = L - next;/插入到表头 L - next = p; void printList_L(LinkList L, int n)/输出长度为n的，链表 int i; LNode *p; printf(链表是:n); for( i=1; idata); p = p-next;/指向下一

24、个，打印出指针的内容 printf(n);Status GetElem_L(LinkList L,int i,ElemType e)/L为带头结点的单链表的头指针。/当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORint j;struct LNode *p;p = L-next; j = 1;/初始化，p指向第一个结点，j为计算器while (p & jnext; +j;if (!p | ji) return ERROR;/第i个元素不存在e = p-data;/取第i个元素赋给e return OK;Status InsertList_L(LinkList L, int i, E

25、lemType e)/在带头结点的单线性链表L中第i个元素之前插入元素estruct LNode *p = NULL;int j = 0;p = L;struct LNode *s;while(p & j next; +j;/寻找第i-1个结点if(!p | ji-1) return ERROR;s = (LinkList)malloc(sizeof(LNode);/生成新结点s - data = e; s - next = p - next;p - next = s;/插入L中return OK;Status DeleteList_L(LinkList L, int i, ElemType

26、e)/在带头结点的单链表L中，删除第i个元素，并有e返回其值struct LNode *q ;struct LNode *p ;int j = 0;p = L;while (p - next & j next; +j;if (!p - next) | j i-1) return ERROR;/删除位置不合理q = p - next; p - next = q - next;e = q - data; free(q);/删除并释放结点return OK;附 注实验结果分析：1. 空的链表初始化成功;2.创建链表并输入数据;3.显示链表内容，便于排错4.插入结点并显示;5.查找某结点内数据6.删除

27、某结点;7,结束;优点：组员合作很好。缺点：没能成功实现查找功能，查找有错，无法正确显示值，有待于提高。改进：第7组还需努力。教师批阅： 2013年10月20日实验项目2：栈的链式存储以及相关操作实现实验目的：1.掌握数据结构中栈的链式存储结构以及操作;2.了解数据结构中栈的链式存储基本操作原理3.掌握数据结构中栈的基本算法的设计方法. 4.掌握程序的基本测试方法。实验仪器：计算机、C语言版数据结构相关实验题集、编写程序软件实验规划：（包括函数说明、公共变量说明、测试说明等）公共变量声明：#include #define SIZE sizeof(LINKSTACK)#define PRINT_

28、ITEM %d /定义输出项的宏#define SCANF_ITEM %d /定义输入项的宏typedef int bool; /定义bool类型bool true = 1; /定义bool类型true常量bool false = 0; /定义bool类型false常量typedef int ELEMTYPE; /定义元素类型typedef struct snode /定义链栈 ELEMTYPE data; struct snode *next; LINKSTACK;程序中的主要函数及功能说明1.onst ELEMTYPE STACK_NULL = -9999;/定义常量栈为NULL的值 2.

29、 LINKSTACK * INITSTACK(); /初始化栈，返回stack3.LINKSTACK * CREATESTACK(ELEMTYPE); /创建链栈, 返回head4.LINKSTACK * PUSH(LINKSTACK *,ELEMTYPE);/进栈操作 返回top5.ELEMTYPE GETTOP(LINKSTACK *);/获取栈顶元素 返回结果result6.LINKSTACK * POP(LINKSTACK *);/出栈操作 返回top7.bool EMPTY(LINKSTACK *);/判断栈是否为NULL 返回结果result8.LINKSTACK * CLEAR(

30、LINKSTACK *); /清空链栈 返回top9.int CURRENT_SIZE(LINKSTACK *); /当前链栈中 的元素个数，返回值是INT型，返回元素个数10.void PRINT_STACK(LINKSTACK *);/打印链栈元素 无返回值11.void menu(); /菜单 无返回值12.void print_enter(); /打印回车 无返回值13.void print_tab(); /打印tab 无返回值14.void print_menu_item(char *,char *); /打印菜单中的每一项 无返回值15.void print_str(char *)

31、; 无返回值16.void print_info(char *,bool); /打印信息，bool意思是是否打印回车 无返回值17.ELEMTYPE get_input();/获取压栈的数据 ，返回结果result18.LINKSTACK * stack_push(LINKSTACK *);/压入链栈 返回top19.LINKSTACK * stack_pop(LINKSTACK *);/出栈返回top20.LINKSTACK * stack_get_top(LINKSTACK *); /获取栈顶元素返回top21.LINKSTACK * stack_empty(LINKSTACK *); /

32、判断栈是否为空返回top22.LINKSTACK * stack_cur_size(LINKSTACK *);/获取栈中的元素个数返回top23.LINKSTACK * stack_clear(LINKSTACK *);/清空栈中元素返回top24.LINKSTACK * link_stack_method(LINKSTACK *,LINKSTACK * (* fun)(LINKSTACK *); /定义函数指针返回 （*fun）(top)测试说明：1.创建一个空栈并初始化 预期结果 内存分配正确2入栈：预期结果是：元素一个个入栈成功 元素为：3 6 9 73：获取栈顶元素：预期结果： 74：

33、出栈：预期结果：只出栈顶元素 75：计算栈的元素个数：预期结果 ：46：清空栈： 预期结果：栈能够清空小组各成员工作分配情况表：胡超：统一定义常量，结构体模版，函数格式（参数、返回值）；编写获取栈元素数，检查编写函数以及测试程序。肖煜：编写创建空栈函数和获取栈顶元素容明彬： 编写入栈函数，清栈函数。陈亮：编写出栈函数 判断链栈是否为空实验内容及步骤（或程序清单）：程序实现栈的创建空栈 入栈 出栈 清空栈元素 计算栈中元素以及判断链栈是否为空的个数等功能。#include #define SIZE sizeof(LINKSTACK)#define PRINT_ITEM %d /定义输出项的宏#d

34、efine SCANF_ITEM %d /定义输入项的宏typedef int bool; /定义bool类型bool true = 1; /定义bool类型true常量bool false = 0; /定义bool类型false常量typedef int ELEMTYPE; /定义元素类型typedef struct snode /定义链栈 ELEMTYPE data; struct snode *next; LINKSTACK;ELEMTYPE STACK_NULL = -9999;/定义常量栈为NULL的值LINKSTACK * INITSTACK(); /初始化栈LINKSTACK *

35、 CREATESTACK(ELEMTYPE); /创建链栈LINKSTACK * PUSH(LINKSTACK *,ELEMTYPE);/进栈操作ELEMTYPE GETTOP(LINKSTACK *);/获取栈顶元素LINKSTACK * POP(LINKSTACK *);/出栈操作bool EMPTY(LINKSTACK *);/判断栈是否为NULLLINKSTACK * CLEAR(LINKSTACK *); /清空链栈int CURRENT_SIZE(LINKSTACK *); /当前链栈中的元素个数void PRINT_STACK(LINKSTACK *);/打印链栈元素void m

36、enu(); /菜单void print_enter(); /打印回车void print_tab(); /打印tabvoid print_menu_item(char *,char *); /打印菜单中的每一项void print_str(char *);void print_info(char *,bool); /打印信息，bool意思是是否打印回车ELEMTYPE get_input();/获取压栈的数据LINKSTACK * stack_push(LINKSTACK *);/压入链栈LINKSTACK * stack_pop(LINKSTACK *);/出栈LINKSTACK * stack_get_top(LINKSTACK *); /获取栈顶元素LINKSTACK * stack_empty(LINKSTACK *); /判断栈是否为空LINKSTACK * stack_cur_size(LINKSTACK *);/获取栈中的元素个数LINKSTACK * stack_clear(LINKSTACK *);/清空栈中元素LINKSTACK * link_stack_method(LINKSTACK *,LINKSTACK * (* fun)(LINKSTACK *); /定义函数指针