《數(shù)據(jù)結(jié)構(gòu)實驗與實訓教程（第3版）》課件

目錄

第一部分預備知識..............................................................1

預備知識...................................................................1

預備知識實驗...............................................................2

第二部分基礎(chǔ)實驗..............................................................3

實驗1線性表的基本操作...................................................3

實驗2鏈表的基本操作.....................................................8

實驗3棧的基本操作......................................................14

實驗4隊列的基本操作....................................................20

實驗5數(shù)組的基本操作....................................................29

實驗6字符串的基本操作..................................................33

實驗7二叉樹的基本操作..................................................38

實驗8樹的遍歷和哈夫曼樹................................................42

實驗9圖的基本操作......................................................49

實驗10排序...........................................................55

實驗11查找...........................................................59

第三部分課程設(shè)計實驗.........................................................63

實驗1航空客運訂票系統(tǒng)...................................................63

實驗2漢諾塔游戲程序.....................................................70

實驗3全屏幕編輯程序設(shè)計.................................................74

實驗4旅游路線安排模擬系統(tǒng)...............................................82

實驗6最小生成樹kruskal算法..............................................84

第一部分預備知識

預備知識

例L1

#include<std

intsumabc(inta,intb,intc)/*求三個整數(shù)之和*/

{ints;

a=b+c;

s=a+b+c;

returns;

}

voiddisplayLine(void)

{printf("----------------------\n")；

)

voidmain()

{intx,y,z,sabc;

x=y=z=8;

displayO;/*畫一條線*/

printf(4t\nsum=%d,\sumabc(x,y,z));/*在輸出語句中直接調(diào)用函數(shù)sumabc()*/

printff4\n%6d%6d%6d,,,x,y,z);

displayO;/*畫一條線*/

x=2;y=4;z=6;

sabc=sumabc(x,y,z);/*在賦值語句中調(diào)用函數(shù)sumabc()*/

printf(t4\n"sum=%d”,sabc);

printf(4€\n%6d%6d%6d,,,x,y,z);

display。;/*畫一條線*/

)

intsumabc(int*a,intb,intc)

(

ints;

*a=b+c;

s=*a+b+c;

returns;

預備知識實驗

intmain()

{〃在main函數(shù)中調(diào)用上述聲明的函數(shù)

intn;〃記錄個數(shù)

STUDENTstu[MAXSIZE;〃順序存儲結(jié)構(gòu)，方法一靜態(tài)一維數(shù)組。

/*

順序存儲結(jié)構(gòu)，方法二動態(tài)一維數(shù)組，用malloc函數(shù)分配如下：

STUDENT*stu;

stu=(STUDENT*)malloc(sizeof(STUDENT)*MAXSIZE);//內(nèi)存空間的分配

注意：分配空間可用malloc。函數(shù)，釋放空間用free。函數(shù)，如free(stu);

*/

intindex;

printf(u\n請輸入學生記錄個數(shù)n=")；scanf(%d,,,&n);

InputStu(stu,n);//預先處理輸入，建表

while(l)//永真循環(huán)，重復顯示菜單，直至退出

printf(''\n**********************學生信息管理主菜單**********************\n")，

printf("\tl.顯示學生信息\n")；

printf(%2.查找學生信息\n")；

printf(”\t3.修改學生信息\n");

printf("\t4,添加學生信息\n");

printf(”\t5.退出\n\n”);

printf("\t\t請選擇(1?5):“)；

scanf(,,%d,',&index);

switch(index){

case1:OutputStu(stu,n);break;

case2:SearchStu(stu,n);break;

case3:UpdateStu(stu,n);break;

case4:AppendStu(stu,&n);break;

case5:return0;

default:printf(H\n輸入有誤,請重新輸入!\nM);

}//switch

}//while(1)

}//main

第二部分基礎(chǔ)實驗

實驗1線性表的基本操作

四、參考程序

程序1:題1線性表基本操作函數(shù)

structLinearList/*定乂線性表結(jié)構(gòu)*/

(

int*list;/*存線性表元素*/

intsize;/*存線性表長度*/

intMaxSize;/*存list數(shù)組元素個數(shù)*/

};

typedefstructLinearListLIST;

voidInitList(LIST*L,intms)/*初始化線性表*/

if((L->list=1)=NULL){

printf(〃內(nèi)存申請錯誤!\n〃);

exit(1);

2

L->MaxSize=ms;

)

intInsertList(LIST*L,intitem,intrc)

/*item:記錄值rc:插入位置*/

(

inti;

if(3)/*線性表已滿*/

returnT;

if(rc<0)/*插入位置為0-->L->size*/

rc=0;

if(4)

rc=L->size;

for(i=L->size-1;i>=rc;i-)/*將線性表元素后移*/

5

L->list[rc]item;

L->size-H-;

return0;

}

voidOutputList(LIST*L)/*輸出線性表元素*/

{

inti;

for(i=0;6i++)

printf(z，%d”,L->list[i]);

printf(〃\n〃);

)

intFindList(LIST*L,intitem)/*返回>=0為元素位置-1沒找到*/

(

inti;

for(i=0;i<L->size;i++)

if(7)/*找到相同的元素，返回位置*/

returni;

return-1;/*沒找到*/

}

intDeleteListl(LIST*L,intitem)

/*刪除指定元素值的線性表記錄，返回>=0：刪除成功*/

(

inti,n;

for(i=0;i<L->size;i++)

if(item=L->list[i])/*找到相同的元素*/

break;

if(i<L->size){

for(n=i;n<L->size-1;n++)

L->list[n]=L->list[n+1];

L->size—;

returni;

)

return-1;

}

intDeleteList2(LISTL,intrc)/*刪除指定位置的線性表記錄*/

(

8/*編寫刪除指定位置的線性表記錄子程序*/

)

程序2：題2

voidmain()

LISTLL;

inti,r;

InitList(&LL,100);

printf("listaddr

while(1)

(

printf(〃請輸入元素值，輸入0結(jié)束插入操作:〃);

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf(繪d〃，&i);

if(])

break;

printf(〃請輸入插入位置：〃);

scanf(&r);

InsertList(2);

printf(〃線性表為：〃)；

3___________

)

while(1)

(

printf(〃請輸入查找元素值，輸入0結(jié)束查找操作:〃);

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf(〃％d〃，&i);

if(i==0)

break;

r=____4________

if(r<0)

printf(〃沒找到\n〃);

else

printf("有符合條件的元素，位置為：%d\n”,r+1);

}

while(1)

(

printf("請輸入刪除元素值，輸入0結(jié)束查找操作：〃);

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf("%d",&i);

if(i=0)

break;

r=5

if(r<0)

printf("沒找到\n");

else{

printf(〃有符合條件的元素，位置為：％d\n線性表為：〃，r+1);

OutputList(&LL);

)

)

while(1)

(

printf(〃請輸入刪除元素位置，輸入0結(jié)束查找操作:〃);

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf(&r);

if(r=0)

break;

i-6________

if(i<0)

printf(〃位置越界\n〃);

else{

printf(〃線性表為：〃);

OutputList(&LL);

)

程序4：題4

#defineX10

^defineY30

ttdefineN20

intA[N]={2,5,15,30,1,40,17,50,9,21,32,8,41,22,49,31,33,18,80,

5);

voiddel(int*A,int*n,intx,inty)

(

inti,j;

for(i=j=0;i<*n;i++)

if(A[i]>y||A[i]<x)//不在x到y(tǒng)之間，則保留

1；

2j；

)

voidoutput(int*A,intn)

(

inti;

printf("\n數(shù)組有%(1個元素:\n”,n);

for(i=0;i<n;i++){

printf("%7d”,A[i]);

if((i+1)%10=0)

printf("\n");

}

printf("\n");

)

voidmain()

{

intn;

n=N;

output(A,n);

3;

output(A,n);

}

實驗2鏈表的基本操作

四、參考程序

程序1：題1鏈表基本操作函數(shù)

typedefstructlist{

intdata;

structlist*next;

}LIST;

voidInitList(LIST**p)/*初始化鏈表*/

(

1/*編寫初始化鏈表子程序*/

)

voidInsertListl(LIST**p,intitem,intrc)

/*向鏈表指定位置［rc］插入元素［item］*/

(

inti;

LIST*u,*q,*r;/*u:新結(jié)點q:插入點前驅(qū)亡插入點后繼*/

u=(LIST*)malloc(sizeof(LIST));

u->data=item;

for(i=0,r=*p;2;i++){

q=r;

r=r->next;

}

if(J)/*插入首結(jié)點或p為空指針*/

*p=u;

else

4

u->next=r;

)

voidInsertList2(LIST**p,intitem)

/*向有序鏈表初插入鍵值為［item］的結(jié)點*/

(

LIST*u,*q,*r;/*u:新結(jié)點q:插入點前驅(qū)r:插入點后繼*/

u=(LIST*)malloc(sizeof(LIST));

u->data=item;

fbr(r=*p;5&&r->data<item;q=r,r=r->next)

；/*從鏈表首結(jié)點開始順序查找*/

if(r==*p)/*插入首結(jié)點或p為空指針*/

6

else

q->next=u;

u->next=r;

/*刪除鍵值為［ilem］的鏈表結(jié)點，返回0:刪除成功1:沒找到*/

intDeleteList(LIST**p,intitem)

LIST*q,*r;/*q:結(jié)點前驅(qū)r:結(jié)點后繼*/

q=*p;

if(q==NULL)/*鏈表為空*/

return1;

if(q->data--7){/*要刪除鏈表首結(jié)點*/

p=q->link;/*更改鏈表首指針*/

8/*釋放被刪除結(jié)點的空間*/

return0;/*刪除成功*/

fdr(;9&&K);r=q,q=q->next)

；/*尋找鍵值為［item］的結(jié)點*/

if(q->data==item){/*找到結(jié)點*/

q->next=r->next/*被刪結(jié)點從鏈表中脫離*/

free(q);/*釋放被刪除結(jié)點的空間*/

return0;/*刪除成功*/

return1;/*沒有指定值的結(jié)點，刪除失敗*/

/*查找鍵值為［item］的鏈表結(jié)點位置，返回>=1:找到-1:沒找到*/

intFindList(LIST*p,intitem)

inti;

for(i=1;p->data!=item&&p!=NULL;11,i++)

；/*查找鍵值為［item］的結(jié)點*/

return(p==NULL)?-l:i;/*找到返回［i］*/

)

voidOutputList(LIST*p)/*輸出鏈表結(jié)點的鍵值*/

while(12){

printf("%4d",p->data);

p=p->next;/*遍歷下一個結(jié)點*/

voidFreeList(LIST**p)/*釋放鏈表空間*/

(

LIST*q,*r;

for(q=*p;q!=NULL;){

13

q=q->next;

14

*p=NULL;/*將鏈表首指針致空*/

)

程序2：題2

voidmain()

(

LIST*p;

intop,i,rc;

In山st(&p);/*初始化鏈表*/

while(1)

(

printf(”請選擇操作1：指定位置追加2:升序追加3:查找結(jié)點3”)；

printf("4:刪除結(jié)點5:輸出結(jié)點6:清空鏈表0：退出\n”);

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf("%d",&op);

switch(op){

case0:/*退出力

return;

easel:/*指定位置追加結(jié)點*/

printf(”請輸入新增結(jié)點鍵值和位置：”)；

scanf(,,%d%d",&i,&rc);

1__________；

break;

case2:_______/*按升序追加結(jié)點*/

printf(”請輸入新增結(jié)點鍵值：”)；

scanf(M%dn,&i);

InsertList2(&p,i);

break;

case3:/*查找結(jié)點*/

printf(”請輸入要查找結(jié)點的鍵值：”);

scanf(n%dn,&i);

rc-2;

if(rc>0)

printf(H位置為rc);

else

printf(K沒找到\n");

break;

case4:/*刪除結(jié)點*/

printf(”請輸入要刪除結(jié)點的鍵值：”);

scanf(H%d",&i);

rc=3;

rc==0)

printf(H刪除成功\n”,rc);

else

printf(M沒找到\n”)；

break;

case5:/*輸出結(jié)點*/

printf(”\n鏈表內(nèi)容為:\n");

____4___________;

break;

case6:/*清空鏈表*/

5________；

break;

)

程序3：題3

typedefstructnode{

intx;

structnode*next;

INODE；

voidinput(NODE**a)

(

NODE*p,*q;

inti;

printf(〃請輸入鏈表的元素，-1表示結(jié)束\n〃);

*a=NULL;

while(1){

scanf(&i);

if(i==-1)

break;

p=(NODE*)malloc(sizeof(NODE));

p->x=i;

p->next=NULL;

if(*a=NULL)

*a=q=p;

else{

q->next=p;

q=q->next;

)

}

)

voidoutput(NODE*a)

(

inti;

for(i=0;a!=NULL;i++,a=a->next){

printf(繪7d”,a->x);

if((i+1)%10=0)

printf("\n");

}

printf("\n");

)

voiddisa(NODE*a,NODE**b)

(

NODE*r,*p,*q;

P=a;

r=*b=(a=NULL)?NULL:a->next;//如果鏈表a為空，則鏈表b也為空

while(1&&2){

q=p->next;//q指向偶數(shù)序號的結(jié)點

3//將q從原a鏈表中刪除

r->next=q;//將q結(jié)點加入到b鏈表的末尾

4//r指向b鏈表的最后一個結(jié)點

p=p->next;//p指向原a鏈表的奇數(shù)序號的結(jié)點

)

r->next=NULL;〃將生成b鏈表中的最后一個結(jié)點的next域置空

)

voidmainO

(

NODE*a,*b;

input(&a);

printf("鏈表a的元素為:\n");

output(a);

5________

printf(〃鏈表a的元素(奇數(shù)序號結(jié)點)為:\n〃);

output(a);

printf(〃鏈表b的元素(偶數(shù)序號結(jié)點)為:\n〃);

output(b);

)

實驗3棧的基本操作

四、參考程序

程序1：題1棧的基本操作函數(shù)

^defineMAXN10/*棧的最大容量*/

/*定義棧的類型為int*/

intpush(int*stack,intmaxn,int*toppt,intx)/*進棧函數(shù)*/

(

if(*toppt>=maxn)/*1*/

return1;

2/*元素進棧*/

++(*toppt);/*棧頂指針+1*/

return0;/*進棧成功*/

}

intpop(int*stack,int*toppt,int*cp)/*出棧函數(shù)*/

(

if(3)/*?？?，出棧失敗，返回1*/

return1;

—(*toppt);/*棧頂指針T*/

________4________

return0;/*出棧成功*/

voidOutputStack(int*stack,inttoppt)/*輸出棧元素*/

(

inti;

for(i=5;i>=0;i—)

printf(z，%d”,stack[i]);

printf(〃\n〃);

)

程序2：題2主函數(shù)

voidmain()

(

ints[MAXN],i;/*定義棧*/

inttop=0;/*設(shè)置為空棧*/

intop;

while(1)

printf(〃請選擇操作，1：進棧2：出棧0：退出");

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf(〃%d〃，&op);

switch(op){

case0:/*退出*/

return;

case1:/*進棧*/

printf(〃請輸入進棧元素：〃);

scanf(〃/d”,&i);

if(]){/*進棧成功*/

printf(〃進棧成功，棧內(nèi)元素為:\n〃);

OutputStack(s,top);

)

else

printf(〃棧滿\n〃);

break;

case2:/*出棧*/

if(2){/*出棧成功*/

printf(〃出棧元素為：[%d],棧內(nèi)元素為:\n〃，i);

3

}

else

printf(〃?？誠n〃);

break;

)

)

)

程序3：題3配對函數(shù)

intcorrect(char*exp,intmax)/*傳入?yún)?shù)為表達式、表達式長度，返回0：成功，返

回]錯誤*/

(

intflag=0;/*括號匹配標志，0:正確*/

chars[MAXN];/*定義棧*/

inttop=0;/*棧指針為0,表示空棧*/

charc;

inti;

for(i=0;1;i++){

/*循環(huán)條件為表達式未結(jié)束且括號匹配*/

if(exp[i]==C|Iexp[i]='['||exp[i]='{'}

push(s,MAXN,&top,exp[i]);

if(expLi]—)'IIexp[i]—]'||exp[i]='}'){/*遇到}出棧*/

2/*置出棧結(jié)果，?？粘鲥e*/

if((exp[i]=')'&&c!=，C)|I(exp[i]="]"&&c!=，[,)

I|(exp[i]-'&&c!='{'))/*括號不匹配*/

flag=1;

)

}

if(3)/*棧不為空，表明還有(,[,{符號沒匹配*/

flag=1;

returnflag;

)

voidmain()

(

chars[MAXN],c;/*定義棧*/

charexp[1024];

inttop=0;/*設(shè)置為空棧*/

while(1){

printf(”請輸入表達式,輸入0退出：");

gets(exp);/*從標準輸入中讀取表達式*/

exp[MAXN]='\0';/*表達式長度<=MAXN*/

if(strcmp(exp,"0")=0)

4

if(5)

printf("表達式內(nèi)容為：\n%s\n表達式括號不匹配\n",exp);

else

printf("表達式括號匹配\n");

)

}

程序4：題4波蘭表達式

^defineMAXN100/*棧的最大容量*/

intpushc()/*char型元素進棧函數(shù)*/

(

/*編寫進棧子程序*/

)

intpopc(char*stack,int*toppt,char*cp)/*char型元素出棧函數(shù)*/

(

/*編寫出棧子程序*/

)

inteval()/*算術(shù)運算*/

/*編寫算術(shù)運算子程序*/

}

intoperate(char*str,int*exp)/*計算后綴表達式的值，返回0:成功T:表達

式錯誤-2:棧滿*/

(

charc;

intopdl,opd2,temp,cl;

ints[MAXN];

inti;

inttop=0;

for(i=0;str[i]!='\0';i++){

c=str[i];

if(c>:'O'&&c〈=’9'){/*數(shù)字進棧*/

cl=c-'O';/*將字符轉(zhuǎn)換成數(shù)字值*/

if(push(s,MAXN,&top,cl)!=0){

printf(〃表達式太長，棧滿〃);

return-2;

}

)

elseif(c='+'||c='||c二二'*'||c='/')

{/*運算符*/

pop(s,&top,&opdl);

if(pop(s,&top,&opd2)[=0)

return-1;

temp=eval(c,opd2,opdl);

1；

else

return-1;

)

2/*取出結(jié)果*/

if(top!=0)~~7*棧非空*/

return-1;

return0;

)

inttrans(char*sin,char*sout)/*將中綴表達式轉(zhuǎn)換成后綴，返回0:處理成功

*/

chars[MAXN],c;/*定義棧，棧元素*/

3/*設(shè)置為空棧*/

intoff=0;/*數(shù)組下標*/

inti;

for(i=0;sin[i]!='\0';i++)/*遇到休止符，表示表達式輸入結(jié)束*/

if(sin[i]>='O'&&sin[i]〈=’9')/*輸入數(shù)字，進數(shù)組*/

sout[4]=sin[i];

elseswitch(sin[i]){

case':/*左括號，括號入棧*/

pushc(s,MAXN,&top,sin[i]);

break;

case:/*右括號，將棧中左括號前的元素出棧，存入數(shù)組*/

while(1){

if(popc(s,&top,&c)!=0){/*?？?/

printf(〃表達式括號不匹配\n〃);

return-1;

)

if(c='(')/*找到匹配的括號*/

break;

sout[off++]=c;/*棧頂元素入數(shù)組*/

)

break;

case':/*為，將棧中左括號前的元素出棧，存入數(shù)組*/

case'-':

while(top>0&&s[top-1]!='('){

5

sout[off++]=c;

}

pushc(s,MAXN,&top,sin[i]);/*'+','」符號入棧*/

break;

case':/*為'將棧頂'符號出棧，存入數(shù)組*/

case'/':

while(top>0&&(s[top~l]='*'||s[top-1]='/')){

pope(s,&top,&c);

sout[off++]=c;

}/*這段循環(huán)如何用if語句實現(xiàn)？*/

pushc(s,MAXN,&top,sin[i]);/*符號入棧*/

break;

)

while(6)/*所有元素出棧，存入數(shù)組*/

sout[off++]=c;

sout[off]='\0';/*加休止符*/

return0;

}

voidmain()

(

char*sin;/*輸入表達式指針，中綴表示*/

char*sout;/*輸出表達式指針，后綴表示*/

inti;

sin=(char*)malloc(1024*sizeof(char));

sout=(char*)malloc(1024*sizeof(char));

if(7){

printf(〃內(nèi)存申請錯誤!\n");

return;

)

printf(〃請輸入表達式：〃);

gets(sin);

if(8){/*轉(zhuǎn)換成功*/

printf(〃后綴表達式為：sout);

switch(9){

case0:

printf(〃計算結(jié)果為：[刎八n〃，i);

break;

case-1:

printf(〃表達式錯誤\n〃);

break;

case-2:

printf("棧操作錯誤\n");

break;

)

)

實驗4隊列的基本操作

四、參考程序

程序1：題1鏈接隊列的基本操作函數(shù)

typedefstructqueue{/*定義隊列結(jié)構(gòu)*/

intdata;/*隊列元素類型為int*/

structqueue*link;

}QUEUE;

voidEnQueue(QUEUE**head,QUEUE**tail,intx)/*進隊操作*/

(

QUEUE*p;

p=(QUEUE*)malloc(sizeof(QUEUE));

_______1_______

p->link=NULL;/*隊尾指向空*/

if(*head==NULL)/*隊首為空，即為空隊列*/

2

else{

(*tail)->link=p;/*新單元進隊列尾*/

*tail=p;/*隊尾指向新入隊單元*/

)

intDeQueue(QUEUE**head,QUEUE**tail,int*cp)/*出隊操作1:對空*/

(

QUEUE*p;

p=*head;

if(*head=NULL)/*隊空*/

return1;

*cp=(*head)->data;

*head=3

if(*head==NULL)/*隊首為空，隊尾也為空*/

*tail=NULL;

free(p);/*釋放單元*/

return0;

)

voidOutputQueue(QUEUE*head)/*輸出隊列中元素*/

(

while4(){

printf(〃%d〃，head->data);

head=head->link;

}

printf(〃\n〃);

程序2：題2主程序：

voidmain()

(

QUEUE*head,*tail;

intop,i;

head=tail=NULL;/*1*/

while(1)

(

printf(〃請選擇操作，1：進隊2：出隊0：退出〃);

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf("刎〃，&op);

switch(op){

case0:/*退出*/

return;

case1:/*進隊*/

printf(〃請輸入進隊元素：〃);

scanf(&i);

2;

printf(〃隊內(nèi)元素為:\n〃);

OutputQueue(head);

break;

case2:/*出隊*/

if(30){/*出隊成功*/

printf(〃出隊元素為：[%d],隊內(nèi)元素為:\n〃，i);

OutputQueue(head);

)

else

printf(〃隊空\n〃);

break;

}

)

)

程序3：題3環(huán)型隊列的基本操作函數(shù)

#defineMAXN11/*定義環(huán)行順序隊列的存儲長度*/

intEnQueue(int*queue,intmaxn,int*head,int*tail,intx)/*進隊操作，返

回1:隊滿*/

if(1=*head)/*隊尾指針趕上隊首指針，隊滿*/

return1;

*tail=2/*隊尾指針+1*/

queue[*tail]=x;/*元素入對尾*/

return0;

)

intDeQueue(int*queue,intmaxn,int*head,int*tail,int*cp)

/*出隊操作返回1:隊空*/

(

if(*head=*tail)/*隊首二隊尾，表明隊列為空*/

return1;

*head=(*head+1)%maxn;/*隊首指針+1*/

3/*取出隊首元素*/

return0;

voidOutputQueue(int*queue,intmaxn,inth,intt)/*輸出隊列中元素*/

(

while(4){/**/

h=(h+1)%maxn;

printf(〃%d〃，queue[h]);

)

printf(〃\n〃);

)

程序4：題4主程序：

voidmain()

(

intq[MAXN];/*假設(shè)環(huán)行隊列的元素類型為int*/

intq_h=O,q_t=O;/*初始化隊首，隊尾指針為0*/

intop,i;

while(1)

(

printf(〃請選擇操作，1：進隊2：出隊0：退出〃)；

fflush(stdin);/*清空標準輸入緩沖區(qū)*/

scanf(〃%d〃，&op);

switch(op){

case0:/*退出*/

return;

case1:/*進隊*/

printf(〃請輸入進隊元素：〃);

scanf(〃％d〃，&i);

if(1!=0)

printf(〃隊列滿\n〃);

else{

printf(〃入隊成功，隊內(nèi)元素為:\n〃);

OutputQueue(q,MAXN,q_h,q_t);

)

break;

case2:/*出隊*/

if(20){/*出隊成功*/

printf(〃出隊元素為：[%d],隊內(nèi)元素為:\n〃，i);

OutputQueue(q,MAXN,q_h,q_t);

)

else

printf(〃隊空\n〃);

break;

)

}

)

程序5：題5醫(yī)務(wù)室模擬程序

typedefstruct{

intarrive;/*病人到達時間*/

inttreat;/*病人處理時間*/

}PATIENT;

typedefstructqueue{/*定義隊列結(jié)構(gòu)*/

PATIENTdata;/*隊列元素類型為int*/

structqueue*link;

}QUEUE;

voidEnQueue(QUEUE**head,QUEUE**tail,PATIENTx)/*進隊操作*/

(

/*編寫進隊操作子程序*/

)

intDeQueue(QUEUE**head,QUEUE**tail,PATIENT*Cp)/*出隊操作1:對空*/

(

/*編寫出隊操作子程序*/

}

voidOutputQueue(QUEUE*head)/*輸出隊列中元素*/

(

while(1){

head=head->link;

)

voidInitData(PATIENT*pa,intn)/*生成病人到達及處理時間的隨機數(shù)列*/

intparr=0;/*前一個病人到達的時間*/

inti;

for(i=0;i<n;i++){

pa[i].arrive=parr+random(15);/*假設(shè)病人到達的時間間隔為0~14

*/

pa[i].treat=random(9)+1;/*假設(shè)醫(yī)生處理時間為廣9*/

parr=pa[i].arrive;

printf(“第[%d]個病人到達時間為[%d]處理時間為i+1,parr,pa[i].treat);

)

)

voidmain()

(

QUEUE*head,*tail;

PATIENT*p,curr;/*病人到達及處理時間信息，當前出隊病人信息*/

intn,i,finish;

intnowtime;/*時鐘*/

intdwait,pwait;/*醫(yī)生累計等待時間，病人累計等待時間*/

head=tail=NULL;/*將隊列頭和尾置為空*/

while(1)

(

n=0;

nowtime=dwait=pwait=0;

printf(〃請輸入病人總數(shù)(廣20),二0：退出〃)；

scanf(〃％d〃，&n);

if(n=0)/*退出*/

return;

if(n>2011n<0)

continue;

if((p=(PATIENT*)malloc(n*sizeof(PATIENT)))二二2)

{printf("內(nèi)存申請錯誤\n");

return;

)

3/*生成病人到達及處理時間的隨機數(shù)列*/

for(i=0;4;){/*病人到達未結(jié)束或還有等待，處理*/

if(head=NULL){/*等待隊列為空*/

if(p[i].arrive-nowtime>0)/*病人到達時間與上次處理時間遲*/

5/*累計醫(yī)生等待時間*/

nowtime=p[i].arrive;/*時鐘推進*/

6/*病人入隊*/

)

DeQueue(&head,&curr);/*出隊一位病人*/

7/*累計病人等待時間*/

while(i<n&&p[i].arrive<=finish)

/*下一位病人到達時間在當前病人等待時間結(jié)束之前，入隊*/

8

nowtime=finish;/*時鐘推進到當前病人處理結(jié)束時間*/

)

free(p);/*釋放空間*/

printf(〃醫(yī)生等待時間[%d],病人平均等待時間[%.2f]\n，z,dwait,

(float)pwait/n);

}

)

程序6：題6招聘程序

^defineDEMARK5/*按第二批錄用的扣分成績*/

typedefstructstu{/*定義招聘人員信息結(jié)構(gòu)*/

intno,total,z[2],sortm,zi;/*編號，總成績，志愿，排除成績，錄取

志愿號*/structstu*next;

}STU;

typedefstructjob{

intImt,count;/*計劃錄用人數(shù)，已錄用人數(shù)*/

STU*stu;/*錄用者有序隊列*/

}JOB;