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

《数据结构课程设计实验报告》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告（18页珍藏版）》请在装配图网上搜索。

1、徐州工程学院管理学院实验报告实验课程名称 ： 数据结构 实验地点： 南主楼七楼机房 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); pri

2、ntf(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

3、(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 s

4、tructint *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

5、;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 Tripl

6、e 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

7、.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-dat

8、apc.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

9、(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

10、 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实验要求：统计二叉树中的叶子结点的个数实验内

11、容：#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)

12、; 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!=

13、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

14、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实验要求：编写一个算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。先确立顶

15、点、弧的信息，并且要定义最大值、一维数组等，要有结构体类型（在函数外定义宏定义），建立数组后初始化，将顶点信息输入进来并存放，即顶点信息初始化。实验内容：#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 VertexN

16、ode 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-adjve

17、x = 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 = f

18、alse;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 Da

19、taType;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-datai; L-datai=

20、L-dataj; L-dataj=temp; return L;int BinSearch(SequeList *L,DataType k) int low=0,high=L-length-1,mid; while(lowdatamid=k) return mid; else if(L-datamidk) high=mid-1; else low=mid+1; return -1;void PrintList(SequeList *L) int i; for(i=0;ilength;i+) printf(%c ,L-datai); printf(n);int main() int i,t; D

21、ataType cc; SequeList *L; L=(SequeList *)malloc(sizeof(SequeList); L=Initist(L); printf(请输入26个字符：n); L-length=26; for(i=0;idatai); L=BubbleSort(L); printf(此组数排完序后为：n); PrintList(L); printf(请输入要查找的字符： n); scanf(%c,&cc); t=BinSearch(L,cc)+1; if(t=0) printf(此顺序表中没有该字符!n); else printf(此字符在顺序表中的第%d个位置。n,t); return 0;实验总结