《数据结构》实训报告.docx

《《数据结构》实训报告.docx》由会员分享，可在线阅读，更多相关《《数据结构》实训报告.docx（17页珍藏版）》请在三一办公上搜索。

1、数据结构实训报告实验一 线性表 1. 实验要求 1.1 掌握数据结构中线性表的基本概念。 1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。 1.3 熟练掌握链表的各种操作和应用。 2. 实验内容 2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。 2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作 2.3 设计一个统计选票的算法，输出每个候选人的得票结果。 3. 实验代码 2.1代码： #include typedef int elemtype; #define maxsi

2、ze 10 int del(int A,int n,elemtype x,elemtype y) int i=0,k=0; while(i=x&Ai=y) k+; else Ai-k=Ai; i+; return(n-k); void main int i,j; int amaxsize; printf(输入%d个数:n,maxsize); for(i=0;imaxsize;i+) scanf(%d,&ai); 数据结构实验报告 j=del(a,maxsize,1,3); printf(输出删除后剩下的数:n); for(i=0;idata=x;s-next=L;L=s; else p=L;j

3、=1; while(p&jnext; if(p|ji-1) return error; s=(Linklist)malloc(sizeof(Lnode); s-data=x;s-next=p-next;p-next=s; 2.3代码： typedef int elemtype typedef struct linknode elemtype data; struct linknode *next; nodetype; 2 数据结构实验报告 nodetype *create elemtype d; nodetype h=NULL,*s,*t; int i=1; printf(建立单链表:n);

4、while(1) printf(输入第%d个结点数据域,i); scanf(%d,&d); if(d=0)break; if(i=1) h=(nodetype *)malloc(sizeof(nodetype); h-data=d;h-next=NULL;t=h; else s=(nodetype *)malloc(sizeof(nodetype); s-data=d;s-next=NULL;t-next=s; t=s; i+; return h; void sat(nodetype *h,int a) nodetype *p=h; while(p!=NULL) ap-data+; p=p-n

5、ext; void main int aN+1,i; for(i=0;iN;i+) ai=0; nodetype *head; head=create; sat(head,a); 3 数据结构实验报告 printf(候选人:); for(i=1;i=N;i+) printf(%3d,i); printf(n得票数n); for(i=1;i=N;i+) printf(%3d,ai); printf(n); 4. 实验小结 线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。 实验二 栈与队列 1. 实验要求 1.1 了解栈和队列的特性，以便灵活运用。 1.2 熟练掌握栈和有关队列的

6、各种操作和应用。 2. 实验内容 2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。 3. 实验代码 2.1代码： #include #include #include #define NULL 0 typedef struct list char str; struct list *next; list; void push(char,list *); int pop(char.list *); void deal(char *str); main(void) char str20; printf(n请输入一个算式:n); 4 数据结构实验报告

7、gets(str); deal(str); printf(正确!); getchar; return 0; void deal(char *str) list *L; L=(list *)malloc(sizeof(list); if(!L) printf(错误!); exit(-2); L-next=NULL; while(*str) if(*str=(|*str=|*str=) push(*str,L); else if(*str=)|*str=|*str=) if(pop(*str,L) puts(错误,请检查!); puts(按回车键退出); getchar;exit(-2); str

8、+; if(L-next) puts(错误,请检查!); puts(按任意键退出); getchar;exit(-2); void push(char c,list *L) list *p; p=(list *)malloc(sizeof(list); if(!p) printf(错误!); exit(-2); 5 数据结构实验报告 p-str=c; p-next=L-next; L-next=p; #define check(s) if(L-next-str=s)p=l-next;L-next=p-next;free(p);return(0); int pop(char c,list *L)

9、 list *p; if(L-next=NULL)return 1; switch(c) case):check() break; case:check() break; case:check() break; return 1; 4. 实验小结 栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。 实验三 树 1. 实验要求 1.1 掌握二叉树，二叉树排序数的概念和存储方法。 1.2 掌握二叉树的遍历算法。 1.3 熟练掌握编写实现树的各种运算的算法。 2. 实验内容 2.1 编写程序，求二叉树的结点数和叶子数。 2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深

10、度。 2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。 6 数据结构实验报告 3. 实验代码 2.1代码： #include #include struct node char data; struct node *lchild,*rchild; bnode; typedef struct node *blink; blink creat blink bt; char ch; ch=getchar; if(ch= ) return(NULL); else bt=(struct node *)malloc(sizeof(bnode); bt-data=ch; bt-lchild=

11、creat; bt-rchild=creat; return bt; int n=0,n1=0; void preorder(blink bt) if (bt) n+; if(bt-lchild=NULL&bt-rchild=NULL) n1+; preorder(bt-lchild); preorder(bt-rchild); void main blink root; root=creat; preorder(root); printf(此二叉数的接点数有:%dn,n); printf(此二叉数的叶子数有:%dn,n1); 7 数据结构实验报告 2.2代码： int get_deep(bi

12、tree T,int x) if(T-data=x) printf(%dn,get_deep(T); exit 1; else if(T-lchild)get_deep(T-lchild,x); if(T-rchild)get_deep(T-rchild,x); int get_depth(bitree T) if(!T)return 0; else m=get_depth(T-lchild); n=get_depth(T-rchild); return(mn?m:n)+1; 2.3代码： #include #include struct node char data; struct node

13、 *lchild,*rchild; bnode; typedef struct node *blink; blink creat blink bt; char ch; ch=getchar; if(ch= ) return(NULL); else bt=(struct node *)malloc(sizeof(bnode); bt-data=ch; 8 数据结构实验报告 bt-lchild=creat; bt-rchild=creat; return bt; void preorder(blink bt) if (bt) printf(%c,bt-data); preorder(bt-lchi

14、ld); preorder(bt-rchild); void inorder(blink bt) if(bt) inorder(bt-lchild); printf(%c,bt-data); inorder(bt-rchild); void postorder(blink bt) if(bt) postorder(bt-lchild); postorder(bt-rchild); printf(%c,bt-data); int max(int x,int y) if(xy) return x; else return y; int depth(blink bt) if (bt) return

15、1+max(depth(bt-lchild),depth(bt-rchild); else 9 数据结构实验报告 return 0; void main blink root; root=creat; printf(n); printf(按先序排列:); preorder(root);printf(n); printf(按中序排列:); inorder(root);printf(n); printf(按后序排列:); postorder(root);printf(n); printf(此二叉数的深度是:); printf(depth=%dn,depth(root); 4. 实验小结 通过本章学

16、习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。 实验四 图 1. 实验要求 1.1 熟悉图的各种存储方法。 1.2 掌握遍历图的递归和非递归的算法。 1.3 理解图的有关算法。 2. 实验内容 2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。 10 数据结构实验报告 2.2 以邻接表作存储结构，给出拓扑排序算法的实现。 3. 实验代码 2.1代码： void mattolist(int a,adjlist b,int n) /*n为图的结点个数*/ for(i=0;in;i+)b

17、i.firstarc=NULL; /*邻接表置空*/ for(i=0;i=0;j-) if(aij!=0) p=(arcnodetp *)malloc(sizeof(arcnodetp);/*产生邻接点*/ p-adjvex=j; p-nextare=bi.firstare; bi.firstarc=p; AdjListvnum; typedef struct graph AdjList adjlist; int vexnum,arcnum; GraphTp; Top_Sort(GraphTp g) 11 数据结构实验报告 LstackTp *p;/*建立入度为0的顶点栈S*/ int m,i

18、,v; initStack(S); for(i=0;ig.vexnum;i+) if(g.adjlisti.in=0)/*if(w的入度=0)*/ push(S,&v);/*w入S栈*/ m=0; whlie(!EmptyStack(S) if(mv printf(%d,v);/*输出v*/ m+; p=g.adjlisti.fristarc;/*p=图g中顶点v的第一个邻接点*/ while(p!=NULL)/p存在 (g.adjlistp-adjvex.in)-;/*p的入度-*/ if(g.adjlistp-adjvex.in=0)/*if(p的入度=0)*/ Push(S,p-adjv

19、ex);/*p入S栈*/ p=p-nextarc;/*p=图g中的顶点v的下一个邻接点*/ 4. 实验小结 通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。 12 数据结构实验报告 实验五 查找 1. 实验要求 1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。 1.2 能运用线性表的查找方法解决实际问题。 2. 实验内容 2.1 编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。 2.2 根据给定的数据表，先建立索引表，然后进行分块查找。 3. 实验代码 2.1代码： #in

20、clude #include #define MAXNUM 20 int input(int *);/*输入数据*/ int search(int *,int,int);/*查找插入位置*/ void plug(int *,int,int);/*插入数据*/ void main(void) int dataMAXNUM,m; int insert=1; m=input(data); printf(Input the insert num:); scanf(%d,data); insert=search(data,1,m);/*返回插入位置*/ plug(data,insert,m); for(

21、insert=1;insert=m+1;insert+)/*显示数据*/ printf(%3d,*(data+insert); 13 数据结构实验报告 getch; int input(int *data) int i,m; printf(nInput the max num:); scanf(%d,&m); printf(input datan); for(i=1;ihigh) return low;/*没有找到插入数据，返回low*/ else search(data,low,high); void plug(int *data,int insert,int m) int i; for(i

22、=m;iinsert;i-) *(data+i+1)=*(data+i); mid=(low+high)/2; if(*(data+mid)=*data) retun mid;/*找到插入数据，返回mid*/ else if(*(data+mid)*data) *(data+insert)=*data 14 数据结构实验报告 2.2代码： #include #include #include #definr N 18 /*元素个数*/ #definr Blocknum 3 /*分块数*/ typedef struct indexterm int key;/*最大关键字*/ int addr;/

23、*块的起始地址*/ index; /*索引表数据类型*/ index * CreateList(int data,int n)/*建索引表*/ index *p; int m,j,k; m=n/BlockNum;/*分为BlockNum块，每块有m个元素*/ p=(index *)malloc(BlockNum *sizeof(index); for(k=0;kkey=dat am*k; (p+k)-addr=m*k; for(j=m*k;j(p+k)-key) (p+k)-key=dataj;/*块的最大关键字*/ 数据结构实验报告 int b=n/m;/*每块有b个元素*/ while(l

24、ow=high)/*块间折半查找*/ if(lowaddr;iadder+b-1&rectabi!=k;i+); return -1; void main int recordN=22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53; int key; index *list; printf(please input key:n); scanf(%d,&key); list=CreateList(record,N); printf(data postion id %dn,BlockSearch(list,record,N,BlockNum,key); if(iaddr+b-1) return i; mid=(low+high)/2; if(list+mid)-key=k) high=mid+1; else low=mid+1; else return -1; 4. 实验小结 通过本章的学习，对排序有较高层次的理解与认识，从平时的练习中可以看出排序是数据处理中经常用到的重要运算。有序的顺序表可以采用查找效率较高的折半查找法，而无序的顺序表只能用效率较低的顺序查找法。 16