中南大学数据结构试验报告

1、 数据结构实验报告课程名称数据结构学生姓名指导教师学 院信息科学与工程学院专业班级通信工程实验一 线性表基本操作和简单程序1 实验目的 掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。2 实验要求（1） 认真阅读和掌握和本实验相关的教材内容。（2） 认真阅读和掌握本章相关内容的程序。（3） 上机运行程序。3.实验代码：1）头文件模块#include iostream.h/头文件#include/库头文件-动态分配内存空间typedef int elemtype;/定义数据域的类型typedef struct linknode/定义结点类型

2、 elemtype data;/定义数据域 struct linknode *next;/定义结点指针nodetype;2）创建单链表nodetype *create()/建立单链表，由用户输入各结点data域之值，/以0表示输入结束 elemtype d;/定义数据元素d nodetype *h=NULL,*s,*t;/定义结点指针 int i=1; cout建立一个单链表endl; while(1) cout 输入第 i d; if(d=0) break;/以0表示输入结束 if(i=1)/建立第一个结点 h=(nodetype*)malloc(sizeof(nodetype);/表示指针

3、h h-data=d;h-next=NULL;t=h;/h是头指针 else/建立其余结点 s=(nodetype*) malloc(sizeof(nodetype); s-data=d;s-next=NULL;t-next=s; t=s;/t始终指向生成的单链表的最后一个节点 i+; return h; 3）输出单链表中的元素void disp(nodetype*h)/输出由h指向的单链表的所有data域之值 nodetype *p=h; cout输出一个单链表:endl ; if(p=NULL)cout空表; while(p!=NULL) coutdatanext; coutnext;i+

4、; return i;5）寻找第i个节点nodetype *find(nodetype *h,int i)/返回第i个节点的指针 nodetype *p=h; int j=1; if(ilen(h)|i=0) return NULL;/i上溢或下溢c else while (p!=NULL&jnext; return p; 6）单链表的插入操作nodetype *ins(nodetype *h,int i,elemtype x)/在单链表head中第i个节点/（i=0）之后插入一个data域为x的节点 nodetype *p,*s; s=(nodetype*)malloc(sizeof(nod

5、etype);/创建节点s s-data=x;s-next=NULL; if(i=0)/i=0:s作为该单链表的第一个节点 s-next=h;h=s; else p=find(h,i);/查找第i个节点，并由p指向该节点 if(p!=NULL) s-next=p-next; p-next=s; return h; 7）单链表的删除操作nodetype *del(nodetype *h,int i)/删除第i个节点 nodetype *p=h, *s; int j=1; if(i=1)/删除第1个节点 h=h-next;free(p); else p=find(h,i-1);/查找第i-1个节点

6、，并由p指向该节点 if(p!=NULL&p-next!=NULL) s=p-next;/s指向要删除的节点 p-next=s-next; free(s); else cout输入i的值不正确next; if(pb=NULL)/只有一个节点的情况 free(pa); else while (pb!=NULL)/有两个及以上节点的情况 free(pa);pa=pb;pb=pb-next; free(pa); 4.实验心得体会 线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。我们需要做到熟练掌握线性表的基本操作，为以后学习的内容做铺垫。实验二 二叉树的基本操作1.实验目的（1）

7、进一步掌握指针变量的用途和程序设计方法。（2） 掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。（3） 掌握构造二叉树的基本方法。（4） 掌握二叉树遍历算法的设计方法。3 实验要求（1）认真阅读和掌握和本实验相关的教材内容。（2）掌握一个实际二叉树的创建方法。（3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。4 实验内容（1）定义二叉链存储结构。（2）设计二叉树的基本操作（初始化一棵带头结点的二叉树、左结点插入、右结点插入、中序遍历二叉树等）。（3）按照建立一棵实际二叉树的操作需要，编写建立二叉树、遍历二叉树的函数。（4）编写测试主函数并上机运行。打印出运行结果，并

8、结合程序运行结果进行分析。实验代码：/二叉树的基本操作#includestdio.h#define max 30#define NULL 0typedef struct BNode char data; /* 数据域 */ struct BNode *lchild,*rchild; /* 指向左右子女 */BinTree;void preorder(BinTree *t); /* 声明先根遍历函数 */void inorder(BinTree *t); /* 声明中根遍历函数 */void postorder(BinTree *t);/* 声明后根遍历函数 */int leafs(BinTre

9、e *b); /* 声明求叶子数函数 */int treedeep(BinTree *p); /* 声明求树的深度函数 */BinTree *swap(BinTree *p); /* 声明交换二叉树的所有结点的左右子树的函数 */* 将字符串中的第i个字符开始的m个字符作为数据生成对应的二叉树 */BinTree *cre_tree(char *str,int i,int m) BinTree *p; if(i=m) /* 无效结点 */ return NULL; p=(BinTree *)malloc(sizeof(BinTree);/* 生成新结点 */ p-data=stri; p-lc

10、hild=cre_tree(str,2*i+1,m);/* 创建新结点的左子树 */ p-rchild=cre_tree(str,2*i+2,m);/* 创建新结点的右子树 */ return p;void main() int i,n; char strmax; BinTree *root;/* 根结点 */ printf(请输入二叉树的结点数:); scanf(%d,&n); getchar();/* 输入数字 */ printf(请输入长度为 %d 的字符串 :,n); for(i=0;in;i+) scanf(%c,&stri); printf(n); root=cre_tree(st

11、r,0,n); printf(二叉树已成功创建! 结点序列为：); for(i=0;idata); if(t-lchild) printf(-); preorder(t-lchild); if(t-rchild) printf(-); preorder(t-rchild); void inorder(BinTree *t) if(t!=NULL) inorder(t-lchild); printf( %c ,t-data); inorder(t-rchild); void postorder(BinTree *t) if(t!=NULL) postorder(t-lchild); postor

12、der(t-rchild); printf( %c ,t-data); int leafs(BinTree *b)/* 求叶子数 */ int num1,num2; if(b=NULL) return (0); else if(b-lchild=NULL & b-rchild=NULL) return (1); else num1=leafs(b-lchild); num2=leafs(b-rchild); return(num1+num2); int treedeep(BinTree *p)/* 求树的深度 */ int ldeep,rdeep,deep; if(p=NULL) deep=0

13、; else ldeep=treedeep(p-lchild); rdeep=treedeep(p-rchild); deep=(ldeeprdeep?ldeep:rdeep)+1; return deep;BinTree *swap(BinTree *p)/* 交换二叉树的所有结点的左右子树 */ BinTree *stackmax; int k=0; stackk=NULL; if(p!=NULL) stack+k=p-lchild; p-lchild=p-rchild; p-rchild=stackk; p-lchild=swap(p-lchild); p-rchild=swap(p-r

14、child); return p;6. 实验心得： 通过本次实验，将课本上的只是用于实际操作。进一步掌握指针变量的用途和程序设计方法。二叉树的结构特征，以及链式存储结构的特点及程序设计方法。构造二叉树的基本方法。二叉树遍历算法的设计方法。掌握了二叉树的基本操作。实验三 图的相关操作1.实验要求1.1 熟悉图的各种存储方法。1.2 掌握遍历图的递归和非递归的算法。1.3 理解图的有关算法。2. 实验内容#include stdio.h#define maxsize 1024 /*假定线性表的最大长度为1024*/#define n 100 /* 图的顶点最大个数 */typedef int da

15、tatype; /*假定线性表元素的类型为整型*/typedef char VEXTYPE; /* 顶点的数据类型 */typedef float ADJTYPE; /* 权值类型 */typedef struct VEXTYPE vexsn ; /* 顶点信息数组 */ ADJTYPE arcsnn ; /* 边权数组 */ int num ; /* 顶点的实际个数 */ GRAPH;/* 1.置空图 */void GraphInit(GRAPH *L) L-num=0;/* 2.求结点数 */int GraphVexs(GRAPH *L) return(L-num);/* 3.创建图 */

16、void GraphCreate(GRAPH *L) int i,j; GraphInit(L); printf(请输入顶点数目：); scanf(%d,&L-num); printf(请输入各顶点的信息(单个符号）：); for(i=0;inum;i+) fflush(stdin); scanf(%c,&L-vexsi); printf(请输入边权矩阵的信息：); for(i=0;inum;i+) for(j=0;jnum;j+) scanf(%f,&L-arcsij); printf(图已经创建完毕！);/* 4.图的输出 */void GraphOut(GRAPH L) int i,j;

17、 printf(n图的顶点数目为：%d,L.num); printf(n图的各顶点的信息为：n); for(i=0;iL.num;i+) printf(%c ,L.vexsi); printf(n图的边权矩阵的信息为：n); for(i=0;iL.num;i+) for(j=0;jL.num;j+) printf(%6.2f ,L.arcsij); printf(n); printf(图已经输出完毕！);/* 5.图的深度周游 */void DFS(GRAPH g,int qidian,int mark)/* 从第qidian个点出发深度优先周游图g中能访问的各个顶点 */ int v1; m

18、arkqidian=1; printf(%c ,g.vexsqidian); for(v1=0;v1g.num;v1+) if(g.arcsqidianv1!=0&markv1=0) DFS(g,v1,mark); /* 6.图的深度周游 */void GraphDFS(GRAPH g)/* 深度优先周游图g中能访问的各个顶点 */ int qidian,v,v1,markmaxsize; printf(n深度周游：); printf(n请输入起点的下标：); scanf(%d,&qidian); for(v=0;vg.num;v+) markv=0; for(v=qidian;vfront=

19、0; sq-rear=0;int QueueIsEmpty(SEQQUEUE sq)/* 如果顺序循环队列sq为空，成功返回1，否则返回0 */ if (sq.rear=sq.front) return(1); else return(0); int QueueFront(SEQQUEUE sq,DATATYPE *e)/* 将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0 */ if(QueueIsEmpty(sq) printf(queue is empty!n);return 0; else *e=sq.data(sq.front); return 1;int Que

20、ueIn (SEQQUEUE *sq,DATATYPE x)/* 将元素x入队列sq的队尾，成功返回1，失败返回0 */ if (sq-front=(sq-rear+1)%maxsize) printf(queue is full!n); return 0; else sq-datasq-rear=x; sq-rear=(sq-rear+1)%maxsize; return(1); int QueueOut(SEQQUEUE *sq)/* 将队列sq队首元素出队列，成功返回1,失败返回0 */ if(QueueIsEmpty(*sq) printf(queue is empty!n); ret

21、urn 0; else sq-front=(sq-front+1)%maxsize; return 1; /* 7.图的广度周游 */void BFS(GRAPH g,int v,int mark)/* 从v出发广度优先周游图g中能访问的各个顶点 */ int v1,v2; SEQQUEUE q; QueueInit(&q); QueueIn(&q,v); markv=1; printf(%c ,g.vexsv); while(QueueIsEmpty(q)=0) QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2g.num;v2+) if(g.arcsv

22、1v2!=0&markv2=0) QueueIn(&q,v2); markv2=1; printf(%c ,g.vexsv2); /* 8.图的广度周游 */void GraphBFS(GRAPH g)/* 深度优先周游图g中能访问的各个顶点 */ int qidian,v,v1,markmaxsize; printf(n广度周游：); printf(n请输入起点的下标：); scanf(%d,&qidian); for(v=0;vg.num;v+) markv=0; for(v=qidian;vg.num+qidian;v+) v1=v%g.num; if(markv1=0) BFS(g,v

23、1,mark); void main() GRAPH tu; GraphCreate(&tu); GraphOut(tu); GraphDFS(tu); GraphBFS(tu);实验四 排序的基本操作 一、 实验目的1通过实验掌握排序的基本概念，对排序的稳定性及排序的时间复杂性有深刻的认识。2掌握各种排序方法的基本思想和算法实现。3能够灵活地选用某种排序方法解决问题。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 保存程序的运行结果，并结合程序进行分析。三、 实验内容 编写一个程序，对所给的数据(程序中给出或通过键盘初始化均可)进行排序，要求尽可能多的选择不同的排序算法，并显示排序前和

24、排序后的结果。四、程序流程图、算法及运行结果算法：常用排序算法总结及C源程序/*直接插入排序*/void InsertSort(int *out, int *op, int length)int i, j;int data; memcpy(out, op, length * sizeof(int);for(i = 1; i length; i+)data = out;for(j = i-1; data =0; j-) outj+1 = outj;outj+1 = data;/*折半插入排序*/void BInsertSort(int *out, int *op, int length)int

25、low, mid, high; int i, j, data;memcpy(out, op, length * sizeof(int);for(i = 1; i length; i+)data = out;low = 0;high = i - 1;while(low = high) mid = (low+high) / 2; if(data = high+1; j-) outj+1 = outj;outj+1 = data;/*冒泡算法*/void BubbleSort(int *out, int *op, int length)int i, j;memcpy(out, op, length * sizeof(int);for(i = length-1; i = 0; i-)for(j = 0; j outj+1) swap(out+j, out+j+1); /*快速排序*/int Partition(int *out, int *op, int length, int low, int high)int pivokey;memcpy(out, op, length * siz