《数据结构》(C语言)实验报告

1、数据结构实验报告姓名： 刘 高学号：031041113成绩： 目录 实验一，线性表的应用3实验二，栈和队列的应用8实验三，数组的应用13实验四，树和二叉树的应用19实验五，图的应用24实验六，查找表的应用32实验七，排序算法的应用44 实验一 线性表的应用【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本实现；4. 通过对本章实验帮助学生加深对C语言的使用（特别是函数参数调用、指针类型的应用和链表的建立等各种基本操作）。【实验内容】约瑟夫问题的实现：n只猴子

2、要选猴王，所有猴子按1,2，n编号围坐一圈，从第1只开始按1，2，m报数，凡报到m号的猴子退出圈外，如此循环报数，直到圈内省剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】1. 要求用顺序表和链表分别实现约瑟夫问题；2. 独立完成，严禁抄袭；3. 上交的实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序：#include<stdio.h>#include<stdlib.h>#define Maxsize 80struct SeqList int dataMa

3、xsize; int len;typedef struct SeqList SeqList;void InitList(SeqList *L) L=(SeqList *)malloc(sizeof(SeqList); L->len=0;void MadeList(SeqList *L) int i; int people; printf("请输入参选的总数:n"); scanf("%d",&people); for (i=0;i<people;i+) L->datai=i+1; printf(" %d ",L

4、->datai); printf("n"); L->len=people;void WentList(SeqList *L) int m,i,j; int k=0; printf("请输入出列数：n"); scanf("%d",&m); for (i=L->len;i>0;i-) k=(k+m-1)%i; printf(" %d ",L->datak); for (j=k;j<i-1;j+) L->dataj=L->dataj+1; L->len=L-&

5、gt;len-1; printf("n");void main() SeqList *L; InitList(L); MadeList(L); WentList(L);二，运行结果及截屏视图：实验二 栈和列队的应用【实验目的】1. 熟练掌握栈和列队的结构，以及这两种数据结构的特点；2. 能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空时的判断条件和描述方法；3. 熟练掌握链队列和循环列表的基本运算，特别注意队列满和队列空时的判断条件和描述方法。【实验内容】表达式求值的实现：输入一个包含“+“、”-“、”*“、”/“、正整数和圆括号的合法表达式，用算法优先法计算该表达

6、式的结果。【实验要求】1. 要求用栈实现表达式求值问题；2. 独立完成，严禁抄袭；3. 上交的实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序: #define DATATYPE1 int#define MAXSIZE 100typedef structDATATYPE1 dataMAXSIZE;int top;SEQSTACK;#include <stdio.h>void initstack(SEQSTACK *s)s->top=0;int push(SEQSTACK *s,DATATYPE1 x)i

7、f(s->top=MAXSIZE-1)printf("栈满n"); return 0;elses->top+;(s->data)s->top=x; return 1;DATATYPE1 pop(SEQSTACK *s)DATATYPE1 x;if(s->top=0)printf("栈空n"); x=0;elsex=(s->data)s->top; s->top-;return x;DATATYPE1 gettop(SEQSTACK *s)DATATYPE1 x;if(s->top=0)printf(&

8、quot;栈空n"); x=0;elsex=(s->data)s->top;return x;check(SEQSTACK *s)int bool;char ch;push(s,'#');printf("请输入一串括号，回车键结束: ");ch=getchar();bool=1;while(ch!='n'&&bool)if(ch='(')push(s,ch);if(ch=')')if(gettop(s)='#') bool=0;else pop(s);ch=

9、getchar();if(gettop(s)!='#')bool=0;if(bool)printf("n括号配对正确n");elseprintf("n括号配对错误n");main()SEQSTACK st,*s;s=&st;initstack(s);check(s);二，实验结果及截屏视图：实验三 数组的应用【实验目的】1. 掌握数组的两种存储表示方法；2. 掌握对特殊矩阵进行压缩存储时的下标变换公式；3. 掌握稀疏矩阵的两种压缩存储方法的特点和适用范围。【实验内容】稀疏矩阵转置的实现:用三元组顺序表做存储结构，实现稀疏矩阵的转置

10、。【实验要求】1. 已知某一稀疏矩阵的三元顺序表，由其直接得到其转置矩阵的三元顺序表；2. 独立完成，严禁抄袭；3. 上交的实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序；#include<stdio.h>#define MAX 80struct tuple3tpint i,j,v;struct sparmattpint m,n,u;struct tuple3tp dataMAX;struct sparmattp a,b;void crt_sparmat()int i;printf("输入稀疏矩阵

11、行值，列值，最大非零元的个数：");scanf("%d%d%d",&a.datai.i,&a.datai.j,&a.datai.v);for(i=1;i<=a.u;i)printf("输入行坐标，列坐标，非零元");scanf("%d%d%d",&a.datai.i,&a.datai.j,&a.datai.v);void trans_sparmat()int col,p,q;b.m=a.n;b.n=a.m;b.u=a.u;if(b.u!=0)q=1;for(col=1;c

12、ol<=a.n;col+)for(p=1;p<=a.u;p+)if(a.datap.j=col)b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;q+;out(struct sparmattp x)int i,j,k,flag;for(i=1;i<=x.m;i+)for(j=1;j<=x.n;j+)flag=0;for(k=1;k<=x.u;k+)if(x.datak.i=i)&&(x.datak.j)=j)flag=1;printf("%5d",x.data

13、k.v);if(flag=0)printf(" 0");main()printf("稀疏矩阵的 建立与专置n");crt_sparmat();trans_sparmat();printf("n");out(a);printf("n");out(b);二，实验结果及截屏视图：实验四 树和二叉树的应用【实验目的】1. 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；2. 重点掌握二叉树的生成、遍历及求深度等算法；3. 掌握哈夫曼树的含义及其应用；4. 掌握运用递归方式描述算法及编写递归C程序的方法，提高

14、算法分析和程序设计能力。【实验内容】二叉树采用二叉链表作存储结构，试编写程序实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目。【实验要求】1. 上交实验报告。2. 独立完成，严禁抄袭。3. 实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序#include<stdio.h>#include<stdlib.h>#define bitreptr struct typ

15、el#define NULL 0#define len sizeof(bitreptr)bitreptr *bt;int f,g;bitreptrchar data;bitreptr *lchild,*rchild;preorder(bitreptr *bt)if(g=1)printf("先序遍历为: n");g=g+1;if(bt)printf("%6c",bt->data);preorder(bt->lchild);preorder(bt->rchild);else if(g=2)printf("树空n");bi

16、treptr *crt_bt()bitreptr *bt;char ch;if(f=1)printf("请输入根节点，以#结束n");else printf("输入节点，以#结束n");scanf("n%c",&ch);f=f+1;if(ch='#')bt=NULL;elsebt=(bitreptr *)malloc(len);bt->data=ch;printf("%c ",bt->data);bt->rchild=crt_bt();printf("%c &qu

17、ot;,bt->data);bt->rchild=crt_bt();return(bt);main()f=1;g=1;bt=crt_bt();preorder(bt);二，实验结果及截屏图示：实验五 图的应用【实验目的】1. 熟练掌握图的邻接矩阵和邻接表的存储方式；2. 实现图的一些基本运算，特别是深度遍历和广度遍历；3. 掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。【实验内容】1. 由给定的顶点和边的信息构造图的邻接矩阵存储；2. 对该图进行深度优先搜索，输出搜索得到的结点序列；3. 以邻接表作存储结构，用克鲁斯卡尔算法构造最小生成树。【实验要求】1. 上交

18、实验报告。2. 独立完成，严禁抄袭。3. 实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一， 源程序：图一：#include<stdio.h>#define INF 9999#define MAXVEX 100typedef char vertexType;typedef float adjtype;typedef structvertexType vexsMAXVEX;adjtype arcsMAXVEXMAXVEX; int n,e;mGraph;void createAdjMatrix(mGraph *G)in

19、t i,j,k;float w;scanf("%d%d",&G->n,&G->e);for(k=0;k<G->n;k+)scanf("%c",&G->vexsk);for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->arcsij=INF;for(k=0;k<G->e;k+)scanf("%d%d%f",&i,&j,&w);G->arcsij=w;G->arcsji=w;void

20、main() mGraph;二， 实验结果及截屏图示：图二：#include<stdlib.h>#include<stdio.h>#include<conio.h>#define MAX_NUM 99typedef structint u,v;int cost;edgesetMAX_NUM;void Kruskal(edgeset E,int m,int n)int x,y,a,b,count,i,p;int vsetMAX_NUM;for(i=0;i<=m;i+) vseti=i;p=0;count=0;while(count<n-1)x=Ep

21、.u;y=Ep.v;a=vsetx;b=vsety;if(a!=b)printf("边：(%d, %d), 权值： %dn",x,y,Ep.cost);count+;for(i=0;i<n;i+)if(vseti=b)vseti=a;p+;void main()int m=6,n=10;edgeset E=0,1,1,1,3,2,3,5,2,2,4,3,1,5,4,1,2,5,2,5,6,4,5,7,0,2,8,3,4,8;Kruskal(E,m,n);截屏视图：实验六 查找表的应用【实验目的】1. 熟悉掌握静态查找表的构造方法和查找算法；2. 熟练掌握二叉排序树的构

22、造和查找方法；3. 熟练掌握哈希表的构造和处理冲突的方法；4. 掌握各种查找表查找效率的分析方法。【实验内容】1. 要求将二叉排序树的建立、插入、删除、显示等算法合并在一个综合程序中、用户可以通过菜单选择方式运行各种操作算法；2. 一直哈希表的表为m，哈希函数为H(key)=key MOD p,用开放定址法（增量序列采用线性探测再散列）解决冲突，试编写构造哈希表的程序。【实验要求】1. 上交实验报告。2. 独立完成，严禁抄袭。3. 实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序：#include<iostream

23、> using namespace std;typedef struct TreeNode int key; struct TreeNode *left; struct TreeNode *right; treeNode; class BiSortTree public: BiSortTree(void); void desplayTree(void); void insertTree(int key); void deleteTree(int key); treeNode* searchTree(int key); BiSortTree(); private: treeNode* bu

24、ildTree(treeNode* head,int number); treeNode* search(treeNode* head ,int key); treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p); treeNode* BiSortTree:searchMinRight(treeNode* head); void showTree(treeNode* head); void destroyTree(treeNode* head); treeNode *Head; ; BiSortTree:BiSortTree(

25、) cout<<"建立一棵二叉排序树,请输入所有节点(以-1 作为结束标志!): "<<endl; Head=NULL; int number; cin>>number; while(number!=-1) Head=buildTree(Head,number); cin>>number; treeNode* BiSortTree:buildTree(treeNode* head,int number) treeNode *p; p=new treeNode; p->key=number; p->left =p-&

26、gt;right=NULL; if(head=NULL) return p; else if(p->key <head->key) head->left=buildTree(head->left,number); else head->right=buildTree(head->right,number); return head; void BiSortTree:insertTree(int key) Head=buildTree(Head,key); treeNode* BiSortTree:searchTree(int key) return s

27、earch(Head,key); treeNode* BiSortTree:search(treeNode* head ,int key) if(head=NULL) return NULL; if(head->key=key) return head; else if(key<head->key ) return search( head->left,key); else return search(head->right,key); void BiSortTree:deleteTree(int key) treeNode *p; p=NULL; p=searc

28、h(Head,key); if(p=NULL) cout<<"Don't find the key" if(p=Head) Head=NULL; else treeNode* parent; parent=searchParent(Head,p); if(p->left=NULL&&p->right=NULL) if(parent->left=p) parent->left=NULL; else parent->right=NULL; else if(p->right=NULL) if(parent-&

29、gt;left=p) parent->left=p->left ; else parent->right=p->left; else treeNode * rightMinSon,* secondParent; rightMinSon=searchMinRight(p->right); secondParent=searchParent(p->right ,rightMinSon); secondParent->left=rightMinSon->right; if(p->right=rightMinSon) p->right=rig

30、htMinSon->right ; p->key=rightMinSon->key ; treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p) if(head->left=p|head->right=p|head=p|head=NULL) return head; else if(p->key<head->key) return searchParent(head->left ,p); else return searchParent(head->right ,p);

31、 treeNode* BiSortTree:searchMinRight(treeNode* head) if(head->left =NULL|head=NULL) return head; else return searchMinRight(head->left); void BiSortTree:desplayTree(void) showTree(Head); cout<<endl; void BiSortTree:showTree(treeNode* Head) if(Head!=NULL) showTree(Head->left ) ; cout&l

32、t;<Head->key<<' ' ; showTree(Head->right) ; BiSortTree:BiSortTree() cout<<"已经消除了一棵树!"<<endl; destroyTree(Head); void BiSortTree:destroyTree(treeNode* head ) if(head!=NULL) destroyTree(head->left ); destroyTree(head->right ); delete head; void print(

33、) cout<<endl<<endl<<"以下是对二叉排序树的基本操作:"<<endl <<"1.显示树"<<endl <<"2.插入一个节点"<<endl <<"3.寻找一个节点"<<endl <<"4.删除一个节点"<<endl; int main() BiSortTree tree; int number; int choiceNumber; ch

34、ar flag; while(1) print() ; cout<<"请选择你要进行的操作(14)"<<endl; cin>>choiceNumber; switch(choiceNumber) case 1: tree.desplayTree();break; case 2: cout<<"请插入一个节点: "<<endl; cin>>number; tree.insertTree(number); tree.desplayTree(); break; case 3: cout&l

35、t;<"请插入你要找的节点: "<<endl; cin>>number; if(tree.searchTree(number)=NULL) cout<<"没有发现你要找的节点"<<endl; else cout<<"发现你要找的节点"<<endl; break; case 4: cout<<"请输入你要删除的节点: "<<endl; cin>>number; tree.deleteTree(number

36、); tree.desplayTree(); break; default: break; cout<<"你是否要继续(Y/N)?"<<endl; cin>>flag; if(flag='N'|flag='n') break; return 0;二，实验结果截屏视图：实验七 排序算法的应用【实验目的】有如下数据：成绩75876892886177968072姓名王华李燕张萍陈涛刘丽章强孙军朱彬徐伟曾亚以成绩做关键字，试编写程序实现如下基本操作：1. 用冒泡排序对上面数据按成绩非递减排列，并分析时空复杂度；2.

37、 用简单选择排序对上面数据按成绩非递减排列，并分析时空复杂度；3. 用快速排序对上面数据按成绩非递减排列，并分析时空复杂度。【实验要求】1. 上交实验报告。2. 独立完成，严禁抄袭。3. 实验报告由如下部分组成：实验名称实验目的实验内容（问题描述，算法描述，程序清单，测试结果，算法分析）。实验结果：一，源程序：/*#include <cstdlib>#include <iostream>using namespace std;int main(int argc, char *argv) system("PAUSE"); return EXIT_SUCCESS;#include <stdio.h>#include <stdlib.h>#include <string.h> typedef struct student int score; char name10; int flag;student;int main() student stu10; stu0.score = 75; strcpy(, "王华"); stu0.flag = 0; stu1.score = 8