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

1、目錄第一局部 預(yù)備知識 1預(yù)備知識 1預(yù)備知識實驗 2第二局部 根底實驗 4實驗 1線性表的根本操作 4實驗 2鏈表的根本操作 9實驗 3棧的根本操作 15實驗 4隊列的根本操作 22實驗 5數(shù)組的根本操作 32實驗 6字符串的根本操作 36實驗 7二叉樹的根本操作 41實驗 8樹的遍歷和哈夫曼樹 46實驗 9 圖的根本操作 53實驗 10 排 序 59實驗 11 查 找 64第三局部 課程設(shè)計實驗 69實驗 1 航空客運訂票系統(tǒng) 69實驗 2 漢諾塔游戲程序 75實驗 3 全屏幕編輯程序設(shè)計 79實驗 4 旅游路線安排模擬系統(tǒng) 90實驗6最小生成樹kruska算法93第一局部 預(yù)備知識預(yù)備知

2、識例 1 1#include <stdio.h>int sumabc(int a, int b, int c) /* 求三個整數(shù)之和 */ int s;a=b+c; s=a+b+c; return s;void displayLine(void) printf( n “);void main( ) int x,y, z ,sabc; x=y=z=8; display(); /* 畫一條線 */ printf( “n sum=%d,sumabc(x,y,z); /* 在輸出語句中直接調(diào)用函數(shù) sumabc( ) */ printf( “n %6d%6d%6d,x,y,z); disp

3、lay();/* 畫一條線 */ x=2; y=4; z=6;sabc =sumabc(x, y, z); /* 在賦值語句中調(diào)用函數(shù) sumabc( ) */ printf( “n “ sum%=d, sabc);printf( “n %6d%6d%6d,x,y,z); display();/* 畫一條線 */例 1.2int sumabc(int *a, int b, int c)int s;*a=b+c; s=*a+b+c;return s;預(yù)備知識實驗int main()/在 main 函數(shù)中調(diào)用上述聲明的函數(shù)int n; /記錄個數(shù)STUDENT stuMAXSIZE;/ 順序存儲結(jié)

4、構(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);*/ int index;printf("n 請輸入學(xué)生記錄個數(shù) n=");scanf(%d,&n);InputStu(stu, n);/ 預(yù)先處理輸入 , 建表while(1) / 永真循環(huán) ,重復(fù)顯示菜單 , 直至退出printf

5、("n*學(xué)生信息管理主菜單);printf("t1. 顯示學(xué)生信息 n");printf("t2. 查找學(xué)生信息 n"); printf("t3. 修改學(xué)生信息 n");printf("t4. 添加學(xué)生信息 n");printf("t5. 退出 nn");printf("tt 請選擇(15): ");scanf("%d",&index);printf("n*n"); switch(index) case 1:Outpu

6、tStu(stu,n); break;case 2:SearchStu(stu,n); break;case 3:UpdateStu (stu,n); break;case 4:AppendStu (stu,&n); break;case 5:return 0;default:printf("n 輸入有誤 ,請重新輸入 ! n");/switch/while 1 /main第局部根底實驗實驗1線性表的根本操作四、參考程序程序1:題1線性表根本操作函數(shù)#in clude<stdio.h>#in clude<stdlib.h>#in clude&

7、lt;alloc.h> struct Lin earList int *list;int size;int MaxSize;typedef struct Lin earList LIST; void InitList( LIST *L, int ms ) /*/*/ *定義線性表結(jié)構(gòu)*/*存線性表元素*/存線性表長度*/存list數(shù)組元素個數(shù)*/*初始化線性表*/if( (L->list = printf( exit( 1 );2)=NULL ) 1內(nèi)存申請錯誤!n");L->MaxSize = ms;int InsertList( LIST *L, int ite

8、m, int rc )/* item:記錄值rc:插入位置*/int i;if( 3) /*線性表已滿*/return -1;if( rc < 0 )/* 插入位置為 0 -> L->size */ rc = 0;if( 4)rc = L->size;/*將線性表元素后移*/for( i = L->size - 1; i >= rc; i-)5L->listrc = item;L->size +;return 0;void OutputList( LIST *L )/* 輸出線性表元素 */int i;for( i = 0;6i+ )prin t

9、f( "%d ", L->listi);prin tf( "n");int FindList( LIST *L, int item )/* 返回 >=0 為元素位置-1 沒找到 */int i;for( i = 0; i < L->size; i+ )if( 7) /*找到相同的元素，返回位置*/return i;return -1;/* 沒找到 */int DeleteList1( LIST *L, int item )/*刪除指定元素值的線性表記錄，返回>=0:刪除成功*/int i, n;for( i = 0; i &

10、lt; L->size; i+ )if( item = L->listi )/* 找到相同的元素 */break;if( i < L->size ) for( n = i; n < L->size - 1; n+ )L->list n = L->list n+1;L->size -;return i;return -1;int DeleteList2( LIST L, int rc )/ *刪除指定位置的線性表記錄*/8 /*編寫刪除指定位置的線性表記錄子程序*/程序2:題2void mai n()LIST LL;int i, r;LL.M

11、axSize );LL.MaxSize );printf("listaddr=%ptsize=%dtMaxSize=%dn",LL.list,LL.size,In itList( & LL, 100 );printf("listaddr=%ptsize=%dtMaxSize=%dn",LL.list,LL.size,while( 1 )printf("請輸入元素值，輸入0結(jié)束插入操作:");fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", & );if( 1)

12、break;prin tf("請輸入插入位置：);scan f( "%d", &r );In sertList(2);printf(" 線性表為:);3while( 1 )printf("請輸入查找元素值，輸入0結(jié)束查找操作:");fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", & );if( i = 0 )break;r = _4if( r < 0 )prin tf(" 沒找到 n");elseprintf(有符合條件的元素，位置

13、為：dn", r+1 );while( 1 )printf("請輸入刪除元素值，輸入0結(jié)束查找操作：)；fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", & );if( i = 0 )break;r = _5if( r < 0 )prin tf(" 沒找到 n");else prin tf("有符合條件的元素，位置為：%dn線性表為：", r+1 );OutputList( &LL );while( 1 )printf("請輸入刪除元素位置，輸

14、入0結(jié)束查找操作:");fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", &r );if( r = 0 )break;i = _6if( i < 0 )prin tf("位置越界 n");else printf("線性表為：)；OutputList( &LL );程序4:題4#defi ne X 10#defi ne Y 30#defi ne N 20int AN= 2, 5, 15, 30, 1,40, 17, 50, 9, 21, 32, 8, 41,22, 49, 3

15、1,33, 18, 80,#in clude<stdio.h>void del( int *A, i nt *n, i nt x, i nt y )int i, j;for( i = j = 0; i < *n; i+ )if( Ai > y | Ai < x )/不在x到y(tǒng)之間，那么保存1 ；2 = j；void output( int *A, int n )int i;printf( "n數(shù)組有 個元素:n", n );for( i = 0; i < n; i+ ) prin tf( "%7d", Ai);if(

16、( i + 1 ) % 10 = 0 )prin tf( "n");prin tf( "n"); void mai n()int n;n = N;output( A, n );3 ;output( A, n );實驗2鏈表的根本操作四、參考程序程序1 ：題1鏈表根本操作函數(shù)#in clude<stdio.h>#in clude<alloc.h>typedef struct list int data;struct list *n ext;LIST;void InitList( LIST *p )/* 初始化鏈表 */1/*編寫初始

17、化鏈表子程序*/void InsertList1( LIST *p, int item, int rc )/*向鏈表指定位置rc插入元素item */int i;LIST *u, *q, *r;/* u:新結(jié)點q:插入點前驅(qū)r:插入點后繼*/u = ( LIST * )malloc( sizeof(LIST);u->data = item;for( i = 0, r = *p ;2; i+ ) q = r;r = r->n ext;if( _J3)/*插入首結(jié)點或p為空指針*/*p = u;else4u_>next = r;void InsertList2( LIST *p,

18、 int item )/*向有序鏈表p插入鍵值為item的結(jié)點*/LIST *u, *q, *r;/* u:新結(jié)點q:插入點前驅(qū)r:插入點后繼*/u = ( LIST * )malloc( sizeof(LIST);u->data = item;for( r = *p; _5&& r->data < item; q = r, r = r->next );/*從鏈表首結(jié)點開始順序查找*/if( r = *p )/*插入首結(jié)點或p為空指針*/6elseq_>next = u;u_>next = r;/*刪除鍵值為item的鏈表結(jié)點，返回0:刪除成

19、功1:沒找到*/int DeleteList( LIST *p, int item )LIST *q, *r;q = *p;if( q = NULL )/* q:結(jié)點前驅(qū)r:結(jié)點后繼*/*鏈表為空*/return 1;if( q->data =7p = q->li nk;8return 0;for( ;9_/*)/*要刪除鏈表首結(jié)點*/*更改鏈表首指針*/釋放被刪除結(jié)點的空間*/*/*刪除成功10;r = q, q = q_>n ext )&&/*尋找鍵值為item的結(jié)點*/if( q->data = item ) /* 找到結(jié)點 */q->nex

20、t=r->next/*被刪結(jié)點從鏈表中脫離*/free( q );/*釋放被刪除結(jié)點的空間*/return 0;/*刪除成功*/return 1;/*沒有指定值的結(jié)點，刪除失敗*/ /*查找鍵值為item的鏈表結(jié)點位置，返回>=1:找到-1:沒找到*/ int FindList( LIST *p, int item )int i;for( i = 1; p->data != item && p != NULL ; 11 , i+ );/*查找鍵值為item的結(jié)點*/return ( p = NULL ) ? -1 : i; /* 找到返回i */void Ou

21、tputList( LIST *p )/*輸出鏈表結(jié)點的鍵值*/while( 12) prin tf( "%4d", p->data );p = p->next;/*遍歷下一個結(jié)點 */void FreeList( LIST *p )/* 釋放鏈表空間 */LIST *q, *r;for( q = *p; q != NULL; ) 13q = q_>n ext;14*p = NULL;/*將鏈表首指針致空*/程序2:題2void mai n()LIST *p;int op, i, rc;InitList( &p );/* 初始化鏈表 */while

22、( 1 )printf("請選擇操作1:指定位置追加2:升序追加3:查找結(jié)點n");printf( "4:刪除結(jié)點5:輸出結(jié)點 6:清空鏈表0 :退出n");fflush( stdin ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", &op );switch( op ) case 0:/* 退出 */return;case 1:/*指定位置追加結(jié)點*/printf("請輸入新增結(jié)點鍵值和位置：);scan f "%d%d", &i, & rc ;1；break;case

23、 2:/*按升序追加結(jié)點*/printf"請輸入新增結(jié)點鍵值：;scan f "%d", & ;InsertList2 &p, i ;break;case 3:/*查找結(jié)點*/printf"請輸入要查找結(jié)點的鍵值：;scan f "%d", & ;rc =2;if rc > 0 printf位置為%dn", rc ;elseprin tf" 沒找到 n"break;case 4:/*刪除結(jié)點*/printf"請輸入要刪除結(jié)點的鍵值：;scan f "%d&

24、quot;, & ;rc =3 ;if rc = 0 printf"刪除成功 n", rc ;elseprin tf" 沒找到 n"break;case 5:/*輸出結(jié)點*/printf "n 鏈表內(nèi)容為:n"4 ;break;case 6:/*清空鏈表*/5 ;break;程序3:題3#in clude<stdio.h>#in clude<alloc.h>typedef struct node int x; struct node *next;NODE;void input( NODE *a )NOD

25、E *p, *q;int i;printf( " 請輸入鏈表的元素， -1表示結(jié)束 n" ); *a = NULL;while( 1 ) scanf( "%d", &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;void output( NODE *a )int i;for( i = 0

26、; a != NULL; i+, a = a->next ) printf( "%7d", a->x );if( ( i + 1 ) % 10 = 0 ) printf( "n" );printf( "n" );void disa( 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ù)序號的

27、結(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域置空 void mai n()NODE *a, *b;in put( &a );printf("鏈表a的元素為:n");output( a );5printf(鏈表a的元素(奇數(shù)序號結(jié)點)為:n");output( a );printf(" 鏈表b的元素(偶數(shù)序號結(jié)點)為:n")

28、; output( b );實驗3棧的根本操作四、參考程序程序1題1棧的根本操作函數(shù)#include<stdio.h>#define MAXN 10/*棧的最大容量*/*進(jìn)棧函數(shù)*/*定義棧的類型為int */int push( int *stack, int max n, int *toppt, i nt x )if( *toppt >= maxn ) /*1 */return 1;2/*兀素進(jìn)棧*/+(*toppt);/*棧頂指針+1 */return 0;/*進(jìn)棧成功*/int pop( int *stack, int *toppt, int *cp )/* 出棧函數(shù)

29、*/if( 3) /*?？?，出棧失敗，返回1 */return 1;-(*toppt);/* 棧頂指針-1 */4return 0;/*出棧成功*/void OutputStack( int *stack, int toppt )/*輸出棧元素 */int i;for( i =5; i >= 0; i-)prin tf( "%d ", stacki);prin tf( "n");程序2:題2主函數(shù)void mai n()int sMAXN, i;/* 定義棧 */int top = 0;/*設(shè)置為空棧*/int op;while( 1 )print

30、f(請選擇操作，1:進(jìn)棧2 :出棧0 :退出);fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", &op );switch( op ) case 0:/* 退出 */return;case 1:/* 進(jìn)棧 */prin tf("請輸入進(jìn)棧元素：)；scan f( "%d", & );if( 1) /*進(jìn)棧成功*/printf("進(jìn)棧成功，棧內(nèi)元素為:n");OutputStack( s, top );elseprin tf("棧滿 n");break

31、;case 2:/* 出棧 */if( 2) /*出棧成功*/printf(" 出棧元素為：%d, 棧內(nèi)元素為:n" , i );3elseprin tf("?？?n");break;程序3:題3配對函數(shù)int correct( char *exp, int max )/*傳入?yún)?shù)為表達(dá)式、表達(dá)式長度，返回0:成功，返回1:錯誤*/int flag = 0;/*括號匹配標(biāo)志，0:正確*/char sMAXN;/* 定義棧 */int top = 0;/*棧指針為0,表示空棧*/char c;int i;for( i = 0;1; i+ ) /*循環(huán)條件為

32、表達(dá)式未結(jié)束且括號匹配*/if( expi='('| expi=''| expi=''push( s, MAXN, &top, expi);if( expi=')' | expi='' | expi='' ) /*遇到, 出棧 */2/*置出棧結(jié)果，?？粘鲥e*/if( ( expi=')' && c!='(' ) | ( expi='' && c!='')| ( expi='' &

33、amp;& c!='' ) )/* 括號不匹配 */flag = 1;if( 3) /*棧不為空，說明還有(，氏 符號沒匹配*/flag = 1; retur n flag;void mai n()char sMAXN, c;/* 定義棧 */char exp1024;int top = 0;/*設(shè)置為空棧*/while( 1 ) printf("請輸入表達(dá)式,輸入0退出:);gets( exp );/*從標(biāo)準(zhǔn)輸入中讀取表達(dá)式*/expMAXN = '0：/* 表達(dá)式長度 <=MAXN */if( strcmp( exp, "0&quo

34、t; ) = 0 )4if( 5)printf("表達(dá)式內(nèi)容為：n%sn表達(dá)式括號不匹配n" , exp );elseprintf("表達(dá)式括號匹配n");程序4:題4波蘭表達(dá)式#in clude<stdio.h>#in clude<alloc.h>#define MAXN 100/*棧的最大容量*/int pushc()/*編寫進(jìn)棧子程序*/* char型元素進(jìn)棧函數(shù)*/int popc( char *stack, int *toppt, char *cp ) /*編寫出棧子程序*/* char型元素出棧函數(shù)*/int eval

35、()/* 算術(shù)運算 */*編寫算術(shù)運算子程序*/int operate( char *str, i nt *exp ) 式錯誤-2:棧滿*/*計算后綴表達(dá)式的值，返回0:成功-1:表達(dá)char c;int opdl, opd2, temp, c1;int sMAXN;int i;int top = 0;for( i = 0; stri != '0： i+ ) c = stri;if( c >= 'O' && c <= 9 ) c1 = c - '0'/*數(shù)字進(jìn)棧*/*將字符轉(zhuǎn)換成數(shù)字值*/if( push( s, MAXN,

36、&top, c1 ) != 0 ) printf(" 表達(dá)式太長，棧滿); return -2;else if( c = '+' | c = '-' | c = '*' | c = '/') /* 運算符*/pop( s, &top, &opd1 );if( pop( s, &top, &opd2 ) != 0 ) return -1;temp = eval( c, opd2, opd1 );1 ; elsereturn -1;2/*取出結(jié)果*/if(r*棧非空*/return -

37、1;return 0;/*將中綴表達(dá)式轉(zhuǎn)換成后綴，返回0:處理成功 int trans( char *sin, char *sout )*/char sMAXN, c;3int off = 0;/*定義棧，棧元素*/*設(shè)置為空棧*/*數(shù)組下標(biāo)*/int i;for( i = 0; sini != '0： i+ ) /*if( sini >= 'O' && sini <= 9 )遇到休止符，表示表達(dá)式輸入結(jié)束*/*輸入數(shù)字，進(jìn)數(shù)組*/sout 4 = sin i;else switch( sin i ) case '(':/*左

38、括號,括號入棧*/pushc( s, MAXN, &top, sini);break;case ')':/*右括號,將棧中左括號前的兀素出棧，存入數(shù)組*/while( 1 )if( popc( s, &top, &c ) != 0 )/* ?？?*/printf表達(dá)式括號不匹配n"return -1;if( c ='(') break;sout off+ = c;/*找到匹配的括號*/*棧頂元素入數(shù)組*/break;case '+':/* 為'+','-'，將棧中左括號前的元素出棧

39、，存入數(shù)組*/case '-':while( top > 0 && stop-1 != '(' ) 5sout off+ = c;pushc( s, MAXN, &top, si ni );/* '+','-'break;case '*':/* 為'*','/', 將棧頂'*','/'符號出棧case '/':while( top>0 && (stop-1 = '*'

40、| stop-1 = T ) ) popc( s, &top, &c );sout off+ = c;/*這段循環(huán)如何用if語句實現(xiàn)？ */pushc( s, MAXN, &top, si ni );/* '*','/'符號入棧*/,存入數(shù)組*/符號入棧*/while( 6)sout off+ = c; sout off = '0： return 0;/*所有元素出棧/*加休止符*/存入數(shù)組void mai n()char *sin;/*輸入表達(dá)式指針，中綴表示*/char *sout;/*輸出表達(dá)式指針，后綴表示*/int i;

41、sin = (char *)malloc( 1024 * sizeof(char);sout = (char *)malloc( 1024 * sizeof(char);if( 7) printf("內(nèi)存申請錯誤!n");return;printf("請輸入表達(dá)式：)；gets( sin );if( 8) /*轉(zhuǎn)換成功*/printf("后綴表達(dá)式為：%sn", sout );switch( 9) case 0:printf(" 計算結(jié)果為:%dn", i ); break;case -1:printf(" 表達(dá)式

42、錯誤n");break;break;case -2:printf " 棧操作錯誤 n" ;break;實驗4隊列的根本操作四、參考程序程序1：題1鏈接隊列的根本操作函數(shù)#in clude<stdio.h>#in clude<alloc.h>typedef struct queue /* 定義隊列結(jié)構(gòu) */int data;/*隊列元素類型為int */struct queue *li nk;QUEUE;void EnQueue( QUEUE *head, QUEUE *tail, int x )/* 進(jìn)隊操作 */QUEUE *p;p =

43、(QUEUE *)malloc( sizeof(QUEUE);1p->li nk = NULL; if( *head = NULL )2else (*tail)->li nk = p;*tail = p;/*隊尾指向空*/*隊首為空，即為空隊列*/*新單元進(jìn)隊列尾*/*隊尾指向新入隊單元*/int DeQueue( QUEUE *head, QUEUE *tail, int *cp )/* 出隊操作 1:對空 */QUEUE *p;p = *head;if( *head = NULL )/* 隊空 */return 1;*cp = (*head)->data;*head =3

44、if( *head = NULL )/*隊首為空，隊尾也為空 */*tail = NULL;free( p );/* 釋放單元*/return 0;void OutputQueue( QUEUE *head )/* 輸出隊列中元素 */while 4() prin tf( "%d ", head->data );head = head->li nk;prin tf( "n");程序2:題2主程序：void mai n()QUEUE *head, *tail;int op, i;head = tail = NULL;/*1*/while( 1

45、)printf(請選擇操作，1:進(jìn)隊2 :出隊0 :退出);fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", &op );switch( op ) case 0:/* 退出 */return;case 1:/* 進(jìn)隊 */prin tf("請輸入進(jìn)隊元素：)；scan f( "%d", & );2 ;printf("隊內(nèi)元素為:n");OutputQueue( head );break;case 2:/* 出隊 */if( 3= 0 ) /* 出隊成功 */printf

46、(" 出隊元素為：%d,隊內(nèi)元素為:n" , i );OutputQueue( head );elseprin tf("隊空 n");break;程序3:題3環(huán)型隊列的根本操作函數(shù)#in clude<stdio.h> #in clude<alloc.h>/*定義環(huán)行順序隊列的存儲長度*/*進(jìn)隊操作,返回1:隊滿*/if( 1= *head )return 1;*tail =2 queue*tail = x;return 0;/*隊尾指針趕上隊首指針,隊滿*/*隊尾指針+1 */*元素入對尾*/#define MAXN 11 int

47、 En Queue( int *queue, int max n, int *head, int *tail, int x )int DeQueue( int *queue, int maxn, int *head, int *tail, int *cp )/*出隊操作返回1:隊空*/ if( *head = *tail )/*隊首=隊尾，說明隊列為空*/return 1;*head = ( *head + 1 ) % maxn;/* 隊首指針 +1 */3 /*取出隊首元素*/return 0;*輸出隊列中元素*/ void OutputQueue( int *queue, int maxn

48、, int h, int t ) / while( 4)/* */h = ( h + 1 ) % maxn;prin tf( "%d ", queueh);prin tf( "n");程序4:題4主程序：void mai n()int qMAXN;/*假設(shè)環(huán)行隊列的元素類型為int */int q_h=O, q_t=O; int op, i;/*初始化隊首,隊尾指針為0 */while( 1 )printf(請選擇操作，1:進(jìn)隊2 :出隊0 :退出);fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d"

49、;, &op );switch( op ) case 0:/* 退出 */return;case 1:/* 進(jìn)隊 */prin tf("請輸入進(jìn)隊元素：)；scan f( "%d", & );if( 1!= 0 )prin tf("隊列滿 n");else printf("入隊成功，隊內(nèi)元素為:n");OutputQueue( q, MAXN, q_h, q_t );break;case 2:/* 出隊 */if( 2= 0 ) /*出隊成功 */printf("出隊元素為：%d, 隊內(nèi)元素為:n&

50、quot; , i );OutputQueue( q, MAXN, q_h, q_t );elseprin tf("隊空 n");break;程序5:題5醫(yī)務(wù)室模擬程序#in clude<stdio.h>/*病人到達(dá)時間*/*病人處理時間*/#in clude<stdlib.h> #in clude<alloc.h> typedef struct int arrive; int treat;PATIENT; typedef struct queue PATIENT data; struct queue *li nk;QUEUE;/*定義隊

51、列結(jié)構(gòu)*/*隊列元素類型為int */void EnQueue( QUEUE *head, QUEUE *tail, PATIENT x )/* 進(jìn)隊操作 */*編寫進(jìn)隊操作子程序*/int DeQueue( QUEUE *head, QUEUE *tail, PATIENT *cp )/* 出隊操作 1:對空 */*編寫出隊操作子程序*/void OutputQueue( QUEUE *head )/* 輸出隊列中元素 */while( 1) printf( "到達(dá)時間：%d 處理時間：%dn", head->data.arrive,head->data.tr

52、eat );head = head->li nk;void InitData( PATIENT *pa, int n )/*生成病人到達(dá)及處理時間的隨機(jī)數(shù)列*/int parr = 0;/*前一個病人到達(dá)的時間*/int i;for( i = 0; i < n; i+ ) pai.arrive = parr + ran dom( 15 );/* 假設(shè)病人到達(dá)的時間間隔為014*/pai.treat = random( 9 ) + 1;/* 假設(shè)醫(yī)生處理時間為 19 */parr = pai.arrive;printf(第%d個病人到達(dá)時間為%d處理時間為%dn", i+1

53、, parr, pai.treat ); void mai n()QUEUE *head, *tail;PATIENT *p, curr;int n, i, finish;int no wtime;/*int dwait, pwait;head = tail = NULL;/*病人到達(dá)及處理時間信息，當(dāng)前出隊病人信息*/時鐘*/*醫(yī)生累計等待時間，病人累計等待時間*/*將隊列頭和尾置為空*/while( 1 )n = 0;no wtime = dwait = pwait = 0;printf("請輸入病人總數(shù)(120),= 0 :退出);scan f( "%d",

54、 &n );if( n = 0 )/*退出*/return;if( n > 20 | n < 0 )con ti nue;if( ( p = ( PATIENT *)malloc( n * sizeof( PATIENT ) ) ) =2)printf("內(nèi)存申請錯誤n");return;3/*生成病人到達(dá)及處理時間的隨機(jī)數(shù)列*/for( i = 0;4; ) /* 病人到達(dá)未結(jié)束或還有等待，處理*/if( head = NULL ) /*等待隊列為空 */if(pi.arrive - nowtime > 0)/*病人到達(dá)時間與上次處理時間遲*/5

55、 /*累計醫(yī)生等待時間*/no wtime = pi.arrive;/* 時鐘推進(jìn) */6 /*病人入隊*/DeQueue( &head, &tail, &curr );/* 出隊一位病人 */7 /*累計病人等待時間*/fin ish = nowtime + curr.treat;/*當(dāng)前病人處理結(jié)束時間 */while( i < n && pi.arrive <= finish )/*下一位病人到達(dá)時間在當(dāng)前病人等待時間結(jié)束之前，入隊*/8nowtime = finish;/*時鐘推進(jìn)到當(dāng)前病人處理結(jié)束時間*/free( p );/*釋放

56、空間*/printf( "醫(yī)生 等待時 間%d,病人平均等待時 間%.2fn", dwait, (float)pwait/n );程序6:題6招聘程序#in clude<stdio.h>#in clude<stdlib.h>#in clude<alloc.h>#define DEMARK 5/*按第二批錄用的扣分成績 */typedef struct stu /*定義招聘人員信息結(jié)構(gòu) */int no, total, z2, sortm, zi;/*編號，總成績，志愿，排除成績，錄取志愿號 */ struct stu *n ext;STU;typedef struct jobint lmt, count;/*方案錄用人數(shù)，已錄用人數(shù)*/STU *stu;/*錄用者有序隊列*/JOB;STU *head=NULL,