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

本文格式為Word版，下載可任意編輯——北科大數(shù)據(jù)結(jié)構(gòu)上機(jī)題代碼《數(shù)據(jù)結(jié)構(gòu)》上機(jī)題（C語(yǔ)言程序）

1．輸入數(shù)據(jù)（設(shè)為整型）建立單鏈表，并求相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)。例如輸入：264730（0為終止符），建立：

所求結(jié)果=4

程序結(jié)構(gòu)：類(lèi)型說(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#include

typedefintdatatype;//設(shè)當(dāng)前數(shù)據(jù)元素為整型typedefstructnode//節(jié)點(diǎn)類(lèi)型{

datatypedata;//節(jié)點(diǎn)的數(shù)據(jù)域structnode*next;//節(jié)點(diǎn)的后繼指針域

}Linknode,*Link;//linknode為節(jié)點(diǎn)說(shuō)明符，link為節(jié)點(diǎn)指針說(shuō)明符

LinkCreatelist()//創(chuàng)立單鏈表的算法{inta,c;floatb;LinkH,P,r;//H,P,r分別為表頭，新節(jié)點(diǎn)和表尾節(jié)點(diǎn)指針H=(Link)malloc(sizeof(Linknode));//建立頭節(jié)點(diǎn)r=H;do{c=(fflush(stdin),scanf(\//判斷輸入的是否是整數(shù)a=(int)b;if(c!=1||a!=b||a>-2^16||a-2^16||adata=a;//存入數(shù)據(jù)

r->next=P;//新節(jié)點(diǎn)鏈入表尾r=P;do{c=(fflush(stdin),scanf(\//判斷輸入的是否是整數(shù)a=(int)b;if(c!=1||a!=b||a>-2^16||a-2^16||anext=NULL;//將尾節(jié)點(diǎn)的指針域置空return(H);//返回已創(chuàng)立的頭節(jié)點(diǎn)}

LinkAdjmax(LinkH)//求鏈表中相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針的算法{Linkp,p1,q;inti,j;p=p1=H->next;if(p1==NULL)return(p1);//表空返回q=p->next;if(q==NULL)return(p1);//表長(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);}

voidmain()//主函數(shù){LinkA,B,p,q;inta,b;do{printf(\請(qǐng)輸入一組整數(shù)(以0為終止符，數(shù)之間回車(chē)):\\n\p=A=Createlist();//創(chuàng)立新鏈表

B=Adjmax(A);//求鏈表中相鄰兩節(jié)點(diǎn)data值之和為最大的第一節(jié)點(diǎn)的指針

a=(int)(B->data);//取第一節(jié)點(diǎn)的data值printf(\第一節(jié)點(diǎn)的data值為:%d\\n\

while(p->next)//釋放鏈表空間{q=p;p=p->next;free(q);}

free(p);

printf(\是否繼續(xù)輸入下一組整數(shù):是:1,否:0\\n\scanf(\}while(b);}

上機(jī)題2.實(shí)現(xiàn)算術(shù)表達(dá)式求值程序（棧的運(yùn)用）。設(shè)操作數(shù)：0，1，2，??，8，9（可擴(kuò)展）；運(yùn)算符：+，—，*，/，（，），#（#號(hào)為終止）。

輸入中綴表達(dá)式，如：5+(4—2)*3#，將其轉(zhuǎn)換成后綴表達(dá)式：542—3*+#，然后計(jì)算，本例結(jié)果為11。程序結(jié)構(gòu)：類(lèi)型說(shuō)明；兩套：Clearstack(S)、Emptystack(S)、Getstop(S)、Push(S)、Pop(S)；中綴到后綴轉(zhuǎn)換的函數(shù)：Mid-post(E[n]，B[n])；后綴表達(dá)式求值的函數(shù)：Postcount(B[n])；main（）{變量說(shuō)明；輸入中綴表達(dá)式，存入E[n]；調(diào)用Mid-post(E，B)；調(diào)用Postcount(B)；打印表達(dá)式結(jié)果；Y繼續(xù)？N中止}

上機(jī)題2：

#include#include#includetypedefstructnode{chardata;structnode*next;}snode,*slink;

typedefstructnode1{intdata;structnode1*next;}snode1,*slink1;

voidClearstack(slinks)//置棧空{(diào)s=NULL;}

intEmptystack(slinks)//判斷棧是否為空{(diào)if(s==NULL)return(1);//?？辗祷?elsereturn(0);//棧非空返回0}

charGetstop(slinks)//取棧頂元素{if(s!=NULL)return(s->data);return(0);}

voidPush(slink*s,charx)//元素x進(jìn)棧{slinkp;p=(slink)malloc(sizeof(snode));//生成進(jìn)棧p節(jié)點(diǎn)p->data=x;//存入新元素p->next=*s;//p節(jié)點(diǎn)作為新的棧頂鏈入*s=p;}

charPop(slink*s)//出棧{charx;slinkp;if(Emptystack(*s))return(-1);//?？?，返回-1else{x=(*s)->data;p=*s;*s=(*s)->next;free(p);return(x);//成功}}

voidPush1(slink1*s,intx)//元素x進(jìn)棧{slink1p;

p=(slink1)malloc(sizeof(snode1));//生成進(jìn)棧p節(jié)點(diǎn)p->data=x;//存入新元素p->next=*s;//p節(jié)點(diǎn)作為新的棧頂鏈入*s=p;}

intPop1(slink1*s)//出棧{intx;slink1p;if(Emptystack1(*s))return(-1);//?？眨祷?1else{x=(*s)->data;p=*s;*s=(*s)->next;free(p);return(x);//成功}}

intEmptystack1(slink1s)//判斷棧是否為空{(diào)if(s==NULL)return(1);//?？辗祷?elsereturn(0);//棧非空返回0}

voidClearstack1(slink1s)//置?？調(diào)s=NULL;}

intGetstop1(slink1s)//取棧頂元素{if(s!=NULL)return(s->data);return(0);}

intPrecede(charx,chary){inta,b;switch(x){case'#'://case'（':case'(':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);elsereturn(0);}

voidMid_post(charE[],charB[])//中綴表達(dá)式B到后綴表達(dá)式E的轉(zhuǎn)換{inti=0,j=0;charx;inta;slinks=NULL;//置空棧Clearstack(s);Push(//終止符入棧do{x=B[i++];//掃描當(dāng)前表達(dá)式分量xswitch(x){case'':break;case'#':{while(!Emptystack(s)){E[j++]='';//棧非空時(shí)E[j++]=Pop(}}break;case')':{while(Getstop(s)!='('){E[j++]='';E[j++]=Pop(}//反復(fù)出棧直到遇到'('Pop(//退掉'('

}break;case'+':case'-':case'*':case'/':case'(':{while(Precede(Getstop(s),x))//棧頂運(yùn)算符（Q1）與x比較{E[j++]='';E[j++]=Pop(}//E[j++]='';Push(//Q1

}break;

case'\\0':break;

default:printf(\非法輸入!請(qǐng)重新輸入!\\n\}i++;}

if(B[0]=='#'){

printf(\表達(dá)式為空!請(qǐng)重新輸入!\\n\}

elseif(B[c-1]!='#'){

printf(\非法輸入!請(qǐng)重新輸入!\\n\}}

voidmain(){

inta,b,c,d;charB[100],E[100];do{do{printf(\請(qǐng)輸入中綴表達(dá)式:\\n\B[100]=fflush(stdin);gets(B);while(B[0]=='\\0'){B[100]=fflush(stdin);gets(B);}b=pd(B);}while(b==0);Mid_post(E,B);printf(\后綴表達(dá)式為:\\n\printf(\a=Ecount(E);printf(\結(jié)果=%d\\n\printf(\是否繼續(xù)?是:1否:0\\n\scanf(\}while(c==1);}

上機(jī)題3.實(shí)現(xiàn)鏈?zhǔn)疥?duì)列運(yùn)算程序（隊(duì)列的運(yùn)用）。程序結(jié)構(gòu)：

類(lèi)型說(shuō)明；Clearqueue(q)、Emptyqueue(q)、Enqueue(q)、Dequeue(q)；main（）{變量說(shuō)明；

上機(jī)題3：

#include#include#includetypedefstructnode{chardata;structnode*next;}Qnode,*Qlink;typedefstruct{Qnode*front,*rear;}linkqueue;

voidClearqueue(linkqueue*q)//清空隊(duì)列{q->front->next=NULL;q->rear=q->front;}

voidCreatqueue(linkqueue*q)//創(chuàng)立隊(duì)列{q->front=(Qlink)malloc(sizeof(Qnode));q->front->next=NULL;q->rear=q->front;

}

}

intEmptyqueue(linkqueue*q)//判斷隊(duì)列是否為空{(diào)if(q->front==q->rear)return(1);elsereturn(0);}

voidEnqueue(linkqueue*q,chare)//元素進(jìn)隊(duì){Qlinkp;p=(Qlink)malloc(sizeof(Qnode));p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;}

charDequeue(linkqueue*q)//元素出隊(duì){Qlinkp;if(Emptyqueue(q))return(NULL);else{p=q->front;q->front=p->next;free(p);return(q->front->data);}}

voidmain(){chara,b;intc;linkqueueq;Creatqueue(do{a=getchar();switch(a){case'0':{if(Emptyqueue(printf(\出隊(duì)\\n\printf(\請(qǐng)繼續(xù)輸入!\\n\}}break;case'@':{if(Emptyqueue(printf(\}printf(\return;}}break;case'\\n':break;default:{Enqueue(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}(%)編寫(xiě)完成以下功能的程序：①構(gòu)造關(guān)于F的Huffman樹(shù)；②求出并打印D總各字符的Huffman編碼。程序結(jié)構(gòu)：類(lèi)型說(shuō)明；構(gòu)造Huffman樹(shù)的函數(shù)：Huffman_tree(H[m+1])；求Huffman編碼的函數(shù)：Huffman_code(code[n+1])；main(){變量說(shuō)明；輸入字符集D及頻率F；調(diào)用Huffman_tree(H)；調(diào)用Huffman_code(code)；打印編碼；

Y繼續(xù)？N中止}

上機(jī)題4：

#include#definen20

#definem2*n-1//H樹(shù)的節(jié)點(diǎn)數(shù)#definemax99typedefstruct{intwi;chardata;intparent,Lchild,Rchild;}huffm;

voidHuffman_tree(huffmHT[],intF[],intp,intq){inti,j,p1,p2;intw,s1,s2;for(i=1;idata.w;i++)printf(\//elsebreak;printf(\}

voidinorder(BSPT){inti;if(T){inorder(T->Lchild);visit(T);inorder(T->Rchild);}//printf(\}

voidmain(){inta;

charA[150];do{a=0;printf(\請(qǐng)輸入一句英文!(以.終止)\\n\gets(A);do{//scanf(\if(A[0]=='.')printf(\句子為空!請(qǐng)重新輸入!\\n\gets(A);}while(A[0]=='.');BSPT;T=CreateBst(A);printf(\遍歷輸出:\\n\inorder(T);printf(\printf(\是否繼續(xù)?是:1否:0\scanf(\}while(a);

}*/

/*#includedata.key,p->data.key)==0){free(S);return(T);}