《数据结构》实训报告

实验一线性表1.实验要求1.1掌握数据结构中线性表的基本概念。1.2熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构上的实验。1.3熟练掌握链表的各种操作和应用。2.实验内容2.1编写一个函数，从一个给定的顺序表A中删除元素值在x到y之间的所有元素，要求以较高效率来实现。2.2试写一个算法，在无头结点的动态单链表上实现线性表插入操作2.3设计一个统计选票的算法，输出每个候选人的得票结果。3.实验代码2.1代码：#includestdio.htypedefintelemtype;#definemaxsize10intdel(intA[],intn,elemtypex,elemtypey){inti=0,k=0;while(in){if(A[i]=x&&A[i]=y)k++;elseA[i-k]=A[i];i++;}return(n-k);}voidmain(){inti,j;inta[maxsize];printf(输入%d个数:\n,maxsize);for(i=0;imaxsize;i++)scanf(%d,,&a[i]);j=del(a,maxsize,1,3);printf(输出删除后剩下的数:\n);for(i=0;ij;i++)printf(%d\n,a[i]);}2.2代码：INSERT(L,i,b)。voidInsert(Linklist&L,inti,elemtypex){if(!L){L=(Linklist)malloc(sizeof(Lnode));(*L).data=x;(*L).next=NULL;}else{if(i==1){s=(Linklist)malloc(sizeof(Lnode));s-data=x;s-next=L;L=s;}else{p=L;j=1;while(p&&ji-1){j++;p=p-next;}if(p||ji-1)returnerror;s=(Linklist)malloc(sizeof(Lnode));s-data=x;s-next=p-next;p-next=s;}}}2.3代码：typedefintelemtypetypedefstructlinknode{elemtypedata;structlinknode*next;}nodetype;nodetype*create(){elemtyped;nodetypeh=NULL,*s,*t;inti=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;}else{s=(nodetype*)malloc(sizeof(nodetype));s-data=d;s-next=NULL;t-next=s;t=s;}i++;}returnh;}voidsat(nodetype*h,inta[]){nodetype*p=h;while(p!=NULL){a[p-data]++;p=p-next;}}voidmain(){inta[N+1],i;for(i=0;iN;i++)a[i]=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,a[i]);printf(\n);}4.实验小结线性表是最简单的、最常用的一种数据结构，是实现其他数据结构的基础。实验二栈与队列1.实验要求1.1了解栈和队列的特性，以便灵活运用。1.2熟练掌握栈和有关队列的各种操作和应用。2.实验内容2.1设一个算术表达式包括圆括号，方括号和花括号三种括号，编写一个算法判断其中的括号是否匹配。3.实验代码2.1代码：#includestdio.h#includemalloc.h#includestring.h#defineNULL0typedefstructlist{charstr;structlist*next;}list;voidpush(char,list*);intpop(char.list*);voiddeal(char*str);main(void){charstr[20];printf(\n请输入一个算式:\n);gets(str);deal(str);printf(正确!);getchar();return0;}voiddeal(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);}}voidpush(charc,list*L){list*p;p=(list*)malloc(sizeof(list));if(!p){printf(错误!);exit(-2);}p-str=c;p-next=L-next;L-next=p;}#definecheck(s)if(L-next-str==s){p=l-next;L-next=p-next;free(p);return(0);}intpop(charc,list*L){list*p;if(L-next==NULL)return1;switch(c){case')':check('(')break;case']':check('[')break;case'}':check('{')break;}return1;4.实验小结栈和队列是最基础的一种数据结构之一，为实现其他数据结构的奠定基石。实验三树1.实验要求1.1掌握二叉树，二叉树排序数的概念和存储方法。1.2掌握二叉树的遍历算法。1.3熟练掌握编写实现树的各种运算的算法。2.实验内容2.1编写程序，求二叉树的结点数和叶子数。2.2编写递归算法，求二叉树中以元素值为X的结点为根的子数的深度。2.3编写程序，实现二叉树的先序，中序，后序遍历，并求其深度。3.实验代码2.1代码：#includestdio.h#includemalloc.hstructnode{chardata;structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkcreat(){blinkbt;charch;ch=getchar();if(ch=='')return(NULL);else{bt=(structnode*)malloc(sizeof(bnode));bt-data=ch;bt-lchild=creat();bt-rchild=creat();}returnbt;}intn=0,n1=0;voidpreorder(blinkbt){if(bt){n++;if(bt-lchild==NULL&&bt-rchild==NULL)n1++;preorder(bt-lchild);preorder(bt-rchild);}}voidmain(){blinkroot;root=creat();preorder(root);printf(此二叉数的接点数有:%d\n,n);printf(此二叉数的叶子数有:%d\n,n1);}2.2代码：intget_deep(bitreeT,intx){if(T-data==x){printf(%d\n,get_deep(T));exit1;}else{if(T-lchild)get_deep(T-lchild,x);if(T-rchild)get_deep(T-rchild,x);}intget_depth(bitreeT){if(!T)return0;else{m=get_depth(T-lchild);n=get_depth(T-rchild);return(mn?m:n)+1;}}2.3代码：#includestdio.h#includemalloc.hstructnode{chardata;structnode*lchild,*rchild;}bnode;typedefstructnode*blink;blinkcreat(){blinkbt;charch;ch=getchar();if(ch=='')return(NULL);else{bt=(structnode*)malloc(sizeof(bnode));bt-data=ch;bt-lchild=creat();bt-rchild=creat();}returnbt;}voidpreorder(blinkbt){if(bt){printf(%c,bt-data);preorder(bt-lchild);preorder(bt-rchild);}}voidinorder(blinkbt){if(bt){inorder(bt-lchild);printf(%c,bt-data);inorder(bt-rchild);}}voidpostorder(blinkbt){if(bt){postorder(bt-lchild);postorder(bt-rchild);printf(%c,bt-data);}}intmax(intx,inty){if(xy)returnx;elsereturny;}intdepth(blinkbt){if(bt)return1+max(depth(bt-lchild),depth(bt-rchild));elsereturn0;}voidmain(){blinkroot;root=creat();printf(\n);printf(按先序排列:);preorder(root);printf(\n);printf(按中序排列:);inorder(root);printf(\n);printf(按后序排列:);postorder(root);printf(\n);printf(此二叉数的深度是:);printf(depth=%d\n,depth(root));}4.实验小结通过本章学习实验，对树有了初步的认识。树就是一种非线性的数据结构，描述了客观世界中事物之间的层次关系。这种结构有着广泛的应用，一切具有层次关系的问题都可以用树来表示。实验四图1.实验要求1.1熟悉图的各种存储方法。1.2掌握遍历图的递归和非递归的算法。1.3理解图的有关算法。2.实验内容2.1写出将一个无向图的邻接矩阵转换成邻接表的算法。2.2以邻接表作存储结构，给出拓扑排序算法的实现。3.实验代码2.1代码：voidmattolist(inta[][],adjlistb[],intn)/*n为图的结点个数*/{for(i=0;in;i++)b[i].firstarc=NULL;/*邻接表置空*/for(i=0;in;i++)/*逐行进行*/for(j=n-1;j=0;j--)if(a[i][j]!=0){p=(arcnodetp*)malloc(sizeof(arcnodetp));/*产生邻接点*/p-ad