数据结构课程设计实验报告.doc

徐州工程学院管理学院实验报告实验课程名称 ： 数据结构 实验地点： 南主楼七楼机房 2011 年 9 月至 2012 年 1 月 专 业 信息管理与信息系统 班 级 09信管2 学生姓名 学 号 指导老师 实验报告实验项目：链表的应用实验学时：2 实验日期：2011.9.9实验要求：对单链表实现就地逆置。实验内容：#include#include#define null 0struct llist int num; struct llist * next;void main() struct llist * head,* p,*q; int len,i; scanf(%d,&len); printf(the number is:n); /*建立链表*/ for(i=1;inum); p-next=null; if(i=1) head=p; else q=head; while(q-next!=null) q=q-next; q-next=p; printf(the llist is:n); p=head; for(i=1;inum); p=p-next; printf(n); p=head; /*链表逆置*/ while(head-next!=null) q=p; p=head-next; head-next=p-next; p-next=q;head=p; p=head; for(i=1;inum); p=p-next; getch();实验项目：栈的应用实验学时： 2 实验日期：2011.9.16实验要求：假设用顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着2个栈，它们的栈底分别设在数组的两个端点，试编写这个双向栈tws的三个操作，初始化initstack(tws), 入栈push(tws i), 出栈pop(tws i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈。实验内容：#include stdio.h/*stack part*/#define bool int#define true 1#define false 0typedef structint *base2;int *top2;bdstacktype;bool initstack(bdstacktype tws,int m);bool pushstack(bdstacktype tws,int i,int x);int main()int i,m,x,n;bdstacktype stack1;scanf(%d,&n);scanf(%d,&m);if( !initstack(stack1,n) )printf(alloc failure!n);exit(0);for( i=0; itws.top1)return false;if( i = 1)*tws.top1-=x;else if( i=0 )*tws.top0+ = x;elsereturn false;return true;实验项目：矩阵的应用实验学时：2 实验日期：2011.10.7实验要求：假设稀疏矩阵a,b均以三元组顺序表作为存储结构，试写出矩阵值相加的算法，另设三元组c存放结果矩阵。实验内容：#include#include#define maxsize 1000 /*用户自定义*/typedef int datatype; /*用户自定义*/typedef struct int i,j; datatype v; triple;/*定义三元组结构*/typedef struct triple datamaxsize;/*定义可存三元组大小*/int mu,nu,tu; tsmatrix;/*行数，列数，非零元*/void addtriple( tsmatrix *a ,tsmatrix *b,tsmatrix *c) /*三元组相加算法*/int x,sum,pb,pc,pa;c-mu=a-mu;c-nu=a-nu;c-tu=0; /*定义矩阵c的非零元个数开始为0个*/ pa=1; pb=1; pc=1; for(x=1;xmu;x+)while(a-datapa.idatapb.idatapa.i=x & b-datapb.i=x) /*行数相等时*/if(a-datapa.j=b-datapb.j) /*列数相等时*/sum=a-datapa.v+b-datapb.v; /*矩阵想加*/if(sum) /*相加不为零时*18c-datapc.i=x;c-datapc.j=a-datapa.j;c-datapc.v=sum; pa+; pb+; pc+; elseif(a-datapa.jb-datapb.j) /*a的列数大于b的列数时*/c-datapc.i=x;c-datapc.j=b-datapb.j; c-datapc.v=b-datapb.v;pb+;pc+; else c-datapc.i=x;c-datapc.j=a-datapa.j;c-datapc.v=a-datapa.v;pa+;pc+; while(a-datapa.i=x) /*插入a剩余的元素*/c-datapc.i=x; c-datapc.j=a-datapa.j; c-datapc.v=a-datapa.v; pa+; pc+;实验项目：实验学时： 实验日期：实验要求：实验内容：c-tu=pc;main() tsmatrix *a , *b, *c; int b,e,k;a=(tsmatrix*)malloc(sizeof(tsmatrix);b=(tsmatrix*)malloc(sizeof(tsmatrix);c=(tsmatrix*)malloc(sizeof(tsmatrix); /*生成a、b、c三元组存储空间*/printf(input a-mu:);/*输入a的行数*/scanf(%d,&a-mu);printf(input a-nu:);scanf(%d,&a-nu); /*输入b的列数*/printf(input a-tu:);scanf(%d,&a-tu);/*输入a 的非零元*/printf(input a:n);/*输入a的非零元三元组*/for(e=1;etu;e+)/*循环输入a的三元组*/scanf(%d%d%d,&a-datae.i,&a-datae.j,&a-datae.v);printf(n);printf(input b.tu:);/*输入b的非零元三元组*/scanf(%d,&b-tu);printf(input b:n);for(k=1;ktu;k+)scanf(%d%d%d,&b-datak.i,&b-datak.j,&b-datak.v);printf(n);addtriple( a,b,c); /*引用相加算法*/printf(output c:n);/*输出c的三元组*/for(b=1;btu;b+)printf(%d,%d,%dn,c-data-i,c-data-j,c-data-v);实验项目：树的应用实验学时： 2 实验日期：2011.10.7实验要求：统计二叉树中的叶子结点的个数实验内容：#include #include #define elemtype chartypedef struct bitnode elemtype data; struct bitnode *lchild,*rchild; bitnode;bitnode *bulid() bitnode *q; bitnode *s20; int i,j; char x; printf(请按顺序输入二叉树的结点以输入0和*号结束n); printf(请输入你要输入的为第几个结点i=n); scanf(%d,&i); printf(请输入你要输入该结点的数为x=); getchar(); scanf(%c,&x); while(i!=0&x!=*) q=(bitnode*)malloc(sizeof(bitnode); q-data=x; q-rchild=null; q-lchild=null; si=q; if(i!=1) j=i/2; if(i%2=0) sj-lchild=q; else sj-rchild=q; printf(请输入你要输入的为第几个结点x=n); scanf(%d,&i); printf(请输入你要输入该结点的数x=); getchar(); scanf(%c,&x); return s1;void preoder(bitnode *bt) /*先序遍历*/ if(bt!=null) printf(%cn,(bt-data); preoder(bt-lchild); preoder(bt-rchild);void inorder(bitnode *bt) /*中序遍历*/ if(bt!=null) inorder(bt-lchild); printf(%cn,bt-data); inorder(bt-rchild);void postorder(bitnode *bt) /*后序遍历*/ if(bt!=null) postorder(bt-lchild); postorder(bt-rchild); printf(%cn,bt-data);main() int a; bitnode *bt; bt=bulid();k1: printf(需要先序遍历输出请输入1，中序遍历请输入2，后序遍历请输入3,结束输入0:); scanf(%d,&a); switch(a) case(1): preoder(bt); goto k1; case(2): inorder(bt); goto k1; case(3): postorder(bt); goto k1; case(0): break; 实验项目：图的应用实验学时： 2 实验日期：2011.10.21实验要求：编写一个算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。先确立顶点、弧的信息，并且要定义最大值、一维数组等，要有结构体类型（在函数外定义宏定义），建立数组后初始化，将顶点信息输入进来并存放，即顶点信息初始化。实验内容：#include stdio.h#include stdlib.h#define maxvertexnum 100typedef char vertextype;typedef struct node int adjvex;struct node *next;edgenode;typedef struct vnodevertextype vertex;edgenode *firstedge;vertexnode;typedef vertexnode adjlistmaxvertexnum;typedef structadjlist adjlist;int n,e;algraph;void creatalgraph(algraph *g)int i,j,k;edgenode *s;scanf(%d%d,&g-n,&g-e);for(i = 0;i n;i+)g-adjlisti.vertex = getchar();g-adjlisti.firstedge = null;for(k = 0;k e;k+)scanf(%d%d,&i,&j);s = (edgenode *)malloc(sizeof(edgenode);s-adjvex = j;s-next = g-adjlisti.firstedge;g-adjlisti.firstedge = s;bool visitedmaxvertexnum;void dfs(algraph *g,int i)edgenode *p = g-adjlisti.firstedge;visitedi = true;while(p)if(!visitedp-adjvex)dfs(g,p-adjvex);p = p-next;bool isconnected(algraph *g)int i,j;for(i = 0;i n;i+)for(j = 0;j n;j+)visitedj = false;dfs(g,i);for(j = 0;j n;j+)if(!visitedj)return false;return true;int main()algraph g;creatalgraph(&g);if(isconnected(&g)printf(连通n);elseprintf(不连通n);system(pause);实验项目：排序、查找的应用实验学时： 2 实验日期：2011.10.28实验要求：先从键盘输入26个字母生成无序数组，对数组排序后，再从键盘输入一个字符进行折半查找。实验内容：#include#include#define max 50typedef char datatype;typedef struct datatype datamax; int length;sequelist;sequelist *initist(sequelist *l) l=(sequelist *)malloc(sizeof(sequelist); l-length=-1; return l;sequelist *bubblesort(sequelist *l) int i,j; datatype temp; for(i=0;ilength;i+) for(j=i+1;jlength;j+) if(l-datail-dataj) temp=l-d