《《数据结构》实训总结报告》由会员分享，可在线阅读，更多相关《《数据结构》实训总结报告（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验一 线性表1. 实验要求1.1 掌握数据结构中线性表的基本概念。1.2 熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。1.3 熟练掌握链表的各种操作和应用。2. 实验内容2.1 编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。2.2 试写一个算法，在无头结点的动态单链表上实现线性表插入操作2.3 设计一个统计选票的算法，输出每个候选人的得票结果。3. 实验代码2.1代码：#includetypedef int elemtype;#define maxsize 10int del(
2、int A,int n,elemtype x,elemtype y)int i=0,k=0;while(i=x&Ai=y)k+;elseAi-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;elsep=L;j=1;while(p&jnext;if(p|ji-1)return er
3、ror;s=(Linklist)malloc(sizeof(Lnode);s-data=x;s-next=p-next;p-next=s;2.3代码：typedef int elemtypetypedef struct linknodeelemtype data;struct linknode *next;nodetype;nodetype *create()elemtype d;nodetype h=NULL,*s,*t;int i=1;printf(建立单链表:n);while(1)printf(输入第%d个结点数据域,i);scanf(%d,&d);if(d=0)break;if(i=1
4、)h=(nodetype *)malloc(sizeof(nodetype);h-data=d;h-next=NULL;t=h;elses=(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-next;void main()int aN+1,i;for(i=0;iN;i+)ai=0;nodetype *head;head=create();sat(h
5、ead,a);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 熟练掌握栈和有关队列的各种操作和应用。2. 实验内容2.1 设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。3. 实验代码2.1代码：#include#include#include#defi
6、ne NULL 0typedef struct listchar str;struct list *next;list;void push(char,list *);int pop(char.list *);void deal(char *str);main(void)char str20;printf(n请输入一个算式:n);gets(str);deal(str);printf(正确!);getchar();return 0;void deal(char *str)list *L;L=(list *)malloc(sizeof(list);if(!L)printf(错误!);exit(-2)
7、;L-next=NULL;while(*str)if(*str=(|*str=|*str=)push(*str,L);elseif(*str=)|*str=|*str=)if(pop(*str,L)puts(错误,请检查!);puts(按回车键退出);getchar();exit(-2);str+;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);p-st
8、r=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)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 掌握二叉树，二叉树排序数
9、的概念和存储方法。1.2 掌握二叉树的遍历算法。1.3 熟练掌握编写实现树的各种运算的算法。2. 实验内容2.1 编写程序，求二叉树的结点数和叶子数。2.2 编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。2.3 编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。3. 实验代码2.1代码：#include#includestruct nodechar data;struct node *lchild,*rchild;bnode;typedef struct node *blink;blink creat()blink bt;char ch;ch=getchar();if(ch
10、= ) return(NULL);elsebt=(struct node *)malloc(sizeof(bnode);bt-data=ch;bt-lchild=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(此二叉
11、数的接点数有:%dn,n);printf(此二叉数的叶子数有:%dn,n1);2.2代码：int get_deep(bitree T,int x)if(T-data=x)printf(%dn,get_deep(T);exit 1;elseif(T-lchild)get_deep(T-lchild,x);if(T-rchild)get_deep(T-rchild,x);int get_depth(bitree T)if(!T)return 0;elsem=get_depth(T-lchild);n=get_depth(T-rchild);return(mn?m:n)+1;2.3代码：#include#includestruct nodechar data;struct node *lchild,*rchild;bnode;typedef struct node *blink;blink creat()blink bt;char ch;ch=getchar();if(ch= ) return(NULL);elsebt=(struct node *)malloc(sizeof(bno
