北科大數(shù)據(jù)結(jié)構(gòu)上機(jī)題代碼

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)題（C語(yǔ)言程序）1輸入數(shù)據(jù)（設(shè)為整型）建立單鏈表，并求相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)。例如輸入：2 6 4 7 3 0（0為結(jié)束符），建立：   所求結(jié)果=4 程序結(jié)構(gòu)： 類型說(shuō)明； 建表函數(shù)：Creatlist(L); 求值函數(shù)：Adjmax(L); main( ) 變量說(shuō)明； 調(diào)用Creatlist(L)建表；調(diào)用Adjmax(L)求值； 打印數(shù)據(jù)；釋放鏈表空間； Y 繼續(xù)？ N 停止 上機(jī)題1：#include<stdio.h>#include<stdlib.h>typedef int datatype; /設(shè)當(dāng)前數(shù)據(jù)元素

2、為整型 typedef struct node /節(jié)點(diǎn)類型 datatype data; /節(jié)點(diǎn)的數(shù)據(jù)域 struct node *next; /節(jié)點(diǎn)的后繼指針域 Linknode,*Link; /linknode為節(jié)點(diǎn)說(shuō)明符，link為節(jié)點(diǎn)指針說(shuō)明符 Link Createlist() /創(chuàng)建單鏈表的算法 int a,c;float b;Link H,P,r; /H,P,r分別為表頭，新節(jié)點(diǎn)和表尾節(jié)點(diǎn)指針 H=(Link)malloc(sizeof(Linknode); /建立頭節(jié)點(diǎn) r=H;doc=(fflush(stdin),scanf("%f",&b); /

3、判斷輸入的是否是整數(shù)a=(int)b;if(c!=1|a!=b|a>-216|a<216-1) printf("非法輸入!請(qǐng)重新輸入!n");while(c!=1|a!=b|a>-216|a<216-1);while(a!=0) P=(Link)malloc(sizeof(Linknode);/申請(qǐng)新節(jié)點(diǎn) P->data=a; /存入數(shù)據(jù) r->next=P; /新節(jié)點(diǎn)鏈入表尾 r=P;doc=(fflush(stdin),scanf("%f",&b); /判斷輸入的是否是整數(shù)a=(int)b;if(c!=1|

4、a!=b|a>-216|a<216-1) printf("非法輸入!請(qǐng)重新輸入!n");while(c!=1|a!=b|a>-216|a<216-1); r->next=NULL; /將尾節(jié)點(diǎn)的指針域置空 return(H); /返回已創(chuàng)建的頭節(jié)點(diǎn) Link Adjmax(Link H) /求鏈表中相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針的算法 Link p,p1,q;int i,j;p=p1=H->next;if(p1=NULL) return(p1); /表空返回 q=p->next;if(q=NULL) return(p

5、1); /表長(zhǎng)=1時(shí)返回 i=p->data+q->data; /相鄰兩節(jié)點(diǎn)data值之和 while(q->next)p=q;q=q->next; /取下一對(duì)相鄰節(jié)點(diǎn)的指針 j=p->data+q->data;if(j>i)p1=p;i=j; /取和為最大的第一節(jié)點(diǎn)指針 return (p1);void main() /主函數(shù) Link A,B,p,q;int a,b;doprintf("請(qǐng)輸入一組整數(shù)(以0為結(jié)束符，數(shù)之間回車):n");p=A=Createlist(); /創(chuàng)建新鏈表 B=Adjmax(A); /求鏈表中相鄰兩

6、節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針 a=(int)(B->data); /取第一節(jié)點(diǎn)的data值 printf("第一節(jié)點(diǎn)的data值為:%dn",a); while(p->next) /釋放鏈表空間 q=p; p=p->next; free(q); free(p); printf("是否繼續(xù)輸入下一組整數(shù):是:1,否:0n"); scanf("%d",&b); while(b); 上機(jī)題2. 實(shí)現(xiàn)算術(shù)表達(dá)式求值程序（棧的運(yùn)用）。 設(shè)操作數(shù)：0，1，2，8，9（可擴(kuò)充）； 運(yùn)算符：+，*，/，（，），#

7、（#號(hào)為結(jié)束）。 輸入中綴表達(dá)式，如：5+(42)*3 #，將其轉(zhuǎn)換成后綴表達(dá)式：5423*+#，然后計(jì)算，本例結(jié)果為11。程序結(jié)構(gòu)： 類型說(shuō)明；兩套：Clearstack(S)、Emptystack(S)、 Getstop(S) 、 Push(S)、Pop(S)； 中綴到后綴轉(zhuǎn)換的函數(shù)：Mid-post(En，Bn)； 后綴表達(dá)式求值的函數(shù)：Postcount(Bn)； main（） 變量說(shuō)明； 輸入中綴表達(dá)式，存入En； 調(diào)用Mid-post(E，B)； 調(diào)用Postcount(B)； 打印表達(dá)式結(jié)果； Y 繼續(xù)？ N 停止 上機(jī)題2：#include<stdio.h>#inc

8、lude<stdlib.h>#include<string.h>typedef struct node char data;struct node *next;snode,*slink;typedef struct node1 int data;struct node1 *next;snode1,*slink1;void Clearstack(slink s) /置?？?s=NULL;int Emptystack(slink s) /判斷棧是否為空if(s=NULL) return(1); /?？辗祷?else return(0); /棧非空返回0 char Getst

9、op(slink s) /取棧頂元素if(s!=NULL) return (s->data); return (0); void Push(slink*s,char x) /元素x進(jìn)棧slink p;p=(slink)malloc(sizeof(snode); /生成進(jìn)棧p節(jié)點(diǎn) p->data=x; /存入新元素 p->next=*s; /p節(jié)點(diǎn)作為新的棧頂鏈入 *s=p;char Pop(slink*s) /出棧char x;slink p;if(Emptystack(*s) return (-1); /?？?，返回-1 elsex=(*s)->data;p=*s;*s

10、=(*s)->next;free(p);return (x); /成功 void Push1(slink1*s,int x) /元素x進(jìn)棧slink1 p;p=(slink1)malloc(sizeof(snode1); /生成進(jìn)棧p節(jié)點(diǎn) p->data=x; /存入新元素 p->next=*s; /p節(jié)點(diǎn)作為新的棧頂鏈入 *s=p;int Pop1(slink1*s) /出棧int x;slink1 p;if(Emptystack1(*s) return (-1); /?？眨祷?1 elsex=(*s)->data;p=*s;*s=(*s)->next;fre

11、e(p);return (x); /成功 int Emptystack1(slink1 s) /判斷棧是否為空if(s=NULL) return(1); /棧空返回1else return(0); /棧非空返回0 void Clearstack1(slink1 s) /置?？?s=NULL;int Getstop1(slink1 s) /取棧頂元素if(s!=NULL) return (s->data); return (0); int Precede(char x,char y) int a,b;switch(x)case '#':/case '（':c

12、ase '(':a=0;break;case '+': case '-':a=1;break; case '*': case '/':a=2;break; switch(y)case '+':case '-':b=1;break;case '*':case '/':b=2;break; /case '（':case '(':b=3;break;if(a>=b) return (1);else return (0);

13、 void Mid_post(char E,char B) /中綴表達(dá)式B到后綴表達(dá)式E的轉(zhuǎn)換 int i=0,j=0;char x; int a;slink s=NULL; /置空棧 Clearstack(s);Push(&s,'#'); /結(jié)束符入棧 dox=Bi+; /掃描當(dāng)前表達(dá)式分量x switch(x) case ' ':break; case '#':while(!Emptystack(s) Ej+=' ' /棧非空時(shí) Ej+=Pop(&s);break; case ')':while

14、(Getstop(s)!='(') Ej+=' ' Ej+=Pop(&s); /反復(fù)出棧直到遇到'(' Pop(&s); /退掉'(' break;case '+':case '-':case '*':case '/':case '(':while(Precede(Getstop(s),x) /棧頂運(yùn)算符（Q1）與x比較 Ej+=' ' Ej+=Pop(&s);/Ej+=' 'Push(&

15、s,x); /Q1<x時(shí)，x進(jìn)棧Ej+=' ' break; default:Ej+=x;while(x!='#'); Ej='0'Clearstack(s);int Ecount(char E) /后綴表達(dá)式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL;while(Ei!='#')x=Ei;switch(x)case ' ':break;case '+':b=Pop1(&s);a=Pop1(&s);z=

16、a+b;Push1(&s,z);break;case '-':b=Pop1(&s);a=Pop1(&s);z=a-b;Push1(&s,z);break;case '*':b=Pop1(&s);a=Pop1(&s);z=a*b;Push1(&s,z);break;case '/':b=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break;default: g=0;g1=0; while(Ei!=' ') g1=Ei-&

17、#39;0' g=g*10+g1; i+; Push1(&s,g); i+;if(!Emptystack1(s) return(Getstop1(s);Clearstack1(s);int pd(char B) int i=0,c,j,k; c=strlen(B); while(Bi!='#') switch(Bi) case ' ':break; case '0': case '1': case '2': case '3': case '4': case '

18、5': case '6': case '7': case '8': case '9': j=i+1; if(Bj=' ') while(Bj=' ') j+; switch(Bj) case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8&#

19、39;: case '9':printf("1非法輸入!請(qǐng)重新輸入!n");return(0);break; break; case '+': case '-': case '*': case '/': j=i-1; while(Bj=' ') j-;switch(Bj)case '+':case '-':case '*':case '/':case '(':case '#':prin

20、tf("2非法輸入!請(qǐng)重新輸入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk)case '+':case '-':case '*':case '/':case ')':case '#':printf("3非法輸入!請(qǐng)重新輸入!n");return(0);break; break;case '(': j=i-1; while(Bj=' ') j-;s

21、witch(Bj)case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':case '#':case ')':printf("4非法輸入!請(qǐng)重新輸入!n");return(0);break; k=i+1; while(Bk=' '

22、) k+; switch(Bk)case '+':case '-':case '*':case '/':case '#':printf("5非法輸入!請(qǐng)重新輸入!n");return(0);break; break;case ')': j=i-1; while(Bj=' ') j-; switch(Bj) case '(':printf("6非法輸入!請(qǐng)重新輸入!n");return(0);break; k=i+1; while

23、(Bk=' ') k+; switch(Bk)case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':printf("7非法輸入!請(qǐng)重新輸入!n");return(0);break; break; case '0':break; default:

24、printf("8非法輸入!請(qǐng)重新輸入!n");return(0); i+; if(B0='#') printf("表達(dá)式為空!請(qǐng)重新輸入!n");return(0); else if (Bc-1!='#') printf("9非法輸入!請(qǐng)重新輸入!n");return(0); void main() int a,b,c,d;char B100,E100;dodo printf("請(qǐng)輸入中綴表達(dá)式:n");B100=fflush(stdin); gets(B); while(B0=&

25、#39;0') B100=fflush(stdin); gets(B); b=pd(B); while(b=0); Mid_post(E,B); printf("后綴表達(dá)式為:n"); printf("%sn",E); a=Ecount(E); printf("結(jié)果=%dn",a); printf("是否繼續(xù)?是:1否:0n"); scanf("%d",&c); while(c=1); 上機(jī)題3. 實(shí)現(xiàn)鏈?zhǔn)疥?duì)列運(yùn)算程序（隊(duì)列的運(yùn)用）。 程序結(jié)構(gòu)： 類型說(shuō)明； Clearqueue

26、(q)、Emptyqueue(q)、Enqueue(q)、Dequeue(q)； main（） 變量說(shuō)明；    上機(jī)題3：#include <stdio.h>#include <string.h>#include<stdlib.h>typedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空隊(duì)列q->front-

27、>next=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /創(chuàng)建隊(duì)列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判斷隊(duì)列是否為空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素進(jìn)隊(duì)Qlink p

28、;p=(Qlink)malloc(sizeof(Qnode);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;char Dequeue(linkqueue *q) /元素出隊(duì)Qlink p;if(Emptyqueue(q) return(NULL);elsep=q->front;q->front=p->next;free(p);return(q->front->data);void main()char a,b;int c;linkqueue q;Creatqueue(&q);

29、doa=getchar();switch (a)case '0': if(Emptyqueue(&q) printf("隊(duì)列為空!n"); printf("請(qǐng)繼續(xù)輸入!n");c=1; else b=Dequeue(&q); printf("%c出隊(duì)n",b); printf("請(qǐng)繼續(xù)輸入!n");break; case '': if(Emptyqueue(&q) printf("隊(duì)列為空!n");return; elseprintf(&q

30、uot;全部元素出隊(duì):n"); while(Emptyqueue(&q)!=1) b=Dequeue(&q); printf("%c",b); printf("n"); return;break; case 'n':break; default :Enqueue(&q,a);c=1;break;while(c);上機(jī)題4設(shè)電文字符集D及各字符出現(xiàn)的概率F如下： D=a，b，c，d，e，f，g，h（字符數(shù)n=8） F=5，29，7，8，14，23，3，11(%)編寫完成下列功能的程序：構(gòu)造關(guān)于F的Huffm

31、an樹；求出并打印D總各字符的Huffman編碼。程序結(jié)構(gòu)：類型說(shuō)明；構(gòu)造Huffman樹的函數(shù)：Huffman_tree(Hm+1)；求Huffman編碼的函數(shù)：Huffman_code(coden+1)；main() 變量說(shuō)明； 輸入字符集D及頻率F； 調(diào)用Huffman_tree(H)； 調(diào)用Huffman_code(code)； 打印編碼； Y 繼續(xù)？ N停止 上機(jī)題4：#include<stdio.h>#define n 20 #define m 2*n-1 /H樹的節(jié)點(diǎn)數(shù)#define max 99typedef structint wi;char data;int p

32、arent,Lchild,Rchild;huffm;void Huffman_tree(huffm HT,int F,int p,int q)int i,j,p1,p2;int w,s1,s2;for(i=1;i<=q;i+) /初始化HTi.wi=0;HTi.parent=0;HTi.Lchild=HTi.Rchild=0;for(i=1;i<=p;i+)HTi.wi=Fi-1;for(i=p+1;i<=q;i+)p1=p2=0;s1=s2=max;for(j=1;j<=i-1;j+)if(HTj.parent=0)if(HTj.wi<s1)s2=s1;s1=H

33、Tj.wi;p2=p1;p1=j;else if(HTj.wi<s2)s2=HTj.wi;p2=j;HTp1.parent=HTp2.parent=i;HTi.Lchild=p1;HTi.Rchild=p2;HTi.wi=HTp1.wi+HTp2.wi;typedef structchar bitsn+1;int start;char ch;ctype;void Huffman_code(ctype code,huffm HT,char D,int F,int p,int q)int i,j,a,s;ctype md;for(i=1;i<=p;i+) codei.ch=Di-1;H

34、Ti.data=codei.ch;for(i=1;i<=p;i+)md.ch=codei.ch;md.start=p+1;s=i;a=HTi.parent;while(a!=0)md.start-;if(HTa.Lchild=s)md.bitsmd.start='0'elsemd.bitsmd.start='1's=a;a=HTa.parent;codei=md;void main()int F30;int i,j,k,p0=0,p1=0,q,d,f,p,i1,w;char D50;huffm HTm+1;ctype coden+1;dodododo p0

35、=0;D50=fflush(stdin); printf("請(qǐng)輸入字符集D!(最多20個(gè)字符,以#為結(jié)束符)n"); scanf("%s",&D); for(k=0;k<50;k+) if(Dk!='0') +p0;p=p0-1; else break; /printf("%d",p); if(D0='#') printf("非法輸入!n"); d=1;D50=fflush(stdin); else if(Dp!='#') printf("非法

36、輸入!n"); d=1;D50=fflush(stdin); else if(p>n) printf("超出范圍!n"); d=1; D50=fflush(stdin); else d=0;while(d); printf("請(qǐng)輸入各字符出現(xiàn)的概率集F!(每個(gè)數(shù)直接要回車!以-1為結(jié)束符)n"); for(i=0;i<50;i+) / scanf("%d",&Fi); w=(fflush(stdin),scanf("%d",&Fi); if(w!=1) printf("

37、;非法輸入!n"); d=1;break; if(Fi=-1) d=0;break; /if(Fi=-1) / break;while(d);p1=0;i1=0;for(k=0;k<50;k+) if(Fk!=-1) +p1; else break; if(F0=-1) printf("非法輸入!n"); d=1; else if(Fp1!=-1) printf("非法輸入!n");d=1; else if(p!=p1)printf("D的元素個(gè)數(shù)與F的元素個(gè)數(shù)不等!n請(qǐng)重新輸入!n");d=1;/for(i=0;i&

38、lt;=p1;i+)/printf("%d ",Fi);while(d); q=2*p-1; /huffm HTq+1; Huffman_tree(HT,F,p,q); /*for(i=1;i<=q;i+) printf("%dt",HTi.wi); printf("%dt",HTi.parent); printf("%dt",HTi.Lchild); printf("%dt",HTi.Rchild); printf("n"); */ printf("打印編碼

39、:n"); /ctype codep+1; Huffman_code(code,HT,D,F,p,q); /printf("%s",D); printf("字符tbitsn"); for(i=1;i<=p;i+) printf("%ct",codei.ch); for(j=codei.start;j<=p;j+) printf("%c",codei.bitsj); printf("n"); printf("是否繼續(xù)?是:1 否:0n"); scanf(&

40、quot;%d",&f);while(f);上機(jī)題5：設(shè)英文句子：“everyone round you can hear you when you speak.”，試編寫完成下面任務(wù)的程序。（1）依次讀入句中各單詞，構(gòu)造一棵二叉排序樹；即：（2）按LDR遍歷此二叉排序樹。LDR： can everyone hear round speak when you（有序）上機(jī)題5：/*#include <stdio.h>#include <string.h>#include<stdlib.h>#define max 200 typedef str

41、uct nodechar key20;int w;Retype;typedef struct BsnodeRetype data;struct Bsnode *Lchild,*Rchild;BSN,*BSP;BSP BSTinsert(BSP T,BSP S)BSP q,p;if(T=NULL) return(S);p=T;q=NULL;while(p)q=p;if(strcmp(S->data.key,p->data.key)=0)free(S);return(T);if(strcmp(S->data.key,p->data.key)<0) p=p->Lc

42、hild;else p=p->Rchild; if(strcmp(S->data.key,q->data.key)<0) q->Lchild=S;else q->Rchild=S;return(T);BSP CreateBst(char A)int i,j,k=0,p=0;char b15,B150;BSP T,S;doif(A0='0') gets(B);A=B;while(A0='0');T=NULL;dowhile(Ak=' ') k+; /while(Ak!=' ')/ / p=0; /

43、switch(Ak)/case ' ':break;/default:bp+=Ak;/ bp+=Ak;/k+;/printf("sdfjkl");p=0;while(Ak!=' ')switch(Ak)case ' ':break;default:bp+=Ak;k+;if(bp-1='.') bp-1='0'bp='0' S=(BSP)malloc(sizeof(BSN);for(i=0;i<20;i+)if(bi!='0') S->data.keyi

44、=bi;S->data.w=i;else break; printf("%sn",b);S->Lchild=S->Rchild=NULL;/printf("dfd");T=BSTinsert(T,S);/scanf("%s",&key);/while(bp-1='.'); return(T);void visit(BSP T)int i; for(i=0;i<=T->data.w;i+) printf("%c",T->data.keyi); / else

45、break;printf(" ");void inorder(BSP T)int i;if(T)inorder(T->Lchild);visit(T);inorder(T->Rchild); /printf("n");void main()int a; char A150;do a=0;printf("請(qǐng)輸入一句英文!(以.結(jié)束)n");gets(A);do/scanf("%s",&key);if(A0='.') printf("句子為空!請(qǐng)重新輸入!n");gets(A);while(A0='.');BSP T;T=CreateBst(A);printf("LDR遍歷輸出:n");inorder(T);printf(&q