《数据结构实验与实训教程（第4版）》程序代码

目 录

第一部分 预备知识 ....................................................................................................... 1

预备知识 ............................................................................................................... 1 预备知识实验 ......................................................................................................... 2 第二部分 基础实验 ....................................................................................................... 4

实验1 线性表的基本操作 ..................................................................................... 4 实验2 链表的基本操作 ......................................................................................... 9 实验3 栈的基本操作 .......................................................................................... 15 实验4 队列的基本操作 ....................................................................................... 22 实验5 数组的基本操作 ....................................................................................... 32 实验6 字符串的基本操作 ................................................................................... 36 实验7 二叉树的基本操作 ................................................................................... 41 实验8 树的遍历和哈夫曼树 ................................................................................ 46 实验9 图的基本操作 .......................................................................................... 53 实验10 排 序................................................................................................... 59 实验11 查 找................................................................................................... 64 第三部分 课程设计实验 .............................................................................................. 69

实验1 航空客运订票系统 ..................................................................................... 69 实验2 汉诺塔游戏程序......................................................................................... 75 实验3 全屏幕编辑程序设计 .................................................................................. 79 实验4 旅游路线安排模拟系统 .............................................................................. 90 实验6 最小生成树kruskal算法 ............................................................................. 93

i

第一部分 预备知识

预备知识

例1．1

#include

int sumabc(int a, int b, int c) /* 求三个整数之和*/

{ 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)); /* 在输出语句中直接调用函数sumabc( ) */ printf(“\\n mmm”,x,y,z); display();/* 画一条线 */

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

sabc =sumabc(x, y, z); /* 在赋值语句中调用函数sumabc( ) */ printf(“\\n “ sum=%d”, sabc);

printf(“\\n mmm”,x,y,z); display();/* 画一条线 */ }

例1.2

int sumabc(int *a, int b, int c) {

int s; *a=b+c;

s=*a+b+c;

1

return s;

}

预备知识实验

int main()

{ //在main函数中调用上述声明的函数 int n; //记录个数

STUDENT stu[MAXSIZE;// 顺序存储结构，方法一 静态一维数组。 /*

顺序存储结构，方法二 动态一维数组，用malloc函数分配如下： STUDENT *stu;

stu=( STUDENT *) malloc(sizeof(STUDENT)* MAXSIZE);// 内存空间的分配 注意：分配空间可用malloc()函数, 释放空间用free()函数，如free(stu); */

int index;

printf(\请输入学生记录个数n=\ scanf(%d”,&n); InputStu(stu, n); // 预先处理输入, 建表

while(1) // 永真循环,重复显示菜单, 直至退出

{

printf(\学生信息管理主菜单**********************\\n\ printf(\显示学生信息\\n\ printf(\查找学生信息\\n\ printf(\修改学生信息\\n\ printf(\添加学生信息\\n\ printf(\退出\\n\\n\);

printf(\请选择(1~5): \

scanf(\%d\

printf(\ switch(index) {

case 1: OutputStu(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\); }//switch

2

}//while（1） }//main

3

第二部分 基础实验

实验1 线性表的基本操作

四、参考程序

程序1：题1 线性表基本操作函数 #include #include #include

struct LinearList ／*定义线性表结构*/ { int *list; /* 存线性表元素 */ int size; /* 存线性表长度 */ int MaxSize; /* 存list数组元素个数 */ };

typedef struct LinearList LIST;

void InitList( LIST *L, int ms ) /* 初始化线性表 */ { if( (L->list = 1 ) == NULL ) { printf( \内存申请错误!\\n\ exit( 1 ); }

2

L->MaxSize = ms;

}

int InsertList( LIST *L, int item, int rc )

/* item:记录值 rc:插入位置 */

{

int i; if( 3 ) /* 线性表已满 */ return -1; if( rc < 0 ) /* 插入位置为 0 --> L->size */

4

rc = 0;

if( 4 ) rc = L->size;

for( i = L->size - 1; i >= rc; i-- ) /* 将线性表元素后移 */ 5 L->list[rc] = item; L->size ++; return 0;

}

void OutputList( LIST *L ) /* 输出线性表元素 */ { int i; for( i = 0; 6 i++ ) printf( \ printf( \}

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 < 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 --; return i;

}

5

return -1; }

int DeleteList2( LIST L, int rc ) /* 删除指定位置的线性表记录 */ {

8 /*编写删除指定位置的线性表记录子程序*/ }

程序2：题2

void main() { LIST LL;

int i, r; printf( \addr=%p\\tsize=%d\\tMaxSize=%d\\n\LL.list, LL.size, LL.MaxSize ); InitList( &LL, 100 ); printf( \addr=%p\\tsize=%d\\tMaxSize=%d\\n\LL.list, LL.size, LL.MaxSize ); while( 1 ) { printf( \请输入元素值，输入0结束插入操作:\ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \ if( 1 ) break; printf( \请输入插入位置：\

scanf( \

InsertList( 2 ); printf( \线性表为: \ 3

}

while( 1 ) { printf( \请输入查找元素值，输入0结束查找操作:\

fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \ if( i == 0 ) break;

r = 4 if( r < 0 ) printf( \没找到\\n\ else

6

printf( \有符合条件的元素，位置为：%d\\n\}

while( 1 ) { printf( \请输入删除元素值，输入0结束查找操作:\ fflush( stdin ); /* 清空标准输入缓冲区 */

scanf( \ if( i == 0 ) break;

r = 5 if( r < 0 ) printf( \没找到\\n\ else { printf( \有符合条件的元素，位置为：%d\\n线性表为：\ OutputList( &LL ); } } while( 1 ) { printf( \请输入删除元素位置，输入0结束查找操作:\ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \ if( r == 0 ) break;

i = 6 if( i < 0 ) printf( \位置越界\\n\ else { printf( \线性表为：\ OutputList( &LL ); } } }

程序4：题4 #define X 10

#define Y 30 #define N 20

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

7

#include

void del( int *A, int *n, int x, int y ) { int i, j; for( i = j = 0; i < *n; i++ ) if( A[i] > y || A[i] < x ) // 不在x到y之间，则保留 1 ; 2 = j; }

void output( int *A, int n ) { int i; printf( \数组有%d个元素:\\n\ for( i = 0; i < n; i++ ) { printf( \ if( ( i + 1 ) % 10 == 0 ) printf( \ }

printf( \}

void main() {

int n; n = N; output( A, n ); 3 ; output( A, n ); }

8

实验2 链表的基本操作

四、参考程序

程序1：题1 链表基本操作函数 #include #include typedef struct list { int data;

struct list *next; }LIST;

void InitList( LIST **p ) /* 初始化链表 */ {

1 /*编写初始化链表子程序*/ }

void InsertList1( LIST **p, int item, int rc ) /* 向链表指定位置[rc]插入元素[item] */ {

int i; LIST *u, *q, *r;

/* u:新结点 q:插入点前驱 r:插入点后继 */

u = ( LIST * )malloc( sizeof(LIST) ); u->data = item;

for( i = 0, r = *p ; 2 ; i++ ) { q = r; r = r->next; }

if( 3 ) /* 插入首结点或p为空指针 */ *p = u; else

4

u->next = r; }

void InsertList2( LIST **p, int item )

/* 向有序链表[p]插入键值为[item]的结点 */

9

{

LIST *u, *q, *r;

/* u:新结点 q:插入点前驱 r:插入点后继 */

u = ( LIST * )malloc( sizeof(LIST) ); u->data = item;

for( r = *p; 5 && r->data < item; q = r, r = r->next ) ; /* 从链表首结点开始顺序查找 */ if( r == *p )

/* 插入首结点或p为空指针 */

6 else

q->next = u; u->next = r; }

/* 删除键值为[item]的链表结点, 返回0: 删除成功 1: 没找到 */ int DeleteList( LIST **p, int item ) {

LIST *q, *r; /* q:结点前驱 r:结点后继 */ q = *p;

if( q == NULL )

/* 链表为空 */

return 1;

if( q->data == 7 ) { /* 要删除链表首结点 */ p = q->link; /* 更改链表首指针 */

8 /* 释放被删除结点的空间 */ return 0; /* 删除成功 */ }

for( ; 9 && 10 ; r = q, q = q->next ) ; /* 寻找键值为[item]的结点 */ if( q->data == item ) { /* 找到结点 */

q->next=r->next /* 被删结点从链表中脱离 */ free( q ); /* 释放被删除结点的空间 */ return 0; /* 删除成功 */ }

return 1; /* 没有指定值的结点, 删除失败 */ }

/* 查找键值为[item]的链表结点位置, 返回>=1: 找到 -1: 没找到 */ int FindList( LIST *p, int item ) { int i;

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

10

; /* 查找键值为[item]的结点 */ return ( p == NULL ) ? -1 : i; /* 找到返回[i] */ }

void OutputList( LIST *p ) /* 输出链表结点的键值 */

{

while( 12 ) { printf( \ p = p->next; /* 遍历下一个结点 */ } }

void FreeList( LIST **p ) /* 释放链表空间 */

{

LIST *q, *r;

for( q = *p; q != NULL; ) { 13 q = q->next; 14 }

*p = NULL; /* 将链表首指针致空 */

}

程序2：题2

void main() {

LIST *p; int op, i, rc;

InitList( &p );

/* 初始化链表 */

while( 1 ) { printf( \请选择操作 1：指定位置追加 2: 升序追加 3: 查找结点\\n\ ); printf( \ 4: 删除结点 5: 输出结点 6: 清空链表 0：退出\\n\ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \%d\ switch( op ) { case 0: /* 退出 */ return; case 1: /* 指定位置追加结点 */

printf( \请输入新增结点键值和位置：\ );

11

scanf( \%d%d\, &rc ); 1 ; break; case 2: /* 按升序追加结点 */ printf( \请输入新增结点键值：\ scanf( \%d\ ); InsertList2( &p, i ); break; case 3: /* 查找结点 */ printf( \请输入要查找结点的键值：\ scanf( \%d\ ); rc = 2 ; if( rc > 0 )

printf( \ 位置为[%d]\\n\

else

printf( \ 没找到\\n\ break; case 4: /* 删除结点 */

printf( \请输入要删除结点的键值：\

scanf( \%d\ );

rc = 3 ; if( rc == 0 ) printf( \ 删除成功\\n\, rc ); else

printf( \ 没找到\\n\ break; case 5: /* 输出结点 */ printf( \链表内容为:\\n\ ); 4 ; break; case 6: /* 清空链表 */

5 ;

break;

} } }

程序3：题3

#include #include

12

typedef struct node { int x; struct node *next; }NODE;

void input( NODE **a ) { NODE *p, *q; int i;

printf( \请输入链表的元素，-1表示结束\\n\ *a = NULL; while( 1 ) { scanf( \ 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; a != NULL; i++, a = a->next ) { printf( \ if( ( i + 1 ) % 10 == 0 ) printf( \ }

printf( \}

void disa( NODE *a, NODE **b ) {

13

NODE *r, *p, *q; p = a;

r = *b = ( a == NULL ) ? NULL : a->next; // 如果链表a为空，则链表b也为空 while( 1 && 2 ) { q = p->next; // q指向偶数序号的结点 3 // 将q从原a链表中删除

r->next = q; // 将q结点加入到b链表的末尾 4 // r指向b链表的最后一个结点

p = p->next; // p指向原a链表的奇数序号的结点

} r->next = NULL;

// 将生成b链表中的最后一个结点的next域置空

}

void main() { NODE *a, *b; input( &a );

printf( \链表a的元素为:\\n\ output( a ); 5 printf( \链表a的元素（奇数序号结点）为:\\n\ output( a ); printf( \链表b的元素（偶数序号结点）为:\\n\ output( b ); }

14

实验3 栈的基本操作

四、参考程序

程序1：题1 栈的基本操作函数

#include #define MAXN 10

/* 栈的最大容量 */

/* 定义栈的类型为int */

int push( int *stack, int maxn, int *toppt, int x ) /* 进栈函数 */

{ if( *toppt >= maxn ) /* 1 */ return 1;

2 /* 元素进栈 */

++(*toppt); /* 栈顶指针+1 */ return 0; /* 进栈成功 */ }

int pop( int *stack, int *toppt, int *cp ) /*出栈函数*/ { if( 3 ) /* 栈空，出栈失败，返回1 */ return 1; --(*toppt); /* 栈顶指针-1 */ 4 return 0; /* 出栈成功 */ }

void OutputStack( int *stack, int toppt ) /* 输出栈元素 */ { int i; for( i = 5 ; i >= 0; i-- ) printf( \ printf( \}

程序2：题2 主函数 void main() {

15

int s[MAXN], i; /* 定义栈 */ int top = 0; /* 设置为空栈 */ int op; while( 1 ) { printf( \请选择操作，1：进栈 2：出栈 0：退出 \

fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \switch( op ) {

case 0: /* 退出 */ return; case 1: /* 进栈 */ printf( \请输入进栈元素：\ scanf( \ if( 1 ) { /* 进栈成功 */ printf( \进栈成功，栈内元素为:\\n\ OutputStack( s, top );

} else printf( \栈满\\n\ break; case 2: /* 出栈 */ if( 2 ) { /* 出栈成功 */ printf( \出栈元素为: [%d] , 栈内元素为:\\n\ }

}

}

3 } else printf( \栈空\\n\break;

程序3：题3 配对函数

int correct( char *exp, int max ) /* 传入参数为表达式、表达式长度,返回0:成功,返回1:错误*/ {

int flag = 0; char s[MAXN]; int top = 0; /* 括号匹配标志，0: 正确 */ /* 定义栈 */

/* 栈指针为0，表示空栈 */

16

char c; int i; for( i = 0; 1 ; i++ ) {

/* 循环条件为表达式未结束且括号匹配 */ if( exp[i]=='(' || exp[i]=='[' || exp[i]=='{' } push( s, MAXN, &top, exp[i] );

if( exp[i]==')' || exp[i]==']' || exp[i]=='}' ) {/* 遇到},},}, 出栈 */ 2 /* 置出栈结果, 栈空出错 */

if( ( exp[i]==')' && c!='(' ) || ( exp[i]==']' && c!='[' )

|| ( exp[i]=='}' && c!='{' ) ) /* 括号不匹配 */

flag = 1; } } if( 3 ) /* 栈不为空，表明还有(,[,{符号没匹配 */ flag = 1; return flag; }

void main() { char s[MAXN], c; /* 定义栈 */ char exp[1024]; int top = 0; /* 设置为空栈 */ while( 1 ) { printf( \请输入表达式, 输入0退出: \ gets( exp ); /* 从标准输入中读取表达式 */ exp[MAXN] = '\\0'; /* 表达式长度 <= MAXN */

if( strcmp( exp, \

4 if( 5 ) printf( \表达式内容为：\\n%s\\n表达式括号不匹配\\n\ else printf( \表达式括号匹配\\n\

} }

程序4：题4 波兰表达式 #include #include #define MAXN 100 /* 栈的最大容量 */

17

int pushc( )/* char型元素进栈函数 */ { /*编写进栈子程序*/ }

int popc( char *stack, int *toppt, char *cp ) /* char型元素出栈函数 */ { }

/*编写出栈子程序*/

int eval( ) /* 算术运算 */ { /*编写算术运算子程序*/ }

int operate( char *str, int *exp ) /* 计算后缀表达式的值, 返回0:成功 -1:表达式错误 -2:栈满 */ { char c; int opd1, opd2, temp, c1; int s[MAXN]; int i;

int top = 0;

for( i = 0; str[i] != '\\0'; i++ ){ c = str[i]; if( c >= '0' && c <= '9' ){ /* 数字进栈 */ c1 = c - '0'; /* 将字符转换成数字值 */

if( push( s, MAXN, &top, c1 ) != 0 ){ printf( \表达式太长, 栈满\ 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 ;

18

} else return -1; }

2 /* 取出结果 */

if( top != 0 ) /* 栈非空 */ return -1; return 0;

}

int trans( char *sin, char *sout ) /* 将中缀表达式转换成后缀, 返回0: 处理成功 */ { char s[MAXN], c; /* 定义栈, 栈元素 */ 3 /* 设置为空栈 */ int off = 0; /* 数组下标 */

int i;

for( i = 0; sin[i] != '\\0'; i++ ) /* 遇到休止符, 表示表达式输入结束 */ if( sin[i] >= '0' && sin[i] <= '9' ) /* 输入数字, 进数组 */ sout[ 4 ] = sin[i]; else switch( sin[i] ) { case '(': /* 左括号, 括号入栈 */ pushc( s, MAXN, &top, sin[i] );

break; case ')': /* 右括号, 将栈中左括号前的元素出栈, 存入数组 */ while( 1 ){ if( popc( s, &top, &c ) != 0 ){ /* 栈空 */ printf( \表达式括号不匹配\\n\ return -1;

} if( c == '(' ) /* 找到匹配的括号 */ break;

sout[ off++ ] = c; }

break;

/* 栈顶元素入数组 */

case '+': /* 为'+','-'，将栈中左括号前的元素出栈, 存入数组 */ case '-': while( top > 0 && s[top-1] != '(' ) { 5

19

sout[ off++ ] = c; } pushc( s, MAXN, &top, sin[i] ); /* '+','-'符号入栈 */ break; case '*': /* 为'*','/', 将栈顶'*','/'符号出栈, 存入数组 */ case '/': while( top>0 && (s[top-1] == '*' || s[top-1] == '/' ) ){ popc( s, &top, &c );

sout[ off++ ] = c;

} /*这段循环如何用if语句实现？ */

pushc( s, MAXN, &top, sin[i] ); /* '*','/'符号入栈 */ break; } while( 6 ) /* 所有元素出栈, 存入数组 */ sout[ off++ ] = c; sout[ off ] = '\\0'; /* 加休止符 */ return 0; }

void main() { char *sin; /* 输入表达式指针, 中缀表示 */ char *sout; /* 输出表达式指针, 后缀表示 */

int i; sin = (char *)malloc( 1024 * sizeof(char) ); sout = (char *)malloc( 1024 * sizeof(char) ); if( 7 ) { printf( \内存申请错误!\\n\ return; }

printf( \请输入表达式: \

gets( sin );

if( 8 ) { /* 转换成功 */ printf( \后缀表达式为:[%s]\\n\ switch( 9 ) { case 0: printf( \计算结果为: [%d]\\n\ break; case -1:

printf( \表达式错误\\n\

20

} } }

break; case -2: printf( \栈操作错误\\n\ break;

21

实验4 队列的基本操作

四、参考程序

程序1：题1 链接队列的基本操作函数 #include #include

typedef struct queue { /* 定义队列结构 */ int data; /* 队列元素类型为int */ struct queue *link; }QUEUE;

void EnQueue( QUEUE **head, QUEUE **tail, int x ) /* 进队操作 */ { QUEUE *p;

p = (QUEUE *)malloc( sizeof(QUEUE) ); 1 p->link = NULL; /* 队尾指向空 */

if( *head == NULL ) /* 队首为空，即为空队列 */ 2 else {

(*tail)->link = p; /* 新单元进队列尾 */

*tail = p; /* 队尾指向新入队单元 */ } }

int DeQueue( QUEUE **head, QUEUE **tail, int *cp ) /* 出队操作 1:对空 */ { QUEUE *p;

p = *head; if( *head == NULL ) /* 队空 */ return 1; *cp = (*head)->data; *head = 3 if( *head == NULL ) /* 队首为空，队尾也为空 */ *tail = NULL; free( p ); /* 释放单元 */ return 0;

22

}

void OutputQueue( QUEUE *head ) /* 输出队列中元素 */ { while 4 () { printf( \ head = head->link; }

printf( \

程序2：题2 主程序： void main() { QUEUE *head, *tail; int op, i; head = tail = NULL; /* 1 */

while( 1 ) { printf( \请选择操作，1：进队 2：出队 0：退出 \ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \ switch( op ) { case 0: /* 退出 */

return;

case 1: /* 进队 */

printf( \请输入进队元素：\ scanf( \ 2 ; printf( \队内元素为:\\n\ OutputQueue( head ); break; case 2: /* 出队 */ if( 3 == 0 ) { /* 出队成功 */ printf( \出队元素为: [%d] , 队内元素为:\\n\ OutputQueue( head ); }

else printf( \队空\\n\

break;

}

23

}

}

程序3：题3 环型队列的基本操作函数 #include #include

#define MAXN 11 /* 定义环行顺序队列的存储长度 */

int EnQueue( int *queue, int maxn, int *head, int *tail, int x )/* 进队操作, 返回1:队满 */

{ if( 1 == *head ) /* 队尾指针赶上队首指针, 队满 */ return 1;

*tail = 2 /* 队尾指针+1 */ queue[*tail] = x; /* 元素入对尾 */ return 0; }

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, int h, int t ) /* 输出队列中元素 */ { while( 4 ) { /* */ h = ( h + 1 ) % maxn;

printf( \

}

printf( \}

程序4：题4 主程序： void main() { int q[MAXN]; /* 假设环行队列的元素类型为int */

24

int q_h=0, q_t=0; /* 初始化队首,队尾指针为0 */ int op, i;

while( 1 ) { printf( \请选择操作，1：进队 2：出队 0：退出 \ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \

switch( op ) {

case 0: /* 退出 */ return; case 1: /* 进队 */ printf( \请输入进队元素：\ scanf( \ if( 1 != 0 ) printf( \队列满\\n\ else {

printf( \入队成功, 队内元素为:\\n\ OutputQueue( q, MAXN, q_h, q_t ); } break; case 2: /* 出队 */ if( 2 == 0 ) {/* 出队成功 */ printf( \出队元素为: [%d] , 队内元素为:\\n\

OutputQueue( q, MAXN, q_h, q_t ); } else printf( \队空\\n\

break;

}

}

}

程序5：题5 医务室模拟程序 #include #include #include typedef struct { int arrive; /* 病人到达时间 */

int treat;

/* 病人处理时间 */

25

}PATIENT;

typedef struct queue { /* 定义队列结构 */ PATIENT data; /* 队列元素类型为int */ struct queue *link; }QUEUE;

void EnQueue( QUEUE **head, QUEUE **tail, PATIENT x ) /* 进队操作 */ { /*编写进队操作子程序*/ }

int DeQueue( QUEUE **head, QUEUE **tail, PATIENT *cp ) /* 出队操作 1:对空 */ {

/*编写出队操作子程序*/ }

void OutputQueue( QUEUE *head ) /* 输出队列中元素 */ { while( 1 ) { printf( \到达时间: [%d] 处理时间: [%d]\\n \head->data.arrive,

head->data.treat ); head = head->link; } }

void InitData( PATIENT *pa, int n ) /* 生成病人到达及处理时间的随机数列 */ {

int parr = 0; /* 前一个病人到达的时间 */ int i; for( i = 0; i < n; i++ ) { pa[i].arrive = parr + random( 15 ); /* 假设病人到达的时间间隔为 0~14 */ pa[i].treat = random( 9 ) + 1; /* 假设医生处理时间为 1~9 */ parr = pa[i].arrive;

printf( \第[%d]个病人到达时间为[%d]处理时间为[%d]\\n\ } }

void main()

26

{ QUEUE *head, *tail; PATIENT *p, curr; /* 病人到达及处理时间信息, 当前出队病人信息 */ int n, i, finish; int nowtime; /* 时钟 */ int dwait, pwait; /* 医生累计等待时间, 病人累计等待时间 */ head = tail = NULL; while( 1 ) {

/* 将队列头和尾置为空 */

n = 0;

nowtime = dwait = pwait = 0; printf( \请输入病人总数(1~20),= 0：退出 \ scanf( \ if( n == 0 ) /* 退出 */ return; if( n > 20 || n < 0 ) continue;

if( ( p = ( PATIENT *)malloc( n * sizeof( PATIENT ) ) ) == 2 ) { printf( \内存申请错误\\n\ return;

} 3 /* 生成病人到达及处理时间的随机数列 */ for( i = 0; 4 ; ) {/* 病人到达未结束或还有等待, 处理 */ if( head == NULL ) { /* 等待队列为空 */

if(p[i].arrive - nowtime > 0)/* 病人到达时间与上次处理时间迟 */ 5 /* 累计医生等待时间 */ nowtime = p[i].arrive; /* 时钟推进 */ 6 /* 病人入队 */

}

DeQueue( &head, &tail, &curr ); /* 出队一位病人 */ 7 /* 累计病人等待时间 */ finish = nowtime + curr.treat; /* 当前病人处理结束时间 */ while( i < n && p[i].arrive <= finish ) /* 下一位病人到达时间在当前病人等待时间结束之前, 入队 */ 8 nowtime = finish; /* 时钟推进到当前病人处理结束时间 */

}

free( p ); /* 释放空间 */ printf( \医生等待时间[%d], 病人平均等待时间[%.2f]\\n\dwait, (float)pwait/n );

27

}

}

程序6：题6 招聘程序 #include #include

#include #define DEMARK 5 /* 按第二批录用的扣分成绩 */ typedef struct stu { /* 定义招聘人员信息结构 */

int no, total, z[2], sortm, zi; /* 编号, 总成绩, 志愿, 排除成绩, 录取志愿号 */ struct stu *next; }STU;

typedef struct job{ int lmt, count; /* 计划录用人数, 已录用人数 */ STU *stu; /* 录用者有序队列 */ }JOB;

STU *head=NULL, *over=NULL;

int all;

void OutPutStu( STU *p ) /* 输出应聘人员有序队列中编号和成绩 */ { for( ; 1 ; p = p->next ) printf( \}

void FreeStu( STU **p ) { STU *q; while( *p != NULL ) { q = *p; 2 free( q ); }

}

void Insert( STU **p, STU *u ) {

/* 释放应聘人员空间 */

/* 按排除成绩从大到小顺序插队 */

STU *v, *q; /* 插队元素的前后元素指针 */ for( q = *p; q != NULL; v = q, q = q->next ) if( 3 ) /* 队中工人成绩<插入元素成绩 */ break;

28

if( q == *p ) /* 插入到队首 */ *p = u; else /* 不为队首插入 */ 4 u->next = q; /* 新元素的后继元素指针 */ }

int InitJob( JOB **h, int n, int *all ) /* 随机生成工种信息 */

{

int i;

JOB *p; *all = 0;

printf( \工种信息{工种号(计划招聘人数)}\\n\ if( ( p = ( JOB * )malloc( n * sizeof( JOB ) ) ) == NULL ) { printf( \内存申请错误!\\n\ return -1; } for( i = 0; i < n; i++ ) { p[i].lmt = random( 10 ) + 1; /* 假设工种招聘人数为 1~10 */ p[i].count = 0; p[i].stu = NULL; *all += p[i].lmt;

printf( \ } printf( \总招聘人数[%d]\\n\ *h = p;

return 0; }

int InitStu( STU **h, int n, int m ) /* 随机生成应聘人员信息 */ { STU *p; int i;

printf( \应聘人员信息{编号, 成绩, 志愿1, 志愿2}\\n\ for( i = 0; i < n; i++ ) { if( ( p = ( STU * )malloc( sizeof( STU ) ) ) == NULL ) { printf( \内存申请错误!\\n\ return -1; } p->no = i;

29

p->total = p->sortm = random( 201 ); p->z[0] = random( m ); /* 应聘人员第一志愿 0 ~ m-1 */ p->z[1] = random( m ); /* 应聘人员第二志愿 0 ~ m-1 */ p->zi = 0; /* 录取志愿初始化为0, 即第一志愿 */ printf( \ Insert( h, p ); } printf( \ return 0; }

void main() { int m;

/* 工种总数, 编号为 0 ~ M-1 */ int n; /* 应聘人员总数 */

JOB *rz; int all;

/* 计划招聘人员总数 */

STU *head=NULL, *over=NULL; /* 应聘人员队列, 落聘人员队列 */ STU *p; int i; while( 1 ) { m = n = 0; printf( \请输入工种总数(1~20),= 0：退出 \ scanf( \ if( m == 0 ) /* 退出 */ return;

if( m > 20 || m < 0 )

continue; if( 5 != 0 ) /* 生成工种信息 */ return; printf( \请输入应聘人员总数(5~400),= 0：退出 \ scanf( \ if( n == 0 ) /* 退出 */ return;

if( n < 5 || n > 400 ) {

free( rz ); /* 释放工种信息空间 */ continue; } if( 6 != 0 ) /* 生成应聘人员信息 */

30

return;

printf( \应聘人员队列\\n\ OutPutStu( head ); While( 7 ) { /* 当人员没招满且队列不为空 */ p = head; /* 取应聘人员队首指针 */ head = head->next; /* 队首指针下移 */ i = p->z[ p->zi ]; /* 取该应聘人员的应聘工种号 */ if( rz[i].count < rz[i].lmt ) { /* 该工种人员没招满 */ rz[i].count++; 8 all--; continue; }

if( p->zi >= 1 ) { p->next = over; /* 该工人入落聘者队列 */

over = p;

continue;

} p->sortm -= DEMARK; /* 该工种已招满, 工人分数降档 */ p->zi = 1; /* 该工人改为第二志愿 */ 9 /* 10 */ }

for( i = 0; i < m; i++ ) { /* 打印各工种招聘情况 */ printf( \工种[%d]招聘情况\\n\ OutPutStu( rz[i].stu ); printf( \ }

printf( \落聘人员\\n\ OutPutStu( head ); OutPutStu( over ); printf( \

for( i = 0; i < m; i++ )

/* 释放各工种招聘人员空间 */

FreeStu( &rz[i].stu ); 11 /* 释放落聘人员空间 */ FreeStu( &over ); /* 释放落聘人员空间 */ free( rz ); /* 释放工种信息空间 */

}

}

31

实验5 数组的基本操作

四、参考程序

程序1：题1 Fibonacci数列 #include #define MAX 20 void main() { int i; int fib[MAX]; fib[0] = 0; fib[1] = 1;

for( i = 2; i < MAX; i++ ) fib[i] = fib[i-1] + fib[i-2];

for( i = 0; i < MAX; i++ ) /* 输出格式: 每个数字以TAB键分隔, 5个为一行 */ printf( \, fib[i], (i%5)==4 ? '\\n' : '\\t' ); }

程序2：题2 数组操作 #include

#define MAX 5 void main() {

int i, j, n = 1;

int a[MAX][MAX];

for( i = 0; 1 ;i++ ) for( j = 0; j < MAX; j++ )

2 ; for( i = 0; i < MAX; i++ ) { for( j = 0 3 ;; j++ ) printf( \, a[i][j] ); printf( \ ); } }

程序3：题3 多项式相除

32

#include #include #define MIN 0.00005 /* 定义近似于0的值 */

/* 已知两多项式的系数和幂次, 返回最大公因式的幂次, 在*q中得到系数表的首指针 */

int Remainder( double *pa, int an, double *pb, int bn, double **q ) {

double x, *temp; int k, j;

if( an < bn ) {

/* 使多项式a(x)的幂次不低于多项式b(x)的幂次 */

temp = pa;

1 ; pb = temp; /* 使pa,pb值互换 */ }

while( 1 ) { while( *pb < MIN && *pb > -MIN && bn > 0 ) {

/* 忽略多项式b(x)最高次系数为0的项 */

bn --; pb ++; }

if( *pb < MIN && *pb > -MIN && 2 )/* 多项式b(x)为0, 退出循环 */ break; if( bn < 0 ) { *q = pb; return 0;

/* 请注意浮点型变量的判断为零方式 */ /* 无最大公因式 */

k = an; an = bn; bn = k;

/* 使an,bn值互换 */

} k = 0; x = *pb; while( k <= bn )

/* 使多项式b(x)的最高次项系数为1 */

pb[k++] /= x;

for( k = 0; k <= an - bn; k++ ) { /* 求a(x)/b(x), 商多项式有an-bn+1项 */ x = pa[k]; /* 商多项式的当前项系数x=pa[k] */ for( j = 0 3 ;; j++ ) /* 从a(x)中减去x*b(x) */ 4 ;/* pa[k]应置0, 但不再使用, 故未置0 */ }

temp = pa;

pa = 5 ;

33

pb = 6 ; /* b(x) = { a(x) / b(x) 后的余数多项式 } */ an = 7 ; /* 余数多项式的幂次为除数多项式幂次-1 */

}

8 ; return an; /* 返回多项式的幂次 */ }

int Input( double **p, int *n, char *note )

/* 多项式输入函数 */

{

int i;

double *pa;

printf( \请输入多项式%s的幂次, <=0退出 \

scanf( \%d\if( *n <= 0 ) return 1;

if( ( pa = (double *)malloc( (*n+1) * sizeof(double) ) ) == NULL ) { printf( \内存申请错误\\n\return -1; }

for( i = *n; i >= 0; i-- ) { printf( \请输入多项式%s%d次幂的系数 \, note, i ); scanf( \%lf\}

*p = pa;

return 0; }

void Print( double *q, int n ) /* 输出最大公因式表达式 */ { int i;

for( i = n; i >= 1; i-- ) if( q[i] > MIN || q[i] < -MIN ) printf( \, q[i], i ); if( q[0] > MIN || q[0] < -MIN ) printf( \, q[0] ); printf( \}

void main() {

34

double *pA, *pB; /* 多项式A(x), B(x)的系数数组 */ double *q; /* 最大公因式系数 */ int An, Bn; /* 多项式A(x), B(x)的幂次 */ int n; while( 1 ) { if( 9 ) return;

if( Input( &pB, &Bn, \ ) != 0 ) return;

printf( \表达式A(x)的格式为\\n\ ); Print( pA, An );

printf( \表达式B(x)的格式为\\n\ Print( pB, Bn );

n = 10 ; printf( \最大公因式表达式为\\n\

Print( q, n ); /* 输出最大公因式表达式 */

free( pA );

free( pB ); } }

35

实验6 字符串的基本操作

四、参考程序

程序1：题1 字符串匹配 #include #include

/* 简单模式匹配算法 */

int simple_match( char *t, char *p ) { int n, m, i, j, k; n = strlen( t ); m = strlen( p );

for( j = 0; 1 ; j++ ) { /* 顺序考察从t[j]开始的子串 */ for( i = 0; 2 ; i++ ) ; /* 从t[j]开始的子串与字符串p比较 */

if( i == m ) /* 匹配成功 */

return 0;

}

return 1; /* 匹配失败 */

}

void main() { char *s1[]={ \ }; char *s2[]={ \c123\ int i; for( i = 0; i < 3; i++ ) {

printf( \长字符串[%s] 匹配子串[%s] \ if( 3 ) printf( \ 匹配成功\\n\ ); else

printf( \匹配失败\\n\

}

}

程序2：题2 公共字符串

int commstr( char *str1, char *str2, int *lenpt )

36

{ int len1, len2, ln, count, i, k, p; char *st, form[20];

if( (len1=strlen(str1)) < (len2=strlen(str2)) ) { /* 使str1的长度不小于str2 */ st = str1; str1 = str2; str2 = st; ln = len1;

len1 = len2;

len2 = ln; } count = 0; for( 1 ; ln > 0; ln-- ) { /* 找长为ln的公共子串 */ for( k = 0; 2 ; k++ ) {

/* 自str2[k]开始的长为ln的子串与str1中的子串比较 */ for( p = 0; p + ln <= len1; p++ ) { /* str1中的子串自str1[p]开始, 两子串比较通过对应字符逐一比较实现 */ for( i = 0 3 ;; i++ ) ;

if( i == ln ) { /* 找到一个最长公共子串 */

sprintf( form, \子串%%d[%%%d.%ds]\\n\

printf( form, ++count, str2+k );

} } } if( 4 ) break; }

5 ; return count; }

void main() { int c, len; c = commstr( \, \, &len ); printf( \共有%d个长为%d的公共子串\\n\}

程序3：题3 排版输出

37

#include #include

/* 正文排版输出函数 s:预处理后的正文 nw:单词个数 sl:单词在s中的起始位置 sn:单词长度 */

void paiban( char *s, int nw, int *sl, int *sn ) {

int i, j, n, k, lnb, ln, m, ln1, lnw; char info[81]; ln = sn[0]; /* 一行中单词长度之和(包括每个单词间的一个空格) */ for( i=1,j=0; i < nw; i++ ) { /* 循环输出至最后一行前 */

ln1 = ln + 1 + sn[i]; if( 1 )

ln = ln1; else { n = 80 - ln; lnw = 2 ; /* 每个单词间隔的空格 */ lnb = 3 ; /* 按lnw个间隔排版后, 还多余的空格 */ for( k = 0; k < 80; k++ ) /* 将行输出内容初始化成全部空格 */ info[k] = ' '; info[80] = '\\0'; k = 0; /* k值为下一个单词在行中的起始位置 */ while( j < i ) { /*在一行中输出第j个至第i个单词*/ for( m = 0; m < sn[j]; m++ ) /* 将单词拷贝到行中 */ 4 = s[ sl[j] + m ]; k += 5 ; /* 设置下一单词位置 */ if( lnb > 0 ) { /* 该行中还有多余的空格 */ k++;

6 ;

} j++; }

printf( \, info );

ln = sn[i]; } }

for( k = 0; k < 80; k++ ) info[k] = ' '; info[80] = '\\0'; k = 0;

while( 7 ) {

38

for( m = 0; m < sn[j]; m++ ) info[k+m] = s[ sl[j] + m ]; k += 1 + sn[j]; j++; }

printf( \

}

void main() { int i;

char form[10]; char str[]=\is\\ trying\\ hard\\ tolearn\\

english\\ spanishisthe\\ language\\ ofherthoughts\\

anddreamsinshcool\\ sheisquietandsad\\ andsometimes\\ angryshemovesalone\\ fromonefourth-grade\\ classtoanother\\

thengoeshometowait\\ forherparents\\ toreturnfromwork\\ wayafterdark\\ shehasnot\\

beenhappysinceshemovetowashington\\ fromperu\\

expertssaythat\\ gamesandactivitys\\

are\\ the\

int sn[]={5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,

20,21,22,23,24,25,26,4,3,2,1};

39

int sl[]={0,5,11,18,26,35,45,56,68,81,95,110,126,143,161, 180,200,221,243,266,290,315,341,345,348,350}; printf( \正文内容为:\\n\\n\ for( i=0; i<26; i++ ) { sprintf( form, \ printf( form, &str[sl[i]] ); }

printf( \排版后输出内容为:\\n\\n\ ); paiban( str, 26, sl, sn );

}

40

实验7 二叉树的基本操作

四、参考程序

程序1：题1 二叉树的基本操作函数 typedef struct tree { /* 定义树的结构 */ int data; /* 假定树的元素类型为int */ struct tree *lchild; /* 左孩子*/

struct tree *rchild; /* 右孩子*/ }TREE;

typedef struct stack { /* 定义链接栈结构 */

TREE *t; /* 栈结点元素为指向二叉树结点的指针 */ int flag; /* 后序遍历时用到该标志 */ struct stack *link; /* 栈节点链接指针 */

}STACK;

void push( STACK **top, TREE *tree ) /* 树结点入栈 */ {

STACK *p; /* 工作指针 */ p = (STACK *)malloc( sizeof(STACK) ); /* 申请栈结点 */ p->t = tree; /* 根结点进栈 */ p->link = *top; /* 新栈结点指向栈顶 */

*top = p; /* 栈顶为新结点 */ }

void pop( STACK **top, TREE **tree ) /* 出栈, 栈内元素赋值给树结点 */ { STACK *p; /* 工作指针 */ if( *top == NULL ) /* 空栈 */ *tree = NULL; else { /* 栈非空 */ *tree = (*top)->t; /* 栈顶结点元素赋值给树结点 */ p = *top; *top = (*top)->link; /* 栈顶指向下一个链接, 完成出栈 */ free( p ); /* 释放栈顶结点空间 */ }

}

41

void SearchNode( TREE *tree, /* 查找树根结点 */ int key, /* 查找键值 */ TREE **pkpt, /* 返回键值为key结点的父节点的指针 */ TREE **kpt ) /* 返回键值为key结点的指针 */ { *pkpt = NULL; /* 初始化为查找结点不存在 */

*kpt = tree; /* 从根结点开始查找 */ while( 1 ) { if( 2 == key ) /* 找到 */

return; *pkpt = *kpt; /* 当前结点作为key键值的父结点, 继续查找 */ if( key < (*kpt)->data ) /* 键值小于当前结点, 查左子树 */ 3 ; else /* 键值大于当前结点, 查右子树 */ 4 ; } }

int InsertNode( TREE **tree, int key )

/* 查找树上插入新结点, 返回1:该键值结点已存在, -1:内存申请失败 */ { TREE *p, *q, *r; SearchNode( *tree, key, &p, &q ); if( 5 ) /* 找到相同键值的结点, 不插入 */ return 1; }

if( (r = (TREE *)malloc( sizeof(TREE) ) ) == NULL ) /* 申请新结点空间 */ return -1; 6 ;

r->lchild = r->rchild = NULL; /* 新结点的左右子树为空 */ if( p == NULL ) /* 如果为空树, 新结点为查找树的根结点 */ *tree = r;

else if( p->data > key ) /* 父结点键值大于新结点 */ 7 ; /* 新结点为左孩子 */ else 8 ; return 0;

/* 新结点为右孩子 */

int DeleteNode( TREE **tree, int key ) 不存在 */ {

/* 查找树上删除结点, 返回1:该键值结点

42

TREE *p, *q, *r;

SearchNode( *tree, key, &p, &q ); if( q == NULL ) /* 该键值结点不存在 */ return 1; if( p == NULL ) /* 被删结点为父结点 */ if( q->lchild == NULL ) /* 被删结点无左子数, 则其右子树作为根结点 */

*tree = 9 ; else { /* 被删结点有左子树, 则将其左节点作为根结点 */ *tree = 10 ;

r = q->lchild;

while( r->rchild != NULL )

/* 寻找被删结点左子树按中序遍历的最后结点 */ r = r->rchild; 11 ; /* 被删结点右子树作为找到结点的右子数 */

/* 被删结点不是根结点, 且无左子树 */

}

else if( __12______ ) if( q == p->lchild )

/* 被删结点为其父结点的左子结点,将其右子树作为父结点的左子树 */ p->lchild = q->rchild; else /* 被删结点为其父结点的右子结点,将其右子树作为父结点的右子树 */ _____13_________; else { /* 被删结点不是根结点, 且有左子树 */ r = q->lchild; while( r->rchild != NULL )

/* 寻找被删结点左子树按中序遍历的最后结点 */ r = r->rchild; _____14_______; /* 被删结点右子树作为找到结点的右子数 */ if(____15_____)

/* 被删结点是其父结点的左子结点,将其左子树作为父结点的左子树 */ p->lchild = q->lchild; else

/* 被删结点为其父结点的右子结点,将其右子树作为父结点的右子树 */

p->rchild = q->lchild; } free( q ); /* 释放被删结点内存空间 */ return 0;

}

程序2：题3 层次遍历打印二叉树 void OutputTree( TREE *tree )

43

{

/* 层次打印树结点, 中序遍历, 采用链接栈的迭代方法 */

STACK *top; /* 栈顶指针 */

int deep=0, no=0, maxdeep=0; /* 初始化树深度和遍历序号为0 */ top = NULL; /* 初始化为空栈 */

while(___1____ ) { /* 循环条件为二叉树还未遍历完, 或则栈非空 */

while( tree != NULL ) { /* 二叉树还未遍历完 */ ___2____; /* 树结点入栈 */ top->flag = ++deep; }

if( maxdeep < deep ) maxdeep = deep; ___3______; /* 沿左子树前进, 将经过的结点依次进栈 */ }

if( top != NULL ) { /* 左子数入栈结束, 且栈非空 */ deep = _____4___; no++; ___5_____; /* 树结点出栈 */

gotoxy( no * 4, deep + 2 ); printf( ____6____ ); /* 访问根结点 */ fflush( stdout ); ____7_____; /* 向右子树前进 */ } }

gotoxy( 1, maxdeep + 3 ); printf( \任意键继续\\n\getch();

程序3：题2 主函数

/* 本程序实现了二叉查找数的建立, 查找结点, 删除结点, 以及中序遍历, 前序遍历, 后序遍历的递归和迭代方法 */ #include #include #include void main() {

TREE *t; /* 定义树 */ int op=-1, i, ret; t = NULL; /* 初始化为空树 */ while( op != 0 )

44

{ printf( \请选择操作，1：增加树结点 2：删除树结点 0：结束操作 \ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \ switch( op ) { case 0: /* 退出 */ break; case 1: /* 增加树结点 */

printf( \请输入树结点元素：\

scanf( \

switch( ____1_____ ) { case 0: /* 成功 */ clrscr(); gotoxy( 1, 1 ); printf( \成功，树结构为:\\n\ OutputTree( t ); break; case 1: printf( \该元素已存在\ break; default: printf( \内存操作失败\

}

case 2: /* 删除结点 */ printf( \请输入要删除的树结点元素：\ scanf( \ if( ____2____ ) { /* 删除成功 */ clrscr(); gotoxy( 1, 1 ); printf( \删除成功, 树结构为:\\n\ OutputTree( t ); } else

printf( \该键值树结点不存在\\n\

break;

}

}

45

break; break;

实验8 树的遍历和哈夫曼树

五、参考程序

程序1：题1 二叉树的遍历操作函数 typedef struct tree { /* 定义树的结构 */ int data; /* 假定树的元素类型为int */ struct tree *lchild; /* 左孩子 */ struct tree *rchild; /* 右孩子 */ }TREE;

typedef struct stack { /* 定义链接栈结构 */ TREE *t; /* 栈结点元素为指向二叉树结点的指针 */ int flag; /* 后序遍历时用到该标志 */ struct stack *link; /* 栈节点链接指针 */ }STACK;

void re_preorder( TREE *tree ) /* 前序遍历, 递归方法 */ { /*编写前序遍历子程序*/ }

void re_midorder( TREE *tree ) /* 中序遍历, 递归方法 */ { if( tree != NULL ) { /* 不为空子树时递归遍历 */ re_midorder( tree->lchild ); /* 先遍历左子树 */ printf( \/* 再遍历父结点 */ re_midorder( tree->rchild ); /* 最后遍历右子树 */ } }

void re_posorder( TREE *tree ) /* 后序遍历, 递归方法 */ {

/*编写后序遍历子程序*/

}

void push( STACK **top, TREE *tree ) /* 树结点入栈 */ {

46

STACK *p; /* 工作指针 */ p = (STACK *)malloc( sizeof(STACK) ); /* 申请栈结点 */ p->t = tree; /* 根结点进栈 */ p->link = *top; /* 新栈结点指向栈顶 */ *top = p; /* 栈顶为新结点 */ }

void pop( STACK **top, TREE **tree ) /* 出栈, 栈内元素赋值给树结点 */ { STACK *p; /* 工作指针 */ if( *top == NULL ) /* 空栈 */ *tree = NULL; else { /* 栈非空 */ *tree = (*top)->t; /* 栈顶结点元素赋值给树结点 */ p = *top; *top = (*top)->link; /* 栈顶指向下一个链接, 完成出栈 */

free( p ); /* 释放栈顶结点空间 */

} }

void st_preorder( TREE *tree ) /* 前序遍历, 采用链接栈的迭代方法 */ { STACK *top; /* 栈顶指针 */ top = NULL; /* 初始化为空栈 */ while( tree != NULL ) { /* 二叉树还未遍历完 */ ____1_______; /* 访问根结点 */ if( ___2_______ ) /* 右子树结点入栈 */ push( &top, tree->rchild ); if( tree->lchild != NULL ) /* 左子树结点入栈 */ ________3_____; pop( &top, &tree ); /* 树结点出栈 */

}

}

void st_midorder( TREE *tree ) /* 中序遍历, 采用链接栈的迭代方法 */

{ STACK *top; /* 栈顶指针 */ top = NULL; /* 初始化为空栈 */

while( ___4_____ ) { /* 循环条件为二叉树还未遍历完, 或则栈非空 */

while( tree != NULL ) { /* 二叉树还未遍历完 */

47

push( &top, tree ); /* 树结点入栈 */ _____5______; /* 沿左子树前进, 将经过的结点依次进栈 */ }

if( top != NULL ) { /* 左子数入栈结束, 且栈非空 */ pop( &top, &tree ); /* 树结点出栈 */ ______6__________; /* 访问根结点 */

_______7______ ; /* 向右子树前进 */

} }

}

void st_posorder( TREE *tree ) /* 后序遍历, 采用链接栈的迭代方法 */ { STACK *top; /* 栈顶指针 */ top = NULL; /* 初始化为空栈 */ do{ while( _____8______ ) { /* 二叉树还未遍历完 */ push( &top, tree ); /* 树结点入栈 */ top->flag = 0; /* 标志为0, 表示右子树未访问 */ _____9______; /* 沿左子树前进, 将经过的结点依次进栈 */ }

if( top != NULL ) { /* 栈非空 */ while( top!=NULL && ____10_____ ) { /* 右子树已访问 */ pop( &top, &tree ); /* 出栈 */ printf( \ }

if( top != NULL ) {

____11______; /* 置右子树为访问标志 */

tree = (top->t)->rchild;/* 查找栈顶元素的右子树 */

} }

}while( top != NULL ); /* 循环条件为栈非空 */

}

程序2：题2 主函数

/* 本程序实现了二叉查找树的中序遍历, 前序遍历, 后序遍历的递归和迭代方法 */ #include #include #include void main()

48

{ TREE *t; int i,op=-1;

/* 定义树 */ t = NULL;

/* 初始化为空树 */

while( op != 0 ) { printf( \请选择操作，1：增加树结点 0：结束操作 \ fflush( stdin ); /* 清空标准输入缓冲区 */

scanf( \

switch( op ) { case 0: /* 退出 */ break; case 1: /* 增加树结点 */ printf( \请输入树结点元素：\ scanf( \ switch( InsertNode( &t, i ) { case 0: /* 成功 */ clrscr(); gotoxy( 1, 1 ); printf( \成功，数结构为:\\n\ OutputTree( t ); break; case 1:

printf( \该元素已存在\

break;

default: printf( \内存操作失败\ break; }

break; } }

printf( \前序遍历, 递归方法\\n\ re_preorder( t ); /* 前序遍历, 递归方法 */ printf( \任意键继续\\n\\n\ getch(); printf( \中序遍历, 递归方法\\n\ re_midorder( t ); /* 中序遍历, 递归方法 */

printf( \任意键继续\\n\\n\

49

本文来源：https://www.bwwdw.com/article/zutw.html