千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數據結構經典題目c語言代碼《數據結構》課程設計題目

(程序實現采納C語言)

題目1：猴子選王（學時：3）

一堆猴子都有編號，編號是1，2，3...m，這群猴子（m個）根據1-m的挨次圍坐一圈，從第1開頭數，每數到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。

要求：m及n要求從鍵盤輸入，存儲方式采納向量及鏈表兩種方式實現該問題求解。

//鏈表

#include

#include

//鏈表節點

typedefstruct_RingNode

{

intpos;

struct_RingNode*next;

}RingNode,*RingNodePtr;

//創建約瑟夫環，pHead:鏈表頭指針，count:鏈表元素個數

voidCreateRing(RingNodePtrpHead,intcount)

{

RingNodePtrpCurr=NULL,pPrev=NULL;

inti=1;

pPrev=pHead;

while(--count>0)

{

pCurr=(RingNodePtr)malloc(sizeof(RingNode));

i++;

pCurr->pos=i;

pPrev->next=pCurr;

pPrev=pCurr;

}

pCurr->next=pHead;//構成環狀鏈表

}

voidKickFromRing(RingNodePtrpHead,intn)

{

RingNodePtrpCurr,pPrev;

inti=1;//計數

pCurr=pPrev=pHead;

while(pCurr!=NULL)

{

if(i==n)

{

//踢出環

printf("\n%d",pCurr->pos);//顯示出圈循序

pPrev->next=pCurr->next;

free(pCurr);

pCurr=pPrev->next;

i=1;

}

pPrev=pCurr;

pCurr=pCurr->next;

if(pPrev==pCurr)

{

//最后一個

printf("\nKingis%d",pCurr->pos);//顯示出圈循序

free(pCurr);

break;

}

i++;

}

}

intmain()

{

intn=0,m=0;

RingNodePtrpHead=NULL;

printf("M(personcount)=");

scanf("%d",

printf("N(outnumber)=");

scanf("%d",

if(mpos=1;

pHead->next=NULL;

CreateRing(pHead,m);

//開頭出圈

printf("\nKickOrder:");

KickFromRing(pHead,n);

printf("\n");

system("pause");

return0;

}

//數組做：

#include

#include

#include

voidSelectKing(intMonkeyNum,intCallNum);

voidmain()

{

intMonkeyNum;

intCallNum;

/*輸入猴子的個數*/

printf("MonkeyNum=");

scanf("%d",

/*輸入M的值*/

printf("CallNum=");

scanf("%d",

SelectKing(MonkeyNum,CallNum);

}

voidSelectKing(intMonkeyNum,intCallNum)

{

int*Monkeys;//申請一個數組，表示全部的猴子；

intcounter=0;//計數，當計數為猴子個數時表示選到最后一個猴子了；

intposition=0;//位置，數組的下標，輪番遍歷數組舉行報數；

inttoken=0;//令牌，將報數時數到M的猴子砍掉；

//申請猴子個數大小的數組，把桌子擺上。

Monkeys=(int*)malloc(sizeof(int)*MonkeyNum);

if(NULL==Monkeys)

{

printf("Somanymonkeys,systemerror.\n");

return;

}

//將數組的全部內容初始化為0，被砍掉的猴子設置為1

memset(Monkeys,0,sizeof(int)*MonkeyNum);

//循環，直到選中大王

while(counter!=MonkeyNum)

{

//假如這個位置的猴子之前沒有砍掉，那么報數有效

if(Monkeys[position]==0)

{

token++;//勝利報數一個，令牌+1，繼續報數直到等于M

//假如報數到M，那么將這個猴子砍去

if(token==CallNum)

{

Monkeys[position]=1;//設置為1，表示砍去

counter++;//計數增強

token=0;//設置為0，下次重新報數

//假如是最后一個猴子，把它的位置打印，這個就是大王了

if(counter==MonkeyNum)

{

printf("Thekingisthe%dmonkey.\n",position+1);

}

}

}

//下一個猴子報數

position=(position+1)%MonkeyNum;

}

//釋放內存，開始為全部猴子創建的桌子

free(Monkeys);

return;

}

題目2：字符逆轉（學時：3）

從鍵盤讀入一個字符串，把它存入一個鏈表（每個結點存儲1個字符），并按相反的次序將字符串輸出到顯示屏。

#include

#include

structnode

{

structnode*prev;

charc;

structnode*next;

};

structnode*input(structnode*top);

intmain(void)

{

structnodeT,*top=

T.prev=NULL;

T.next=NULL;

T.c='\0';

bottom=input(top);

p=bottom->prev;

while(p!=NULL)

{

printf("%c",p->c);

p=p->prev;

}

return0;

}

structnode*input(structnode*top)

{

structnode*t;

charx;

while((x=getchar())!='\n')

{

top->c=x;

t=(structnode*)malloc(sizeof(structnode));

top->next=t;

t->prev=top;

t->next=NULL;

t->c='\0';

top=top->next;

}

returntop;

}

題目3：工資核算（學時：3）

設有一個單位的人員工資有如下信息：name、department、basepay、allowance、total。現從鍵盤輸入一組人員工資數據并將它們存儲到名為paydata的文件中；再從paydata取出工資數據并給每個人的basepay增強100元，增強后將工資數據顯示于屏幕(每行1人)。

#include

#include

#defineSIZE2

#defineLENTHsizeof(structstuff)

structstuff

{

charname[100];

chardepartment[100];

intbasepay;

intallowance;

inttotal;

}stuff[SIZE];

main()

{

FILE*fp;

inti;

printf("Pleaseenternamedepartmentbasepayallowance：\n");

for(i=0;i

voidmain()

{

inta[7],b[5],c[6],d[7];

inti,j,k,t,m;

printf("\nPleaseenter7numbersofA:");

for(i=0;ia[i+1])

{t=a[i];a[i]=a[i+1];a[i+1]=t;}

printf("thesortednumbers：\n");

for(i=0;ib[i+1])

{t=b[i];b[i]=b[i+1];b[i+1]=t;}

printf("thesortednumbers:\n");

for(i=0;ic[i+1])

{t=c[i];c[i]=c[i+1];c[i+1]=t;}

printf("thesortednumbers：\n");

for(i=0;i

structPolynode

{

intcoef;

intexp;

Polynode*next;

}Polynode,*Polylist;

voidPolycreate(Polylisthead)

{

Polynode*rear,*s;

intc,e;

rear=head;printf("請輸入多項式的系數項和指數項");

scanf("%d,%d",

while(c!=0)

{

s=(Polynode*)malloc(sizeof(Polynode));

s->coef=c;

s->exp=e;

rear->next=s;

rear=s;

scanf("%d,%d",

}

rear->next=NULL;

}

voidPolyadd(Polylistpolya,Polylistpolyb)

{

Polynode*p,*q,*tail,*temp;

intsum;

p=polya->next;

q=polyb->next;

tail=polya;

while(p!=NULL

tail=p;

p=p->next;

}

elseif(p->exp=q->exp)

{

sum=p->coef+q->coef;

if(sum!=0)

{

p->coef=sum;

tail->next=p;

tail=p;

p=p->next;

temp=q;

q=q->next;

free(temp);

}

else

{

temp=p;

p=p->next;

free(temp);

q=q->next;

free(temp);

}

}

else

{

tail->next=q;

tail=q;

q=q->next;

}

}

if(p!=NULL)

tail->next=p;

else

tail->next=q;

}

voidPolysubstract(Polylistpolya,Polylistpolyb){

Polylisth=polyb;

Polylistp=pb->next;

Polylistpd;

while(p)

{p->coef*=-1;

p=p->next;

}

pd=Polyadd(pa,h);

for(p=h->next;p;p=p->next)

p->coef*=-1;

returnpd；

}

voidPrintPolyn(PolynP)

voidprintfPolyn(Polynode*head){

Polynode*p=head->next;

while(p)

{printf("%dx^%d",p->coef,p->exp);if(p->next)

printf("+");p=p->next;}

}

intmain()

{

Polynode*La,Lb;

La=Polycreate();

Lb=Polycreate();

PrintPolyn(La);

printf("/n");

PrintPolyn(Lb);

printf("/n");

Polyadd(polya,polyb);

printPolyn(polya);

return0;

}

題目6：床位分配（學時：6）

某客店有N個等級的房間，第k級客房有A（k）個，每個房間有B（k）個單人床，以菜單調用方式設計為單身旅客分配床位以及離店時收回床位的程序。要求分配勝利時，印出旅客姓名、年齡、性別、到達日期、客房等級、房間號及床位號；分配不勝利時，允許更改房間等級，若不更改等級，印出“滿客”提醒。

#include

#include

#include

#include

#defineN3

typedefstructRoom

{

introomlevel;

introomnum;

intbednum;

intpeoplenum;

intbed[N];

intsex;

charname[10];

structRoom*next;

}Room;

Room*creat(introomlevel,introom[],intbed[])

{

Room*head,*p,*q;

inti=1,j,h,num=1;

head=(Room*)malloc(sizeof(Room));

head->peoplenum=0;

q=head;

while(iroomlevel=i;p->roomnum=num++;p->peoplenum=0;

p->sex=-1;

for(h=0;hbed[h]=0;

q->next=p;

q=p;

}

i++;

}

p->next=NULL;

return(head);

}

voidInit(Room*head)

{

Room*p;

inti;

p=head;

while(p!=NULL)

{

p->peoplenum=0;

p->sex=-1;

for(i=0;ibed[i]=0;

p=p->next;

}

printf("\n\n操作勝利\n");}

voidGetin(Room*head)

{

Room*p;

inti,s,lev,age;

charname[10];

intnumber=0;

intbednumber=0;

printf("\n\n歡迎使用訂房系統\n\n");

printf("請輸入性別（1為男，2為女）：");

scanf("%d",

printf("\n\n請輸入想入住的房間等級：");

scanf("%d",

p=head->next;

while(p!=NULL)

{

if((p->roomlevel==lev)ibed[i]==0)

{

number=p->roomnum;

bednumber=i+1;

p->bed[i]=1;

p->sex=s;

p->peoplenum++;

break;

}

if(number!=0)break;

}

p=p->next;

}

if(number==0

else

{

head->peoplenum++;

printf("\n訂單已下，請輸入客人信息:\n");

printf("名字:\n");scanf("%s",name);

printf("年齡:\n");scanf("%d",

printf("您的訂單3:\n");

printf("名字年齡性別到達時光房間等級房間號床位號\n");

if(s==1)

printf("%s%dmale11-19%d%d%d\n",name,age,p->roomlevel,p->roomnum,bednumber);

else

printf("%s%dformale11-19%d%d%d\n",name,age,p->roomlevel,p->roomnum,bednumber);

printf("\n");

}

}

voidCheckout(Room*head)

{

Room*p;

intnumber,bednumber,i,s;

printf("歡迎使用退房系統：");

printf("\n\n請輸入房間號：");

scanf("%d",

printf("\n\n請輸入性別（1為男，0為女）：");

scanf("%d",

printf("請輸入床位號：");

scanf("%d",

p=head->next;

while(p!=NULL)

{

if(p->roomnum==number)

for(i=0;iroomlevel;i++)

if(i+1==bednumber)

{

p->bed[i]=0;

p->peoplenum--;

if(p->peoplenumpeoplenum=0;

if(p->peoplenum==0)

p->sex=-1;

printf("您已退房，歡迎下次光臨");

break;

}

p=p->next;

}

}

voidDisplay(Room*head)

{

Room*p;

inti=0;

p=head->next;

printf("\n\n已訂房間查詢");

if(head->peoplenum==NULL)

{

printf("全部等級房間空房");

return;

}

while(p->peoplenum!=NULL)

{

if(p->sex==1)

printf("\n房間號：%d，房間等級：%d，已住人數：%d，住房人性別：男",p->roomnum,p->roomlevel,p->peoplenum);

else

printf("\n房間號：%d，房間等級：%d，已住人數：%d，住房人性別：女",p->roomnum,p->roomlevel,p->peoplenum);

while(ipeoplenum)

if(p->bed[i]==1)

{

printf("，已住床位號：%d",i+1);

i++;

}

printf("\n");

p=p->next;

}

}

voidmain()

{

intn,k=1,i,roomlevel,room[10],bed[10],sum=0;

Room*head;

printf("請輸入房間等級數:\n");

printf("Roomlevel:");scanf("%d",

for(i=1;i

#include

#include

typedefstructStringWord

{

charch[100];

}SW;

voidCreatTextFile()

{

charfilename[10],ch;

FILE*fp;

printf("請輸入所用的文件名:");

scanf("\n%s",filename);

fp=fopen(filename,"w");

printf("請輸入一段文字，以$號結束:\n");

scanf("%s",

while(ch!='$')

{

fwrite(

scanf("%c",

}

fclose(fp);

}

voidCountWord()

{

FILE*fp;

SWS,T;

charch;

charfilename[10];

inti=0,number=0;

printf("輸入文本文件名：");

scanf("%s",filename);

fp=fopen(filename,"r");

printf("輸入要統計計數的單詞：");

scanf("%s",T.ch);

while(!feof(fp))

{

ch=fgetc(fp);

if(ch=='')

{

if(i!=0)

{

S.ch[i]='\0';

i=0;

if(strcmp(S.ch,T.ch)==0)

number++;

}

}

elseif(ch=='\n')

{

if(i!=0)

{

S.ch[i]='\0';

i=0;

if(strcmp(S.ch,T.ch)==0)

number++;

}

}

else

{

S.ch[i]=ch;i++;

}

}

if(number==0)

printf("單詞不在文本中\n");

else

printf("單詞%s在文件%s中共浮現了%d次:",T.ch,filename,number);

fclose(fp);

}

voidSearchWord()

{

FILE*fp;

SWS,T;

charfilename[10];

inti,i_r,line,flag=0;

charch;

printf("\n輸入文本文件名：");

scanf("%s",filename);

fp=fopen(filename,"r");

printf("輸入要統計計數的單詞：");

scanf("%s",T.ch);

i=i_r=0;

line=1;

while(!feof(fp))

{

ch=fgetc(fp);

if(ch=='')

{

if(i!=0)

{

i_r++;S.ch[i]='\0';

i=0;

if(strcmp(T.ch,S.ch)==0)

{

printf("%s單詞第一次浮現是在%d行,%d列\n",T.ch,line,i_r);

flag=1;

break;

}

}

}

elseif(ch=='\n')

{

if(i!=0)

{

i_r++;S.ch[i]='\0';

if(strcmp(T.ch,S.ch)==0)

{

printf("%s單詞第一次浮現是在%d行,%d列\n",T.ch,line,i_r);

flag=1;

break;

}

i=0;i_r=0;line++;

}

else

{

line++;i_r=0;

}

}

else

{

S.ch[i]=ch;i++;}

}

if(flag==0)

printf("%s單詞不在文本中\n",T.ch);

fclose(fp);

}

intmain()

{

CreatTextFile();

CountWord();

SearchWord();

}

題目8：二叉樹的遍歷（學時：6）

二叉樹以lson-rson鏈接方式存儲，以菜單方式設計并完勝利能任務：建立并存儲樹、輸出前序遍歷結果、輸出中序遍歷結果、輸出后序遍歷結果、交換左右子樹、統計高度，其中對于中序、后序的遍歷運算要求采納非遞歸方式。

#include

#include

#defineM100

typedefstructnode//定義二叉樹結點

{

chardata;

structnode*lchild,*rchild;

}BTNode;

BTNode*CreatBTree()//創建二叉樹(先序遞歸)

{

charch;

BTNode*b;

scanf("%c",

if(ch=='#')//遞歸結束控制符

b=NULL;

else

{

b=(BTNode*)malloc(sizeof(BTNode));

b->data=ch;

b->lchild=CreatBTree();//遞歸先序建立左子樹

b->rchild=CreatBTree();//遞歸先序建立右子樹}

returnb;

}

voidPreOrder(BTNode*b)//遞歸先序遍歷二叉樹函數

{

if(b!=NULL)

{

printf("%c",b->data);

PreOrder(b->lchild);

PreOrder(b->rchild);

}

}

voidInOrder(BTNode*b)//非遞歸中序遍歷二叉樹函數{

BTNode*stack[M],*p;

inttop=-1;

if(b!=NULL)

{

p=b;

while(top>-1||p!=NULL)

{

while(p!=NULL)//掃描p的全部左結點并入棧

{

top++;

stack[top]=p;

p=p->lchild;

}

if(top>-1)

{

p=stack[top];//出棧拜訪結點

top--;

printf("%c",p->data);

p=p->rchild;//掃描p的右結點

}

}

printf("\n");

}

}

voidPostOrder(BTNode*b)//非遞歸后序遍歷二叉樹函數

{

BTNode*stack[M],*p;

intsign,top=-1;

if(b!=NULL)

{

do

{

while(b!=NULL)//b全部左結點入棧

{

top++;

stack[top]=b;

b=b->lchild;

}

p=NULL;//p指向棧頂前一個已拜訪結點

sign=1;//置b為已拜訪

while(top!=-1//取出棧頂結點

if(b->rchild==p)//右孩子不存在或右孩子已拜訪則拜訪b

{

printf("%c",b->data);

top--;

p=b;//p指向被拜訪的結點

}

else

{

b=b->rchild;//b指向右孩子結點

sign=0;//置未拜訪標記

}

}

}while(top!=-1);

printf("\n");

}

}

voidchange(BTNode*b)//左右子樹交換(遞歸)

{

BTNode*r;

r=(BTNode*)malloc(sizeof(BTNode));

intf1=0,f2=0;

if(b==0)return;//樹為空時，跳出

if(b->lchild)

{

change(b->lchild);

r->lchild=b->lchild;

f1++;//有左子樹，符號位不為空}

if(b->rchild)

{

change(b->rchild);

r->rchild=b->rchild;

f2++;//有右子樹，符號位不為空}

if(f1==0)r->lchild=NULL;//否則，給中間變量賦空值if(f2==0)r->rchild=NULL;

if(f1||f2)

{

b->rchild=r->lchild;//左右子樹交換

b->lchild=r->rchild;

}

}

intmax(intm,intn)

{

if(m>n)

returnm;

elsereturnn;

}

intcount(BTNode*b)//計算樹高(遞歸)

{

if(b==NULL)

return0;

elsereturn(1+max(count(b->lchild),count(b->rchild)));

}

intmain()

{

BTNode*root=NULL;

printf("二叉樹的遍歷\n\n");

printf("請按先序遞歸挨次創建二叉樹(結束符#):\n");

root=CreatBTree();

printf("\n遞歸先序遍歷結果:\n");

PreOrder(root);

printf("\n非遞歸中序遍歷結果:\n");

InOrder(root);

printf("非遞歸后序遍歷結果:\n");

PostOrder(root);

printf("\n樹高:%d\n",count(root));

printf("\n左右子樹交換位置:");

change(root);

printf("\n遞歸先序遍歷結果:\n");

PreOrder(root);

printf("\n非遞歸中序遍歷結果:\n");

InOrder(root);

printf("非遞歸后序遍歷結果:\n");

PostOrder(root);

return0;

題目9：創建二叉排序樹（學時：3）

二叉排序樹以lson-rson鏈接方式存儲，編寫能夠通過鍵盤輸入建立二叉排序樹，并在建立完立刻在屏幕顯示中序遍歷結果的程序。

#include

#include

typedefstructnode

{

intdata;

structnode*lchild,*rchild;

}BSTNode,*BSTTree;

//二叉排序樹的插入（遞歸算法）

voidInsertBST(BSTTree*BST,intkey)

{

if((*BST)==NULL)

{

(*BST)=(BSTNode*)malloc(sizeof(BSTNode));

(*BST)->data=key;

(*BST)->lchild=NULL;

(*BST)->rchild=NULL;

}

elseif((*BST)->data>key)//假如待插入的元素比根結點元素值小InsertBST(//插入在根結點的左子樹else

InsertBST(//插入在根結點的右子樹上}

//創建一棵二叉排序樹

BSTTreeCreateBSTTree()

{

BSTTreebst=NULL;

intx;

while(1)

{

scanf("%d",

if(x==00)break;

InsertBST(

}

returnbst;

}

//中序遍歷

voidInOrder(BSTTreeBST)

{

if(BST!=NULL)

{

InOrder(BST->lchild);

printf("%5d",BST->data);

InOrder(BST->rchild);

}

}

voidmain()

{

BSTTreeBST;

printf("建立二叉排序樹，請輸入序列:\n");

BST=CreateBSTTree();

printf("中序遍歷后輸出的該序列為:");

InOrder(BST);

printf("\n");

}

題目10：霍夫曼編碼應用（學時：3）

假設一串由大寫字母構成的電文，采納霍夫曼規章對其舉行編碼，以菜單方式設計并完勝利能任務：建立霍夫曼樹、霍夫曼編碼生成、編碼文件譯碼。

#include

#include

#include

#definen100

#definem2*n-1

typedefstruct

{

intweight;

charch;

intparent,lchild,rchild;

}HTNode;

typedefstruct{

charch;

charbits[n+1];

}CodeNode;

typedefstruct

{

charcha;

intnumber;

}COUNTER;

intInit(HTNodeht[])//初始化函數，為每一個字母信息賦權值{

inti,s=1;

COUNTERcounter[27];

charch;

printf("請輸入字符：\n");

scanf("%c",

counter[1].cha='A';

counter[2].cha='B';

counter[3].cha='C';

counter[4].cha='D';

counter[5].cha='E';

counter[6].cha='F';

counter[7].cha='G';counter[8].cha='H';counter[9].cha='I';counter[10].cha='J';counter[11].cha='K';counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16].cha='P';counter[17].cha='Q';counter[18].cha='R';counter[19].cha='S';counter[20].cha='T';counter[21].cha='U';counter[22].cha='V';counter[23].cha='W';counter[24].cha='X';counter[25].cha='Y';counter[26].cha='Z';

for(i=1;iy)

{

*p1=y;

*p2=x;

}

else

{

*p1=x;

*p2=y;

}

}

voidhuffman_setup(HTNodeht[],ints){

inti,a;

intp1,p2;

a=2*s-1;

for(i=1;i%s\n",hc[i].ch,hc[i].bits);

}

while(flag)

{

printf("請輸入您想要舉行的操作：\n1編碼\n2解碼\n3退出\n");

fflush(stdin);

scanf("%d",

switch(choice)

{

case1:

huffman_code(hc);

printf("\n");

break;

case2:

huffman_read(ht,s);

printf("\n");

break;

case3:

flag=0;

}

}

return0;

}

題目11：關鍵路徑尋覓（學時：6）

對于給定的一個工程施工圖，該圖以邊為單位從鍵盤輸入，編寫能夠找出該圖的關鍵路徑的程序。

#include

#include

structNode//鄰接點

{

intvex;//頂點信息

intweight;//權值

structNode*next;

};

structHnode//頭結點

{

intvex2;

intid;//入度

structNode*link;

}A[20];

voidcreate(structHnodeA[20],intn,inte){

inti,j,k,l;

structNode*p;

for(i=1;ivex=j;

p->weight=l;

p->next=A[i].link;

A[i].link=p;

}

for(i=1;ivex;

A[k].id=A[k].id+1;

p=p->next;

}

}

}

voidfind(structHnodeA[20],intn)

{