数据结构实验报告(全)安工大

数据结构实验报告姓名：韦勇 学号：班级：软件工程141班学院：计算机科学与技术学院实验时间：2016指导老师：陈学进实验一 约瑟夫问题实现1、实验目的 1）掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。2）掌握在顺序结构中实现查找、插入、删除操作的基本方法。3）掌握在各种链表结构中实现查找、插入、删除操作的基本方法2、实验内容 设有n个人围坐在一圈，现从指定的第个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，如此重复，直到所有的人全部出列为止。3、实验要求 针对实验内容，认真设计算法，上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序，上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）顺序结构：#include stdio.h#include stdlib.h#define MAXSIZE 100typedef struct nodeint dataMAXSIZE;int length;SeqList,*PSeqList;int Delete(PSeqList PL,int i)int j;if(!PL)printf(表不存在);return (-1);if(iPL-length)printf(删除位置不合法);return(0);for(j=i;jlength;j+)PL-dataj-1=PL-dataj;PL-length-;return(1);PSeqList Init(void)int n,i;PSeqList PL;PL=(PSeqList)malloc(sizeof(SeqList);if(PL) PL-length=0;printf(请输入圆桌人数:n);scanf(%d,&n);if(nMAXSIZE)printf(溢出);for(i=0;idatai=i;PL-length+;return PL;int josephus(PSeqList josephus,int s,int m)/*josephus为顺序表，s为首位置，m为计数值*/int s1,i,w;if(!josephus-length)printf(表中无元素);return(0);s1=s-1;printf(输出约瑟夫序列:n);for(i=josephus-length;i0;i-)s1=(s1+m-1)%i;w=josephus-datas1;printf(%dt,w);Delete(josephus,s1+1);return(1);int main()PSeqList PL;int m,n;PL=Init();printf(请分别输入起始序号和计数值:n); scanf(%d%d,&m,&n);josephus(PL,4,3);return(0);链式结构：#include #include #include typedef struct nodeint data;struct node* next;Lnode,*Linklist;/*创建一个单链表并初始化*/ Linklist create(int n) /*此函数带回一个指向链表头的指针*/ int i; Linklist head; Linklist p1,p2; p1=p2=(Linklist)malloc(sizeof(Lnode); /*开辟一个新单元*/ p1-data=0; head=p1; for(i=1;idata=i; p2-next=p1; p1-next=head; return(head);int josephus(Linklist josephus,int s,int m)Linklist p,pre;int count;if(!josephus) printf(表中无元素); return(0);p=josephus;for(count=1;countnext;printf(输出约瑟夫序列:n);while(p!=p-next)pre=p-next;while(pre-next!=p) pre=pre-next;for(count=1;countnext;printf(%dt,p-data);pre-next=p-next;free(p);p=pre-next;printf(%dt,p-data);free(p);return(1);int main()Linklist PL;int s,m,n,i;printf(请输入圆桌的人数,起始位置，间隔);scanf(%d%d%d,&s,&m,&n); PL=create(s); /* for(i=0;idata); PL=PL-next; */josephus(PL,m,n); return(1);静态链表：#include stdio.h#include stdlib.h#define MAXSIZE 100typedef structint data;int next;SNode;typedef structSNode spMAXSIZE;int SL;StList,*PStList;PStList Init(int n)int i;/设置游标 PStList PL;PL=(PStList)malloc(sizeof(StList);if(PL) PL-SL=0;for(i=0;ispi.next=i+1;PL-spi.data=i; PL-spn-1.next=0;PL-spn-1.data=n;return(PL);void josephus(PStList p,int s,int m,int n)int i,s1,h,j;printf(输出约瑟夫序列：n); s1=s-1;for(i=n;i1;i-) for(j=1;jsps1.next;h=s1;s1=p-sps1.next;printf(%d , p-sps1.data); p-sph.next=p-sps1.next; s1 = p-sps1.next;printf(%d , p-sps1.data); int main()int s,m,n;printf(请输入人数:n);scanf(%d,&n); printf(请输入起始位置和间隔:n);scanf(%d%d,&s,&m);PStList PL;PL=Init(n);josephus(PL,s,m,n);return(0);心得体会：通过这次的是实验我可以基本掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。掌握在各种链表结构中实现查找、插入、删除操作的基本方法，掌握在顺序结构中实现查找、插入、删除操作的基本方法。并且将这些方法运用到实际的约瑟夫问题中，难点在于对约瑟夫算法的理解，在实验中因为未能深刻理解约瑟夫算法出过很多小问题使得输出的约瑟夫序列不正确。实验二：数制转换算法实现1、实验目的 1）掌握栈、队列的两类存储结构（顺序存储结构和链式存储结构）的描述方法。2）掌握在不同结构中实现基本操作的基本方法。3）掌握在两种结构中实现查找、插入、删除操作的基本方法2、实验内容 编写算法实现任意一个十进制数转换r进制数。3、实验要求 针对实验内容，认真设计算法，上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序，上机后，认真整理源程序及其注释，完成实验报告（包括算法、源程序、实验结果、算法分析等）源程序1（顺序结构）：#include#include#include#definemaxsize100typedefstructintdatamaxsize;inttop;seqstack,*Pseqstack;typedefstructintdatamaxsize;intrear,front;seqqueue,*Pseqqueue;Pseqstackinit_seqstack(void)PseqstackS;S=(Pseqstack)malloc(sizeof(seqstack);if(S)S-top=-1;returnS;/初始化栈intempty_seqstack(PseqstackS)if(S-top=-1)return1;elsereturn0;/判断栈是否为空intpush_seqstack(PseqstackS,intx)if(S-top=maxsize-1)printf(thestackisfull);return0;elseS-top+;S-dataS-top=x;return1;/入栈intpop_seqstack(PseqstackS,int*x)if(empty_seqstack(S)printf(thestackisempty);return0;else*x=S-dataS-top;S-top-;return1;/出栈intdestory_seqstack(Pseqstack*S)if(*S)free(*S);*S=NULL;return0;/销毁栈intconversion(PseqstackS,intn,intr)intx;/*if(!r)printf(基数不能为0);return0;*/S=init_seqstack();/*if(!S)printf(初始化栈失败);return0;*/while(n)push_seqstack(S,n%r);n=n/r;while(!empty_seqstack(S)pop_seqstack(S,&x);printf(%d,x);destory_seqstack(&S);return0;/整数部分转换Pseqqueueinit_seqqueue(void)PseqqueueQ;Q=(Pseqqueue)malloc(sizeof(seqqueue);if(Q)Q-front=0;Q-rear=0;returnQ;/初始化队列intempty_seqqueue(PseqqueueQ)if(Q&Q-rear=Q-front)return1;elsereturn0;/判断队是否为空intin_seqqueue(PseqqueueQ,intx)if(Q-rear+1)%maxsize=Q-front)printf(队满);return-1;elseQ-rear=(Q-rear+1)%maxsize;Q-dataQ-rear=x;return0;/入队intout_seqqueue(PseqqueueQ,int*x)if(empty_seqqueue(Q)printf(队空);return0;elseQ-front=(Q-front+1)%maxsize;*x=Q-dataQ-front;return1;/出队voiddestory_seqqueue(Pseqqueue*Q)if(*Q)free(*Q);*Q=NULL;/销毁队列inttranslate(PseqqueueQ,floata,intb)intx;/*if(!b)printf(基数不能为0);return0;*/Q=init_seqqueue();/*if(Q)printf(队列初始化失败);return-1;*/while(a)in_seqqueue(Q,int(a*b);a=a*b-int(a*b);while(!empty_seqqueue(Q)out_seqqueue(Q,&x);printf(%d,x);destory_seqqueue(&Q);return1;/小数部分的转化voidchange(PseqstackS,PseqqueueQ)intz,r;floatc,x;printf(请输入需要转换的数：);scanf(%f,&x);printf(进制是：);scanf(%d,&r);z=int(x);c=x-int(x);printf(转换后的结果是：);conversion(S,z,r); printf(.);translate(Q,c,r);/链接栈、队列intmain()/floatX;/intR;PseqstackS;/S=(Pseqstack)malloc(sizeof(seqstack);PseqqueueQ;/Q=(Pseqqueue)malloc(sizeof(seqqueue);change(S,Q);return0;2链式结构：#include #include typedef int datatype;typedef struct nodedatatype data;struct node *next; StackNode,*PStackNode; typedef struct PStackNode top; LinkStack,*PLinkStack; typedef struct Node datatype data; struct Node *next; Qnode, *PQNode;/*链队结点的类型*/ typedef struct PQNode front , rear;LinkQueue, *PLinkQueue; /*将头尾指针封装在一起的链队*/ PLinkStack Creat1() /*初始化链栈，入口参数：空，返回值：链栈指针，NULL表示初始化失败*/ PLinkStack S; S=(PLinkStack)malloc(sizeof(LinkStack); if(S) S-top =NULL; return S; int Empty(PLinkStack S) /*判断链栈是否为空，入口参数：链栈指针*/ return (S-top =NULL); void Push(PLinkStack S,datatype x) /*进栈，入口参数：链栈指针*/ PStackNode P; P=(PStackNode)malloc(sizeof(StackNode); if(!P) printf(内存溢出！n); else P-data =x; P-next =S-top ; S-top =P; void Pop(PLinkStack S ,datatype *x) /*出栈，*x保存被删除的元素值*/ PStackNode P; if(Empty(S) printf(栈空不能出栈！n); else *x=S-top-data; P=S-top ; S-top =S-top-next ; free(P); void Convert1(PLinkStack S,int n,int r) /*转化，入口参数：链栈指针，数n,进制r*/ int x; S=Creat1(); while(n) Push(S,n%r); n/=r; while(!Empty(S) Pop(S,&x); printf(%d,x); PLinkQueue Creat2() /*初始化一新队列，入口参数：无，返回值：新链队列指针，NULL表示失败*/ PLinkQueue Q; Q=(PLinkQueue)malloc(sizeof(LinkQueue); /*申请链队结点*/ if (Q) Q-front=NULL; Q-rear=NULL; return Q;int Empty_LinkQueue(PLinkQueue Q)if(Q&Q-front =NULL&Q-rear =NULL)return 1;elsereturn 0;void In_LinkQueue (PLinkQueue Q, datatype x) /*入队操作，入口参数：链队列和待入队元素x ，返回值：1表示成功，0表示系统内存溢出*/PQNode p;p=(PQNode)malloc(sizeof(Qnode);if(!p) printf(内存溢出！n);return ;p-data=x;p-next=NULL;if (Empty_LinkQueue(Q) Q-front = Q-rear = p;else Q-rear -next=p; Q-rear = p; /*入队完成*/void Out_LinkQueue (PLinkQueue Q , datatype *x) /*出队操作，入口参数：链队列，返回值：1表示成功，0表示队空*/ PQNode p; if (Empty_LinkQueue(Q) printf(队空不能出队！n); /*队空不能出队*/ return ; else *x=Q-front-data; p=Q-front; Q-front=Q-front-next; free(p); if(!Q-front) Q-rear=NULL; /*出队完成*/void Convert2(PLinkQueue Q,float n,int r)int x;Q=Creat2(); while (n) In_LinkQueue(Q,n*r); n=n*r-int(n*r); while (!Empty_LinkQueue(Q) /依次从队列中弹出每一个余数，并输出之Out_LinkQueue(Q,&x); printf(%d,x);void Change(PLinkStack S,PLinkQueue Q) int r,X;float n,Y;printf(请输入要转化的数：);scanf(%f,&n);printf(请输入要转化的进制r：);scanf(%d,&r);X=int(n);Y=n-X;printf(转化的r进制数为:);Convert1(S,X,r);printf(.);Convert2(Q,Y,r);getchar(); int main() PLinkStack S; PLinkQueue Q; Change(S,Q); return 0; 心得体会：通过本次实验我基本掌握了栈、队列的两类存储结构（顺序存储结构和链式存储结构）的描述方法。掌握在不同结构中实现基本操作的基本方法。掌握在两种结构中实现查找、插入、删除操作的基本方法，通过运用队列和堆栈，实现了数制转换问题，实验中主要是要注意链式和顺序的基本操作的运用，有些地方是有区别的，要注意这方面的使用。实验三 二叉树的遍历试编写程序： （1） 建立下面这样一棵二叉树 （2） 后序遍历这棵二叉树 （3） 按层次遍历 （4） 求叶子数和深度。 #include stdio.h#include stdlib.htypedef char Datatype; #define MAXSIZE 100typedef struct bnodeDatatype data;struct bnode *lchild,*rchild;BNode,*BTree;typedef structBTree dataMAXSIZE;int front,rear;seqqueue,*Pseqqueue;typedef structBNode *node;int flag;Data; typedef struct node Data DataMAXSIZE;int top;SeqStack,*PSeqStack;PSeqStack Init(void)PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);if(S)S-top=-1;return S; int Empty(PSeqStack S)if(S-top=-1)return 1;elsereturn 0;int Push(PSeqStack S,Data x)if(S-top=MAXSIZE-1)return 0;elseS-top+;S-DataS-top=x;return 1;int Pop(PSeqStack S,Data *x)if(Empty(S)return 0;else*x=S-DataS-top;S-top-;return 1;/栈的基本操作Pseqqueue init_seqqueue(void)Pseqqueue Q;Q=(Pseqqueue)malloc(sizeof(seqqueue);if(Q)Q-front=0;Q-rear=0; return Q;/初始化队列int empty_seqqueue(Pseqqueue Q)if(Q&Q-rear=Q-front)return 1;else return 0;/判断队是否为空int in_seqqueue(Pseqqueue Q,BTree x)if(Q-rear+1)%MAXSIZE=Q-front)printf(队满);return -1;elseQ-rear=(Q-rear+1)%MAXSIZE;Q-dataQ-rear=x;return 0;/入队int out_seqqueue(Pseqqueue Q,BTree *x)if(empty_seqqueue(Q)printf(队空);return 0;elseQ-front=(Q-front+1)%MAXSIZE;*x=Q-dataQ-front;return 1;/出队void destory_seqqueue(Pseqqueue *Q)if(*Q)free(*Q);*Q=NULL;/销毁队列void PreOrder(BTree t)if(t)printf(%c,t-data);PreOrder(t-lchild);PreOrder(t-rchild);/*void PreOrder1(BTree t) PSeqStack S; BTree p=t; S=Init(); while(p|!Empty(S) if(p) printf(%c,p-data); Push(S,p); p=p-lchild; else Pop(S,&p); p=p-rchild; void InOrder1(BTree t)PSeqStack S;BTree p=t;S=Init();while(p|!Empty(S)if(p)Push(S,p);p=p-lchild;elsePop(S,&p);printf(%c,p-data);p=p-rchild;void InOrder(BTree t)if(t)InOrder(t-lchild);printf(%c,t-data);InOrder(t-rchild);void PostOrder(BTree t)if(t)PostOrder(t-lchild);PostOrder(t-rchild);printf(%c,t-data); void PostOrder1(BTree t)PSeqStack S1;PSeqStack S2;BTree p;p=t;S1=Init();S2=Init();while(p|!Empty(S2)if(p)Push(S1,p);Push(S2,p);p-p-rchild;elsePop(S2,&p);p=p-lchild;while(!Empty(S1)Pop(S1,&p);printf(%c,p-data);*/后序遍历第二种 void PostOrder2(BTree t)PSeqStack S;Data Sq;BTree p=t;S=Init();while(p|!Empty(S)if(p)Sq.flag=0;Sq.node=p;Push(S,Sq);p=p-lchild; elsePop(S,&Sq);p=Sq.node;if(Sq.flag=0)Sq.flag=1;Push(S,Sq);p=p-rchild;elseprintf(%c,p-data);p=NULL; BTree create() BTree T;char c; scanf(%c,&c); if(# = c) T=NULL; else T =(BTree)malloc(sizeof(BNode); T-data = c; T-lchild=create(T-lchild); T-rchild=create(T-rchild); return T; void HBiTree(BTree t)Pseqqueue q;q=init_seqqueue();if(t=NULL) return;BTree p=t;printf(%c,p-data);if(p-lchild) in_seqqueue(q,p-lchild);if(p-rchild) in_seqqueue(q,p-rchild);while(!empty_seqqueue(q)out_seqqueue(q,&p);printf(%c,p-data);if(p-lchild) in_seqqueue(q,p-lchild); if(p-rchild) in_seqqueue(q,p-rchild);destory_seqqueue(&q);return;int leaf(BTree T) if (T = NULL) return 0; if (T-lchild = NULL & T-rchild = NULL) return 1; return leaf(T-lchild) + leaf(T-rchild);/求叶子的个数 int Height(BTree t)int h1,h2;if(t=NULL) return 0;elseh1=Height(t-lchild);h2=Height(t-rchild);if(h1h2) return h1+1; else return h2+1; int main()BTree T;int a=0;int b=0; T=create();/PreOrder(T);/InOrder(T);/PostOrder(T);/PreOrder1(T);/InOrder1(T);PostOrder2(T);printf(n);HBiTree(T);printf(n);a=Height(T);printf(深度为:%dn,a);b=leaf(T); printf(叶子数:%dn,b);return 0;实验心得：这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解，从非递归的遍历算法中可以更好的理解先序，中序和后序遍历算法的理解，同时认识到，在设计程序时辅以图形化的描述是非常有用的。实验四 图的遍历算法实现一、 实验目的掌握图的基本操作,运用图的邻接矩阵和邻接表解决问题。二、 实验要求建立图的邻接矩阵或邻接表，实现图的遍历（DFS/BFS）三、 实验内容1、图的邻接矩阵或邻接表的建立#include #include /建立邻接矩阵 #define MAXSIZE 30#define VertexType char#define Edgetype inttypedef structVertexType vertexsMAXSIZE; Edgetype arcsMAXSIZEMAXSIZE; int vertexNum,edgeNum; MGrah;int CreatMgrah(MGrah *G)int i,j,k,t;scanf(%d%d,&(G-vertexNum),&(G-edgeNum);for(i=0;ivertexNum;i+)scanf(%c,&G-vertexsi);for(i=0;iedgeNum;j+)for(j=0;jedgeNum;j+)G-arcsij=0;for(k=0;kedgeNum;k+)scanf(%d%d,&i,&j);G-arcsij=1;/建立邻接表 #define MAXSZIE 30typedef struct nodeint adjvertex;/InfoType info;struct node * next;EdgeNode;typedef structVertexType vertex;EdgeNode* firstedge;VertexNode;typedef structVertexNode adjlistMAXSIZE;int vertexNum,edgeNum;ALGraph;void CreatALGraph(ALGraph* G)int i,j,k;EdgeNode* p; scanf(%d,%d,&(G-vertexNum),&(G-edgeNum);for(i=0;ivertexNum;i+)scanf(%c,&(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;for(k=0;kedgeNum;k+)scanf(%d,%d,&i,&j);p=(EdgeNode*)malloc(sizeof(EdgeNode);p-adjvertex=j;p-next=G-adjlisti.firstedge;G-adjlisti.firstedge=p;int main()ALGraph* G;CreatALGraph(G);MGrah *G1;CreatMgrah(G1);2、图的遍历算法实现#include #include #define MAXSIZE 100#define VertexType char#define False 0#define True 1typedef structint dataMAXSIZE;int front,rear;SeqQueue,*PseqQueue;PseqQueue Init()PseqQueue Q;Q=(PseqQueue)malloc(sizeof(SeqQueue);if(Q)Q-front=0;Q-rear=0;return Q;int Empty(PseqQueue Q)if(Q&Q-front=Q-rear)return(1);elsereturn(0);int IN(PseqQueue Q,int x)if(Q-rear+1)%MAXSIZE=Q-front)printf(队满);return -1; elseQ-rear=(Q-rear+1)%MAXSIZE;Q-dataQ-rear=x;return 1;int Out (PseqQueue Q,int *x)if(Empty(Q)printf(队空);return -1; elseQ-front=(Q-front+1)%MAXSIZE;*x=Q-dataQ-front;return 1; /*队列的初始化*/ typedef struct nodeint adjvertex;/InfoType info;struct node *next;EdgeNode;typedef structVertexType vertex;EdgeNode *firstedge;VertexNode;typedef structVertexNode adjlistMAXSIZE;int vertexNum,edgeNum;ALGraph;void CreatALGraph(ALGraph *G)int i,j,k;EdgeNode *p; printf(请输入（顶点数，边数）：n); scanf(%d%d,&(G-vertexNum),&(G-edgeNum);printf(n请输入顶点信息：n);for(i=0;ivertexNum;i+)scanf(n%c, &(G-adjlisti.vertex);G-adjlisti.firstedge=NULL;printf(n请输入边的信息：n); for(k=0;kedgeNum;k+)scanf(%d%d,&i,