數據結構課程設計16062

1、實習 1 線性表及其應用1集合的并、交和差/*【實驗目的】編制一個能演示執(zhí)行集合的并、交和差運算的程序【實驗任務】1）集合的元素限定為小寫字母；2）演示程序以用戶和計算機的對話方式執(zhí)行?！靖乓O計】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; /使每次循環(huán)從n的第

5、一個結點開始 while(p->next) if(m->next->data=p->next->data) makenode(L,m->next->data); /有相等元素是將元素放入鏈表中跳出循環(huán) break; p=p->next; m=m->next; /whilevoid bing(linklist &L,linklist m,linklist n) /求兩個集合的并，并且存入一個鏈表中l(wèi)inklist 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; /當有相同元素時跳出循環(huán) 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; /當在交中有相同元素時，跳出循環(huán)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<<"不能繼續(xù)執(zhí)行交并差的運算!"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不能繼續(xù)執(zhí)行交并差的運算!本程序可以較好的完成集合的交并差運算,將集合的元素限定為小寫字母.*/實習 2 棧、隊列和遞歸程序設計1.

13、 求算術表達式的值。/*【實驗目的】 設計一個程序，演示用算符優(yōu)先法對算術表達式求值的過程?！緦嶒炄蝿铡?以字符序列的形式從終端輸入以'#'結束表達式。如果表達式正確計算表達式的值否則指出表達式中錯誤的類型。在輸入的表達式中可以有加、減、乘、除和括號運算，輸入的數據為實數。輸出表達式的值，并且輸出在求值中運算符棧、運算數棧、輸入字符和主要操作的變化過程。【概要設計】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) /判斷運算符的優(yōu)先級 */*【程序代碼】*/#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) /判斷運算符的優(yōu)先級 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. 三元組表示的稀疏矩陣的轉置、加法和乘法的實現。/*【實驗目的】編制一個能演示執(zhí)行集合的并、交和差運算的程序【實驗任務】（1）演示稀疏矩陣A的三元組和十字鏈表的建立過程。（2）演示稀疏矩陣A的轉置過程。（3）演示稀疏矩陣A和B 的相加過程。（4）演示稀疏矩陣A和B 的相乘過程?！靖乓O計】 void StoreRpos(RLSMtrix &M) /用于存儲 void FastTransportRLS(RLSMtrix M,RLSMtrix &T) /實現矩陣的轉置 void Create

24、RLSMtrix(RLSMtrix &M) / 創(chuàng)建矩陣用于矩陣的乘法與轉置 bool MulSMatrix(RLSMtrix M,RLSMtrix N,RLSMtrix &Q) /矩陣的乘法運算 void PrintRLSMatrix(RLSMtrix A)/矩陣的輸出 bool CreateSMatrix_OL(CrossList &M) /創(chuàng)建矩陣用于矩陣的加法 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) / 創(chuàng)建矩陣用于矩陣的乘法與轉置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) /創(chuàng)建矩陣用于矩陣的加法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）演示程序以用戶和計算機的對話方式執(zhí)行?！靖乓O計

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)/先序遍歷二叉樹