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

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

2、識(shí)例 1 1#include <stdio.h>int sumabc(int a, int b, int c) /* 求三個(gè)整數(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ù)備知識(shí)實(shí)驗(yàn)int main()/在 main 函數(shù)中調(diào)用上述聲明的函數(shù)int n; /記錄個(gè)數(shù)STUDENT stuMAXSIZE;/ 順序存儲(chǔ)結(jié)

4、構(gòu)，方法一 靜態(tài)一維數(shù)組。 /*順序存儲(chǔ)結(jié)構(gòu)，方法二 動(dòng)態(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 請(qǐng)輸入學(xué)生記錄個(gè)數(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 請(qǐng)選擇(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 輸入有誤 ,請(qǐng)重新輸入 ! n");/switch/while 1 /main第局部根底實(shí)驗(yàn)實(shí)驗(yàn)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)*/*存線性表元素*/存線性表長(zhǎng)度*/存list數(shù)組元素個(gè)數(shù)*/*初始化線性表*/if( (L->list = printf( exit( 1 );2)=NULL ) 1內(nèi)存申請(qǐng)錯(cuò)誤!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("請(qǐng)輸入元素值，輸入0結(jié)束插入操作:");fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", & );if( 1)

12、break;prin tf("請(qǐng)輸入插入位置：);scan f( "%d", &r );In sertList(2);printf(" 線性表為:);3while( 1 )printf("請(qǐng)輸入查找元素值，輸入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("請(qǐng)輸入刪除元素值，輸入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("請(qǐng)輸入刪除元素位置，輸

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ù)組有 個(gè)元素: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 );實(shí)驗(yà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é)點(diǎn)q:插入點(diǎn)前驅(qū)r:插入點(diǎn)后繼*/u = ( LIST * )malloc( sizeof(LIST);u->data = item;for( i = 0, r = *p ;2; i+ ) q = r;r = r->n ext;if( _J3)/*插入首結(jié)點(diǎn)或p為空指針*/*p = u;else4u_>next = r;void InsertList2( LIST *p,

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

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

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

21、tputList( LIST *p )/*輸出鏈表結(jié)點(diǎn)的鍵值*/while( 12) prin tf( "%4d", p->data );p = p->next;/*遍歷下一個(gè)結(jié)點(diǎn) */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("請(qǐng)選擇操作1:指定位置追加2:升序追加3:查找結(jié)點(diǎn)n");printf( "4:刪除結(jié)點(diǎn)5:輸出結(jié)點(diǎn) 6:清空鏈表0 :退出n");fflush( stdin ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", &op );switch( op ) case 0:/* 退出 */return;case 1:/*指定位置追加結(jié)點(diǎn)*/printf("請(qǐng)輸入新增結(jié)點(diǎn)鍵值和位置：);scan f "%d%d", &i, & rc ;1；break;case

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

24、quot;, & ;rc =3 ;if rc = 0 printf"刪除成功 n", rc ;elseprin tf" 沒找到 n"break;case 5:/*輸出結(jié)點(diǎn)*/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( " 請(qǐng)輸入鏈表的元素， -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ù)序號(hào)的

27、結(jié)點(diǎn)3/將q從原a鏈表中刪除r->next = q;/將q結(jié)點(diǎn)參加到b鏈表的末尾4 / r指向b鏈表的最后一個(gè)結(jié)點(diǎn)p = p->next;/ p指向原a鏈表的奇數(shù)序號(hào)的結(jié)點(diǎn)r->next = NULL;/將生成b鏈表中的最后一個(gè)結(jié)點(diǎn)的next域置空 void mai n()NODE *a, *b;in put( &a );printf("鏈表a的元素為:n");output( a );5printf(鏈表a的元素(奇數(shù)序號(hào)結(jié)點(diǎn))為:n");output( a );printf(" 鏈表b的元素(偶數(shù)序號(hào)結(jié)點(diǎn))為:n")

28、; output( b );實(shí)驗(yàn)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(請(qǐng)選擇操作，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("請(qǐng)輸入進(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配對(duì)函數(shù)int correct( char *exp, int max )/*傳入?yún)?shù)為表達(dá)式、表達(dá)式長(zhǎng)度，返回0:成功，返回1:錯(cuò)誤*/int flag = 0;/*括號(hào)匹配標(biāo)志，0:正確*/char sMAXN;/* 定義棧 */int top = 0;/*棧指針為0,表示空棧*/char c;int i;for( i = 0;1; i+ ) /*循環(huán)條件為

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

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

34、t; ) = 0 )4if( 5)printf("表達(dá)式內(nèi)容為：n%sn表達(dá)式括號(hào)不匹配n" , exp );elseprintf("表達(dá)式括號(hào)匹配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ù)運(yùn)算 */*編寫算術(shù)運(yùn)算子程序*/int operate( char *str, i nt *exp ) 式錯(cuò)誤-2:棧滿*/*計(jì)算后綴表達(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á)式太長(zhǎng)，棧滿); return -2;else if( c = '+' | c = '-' | c = '*' | c = '/') /* 運(yùn)算符*/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、括號(hào),括號(hào)入棧*/pushc( s, MAXN, &top, sini);break;case ')':/*右括號(hào),將棧中左括號(hào)前的兀素出棧，存入數(shù)組*/while( 1 )if( popc( s, &top, &c ) != 0 )/* 棧空 */printf表達(dá)式括號(hào)不匹配n"return -1;if( c ='(') break;sout off+ = c;/*找到匹配的括號(hào)*/*棧頂元素入數(shù)組*/break;case '+':/* 為'+','-'，將棧中左括號(hào)前的元素出棧

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

40、| stop-1 = T ) ) popc( s, &top, &c );sout off+ = c;/*這段循環(huán)如何用if語句實(shí)現(xiàn)？ */pushc( s, MAXN, &top, si ni );/* '*','/'符號(hào)入棧*/,存入數(shù)組*/符號(hào)入棧*/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)存申請(qǐng)錯(cuò)誤!n");return;printf("請(qǐng)輸入表達(dá)式：)；gets( sin );if( 8) /*轉(zhuǎn)換成功*/printf("后綴表達(dá)式為：%sn", sout );switch( 9) case 0:printf(" 計(jì)算結(jié)果為:%dn", i ); break;case -1:printf(" 表達(dá)式

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

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

44、if( *head = NULL )/*隊(duì)首為空，隊(duì)尾也為空 */*tail = NULL;free( p );/* 釋放單元*/return 0;void OutputQueue( QUEUE *head )/* 輸出隊(duì)列中元素 */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(請(qǐng)選擇操作，1:進(jìn)隊(duì)2 :出隊(duì)0 :退出);fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d", &op );switch( op ) case 0:/* 退出 */return;case 1:/* 進(jìn)隊(duì) */prin tf("請(qǐng)輸入進(jìn)隊(duì)元素：)；scan f( "%d", & );2 ;printf("隊(duì)內(nèi)元素為:n");OutputQueue( head );break;case 2:/* 出隊(duì) */if( 3= 0 ) /* 出隊(duì)成功 */printf

46、(" 出隊(duì)元素為：%d,隊(duì)內(nèi)元素為:n" , i );OutputQueue( head );elseprin tf("隊(duì)空 n");break;程序3:題3環(huán)型隊(duì)列的根本操作函數(shù)#in clude<stdio.h> #in clude<alloc.h>/*定義環(huán)行順序隊(duì)列的存儲(chǔ)長(zhǎng)度*/*進(jìn)隊(duì)操作,返回1:隊(duì)滿*/if( 1= *head )return 1;*tail =2 queue*tail = x;return 0;/*隊(duì)尾指針趕上隊(duì)首指針,隊(duì)滿*/*隊(duì)尾指針+1 */*元素入對(duì)尾*/#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 )/*出隊(duì)操作返回1:隊(duì)空*/ if( *head = *tail )/*隊(duì)首=隊(duì)尾，說明隊(duì)列為空*/return 1;*head = ( *head + 1 ) % maxn;/* 隊(duì)首指針 +1 */3 /*取出隊(duì)首元素*/return 0;*輸出隊(duì)列中元素*/ 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)行隊(duì)列的元素類型為int */int q_h=O, q_t=O; int op, i;/*初始化隊(duì)首,隊(duì)尾指針為0 */while( 1 )printf(請(qǐng)選擇操作，1:進(jìn)隊(duì)2 :出隊(duì)0 :退出);fflush( std in ); /*清空標(biāo)準(zhǔn)輸入緩沖區(qū)*/scan f( "%d"

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

50、quot; , i );OutputQueue( q, MAXN, q_h, q_t );elseprin tf("隊(duì)空 n");break;程序5:題5醫(yī)務(wù)室模擬程序#in clude<stdio.h>/*病人到達(dá)時(shí)間*/*病人處理時(shí)間*/#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;/*定義隊(duì)

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

52、eat );head = head->li nk;void InitData( PATIENT *pa, int n )/*生成病人到達(dá)及處理時(shí)間的隨機(jī)數(shù)列*/int parr = 0;/*前一個(gè)病人到達(dá)的時(shí)間*/int i;for( i = 0; i < n; i+ ) pai.arrive = parr + ran dom( 15 );/* 假設(shè)病人到達(dá)的時(shí)間間隔為014*/pai.treat = random( 9 ) + 1;/* 假設(shè)醫(yī)生處理時(shí)間為 19 */parr = pai.arrive;printf(第%d個(gè)病人到達(dá)時(shí)間為%d處理時(shí)間為%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á)及處理時(shí)間信息，當(dāng)前出隊(duì)病人信息*/時(shí)鐘*/*醫(yī)生累計(jì)等待時(shí)間，病人累計(jì)等待時(shí)間*/*將隊(duì)列頭和尾置為空*/while( 1 )n = 0;no wtime = dwait = pwait = 0;printf("請(qǐng)輸入病人總數(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)存申請(qǐng)錯(cuò)誤n");return;3/*生成病人到達(dá)及處理時(shí)間的隨機(jī)數(shù)列*/for( i = 0;4; ) /* 病人到達(dá)未結(jié)束或還有等待，處理*/if( head = NULL ) /*等待隊(duì)列為空 */if(pi.arrive - nowtime > 0)/*病人到達(dá)時(shí)間與上次處理時(shí)間遲*/5

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

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