《数据结构》实训报告

实验一 线性表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(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 error;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)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(head,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#define 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);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-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)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的结点为根的子数的深度。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= ) 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(此二叉数的接点数有:%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(bnode);bt-data=ch;bt-lchild=creat();bt-rchild=creat();return bt;void preorder(blink bt)if (bt)printf(%c,bt-data);preorder(bt-lchild);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 1+max(depth(bt-lchild),depth(bt-rchild);elsereturn 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. 实验小结通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。 实验四 图1. 实验要求1.1 熟悉图的各种存储方法。1.2 掌握遍历图的递归和非递归的算法。1.3 理解图的有关算法。2. 实验内容2.1 写出将一个无向图的邻接矩阵转换成邻接表的算法。2.2 以邻接表作存储结构，给出拓扑排序算法的实现。3. 实验代码2.1代码：void mattolist(int a,adjlist b,int n) /*n为图的结点个数*/for(i=0;in;i+)bi.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;2.2代码：typedef struct vexnodeVertexType vertex;int in;/*增加一个入度域*/ArecNodeTp * fristarc;AdjListvnum;typedef struct graphAdjList adjlist;int vexnum,arcnum;GraphTp;Top_Sort(GraphTp g) LstackTp *p;/*建立入度为0的顶点栈S*/int m,i,v; initStack(S);for(i=0;ivprintf(%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-adjvex);/*p入S栈*/p=p-nextarc;/*p=图g中的顶点v的下一个邻接点*/if(mg.vexnum) return 0;/*图含有环*/else return 1;4. 实验小结通过本章学习实验，对图有了具体的认识。图也是一种非线性的数据结构，这种结构有着广泛的应用，一切具有关系的问题都可以用图来表示。 实验五 查找1. 实验要求1.1 掌握顺序查找、二分法查找、分块查找和哈希表查找的算法。1.2 能运用线性表的查找方法解决实际问题。2. 实验内容2.1 编写一个算法，利用二分查找算法在一个有序表中插入一个元素X，并保持表的有序性。2.2 根据给定的数据表，先建立索引表，然后进行分块查找。3. 实验代码2.1代码：#include #include #define MAXNUM 20int 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(insert=1;insert=m+1;insert+)/*显示数据*/printf(%3d,*(data+insert);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*/elsemid=(low+high)/2;if(*(data+mid)=*data) retun mid;/*找到插入数据，返回mid*/else if(*(data+mid)*data)search(data,low,high);void plug(int *data,int insert,int m) int i;for(i=m;iinsert;i-)*(data+i+1)=*(data+i);*(data+insert)=*data2.2代码：#include #include #include #definr N 18 /*元素个数*/#definr Blocknum 3 /*分块数*/typedef struct indextermint key;/*最大关键字*/int addr;/*块的起始地址*/index; /*索引表数据类型*/index * CreateList(int data,int n)/*建索引表*/index *p;int m,j,k;m=n/BlockNum;/*分为BlockNum块，每块有m个元素*/p=(in