數(shù)據(jù)結構上機實驗答案

《數(shù)據(jù)結構上機實驗答案》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構上機實驗答案（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結構實驗指導書答案實驗一：1、 請編寫函數(shù)int fun(int *a, int *b),函數(shù)的功能是判斷兩個指針a和b所指存儲單元的值的符號是否相同；若相同函數(shù)返回1，否則返回0。這兩個存儲單元中的值都不為0。在主函數(shù)中輸入2個整數(shù)、調用函數(shù)fun、輸出結果。#include int fun(int *a, int *b) if (*a*(*b)0) return(1); else return(0);main()int x,y;scanf(%d%d,&x,&y);if (fun(&x,&y) printf(yesn);else printf(no);2、 計算1+2+3+100，要求用

2、指針進行設計。即設計函數(shù)int fun(int *n)實現(xiàn)求1+2+3+*n，在主函數(shù)中輸入、調用、輸出結果。#include int fun(int *n) int i,sum=0; for (i=1;i=*n;i+) sum+=i; return(sum);main()int x,sum;scanf(%d,&x); printf(the sum is %dn,fun(&x);3、 函數(shù)的功能是求數(shù)組a中最大數(shù)的位置（位序號）。在主函數(shù)中輸入10個整數(shù)、調用函數(shù)fun、輸出結果。#define N 10#include void input(int *a,int n)int i; for (

3、i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/int fun(int *a,int n)int i,*max;max=a;for (i=1;i*max) max=a+i;return(max-a);main()int aN,maxi;input(a,N);maxi=fun(a,N);printf(n the max position is %dn,maxi);4、請編寫函數(shù)fun(int *a,int n, int *odd, int *even),函數(shù)的功能是分別求出數(shù)組a中所有奇數(shù)之和和所有偶數(shù)之和。形參n給出數(shù)組中數(shù)據(jù)的個數(shù)；利用指針odd和ev

4、en分別返回奇數(shù)之和和偶數(shù)之和。在主函數(shù)中輸入10個整數(shù)、調用函數(shù)fun、輸出結果。#define N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/void fun(int *a,int n, int *odd, int *even)int i,sum1=0,sum2=0;for (i=0;in;i+)if (ai%2=0) sum1+=ai; else sum2+=ai;*odd=sum1;*even=sum2;main()int aN,odd,even;

5、input(a,N);fun(a,N, &odd, &even);printf(the odd is %dtthe even is %dn,odd,even);5、請編寫函數(shù)int fun(int *a, int *b，int n),函數(shù)的功能是把數(shù)組a中所有為偶數(shù)的數(shù)，放在另一個數(shù)組中b。在主函數(shù)中輸入10個整數(shù)、調用函數(shù)fun、輸出結果。#define N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/void output(int *a,int n)in

6、t i;printf(nthe odd is:n);for (i=0;in;i+) printf(%5d,*(a+i); /*printf(%d,ai);*/int fun(int *a, int *b,int n)int i,j=0;for (i=0;in;i+)if (ai%2=0) bj=ai; j+;return(j);main()int aN,bN,m;input(a,N);m=fun(a,b,N);output(b,m);6、請編寫函數(shù)int fun(int *a,，int n),函數(shù)的功能是把數(shù)組a中最大數(shù)和最小數(shù)交換。在主函數(shù)中輸入10個整數(shù)、調用函數(shù)fun、輸出結果。#def

7、ine N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/void output(int *a,int n)int i;printf(nthe result is:n);for (i=0;in;i+) printf(%5d,*(a+i); /*printf(%d,ai);*/void fun(int *a,int n)int i,*max,*min,temp;max=min=a;for (i=1;i*max) max=a+i;if (ai*min) min=a

8、+i;printf(the max is %d,the position is %dn,*max,max-a);printf(the min is %d,the position is %dn,*min,min-a);if (max!=min)temp=*max;*max=*min;*min=temp;main()int aN,m;input(a,N);fun(a,N);output(a,N);7、請編寫函數(shù)int fun(int a44),函數(shù)的功能是把矩陣a轉置。在主函數(shù)中輸入、調用函數(shù)fun、輸出結果。#define N 4#include void input(int a4,int n

9、)int i,j; for (i=0;in;i+) for (j=0;jn;j+) scanf(%d,&aij);void output(int a4,int n)int i,j;printf(nthe result is:n);for (i=0;in;i+) printf(n); for (j=0;jn;j+)printf(%4d,*(*(a+i)+j); /*printf(%d,aij);*/ void fun(int a4,int n)int i,j,temp;for (i=0;in;i+)for (j=0;ji;j+) temp=aij;aij=aji;aji=temp;main()i

10、nt aNN;input(a,N);fun(a,N);output(a,N);8、 請編寫函數(shù)int fun(char *a),函數(shù)的功能是分別求出字符串a(chǎn) 的長度。在主函數(shù)中輸入1個字符串、調用函數(shù)fun、輸出結果。#include int fun(char *a)int i=0;char *p;p=a;while (*p) i+; p+;return(i);main()char str20,*cp;cp=str;gets(cp);printf(the length of %s is %dn,cp,fun(cp);9、10、#include #include #define N 2typed

11、ef struct student /*定義數(shù)據(jù)結構（數(shù)據(jù)類型）*/ long num; char name10; int score3; /*存放三門課成績 */ float average; /*/平均成績*/ stu;void intput(stu s,int n) /*輸入數(shù)據(jù) */int i,j; /*i表示處理學生的下標，J表示成績編號 */ for (i=0;in;i+) printf(input num:n); scanf(%ld,&si.num); printf(input name:n); scanf(%s,si.name); printf(input 3 score:n)

12、; for (j=0;j3;j+) scanf(%d,&si.scorej); void stu_av(stu s,int n)/*求每個學生的平均成績*/ int i,j,sum; for (i=0;in;i+) sum=0; for (j=0;j3;j+) sum+=si.scorej ; si.average=sum/3.0; float av(stu s,int n)/*求總平均成績*/ int i; float sum=0.0,ave; for (i=0;in;i+) sum+=si.average; ave=sum/n; return(ave);int max(stu s,int

13、n)/*求平均成績最高學生的下標*/ int i,maxi=0; for (i=1;ismaxi.average) maxi=i; return(maxi);main()int maxi,j; stu aN;/*定義變量 */ intput(a,N); stu_av(a,N); printf(the score average is %fn, av(a,N); maxi=max(a,N); printf(the max average student data:n); printf(%10ld,amaxi.num); printf(%10s,amaxi.name); for (j=0;j3;j

14、+) printf(%5d,amaxi.scorej); printf(%5.1f,amaxi.average); getch();實驗二 1、#include #define MaxLen 50typedef int elemtype;struct datatypeelemtype *elem; int length;typedef struct datatype sqlist;void create (sqlist *a)int i,n;a-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);printf(創(chuàng)建一個順序表n);printf(輸入元

15、素個數(shù)n);scanf(%d,&a-length);for (i=0;ilength;i+) printf(輸入第%d個元素值:,i+1); scanf(%d,a-elem+i);void invert(sqlist *a) int m=a-length/2,i;elemtype temp;for (i=0;ielem+i); *(a-elem+i)=*(a-elem+a-length-1-i); *(a-elem+a-length-1-i)=temp; void disp(sqlist *a) int i;for (i=0;ilength;i+) printf(%5d:%dn,i+1,*(a

16、-elem+i);getch();void main()sqlist a;create(&a);disp(&a);invert(&a);disp(&a);2、#include #include #define NULL 0typedef int elemtype;typedef struct linknodeelemtype data;struct linknode *next;nodetype;nodetype *create()elemtype d;nodetype *h,*s,*t;int i=1;h=NULL;printf(建立一個單鏈表n);while (1) printf(輸入第%

17、d節(jié)點data域值:,i); scanf(%d,&d);if (d=0) break ; /*以0表示輸入結束*/if(i=1) /*建立第一個結點*/h=(nodetype *)malloc(sizeof(nodetype);h-data=d;h-next=NULL;t=h;elses=(nodetype *)malloc(sizeof(nodetype);s-data=d;s-next=NULL;t-next=s;t=s; /*t始終指向生成的單鏈表的最后一個結點*/i+;return h;void disp(nodetype *h)nodetype *p=h;printf(輸出一個單鏈表

18、：n);if (p=NULL) printf(空表);while (p!=NULL)printf(%d,p-data);p=p-next;printf(n);getch();int len(nodetype *h)int i=0;nodetype *p=h;while (p)i+;p=p-next;return(i);nodetype *invert(nodetype *h)nodetype *p,*q,*r;if (len(h)next;while (q!=NULL)r=q-next;q-next=p;p=q;q=r;h-next=NULL;h=p;return h;void main()n

19、odetype *head;head=create();disp(head);head=invert(head);disp(head);4、（1）#include #define MaxLen 50typedef structlong num; int score; elemtype;typedef struct datatypeelemtype *elem; int length;sqlist;void create (sqlist *a)long i=0,n;int s;a-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);printf(創(chuàng)建一

20、個順序表n);printf(輸入學生學號和成績：0作為結束標志n);scanf(%ld%d,&n,&s);while (n!=0) (a-elem)i.num=n; (a-elem)i.score=s; i+; scanf(%ld%d,&n,&s);a-length=i;void disp(sqlist *a) int i;for (i=0;ilength;i+) printf(%5d:%ld %dn,i+1,(a-elem)i.num,(a-elem)i.score);getch();void main()sqlist a;create(&a);disp(&a);（2）見5（2）5、（1）#

21、include #define MaxLen 50typedef structlong num; int score; elemtype;typedef struct datatypeelemtype *elem; int length;sqlist;void create (sqlist *a)long i=0,n;int s;a-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);printf(創(chuàng)建一個順序表n);printf(輸入學生學號和成績：0作為結束標志n);scanf(%ld%d,&n,&s);while (n!=0) (a-elem)

22、i.num=n; (a-elem)i.score=s; i+; scanf(%ld%d,&n,&s);a-length=i;void sort(sqlist *a) int i,j,k,s; long n; for (i=0;ilength-1;i+) k=i; for (j=i+1;jlength;j+) if (a-elem)j.scoreelem)k.score) k=j; if (k!=i) n=(a-elem)i.num;(a-elem)i.num=(a-elem)k.num; (a-elem)k.num=n; s=(a-elem)i.score;(a-elem)i.score=(a

23、-elem)k.score; (a-elem)k.score=s; void disp(sqlist *a) int i;for (i=0;ilength;i+) printf(%5d:%ld %dn,i+1,(a-elem)i.num,(a-elem)i.score);getch();void main()sqlist a;create(&a);disp(&a);sort(&a);disp(&a);（2）#include #include #define NULL 0typedef struct linknodelong num;int score;struct linknode *next

24、;nodetype;nodetype *create()long n;int sc;nodetype *h,*s,*t;h=(nodetype *)malloc(sizeof(nodetype);h-next=NULL;t=h;printf(創(chuàng)建一個順序表n);printf(輸入學生學號和成績：0作為結束標志n);scanf(%ld%d,&n,&sc); while (n!=0) s=(nodetype *)malloc(sizeof(nodetype); s-num=n;s-score=sc;t-next=s;t=s; scanf(%ld%d,&n,&sc); t-next=NULL;ret

25、urn h;void disp(nodetype *h)nodetype *p=h-next;printf(輸出一個單鏈表：n);while (p!=NULL) printf(%ld %dn,p-num,p-score);p=p-next;printf(n);getch();nodetype *insertorder(nodetype *h,nodetype *s)nodetype *p,*q;q=h;p=q-next;while (p!=NULL & s-scorep-score) q=p; p=p-next; s-next=p;q-next=s;return(h);nodetype *so

26、rt(nodetype *h) nodetype *p,*s; p=h-next; h-next=NULL; while (p!=NULL) s=p-next; h=insertorder(h,p); p=s; return h;void main()nodetype *head;head=create();disp(head);head=sort(head);disp(head);實驗三：7、試寫一個算法，識別依次讀入的一個以為結束符的字符序列是否為形如序列1&序列2模式的字符序列。其中序列1和序列2中不包含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是屬于該模式的字符序列，而1+

27、2&2-1則不是。int IsReverse()/判斷輸入的字符串中&前和&后部分是否為逆串,是則返回1,否則返回0InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s) return 0;return 1;/IsReverse 8、編寫一個函數(shù)將一般算術表達式轉化為逆波蘭表達式。 解：假設表達式中的符號以字符形式由鍵盤輸入（為簡單起見，設算術表達式中的參加運算的數(shù)都只有一位數(shù)字），

28、該算術表達式存放在字符型數(shù)組 str 中，其逆波蘭表示式依次存放在字符型數(shù)組 exp 中，在處理函數(shù)中用一個字符型數(shù)組 stack 作為棧。設字符“#”為表達式的終止符，將算術表達式轉換成逆波蘭表示的方法如下： 依次從鍵盤輸入表達式中的字符 c，對于每一個 c： 若 c 為數(shù)字，則將 c 依次存入數(shù)組 exp 中； 若 c 為左括弧“(”，則將此括弧壓入棧 stack； 若 c 為右括弧“)”，則將棧 stack 中左括弧“(”以前的字符依次彈出存入數(shù)組 exp中，然后將左括弧“(”彈出； 若 c 為“+”或“-”，則將當前棧 stack 中“(”以前的所有字符（運算符）依次彈出存入數(shù)組 ex

29、p 中；如果沒有“（”，則將棧stack中的所有字符依次彈出存入數(shù)組exp中,然后將 c 壓入棧 stack 中； 若 c 為“*”或“/”，則將當前棧 stack 中的棧頂端連續(xù)的“*”或“/”彈出并依次存入數(shù)組 exp 中，然后將 c 壓入棧 stack 中； 若 c 為“#”，則將棧 stack 中的所有運算符依次彈出并存入數(shù)組 exp 中，然后再將c 存入數(shù)組 exp 中，最后可得到表達式的波蘭表示在數(shù)組 exp 中。 根據(jù)上述轉換原理得到的函數(shù)如下： #define Maxsize 100 /* Maxsize 為算術表達式中最多字符個數(shù) */ void trans() char s

30、trMaxsize； /*存儲原算術表達式*/ char expMaxsize； /*存儲轉換成的逆波蘭表達式*/ char stackMaxsize； /*作為棧使用*/ char ch； int i，j，t，top=0；/*t 作為 exp 的下標，top 作為 stack 的下標，i 作為 str 的下標*/ i=0； /*獲取用戶輸入的表達式*/ do i+； scanf(%c，&stri)； while (stri!=# & i=0 & ch=9) /*判定為數(shù)字*/ expt=ch；t+； else if (ch=() /*判定為左括號*/ top+；stacktop=ch； el

31、se if (ch=) /*判定為右括號*/ while (stacktop!=() expt=stacktop；top-；t+； top-； else if (ch=+ | ch=-) /*判定為加減號*/ while (top!=0 & stacktop!=() expt=stacktop；top-；t+； top+； stacktop=ch； else if (ch=* | ch=/) /*判定為*或/號*/ while (stacktop=* | stacktop=/) expt=stacktop；top-；t+； top+； stacktop=ch； ch=stri；i+； whil

32、e (top!=0) expt=stacktop；t+；top-； expt=#； for (j=1；j=t；j+) printf(%c，expj)； printf(n)； 9、編寫一個函數(shù)求逆波蘭表達式的值，其中波蘭表達式是在該函數(shù)中輸入的。 解：對逆波蘭表達式求值函數(shù)中要用到一個數(shù)棧 stack，其實現(xiàn)函數(shù)如下：先用戶以字符形式由鍵盤輸入一個逆波蘭表達式（為簡單起見，設逆波蘭表達式中的參加運算的數(shù)都只有一位數(shù)字），該逆波蘭表達式存放在字符型數(shù)組 exp 中，從逆波蘭表示式的開始依次掃描這個波蘭表示式，當遇到運算對象時，就把它壓入數(shù)棧 stack；當遇到運算符時，就執(zhí)行兩次彈出數(shù)棧 stac

33、k 中的數(shù)的操作，對彈出的數(shù)進行該運算符所指定的運算，再把結果壓入數(shù)棧 stack，重復上述過程，直至掃描到表達式的終止符“#”，在數(shù)棧頂?shù)玫奖磉_式的值。 根據(jù)上述計算原理得到的函數(shù)如下： #define Maxsize 100 /* Maxsize 為算術表達式中最多字符個數(shù) */ void compvalue() char expMaxsize； /*存儲用戶輸入的逆波蘭表達式*/ float stackMaxsize，d； /*作為棧使用*/ char c； int i=0，t=0，top=0； /*t 作為 exp 的下標，top 作為 stack 的下標*/ do /*獲取用戶輸入的

34、逆波蘭表達式*/ i+； scanf(%c，&expi)； while (expi!=# & i=0 & c=9) /*判定為數(shù)字字符*/ d=c-0； /*將數(shù)字字符轉換成對應的數(shù)值*/ top+； stacktop=d； else /*判定是運算符*/ switch (c) case +:stacktop-1=stacktop-1+stacktop；break；case -:stacktop-1=stacktop-1-stacktop；break；case *:stacktop-1=stacktop-1*stacktop；break； case/:if(stacktop!=0) stack

35、top-1=stacktop-1/stacktop； else printf(除零錯誤!n)；break; top-； c=expt；t+； printf(計算結果是:%g，stacktop)； 實驗四：4、請編寫函數(shù)int fun(char *a, char *b),函數(shù)的功能是求在字符串a(chǎn)中出現(xiàn)字符串b次數(shù)。在主函數(shù)中輸入兩個字符串、調用函數(shù)fun、輸出結果。#include #include #define NULL 0int fun(char *a,char *b) int num=0,len;/*num計數(shù)，len為b串的長度*/ char *p,*s;/*p為源串，s為子串位置*/

36、 p=a; len=strlen(b); while (strlen(p)len) s=strstr(p,b); if (s!= NULL) num+; else break; p=s+len; return(num);main()char str181,str281,*cp1,*cp2;cp1=str1;cp2=str2;gets(cp1);gets(cp2);printf(the number of %s in %s is %dn,cp2,cp1,fun(cp1,cp2);6、請編寫函數(shù)void fun(char a20, int n),函數(shù)的功能是把n個字符串中所有空格刪除。在主函數(shù)中輸

37、入、調用函數(shù)fun、輸出結果。#include void fun1(char *a)int i=0;char *p1,*p2;p1=p2=a;while (*p1)if (*p1!= )*p2=*p1;p2+; p1+;*p2=0;void fun(char a20, int n)int i;for (i=0;in;i+) fun1(ai);main()int i;char str20=aa aa a,b bb b , c c ;fun(str,3);printf(the string of result is:n);for (i=0;i3;i+) puts(stri);getch();7、請

38、編寫函數(shù)void fun(char a20, int n),函數(shù)的功能是把n個字符串排序。在主函數(shù)中輸入、調用函數(shù)fun、輸出結果。#include void fun(char a20, int n)int i,j,k;char *temp;for (i=0;in-1;i+) for (j=0;j0) strcpy(temp,aj); strcpy(aj,aj+1); strcpy(aj+1,temp); main()int i;char str20=b bb b ,aa aa a,c c ;fun(str,3);printf(the string of result is:n);for (i

39、=0;i3;i+) puts(stri);getch();實驗五：7、對于二維數(shù)組 Amn，其中 m80，n80，先讀入 m 和 n，然后讀該數(shù)組的全部元素，對如下三種情況分別編寫相應函數(shù)： （1）求數(shù)組 A 靠邊元素之和； （2）求從 A00開始的互不相鄰的各元素之和； （3）當 m=n 時，分別求兩條對角線上的元素之和，否則打印出 mn 的信息。解： （1）本小題是計算數(shù)組 A 的最外圍的 4 條邊的所有元素之和，先分別求出各邊的元素之和，累加后減除 4 個角的重復相加的元素即為所求。 （2）本小題的互不相鄰是指上、下、左、右、對角線均不相鄰，即求第 0，2，4，.的各行中第 0，2，4，

40、.列的所有元素之和，函數(shù)中用 i 和 j 變量控制即可。 （3）本小題中一條對角線是 Aii，其中（0im-1），另一條對角線是 Am-i-1，i，其中（0im-1），因此用循環(huán)實現(xiàn)即可。實現(xiàn)本題功能的程序如下： #include /*實現(xiàn)(1)小題功能的函數(shù)*/ void proc1(maxix A) int s=0，i，j; for (i=0;im;i+) /*第一列*/ s=s+Ai1; for (i=0;im;i+) /*最后一列*/ s=s+Ain; for (j=0;jn;j+) /*第一行*/ s=s+A1j; for (j=0;jm;j+) /*最后一行*/ s=s+Amj;

41、for (j=0;jn;j+) /*第一行*/ s=s+A1j; for (j=0;jm;j+) /*最后一行*/ s=s+Amj; s=s-A00-A0n-1-Am-10-Am-1n-1; /*減去 4 個角的重復元素值*/ printf(s=%dn，s); /*實現(xiàn)(2)小題功能的函數(shù)*/ void proc2(maxix A) int s=0，i，j; i=0; while(im) j=0; while(jn) s=s+Aij; j=j+2; /*跳過一列*/ i=i+2; /*跳過一行*/ printf(s=%dn，s); /*實現(xiàn)(3)小題功能的函數(shù)*/ void proc3(max

42、ix A) int i，s; if (m!=n) printf(mn); else s=0; for (i=0;im;i+) s=s+Aii; /*求第一條對角線之和*/ for (i=0;in;i+) s=s+An-i-1i; /*累加第二條對角線之和*/ printf(s=%dn，s); main() int m，n，i，j; maxix A; printf(m，n:); scanf(%d，%d，&m，&n); printf(元素值:n); for (i=0;im;i+) /*建立數(shù)組 A*/ for (j=0;j0) /*非 0 矩陣才做轉置*/ q=1; for (col=0;coln

43、;col+) /*按列轉置*/ for (p=1;pdata=x) printf(%dn,Get_Depth(T); /找到了值為x的結點,求其深度 exit 1; else if(T-lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子樹中繼續(xù)尋找 /Get_Sub_Depth int Get_Depth(Bitree T)/求子樹深度的遞歸算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); re

44、turn (mn?m:n)+1; /Get_Depth12、已知一棵完全二叉樹存于順序表sa中，sa.elem1.sa.last含結點值。試編寫算法由此順序存儲結構建立該二叉樹的二叉鏈表。Status CreateBitree_SqList(Bitree &T,SqList sa)/根據(jù)順序存儲結構建立二叉鏈表 Bitree ptrsa.last+1; /該數(shù)組儲存與sa中各結點對應的樹指針 if(!sa.last) T=NULL; /空樹 return; ptr1=(BTNode*)malloc(sizeof(BTNode); ptr1-data=sa.elem1; /建立樹根 T=ptr1

45、; for(i=2;idata=sa.elemi; j=i/2; /找到結點i的雙親j if(i-j*2) ptrj-rchild=ptri; /i是j的右孩子 else ptrj-lchild=ptri; /i是j的左孩子 return OK;/CreateBitree_SqList13、試編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計葉子的個數(shù)。int LeafCount_CSTree(CSTree T)/求孩子兄弟鏈表表示的樹T的葉子數(shù)目 if(!T-firstchild) return 1; /葉子結點 else count=0; for(child=T-firstchild;child;child