数据结构课程设计16062

1、实习 1 线性表及其应用1集合的并、交和差/*【实验目的】编制一个能演示执行集合的并、交和差运算的程序【实验任务】1）集合的元素限定为小写字母；2）演示程序以用户和计算机的对话方式执行。【概要设计】int Initlist(linklist &L)用来初始化线性链表void makenode(linklist &L,char e)生成结点int xiaoxie(char e,int flag)判断输入的字符是否是小写字母void jiao(linklist &L,linklist m,linklist n)求两个集合的交void bing(linklist &L

2、,linklist m,linklist n)求两个集合的并void cha(linklist &L,linklist m,linklist n)求两个集合的交*/ c.cpp : Defines the entry point for the console application./*【程序代码】*/#include "stdafx.h"#include "malloc.h"#include "iostream.h"typedef char elemtype;#define TRUE 1;#define FALSE 0;t

3、ypedef struct lnode /单链表存储结构 elemtype data; struct lnode *next;lnode,*linklist;int Initlist(linklist &L) /初始化线性链表L=(linklist)malloc(sizeof(lnode);if(!L) return FALSE;L->next=NULL;return TRUE;void makenode(linklist &L,char e) /生成结点linklist s;s=(linklist)malloc(sizeof(lnode);s->data=e;s-

4、>next=L->next;L->next=s;int xiaoxie(char e,int flag) /判断输入的字符是否是小写字母 if(e<'a')|(e>'z')printf("输入错误!必须为小写字母!n");flag=0;return flag;void jiao(linklist &L,linklist m,linklist n) /求两个集合的交，并且将其存入另一个链表中 linklist p; Initlist(p); while(m->next) p=n; /使每次循环从n的第

5、一个结点开始 while(p->next) if(m->next->data=p->next->data) makenode(L,m->next->data); /有相等元素是将元素放入链表中跳出循环 break; p=p->next; m=m->next; /whilevoid bing(linklist &L,linklist m,linklist n) /求两个集合的并，并且存入一个链表中linklist J;Initlist(J);jiao(J,m,n); /利用上面所求的两个集合的交进行下一步运算linklist p;wh

6、ile(m->next) /先将其中一个集合的的元素存入链表 makenode(L,m->next->data); m=m->next;while(n->next) /再将另一个集合中不同于前一个集合的元素存入此链表中p=J;while(p->next)if(n->next->data=p->next->data)break; /当有相同元素时跳出循环 p=p->next;/whileif(!p->next)makenode(L,n->next->data); n=n->next;/whilevoid c

7、ha(linklist &L,linklist m,linklist n) /利用两集合的交J,将第一个集合中的与J不同的元素放入链表 linklist J;Initlist(J);jiao(J,m,n); /求交linklist p;while(m->next)p=J;while(p->next)if(m->next->data=p->next->data) break; /当在交中有相同元素时，跳出循环p=p->next;/whileif(!p->next)makenode(L,m->next->data);m=m->

8、;next;/whileint main(int argc, char* argv) char a50,b50; /将两个数组的元素存入链表中int i;int flag=1;cout<<"输入第一个集合A:"cin>>a; /使两个集合中的元素全部限定为小写字母for(i=0;*(a+i)!='0'&&flag;i+)flag=xiaoxie(*(a+i),flag); cout<<"输入第二个集合B:"cin>>b;for(i=0;*(a+i)!='0'&

9、amp;&flag;i+)flag=xiaoxie(*(a+i),flag);if(flag=0) /如果输入不是小写字母则报错并终止 cout<<"不能继续执行交并差的运算!"return 0;linklist m,n;Initlist(m);Initlist(n);for(i=0;*(a+i)!='0'i+)makenode(m,*(a+i);for(i=0;*(b+i)!='0'i+)makenode(n,*(b+i); linklist J,B,C; /J,B,C分别为两集合的交,并,差/初始化链表，并且分别对其操

10、作Initlist(J); Initlist(B);Initlist(C);jiao(J,m,n);bing(B,m,n);cha(C,m,n);linklist p; /以下为输出集合，并释放存储空间 cout<<"两个集合的交是:"p=J;while(p->next)cout<<p->next->data;p=p->next;cout<<endl;cout<<"两个集合的并是:"p=B;while(p->next)cout<<p->next->dat

11、a; p=p->next;cout<<endl;cout<<"两个集合的差A-B是:"p=C;while(p->next)cout<<p->next->data;p=p->next;cout<<endl;while(m->next!=NULL) p=m; m=m->next;free(p);while(n->next) p=n;n=n->next;free(p); while(J->next)p=J;J=J->next;free(p); while(B->

12、next)p=B;B=B->next;free(p); while(C->next)p=C;C=C->next;free(p);return 0;/*【测试数据及结果分析】第一组的测试数据为wsxjtwbxt结果输入第一个集合A:wsxjt输入第二个集合B:wbxt两个集合的交是:wxt两个集合的并是:bwsxjt两个集合的差A-B是:sj第二组的测试数据为ASDACD结果输入第一个集合A:ASD输入错误!必须为小写字母!输入第二个集合B:ACD不能继续执行交并差的运算!本程序可以较好的完成集合的交并差运算,将集合的元素限定为小写字母.*/实习 2 栈、队列和递归程序设计1.

13、 求算术表达式的值。/*【实验目的】 设计一个程序，演示用算符优先法对算术表达式求值的过程。【实验任务】 以字符序列的形式从终端输入以'#'结束表达式。如果表达式正确计算表达式的值否则指出表达式中错误的类型。在输入的表达式中可以有加、减、乘、除和括号运算，输入的数据为实数。输出表达式的值，并且输出在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。【概要设计】void InitStack(SqStack &S) /栈的初始化void Push(SqStack &S,char e) /插入栈数据void Pop(SqStack &S,char &am

14、p;e) /删除头结点,并返回值char GetTop(SqStack S) /返回栈顶元素int In(char c) /限定运算符char Precede(char a,char b) /判断运算符的优先级 */*【程序代码】*/#include "stdafx.h"#include "malloc.h"#include "iostream.h"#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct /栈结点char *base;char *top;in

15、t stacksize;SqStack;void InitStack(SqStack &S) /栈的初始化S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S.base)cout<<"Error1!"<<endl;elseS.top=S.base;S.stacksize=STACK_INIT_SIZE;void Push(SqStack &S,char e) /插入栈数据if(S.top-S.base>=S.stacksize)S.base=(char *)reallo

16、c(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base)cout<<"Error2!"<<endl;elseS.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;void Pop(SqStack &S,char &e) /删除头结点,并返回值if(S.top=S.base)cout<<"Error3!"<<endl;elsee=*-S.top;char

17、GetTop(SqStack S) /返回栈顶元素if(S.top=S.base)cout<<"Error4!"<<endl;elsereturn *(S.top-1);int In(char c) /限定运算符switch(c)case ')':case '#':case '+':case '-':case '*':case '/':case '(': return 1;break;default:return 0;char Preced

18、e(char a,char b) /判断运算符的优先级 int t=-1;if(a=')'&&b!='(')t=1;if(a='*'|a='/')&&b!='(')t=1;if(a='+'|a='-')&&(b='+'|b='-'|b=')'|b='#')t=1;if(a='('&&b=')')|(a='#'&

19、amp;&b='#')t=1;if(a='('&&b=')')|(a='#'&&b='#')t=0; switch(t)case 1:return '>'break;case -1:return '<'break;case 0: return '='break;char Operate(char a,char t,char b) /运算符的运算switch(t)case '+':return a+b-

20、'0'break;case '-':return a-b+'0'break;case '*':return (a-'0')*(b-'0')+'0'break;case '/':return (a-'0')/(b-'0')+'0'break;default:cout<<"Error5!"<<endl;int main() SqStack OPTR,OPND; char a,b,c

21、,x,theta; InitStack(OPTR); Push(OPTR,'#'); InitStack(OPND); cout<<"请输入表达式:"<<endl; c=getchar(); while(c!='#'|GetTop(OPTR)!='#') if(!In(c) Push(OPND,c); c=getchar(); else switch(Precede(GetTop(OPTR),c) case '<': Push(OPTR,c); c=getchar(); break

22、; case '=': Pop(OPTR,x); c=getchar(); break; case '>': Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; cout<<"Result="<<(GetTop(OPND)-'0')<<endl; return 0;/*【测试数据及结果分析】测试数据为1+3*4+(9/3)-5#结果请输入表达式:1+3*4+(9/3)-5#res

23、ult=11本程序通过栈的运用完成了加、减、乘、除和括号的运算*/实习 3 数组和广义表1. 三元组表示的稀疏矩阵的转置、加法和乘法的实现。/*【实验目的】编制一个能演示执行集合的并、交和差运算的程序【实验任务】（1）演示稀疏矩阵A的三元组和十字链表的建立过程。（2）演示稀疏矩阵A的转置过程。（3）演示稀疏矩阵A和B 的相加过程。（4）演示稀疏矩阵A和B 的相乘过程。【概要设计】 void StoreRpos(RLSMtrix &M) /用于存储 void FastTransportRLS(RLSMtrix M,RLSMtrix &T) /实现矩阵的转置 void Create

24、RLSMtrix(RLSMtrix &M) / 创建矩阵用于矩阵的乘法与转置 bool MulSMatrix(RLSMtrix M,RLSMtrix N,RLSMtrix &Q) /矩阵的乘法运算 void PrintRLSMatrix(RLSMtrix A)/矩阵的输出 bool CreateSMatrix_OL(CrossList &M) /创建矩阵用于矩阵的加法 void Translate(char c) /确定矩阵进行的运算 void PrintCrossList(CrossList A) /输出矩阵的值*/*【程序代码】*/#include "st

25、dafx.h"#include "malloc.h"#include "iostream.h"#define MAXSIZE 100#define MAXRC 10#define NUM 10typedef struct int i,j;int e;Triple;typedef struct Triple dataMAXSIZE+1;int rposMAXRC+1;int mu,nu,tu;RLSMtrix;typedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,

26、*OLink;typedef struct OLink rhead,chead;int mu,nu,tu;CrossList;void StoreRpos(RLSMtrix &M) /用于存储int numNUM=0;int t;if(M.tu)for(t=1;t<=M.tu;t+)+numM.datat.i;M.rpos1=1;for(t=2;t<=M.nu;+t)M.rpost=M.rpost-1+numt-1;void FastTransportRLS(RLSMtrix M,RLSMtrix &T) /实现矩阵的转置int p,q,col;T.mu=M.nu;

27、T.nu=M.mu;T.tu=M.tu;if(T.tu)for(p=1;p<=M.tu;+p)col=M.datap.i;q=M.rposcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.dataq.e;+M.rposcol;StoreRpos(T);void CreateRLSMtrix(RLSMtrix &M) / 创建矩阵用于矩阵的乘法与转置int t;cout<<"请输入 mu,nu,tu:"<<endl;cin>>M.mu>>M.nu>

28、>M.tu;cout<<"请输入非零元:"<<endl;for(t=1;t<=M.tu;t+)cin>>M.datat.i>>M.datat.j>>M.datat.e;StoreRpos(M);bool MulSMatrix(RLSMtrix M,RLSMtrix N,RLSMtrix &Q) /矩阵的乘法运算int arrow,p,q,t,tp,brow,col;if(M.nu!=N.mu)return false;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu

29、!=0)for(arrow=1;arrow<=M.mu;arrow+)int ctempNUM=0;Q.rposarrow=Q.tu+1;if(arrow<M.mu)tp=M.rposarrow+1;elsetp=M.tu+1;for(p=M.rposarrow;p<tp;p+)brow=M.datap.j;if(brow<N.mu)t=N.rposbrow+1;elset=N.tu+1;for(q=N.rposbrow;q<t;+q)col=N.dataq.j;ctempcol+=M.datap.e*N.dataq.e;for(col=1;col<=Q.n

30、u;+col)if(ctempcol)if(+Q.tu>MAXSIZE)return false;Q.dataQ.tu.i=arrow;Q.dataQ.tu.j=col;Q.dataQ.tu.e=ctempcol;return true;void PrintRLSMatrix(RLSMtrix A)/矩阵的输出int aNUMNUM=0;int i,j,k; for(k=1;k<=A.tu;k+)aA.datak.i-1A.datak.j-1=A.datak.e;for(i=0;i<A.mu;i+)for(j=0;j<A.nu;j+)cout<<aij<

31、;<" "cout<<endl;bool CreateSMatrix_OL(CrossList &M) /创建矩阵用于矩阵的加法int i,j,e;OLink p,q;cout<<"请输入M的 mu,nu,tu:"<<endl;cin>>M.mu>>M.nu>>M.tu;if(!(M.rhead=(OLNode *)malloc(M.mu+1)*sizeof(OLNode)return false;if(!(M.chead=(OLNode *)malloc(M.nu+1

32、)*sizeof(OLNode)return false;for(i=1;i<=M.mu;i+) M.rheadi.right=NULL;for(j=1;j<=M.nu;j+) M.cheadj.down=NULL;cout<<"请输入非零元以i=0结束:"<<endl;for(cin>>i>>j>>e;i!=0;cin>>i>>j>>e)if(!(p=(OLNode *)malloc(sizeof(OLNode)return false;p->i=i;p-&g

33、t;j=j;p->e=e;if(M.rheadi.right=NULL|M.rheadi.right->j>j)p->right=M.rheadi.right;M.rheadi.right=p;elsefor(q=M.rheadi.right;(q->right)&&q->right->j<j;q=q->right);p->right=q->right;q->right=p;if(M.cheadj.down=NULL|M.cheadj.down->i>i)p->down=M.cheadj.

34、down;M.cheadj.down=p;elsefor(q=M.cheadj.down;(q->down)&&q->down->i<i;q=q->down);p->down=q->down;q->down=p;return true;bool AddSMatrix_OL(CrossList &A,CrossList B) /矩阵的加法运算OLink pa,pb,pre,p,hlNUM;int i=1,k=1,j;pa=A.rhead1.right;pb=B.rhead1.right;pre=NULL;for(j=1;j&

35、lt;=A.nu;+j)hlj=A.cheadj.down;label:while(pb!=NULL)if(pa=NULL|pa->j>pb->j)p=(OLNode *)malloc(sizeof(OLNode);if(!p)return false;p->i=pb->i;p->j=pb->j;p->e=pb->e;p->down=NULL;p->right=NULL;if(pre=NULL)A.rheadp->i.right=p;elsepre->right=p;p->right=pa;pre=p;if(A

36、.cheadp->j.down=NULL|A.cheadp->j.down->i>p->i)p->down=A.cheadp->j.down;A.cheadp->j.down=p;hlj=A.cheadj.down;elsefor(;hlp->j->down&&hlp->j->down->i<p->i;hlp->j=hlp->j->down);p->down=hlp->j->down;hlp->j->down=p;hlj=A.cheadj.d

37、own;pb=pb->right;if(pa!=NULL&&pb!=NULL&&pa->j<pb->j)pre=pa;pa=pa->right;if(pa!=NULL&&pb!=NULL&&pa->j=pb->j)pa->e+=pb->e;if(pa->e!=0)pre=pa;pa=pa->right;pb=pb->right; elseif(pre=NULL)A.rheadpa->i.right=pa->right;elsepre->rig

38、ht=pa->right;p=pa;pa=pa->right;if(A.cheadp->j.down=p)A.cheadp->j.down=p->down; hlj=A.cheadj.down;elsefor(;hlp->j&&hlp->j->down!=p;hlp->j=hlp->j->down);hlp->j->down=p->down;hlj=A.cheadj.down; free(p); pb=pb->right;if(i+1<=A.mu)pre=NULL;pa=A.rhea

39、d+i.right;pb=B.rhead+k.right;goto label;elsereturn true;void PrintCrossList(CrossList A) /输出矩阵的值int aNUMNUM=0;int m,n;OLink p;for(m=1;m<=A.mu;m+) p=A.rheadm.right;for(n=1;n<=A.nu;n+) if(p!=NULL)ap->i-1p->j-1=p->e; p=p->right;elsebreak; for(m=0;m<A.mu;m+)for(n=0;n<A.nu;n+)cout

40、<<amn<<" "cout<<endl;void Translate(char c) /确定矩阵进行的运算switch(c)case '*':RLSMtrix C,D,Q; CreateRLSMtrix(C); PrintRLSMatrix(C); CreateRLSMtrix(D); PrintRLSMatrix(D); MulSMatrix(C,D,Q); PrintRLSMatrix(Q); break;case 't':RLSMtrix E,F; CreateRLSMtrix(E); PrintR

41、LSMatrix(E); FastTransportRLS(E,F); PrintRLSMatrix(F); break;case '+':CrossList A,B; CreateSMatrix_OL(A); PrintCrossList(A); CreateSMatrix_OL(B); PrintCrossList(B); AddSMatrix_OL(A,B); PrintCrossList(A); break;default:cout<<"输入有误!"<<endl;void main()char c;cout<<&q

42、uot;输入欲进行的运算+,*,t(代表转置):"<<endl;cin>>c;Translate(c);/*【测试数据及结果分析】一 第一组的测试数据为+结果输入欲进行的运算+请输入M的 mu,nu,tu:3 3 3请输入非0元以i=0结束:1 1 22 3 23 2 10 0 02 0 00 0 20 1 0请输入M的 mu,nu,tu:3 3 3请输入非零元以i=0结束:1 1 12 2 23 2 20 0 01 0 00 2 00 2 03 0 00 2 20 3 0二 第二组的测试数据为*结果输入欲进行的运算*请输入 mu,nu,tu:2 2 2请输入

43、非零元:1 1 12 2 21 00 2请输入 mu,nu,tu:2 2 2请输入非零元:1 1 12 2 21 00 21 00 4三 第三组的测试数据为t结果输入欲进行的运算t请输入 mu,nu,tu:3 3 3请输入非零元:1 2 12 2 23 3 30 1 00 2 00 0 30 0 01 2 00 0 3演示稀疏矩阵的三元组和十字链表的建立过程。演示稀疏矩阵的转置过程。演示稀疏矩阵的相加过程。演示稀疏矩阵的相乘过程。*/实习 4 树、图及其应用1.二叉树的遍历/*【实验目的】二叉树的遍历【实验任务】1）集合的元素限定为小写字母；2）演示程序以用户和计算机的对话方式执行。【概要设计

44、】void PreorderTraversa (BitTree bt)/先序遍历二叉树void InOrderTraverse(BitTree bt)/中序遍历二叉树void PostorderTraversal (BitTree bt)/后序遍历二叉树int CreateBiTree (BitTree &T)/建立二叉树*/ c.cpp : Defines the entry point for the console application./*【程序代码】*/#include "stdafx.h"#include "malloc.h"#include "iostream.h"typedef char TelemType;typedef struct BitNode /二叉树的二叉链表 TelemType data; struct BitNode *lchild,*rchild;BitNode,*BitTree;void PreorderTraversa (BitTree bt)/先序遍历二叉树