數(shù)據(jù)結(jié)構(gòu)試驗(yàn)(cdut)練習(xí)題

1、實(shí)驗(yàn)一c+語言編程一、實(shí)驗(yàn)?zāi)康模簭?fù)習(xí)、鞏固c+語言上機(jī)操作的基本技能和方法，熟悉：框圖（或流程圖）代碼調(diào)試修改運(yùn)行這一基本上機(jī)過程。二、實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2. 上機(jī)運(yùn)行程序。3. 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4. 按照操作需要，打印出文件清單和運(yùn)行結(jié)果。三、實(shí)驗(yàn)內(nèi)容：編寫一個程序?qū)崿F(xiàn)下列目標(biāo):1. 從鍵盤輸入集合a、b，長度隨機(jī)，以-9999表示輸入結(jié)束，集合a、b的并集和交集，從大到小輸出，不能有同樣的。#include void intersection(int a,int b,int m,int n) /求交集 for(int i=0;im;i

2、+) for(int j=0;jn;j+) if(ai=bj) coutai ; void union(int a,int b,int m,int n) /求并集 int i=0,j=0; while(im&jn) if(ai=bj) coutaibj) coutai ; i+; else coutbj ; j+;int main()int a100=0,b100=0,m,n,i,j; coutm; cout請輸入第一個數(shù)組中的元素:; for(i=0;iai; if(ai=-9999) break; coutn; cout請輸入第二個數(shù)組中的元素:; for(j=0;jbj; if(bj=-

3、9999) break; for(i=0;im;i+) /將數(shù)組a按從小到大排序 for(j=i+1;jm+1;j+) if(aiaj) int temp; temp=ai; ai=aj; aj=temp; for(i=0;im;i+)/將數(shù)組b按從小到大排序 for(j=i+1;jm+1;j+) if(bibj) int temp; temp=bi; bi=bj; bj=temp; cout交集：; intersection(a,b,m,n); coutendl; cout并集：; union(a,b,m,n); coutendl; return 0;2.分別輸入圓柱體的半徑和高，求其體積；

4、輸入球半徑，求其表面積；輸入長方體的長、寬、高，求其體積。#includeint main()const double pi=3.1415926;double r1,h,v1,r2,area,length,wide,height,v2;couth;cinr1;v1=pi*r1*r1*h;cout圓柱體的體積:v1endl;coutr2;area=4*pi*r2*r2;cout球的表面積:areaendl;coutlength;cinwide;cinheight;v2=length*wide*height;cout長方體的體積:v2endl;return 0;實(shí)驗(yàn)二線性表的應(yīng)用一、實(shí)驗(yàn)?zāi)康模赫莆?/p>

5、線性表的基本結(jié)構(gòu)和操作方法，培養(yǎng)學(xué)生靈活使用結(jié)構(gòu)解決實(shí)際問題的能力。二、實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2. 上機(jī)運(yùn)行程序。3. 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4. 按照操作需要，打印出文件清單和運(yùn)行結(jié)果。三、實(shí)驗(yàn)內(nèi)容：1. 運(yùn)行下述程序。說明它所實(shí)現(xiàn)的功能。程序如下：#include #include /*順序表的定義：*/#define listsize 100typedef structint datalistsize;/*向量data用于存放表結(jié)點(diǎn)*/int length;/*當(dāng)前的表長度*/seqlist;void main()void createlis

6、t(seqlist *l,int n);void printlist(seqlist *l,int n);int locatelist(seqlist *l,int x);void insertlist(seqlist *l,int x,int i);void deletelist(seqlist *l,int i); seqlist l;int i,x;int n=10;/*the length of list*/l.length=0;createlist(&l,n);/*creat the list*/printlist(&l,n);/*print the list*/printf(inp

7、ut the research element);scanf(%d,&x);i=locatelist(&l,x);printf(the research position is %dn,i);/*順序表查找*/printf(input the position of insert:n);scanf(%d,&i);printf(input the value of insertn);scanf(%d,&x);insertlist(&l,x,i);/*順序表插入*/printlist(&l, l.length);/*打印順序表*/printf(input the position of delet

8、en);scanf(%d,&i);deletelist(&l,i);/*順序表刪除*/printlist(&l,n);getchar();/*打印順序表*/*順序表的建立：*/void createlist(seqlist *l,int n)int i;printf(please input n numbersn);for(i=1;idatai);l-length=n;/*順序表的打?。?/void printlist(seqlist *l,int n)int i;printf(the sqlist isn);for(i=1;idatai);/*順序表的查找：*/int locatelist(

9、seqlist *l,int x)int i;for(i=1;idatai)=x) return(i);break; return(0);/*順序表的插入：*/void insertlist(seqlist *l,int x,int i)int j;for(j=l-length;j=i;j-)l-dataj+1=l-dataj;l-datai=x;l-length+;/*順序表的刪除：*/void deletelist(seqlist *l,int i) int j;for(j=i;jlength)-1;j+)l-dataj=l-dataj+1;2. 設(shè)計(jì)一個100位以內(nèi)的長整數(shù)加減運(yùn)算的程序

10、。#include#includeint getlength(char *ch) int i; for(i=0;i100;i+) if(chi=0)break; return i;void plusdata(int *dt,int *pdt,int k,int kk) int i; for(i=0;i9) dti-=10; dti+1+; if(dti9) dti-=10; dti+1+; if(dtkk!=0) i=kk; else i=kk-1; for(;i=0;i-) coutdti; coutendl;void minusdata(int *dt,int *mdt,int k,int

11、 kk,int signal) int i; for(i=0;ik;i+) dti=dti-mdti; if(dti0) dti+=10; dti+1-; if(dti0) dti+=10; dti+1-; while(dtkk=0) kk-; if(signal=0) cout=0;i-) coutdti; coutendl;void main() char ch1100,ch2100,ch02,ch; int data1100,data2100; int i,j,k1,k2,flag=0; for(i=0;i100;i+) data1i=0; data2i=0; coutyou can i

12、nput the first datach1; coutyou can input the second datach2; coutwhat operation you want?( + or - )ch; ch01=0; j=0; while(ch1j=0) j+; for(i=0;i99-j;i+) ch1i=ch1i+j; j=0; while(ch2j=0) j+; for(i=0;i99-j;i+) ch2i=ch2i+j; k1=getlength(ch1); k2=getlength(ch2); j=k1; for(i=0;ik1;i+) j-; ch00=ch1j; data1

13、i=atoi(ch0); if(ch1i9) flag=1; j=k2; for(i=0;ik2;i+) j-; ch00=ch2j; data2i=atoi(ch0); if(ch2i9) flag=1; if(flag=0) if(ch=+) if(k1data2k1-1) minusdata(data1,data2,k2,k2,1); else minusdata(data2,data1,k2,k2,0); else if(k1k2) minusdata(data1,data2,k2,k1,1); else minusdata(data2,data1,k1,k2,0); else cou

14、tyou have input a invaluable char!endl;四、 注意事項(xiàng)：1. 在磁盤上創(chuàng)建一個目錄，專門用于存儲數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的程序；2. 輸入輸出要求：每四位一組，組間用逗號分隔；3. 加和減分別用不同的程序?qū)崿F(xiàn)；4. 程序應(yīng)考慮輸入數(shù)據(jù)的符號。實(shí)驗(yàn)三單鏈表操作一、實(shí)驗(yàn)?zāi)康模赫莆瘴諉捂湵淼幕静僮鳎翰迦?、刪除、查找等運(yùn)算。二、實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2. 上機(jī)運(yùn)行程序。3. 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4. 按照操作需要，打印出文件清單和運(yùn)行結(jié)果。三、實(shí)驗(yàn)內(nèi)容：1. 運(yùn)行下述程序。說明它所實(shí)現(xiàn)的功能。#include#include#

15、include#includetypedef struct node int data; struct node *next; node;/*/node *create()node *p,*head;int x;head=(node *)malloc(sizeof(node);head-next=null;printf(input data,-1 to end!n);scanf(%d,&x);while(x!=-1) p=(node *)malloc(sizeof(node); p-data=x; p-next=head-next; head-next=p; scanf(%d,&x);retu

16、rn(head);/*/void output(node *head) node *p; p=head; printf(begin to dump the linklist.n); while(p-next!=null) printf(-%d,p-next-data); p=p-next; printf(nthe linklist ended!n);/*/int listlen(node *head) int i=0; node *p=head; while(p-next!=null) i+; p=p-next; return(i);/*/int get(node *head,int i)in

17、t j=0;node *p=head;while(p-next&jnext;if(!p-next|ji) return(0);else return(p-data);/*/void del(node *head,int i)node *p=head;int j=0;while(p-next&jnext;if(!p-next|ji-1) printf(the position is wrongn);elsep-next=p-next-next;/*/void ins(node *head,int i,int e)node *p=head,*q;int j=0;while(p-next&jnext

18、;if(!p-next&ji-1) printf(wrong positionn );else q=(node *)malloc(sizeof(node); q-data=e; q-next=p-next; p-next=q;/*/void main() node *head; int length; int i,element; head=create(); output(head); length=listlen(head); printf(the length of the link is %dn,length); printf(input the order :n); scanf(%d

19、,&i); element=get(head,i);printf(the element of the order is %dn,element); printf(input the del position n); scanf(%d,&i); del(head,i); output(head); printf(input the insert posion and element:n); scanf(%d%d,&i,&element); ins(head,i,element); output(head); getchar();2. 編寫一個程序?qū)崿F(xiàn)下列目標(biāo):1) 建立一個鏈表，用于存放成績（

20、整型）；2) 輸出鏈表中的所有數(shù)據(jù)、平均成績和最高成績。#includeusing namespace std;struct node int id;int score;node* next;void display(const node*);node* create();void main() node* head = null;head = create();if(head != null) display(head);else cout學(xué)生人數(shù)為0endl;node* create() node *head, *temp;int n;coutn;if(n = 0) return null

21、;head = new node; temp = head;for(int i = 1; i = n; i+) cout請輸入第itemp-id;cout請輸入第itemp-score;if(i != n) temp-next = new node; temp = temp-next; temp-next = null;return head;/display函數(shù)void display(const node* head) int i = 1;int sum = 0;int max = head-score;coutendl;while(head) cout第i個學(xué)生成績: scorescor

22、e;if(head-score max) max = head-score;head = head-next;i+;cout平均分：sum/(i-1)endl;cout最高分：maxendl;四、 注意事項(xiàng)：1. 在磁盤上創(chuàng)建一個目錄，專門用于存儲數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的程序。2. 數(shù)據(jù)個數(shù)和數(shù)據(jù)從鍵盤輸入，每個結(jié)點(diǎn)包括學(xué)號和成績。實(shí)驗(yàn)四 棧的基本操作一、 實(shí)驗(yàn)?zāi)康模赫莆諚５幕静僮鳎撼跏蓟瘲！⑴袟榭?、出棧、入棧等運(yùn)算。二、實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法；2 上機(jī)將本算法實(shí)現(xiàn)； 3 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。三、實(shí)驗(yàn)內(nèi)容：利用棧的基本操作實(shí)現(xiàn)將任意一個十進(jìn)制整數(shù)轉(zhuǎn)化為r

23、進(jìn)制整數(shù)。算法為：1 定義棧的順序存取結(jié)構(gòu)2 分別定義棧的基本操作（初始化棧、判棧為空、出棧、入棧等）3 定義一個函數(shù)用來實(shí)現(xiàn)上面問題：十進(jìn)制整數(shù)x和r作為形參初始化棧只要不為重復(fù)做下列動作將入棧x=x/r只要棧不為空重復(fù)做下列動作棧頂出棧輸出棧頂元素四、 注意事項(xiàng)：1. 在磁盤上創(chuàng)建一個目錄，專門用于存儲數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的程序。#include#define maxsize 100#includestruct stack int datamaxsize; int top;void init(struct stack *s) s-top=-1;int empty(struct stack *s)

24、if(s-top=-1) return 1; else return 0; void push(struct stack *s,int i) if(s-top=maxsize-1) printf(stack is fulln); return; s-top+; s-datas-top=i;int pop(struct stack *s) if(empty(s) printf(stack is empty); return -1; return(s-datas-top-);void trans(int num) struct stack s; int k; int(&s); while(num)

25、 k=num%16; push(&s,k); num=num/16; while(!empty(&s) k=pop(&s); if(k10) printf(%d,k); else printf(%c,k+55); printf(n);void main() int num; int r; printf(input r); scanf(%d,&r); /clrscr(); printf(input a num,-1 to quit:n); scanf(%d,&num); while(num!=-1) trans(num); scanf(%d,&num); 實(shí)驗(yàn)五 數(shù)組的基本操作一、實(shí)驗(yàn)?zāi)康模夯仡?/p>

26、c+語言中數(shù)組的定義和基本應(yīng)用；二、 實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2 上機(jī)運(yùn)行本程序。3 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。三、 實(shí)驗(yàn)內(nèi)容：有m個學(xué)生，學(xué)習(xí)n門課程，已知所有學(xué)生的各科成績，編程：分別求每個學(xué)生的平均成績和每門課程的平均成績。四、 注意事項(xiàng)：1. 在磁盤上創(chuàng)建一個目錄，專門用于存儲數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的程序。#define m 5#define n 4#include stdio.hvoid main() int i,j; static float scorem+1n+1=78,85,83,65, 88,91,89,93, 72,65,54,75,86,88

27、,75,60, 69,60,50,72; for(i=0;im;i+) for(j=0;jn;j+) scorein += scoreij; scoremj += scoreij; scorein /= n; for(j=0;jn;j+) scoremj /= m; /clrscr();printf(學(xué)生編號 課程1 課程2 課程3 課程4 個人平均n);for(i=0;im;i+) printf(學(xué)生%dt,i+1); for(j=0;jn+1;j+) printf(%6.1ft,scoreij); printf(n); for(j=0;j8*(n+2);j+) printf(-); pri

28、ntf(n課程平均); for(j=0;jn;j+) printf(%6.1ft,scoremj); printf(n); getchar(); 實(shí)驗(yàn)六稀疏矩陣運(yùn)算一、實(shí)驗(yàn)?zāi)康模赫莆杖M法存儲稀疏矩陣的方法及相關(guān)的基本操作。二、 實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2 上機(jī)運(yùn)行本程序。3 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。三、實(shí)驗(yàn)內(nèi)容：編寫一個程序?qū)崿F(xiàn)下列目標(biāo)。1，用三元組法存放稀疏矩陣；2，求出矩陣相乘結(jié)果；3，輸出結(jié)果矩陣。#include #include #define ok 1 #define error 0 #define maxsize 100 /最多非0元

29、素的個數(shù) #define maxr 50 /rpos所能處理的最大行數(shù) #define maxc 50 /系數(shù)矩陣相乘時，保留臨時列結(jié)果的數(shù)組tempmaxc typedef struct node /定義稀疏矩陣結(jié)點(diǎn) int i; int j; int data; node; typedef struct matrix /定義稀疏矩陣（可以快速訪問） int mu, nu, tu; node matrixmaxsize+1; int rposmaxr+1; matrix; int creatsmatrix( matrix* m ); /創(chuàng)建一個矩陣（由用戶輸入原始矩陣，轉(zhuǎn)化為稀疏矩陣方式儲存

30、） int print( matrix m ); /打印一個稀疏矩陣 int mul_smatrix( matrix m, matrix n, matrix *q); /兩個稀疏矩陣相乘 int main() matrix a1, a2, a3; /定義矩陣 creatsmatrix( &a1 ); creatsmatrix( &a2 ); if( a1.nu=a2.mu ) /判斷能否相乘 mul_smatrix( a1, a2, &a3 ); printf(兩矩陣相乘得：n); print(a3); system(pause); return 0; /構(gòu)建稀疏矩陣 int creatsma

31、trix( matrix* m ) int temp, i,j; printf(輸入矩陣的行列數(shù)：); scanf(%d%d, &m-mu, &m-nu); m-tu=0; printf(按行序輸入矩陣：n); for( i=1; imu; i+) m-rposi=m-tu+1; /每計(jì)算完一行，給rpos賦值 for( j=1; jnu; j+) scanf(%d,&temp); if( temp ) /非0值保存 m-matrixm-tu+1.i= i; m-matrixm-tu+1.j= j; m-matrixm-tu+1.data=temp; m-tu+; return ok; /打印

32、稀疏矩陣 int print( matrix m) int i; if(m.tu=0) printf(空矩陣nn); return error; printf(itjtdatan); for( i=1; itu=0;/初始化q q-mu=m.mu; q-nu=m.nu; if(m.tu*n.tu!=0) /非零矩陣 for(arow=1; arow=m.mu; arow+) for(i=1; irposarow=q-tu+1; /給q-rpos數(shù)組賦值 mlim = arowm.mu ? m.rposarow+1 : m.tu+1;/m中第arow行在結(jié)點(diǎn)數(shù)組中的范圍 for( mcol=m.

33、rposarow; mcolmlim; mcol+ )/遍歷m中第arow行的每一個j mj=m.matrixmcol.j; nlim = mjn.mu ? n.rposmj+1 : n.tu+1;/在n中找到行號i等于m中的列號j的位置 for( nrow=n.rposmj; nrownlim; nrow+ )/乘積元素在q中的列號 ctempn.matrixnrow.j += m.matrixmcol.data * n.matrixnrow.data; for(i=1; inu; i+)/列號對應(yīng)元素不為零，賦值 if( ctempi ) if( +q-tu maxsize ) retur

34、n 0; q-matrixq-tu.i = arow; q-matrixq-tu.j = i; q-matrixq-tu.data = ctempi; return 1; 四、 注意事項(xiàng)：1. 在磁盤上創(chuàng)建一個目錄，專門用于存儲數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的程序；2. 用數(shù)組存放矩陣的三元組，矩陣的行數(shù)和列數(shù)及非0數(shù)據(jù)從鍵盤輸入；3. 若兩個矩陣不能相乘則輸出“error”實(shí)驗(yàn)七二叉樹1一、實(shí)驗(yàn)?zāi)康模? 進(jìn)一步掌握指針變量的含義。2 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。3 掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。二、 實(shí)驗(yàn)要求：1 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2 上機(jī)運(yùn)行本程序。3 保

35、存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4 按照二叉樹的操作需要，重新改寫主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果。三、實(shí)驗(yàn)內(nèi)容：編寫一個程序?qū)崿F(xiàn)下列目標(biāo)。1，根據(jù)輸入的數(shù)據(jù)建立一個二叉樹2，輸出二叉樹（輸出的結(jié)果應(yīng)為樹型結(jié)構(gòu)）3，輸出其前序、中序和后序遍歷的結(jié)果#include#include#define maxsize 100typedef char elemtype;typedef struct nodeelemtype data;struct node *lchild;struct node *rchild;btnode;void createbtnode(btnode *&b,

36、char *str)btnode *stmaxsize,*p=null;int top=-1,k,j=0;char ch;b=null;ch=strj;while(ch!=0)switch(ch)case(:top+;sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(btnode *)malloc(sizeof(btnode);p-data=ch;p-lchild=p-rchild=null;if(b=null)b=p;elseswitch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;void dispbtnode(btnode *b)if(b!=null)printf(%c,b-data);if(b-lchild!=null|b-rchild!=null)printf();dispbtnode(b-lchild);if(b-rchild!=null)printf(,);dispbtnode(b-rchild);printf();void preorder(btnode *b)if(b!=null)printf(%c,b-data);pre