《软件技术基础》实验指导书实验三四

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！《软件技术基础》实验指导书2009年9月软件技术基础实验三队列的应用实验目的与基本要求1、掌握队列的顺序存储和链式存储结构。2、掌握队列的特点。3、掌握队列的基本运算。实验条件1、硬件：一台微机2、软件：操作系统和C语言系统实验方法确定存储结构后，上机调试实现队列的基本运算。实验内容1、写出队列的出队和入队算法。2、设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚，依次从停车场最里面向大门口处停放（最先到达的第一辆车n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一个程序模拟该停车场的管理。性质：必做类型：验证2h队列是从日常排队现象抽象出来的一种数学模型。当然数据结构中的队列远没有生活中的排队灵活。数据结构中的队列规定：数据只能从队尾进，从队首出来。已经进入队列的数据次序不能再做改变。这就叫做“先进先出”(FIFO)或者说“后进后出”(LILO)。允许插入的一端称为队尾，通常用一个称为尾指针（rear）的指针指向队尾元素，即尾指针总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针（front）指向队首元素的前一个位置（当然也可以直接指向队首元素，只是许多数据结构的书上都链表来模拟。根据以上描述，队列可以可以有以下基本操作：1、创建初始化：按约定置队列为空状态。2、入队列：在队尾加入一个新数据项。3、出队列：从队首取出一个数据项，并使余下诸项向队首移动。4、队列空：判断队列是否为空。5、队列满：判断队列是否已满。从概念上说，队列不存在“满”状态，其长度可以任意增加，但实现（不论静态或-1-软件技术基础动态）中总有空间限制的。下面我就来讨论用数组实现队列结构。假定队列中元素的类型为T,队列的最大长度为queue_size,在任何一刻队列首、尾位置分别用下标head、tail指向。队列初始状态应为：head=0,tail=-1。根据队列定义，head值应恒为0，那么每当出x=(x+1)mod100，则x的变化范围在[0，99]之间，超过100的又从0，1开始。这不就是我们所需要的嘛！许多书上把它叫作“循环数组”技术。即当入队列时先移动tail(即tail=(tail+1)modqueue_size)，出队列时先移动head(即head=(head+1)modqueue_size)。head(或tail)值为queue_size-1,则移动后head(或tail)的值就变成0了，对这种特征就是一个环，只要数组有空间，就可以入队列。用“循环数组”实现队列，必须注意怎样判断队列的空与满的状态。除起始状态外。任何时刻tail所指为最后一个进入队列的元素，而head所指的是刚刚出队列的那个元素原先所占的位置。因此(head+1)modqueue_size才是真正当前队列中首元素位置。采用条件：(tail+1)modqueue_size==head作为“队列满”的判断条件。实际上此时队列中还有一个空位置，这样队列的利用空间比定义的最大空间少一个单元。假如把这个单元也利用上，则就不好判断“满”或“空”了（当head==tailtail追上了head,还是head追上了tail才能区分，这样给处理带来了不便。#include<stdlib.h>#include<stdio.h>#defineNULL0typedefstructnode{intdata;}NODE;#defineLENsizeof(NODE)/*队列的需要变量*/typedefenum{false,true}bool;/*定义bool类型*/unsignedinthead;/*定义队首下标变量*/unsignedinttail;/*定义队尾下标变量*/staticNODE*queue=NULL;/*定义一个队列*/staticunsignedintqueue_size=0;/*队列的大小*//*========================功能：初始化队列的大小返回：trueorfalse========================-2-软件技术基础*/boolInitQueue(unsignedintsize){queue=(NODE*)malloc(size*LEN);/*开辟空间*/if(queue==NULL)/*开辟空间失败，则返回false*/{returnfalse;}queue_size=size;/*保存队列空间大小值*/head=queue_size-1;/*队首下标赋初值*/tail=queue_size-1;/*队尾下标赋初值*/returntrue;/*初始化成功，返回true*/}/*======================功能：释放队列的内存返回：void======================*/voidFreeQueue(){free(queue);/*注意：这一点很重要。free()之后并不能将queue置为NULL,所以我们一定要自己做。这样能防止产生“野指针”,即地址不确定的指针。*/queue=NULL;}/*==========================功能：判断队列是否已满返回：trueorfalse==========================*/boolFull(){return(((tail+1)%queue_size)==head);}/*-3-软件技术基础===========================功能：判断队列是否为空返回：trueorfalse===========================*/boolEmpty(){return(head==tail);}/*========================功能：入队列返回：trueorfalse========================*/boolPush(NODEp){if(!Full())/*队列不满，则入队列；队尾下标要加1*/{tail=(tail+1)%queue_size;queue[tail]=p;returntrue;}else{printf("queueisoverflow!\n");returnfalse;}}/*===================功能：出队列返回：出队列元素指针===================*/NODE*Pop(){if(!Empty())/*队列不空，则出队列；队首下标要加1*/{head=(head+1)%queue_size;-4-软件技术基础return(&queue[head]);}else{printf("queueisempty!\n");returnNULL;}}voidmain(void){NODEnode1={3};NODE*p;if(!InitQueue(3))/*初始化不成功，则退出*/{exit(0);}Push(node1);/*去掉下面的注释，你可以验证讲解中空间利用问题*//*Push(node1);Push(node1);Push(node1);*/p=Pop();printf("%d",p->data);FreeQueue();/*注意程序退出时释放队列内存*/printf("\n");system("pause");}提示：可以停车场内的车辆管理，看做是堆栈，采用先进后出的运算规则；而在停车场外排队的车辆管理，可以看做是队列，采用先进先出的运算规则。基本思想：根据题目要求，停车场只有一个大门，因此可用一个栈来模拟。而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于排在停车场中间的车辆可以提出离开停车场，并且要求在离开车辆到停车场大门之间的车辆都必须离开停车场，让此车辆离去，然后再让这些车辆依原来的次序进入停车场，因此在一个栈和一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，很显然这也应该用一个栈来模拟，因此，本题中要用到两个栈和一个队列。参考程序如下：-5-软件技术基础#defineN2/*定义停车场栈长度*//*M为单元时间的收费值*/#defineM5#defineTrue1#defineFalse0#include“stdio.h”/*存储结构*/typedefstruct{intnum；/*定义栈元素类型*/intarrtime；}elemtype；typedefstruct{elemtypestack[N]；inttop；/*定义栈*/}sqstktp；typedefstructnode{intnum；/*定义队列结点的类型*/structnode*next；}queueptr；typedefstruct{queueptr*front，*rear；}Linkedquetp；voidinistack（sqstktp*s）{s->top=-1;/*定义队列*//*初始化栈*/intpush(sqstktp*s,elemtypex)/*数据元素x入指针s所指的栈*/{if(s->top==N-1)return(False);else/*如果栈满,返回False*//*栈不满,x入栈*/{s->stack[++s->top]=x;return(True);}elemtypepop(sqstktp*s){elemtypex;if(s->top<0){x.num=NULL;x.arrtime=NULL;return(x);/*栈顶元素出栈*//*如果栈空,返回空值*/}else{s->top--;-6-软件技术基础return(s->stack[s->top+1]);/*栈不空,返回栈顶元素*/}}-7-软件技术基础实验四二叉树的应用实验目的与基本要求1、掌握指针变量，动态变量的含义。2、掌握二叉树的结构特性，以及存储结构的特点及适用范围。3、掌握用指针类型描述，访问和处理二叉树的运算实验条件1、硬件：一台微机2、软件：操作系统和C语言系统实验方法确定存储结构后，上机调试实现二叉树的基本运算。实验内容1、验证二叉树的几个基本性质。2、实现二叉树的遍历运算。性质：必做类型：验证2h树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。1.二叉树的基本形态：二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(1)空二叉树——(a)；(2)只有一个根结点的二叉树——(b)；(3)右子树为空的二叉树——(c)；(4)左子树为空的二叉树——(d)；(5)完全二叉树——(e)2．二叉树的遍历遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍-8-软件技术基础历有三种情况：DLRLDRLRD（称为后根次(1)先序遍历访问根；按先序遍历左子树；按先序遍历右子树(2)中序遍历按中序遍历左子树；访问根；按中序遍历右子树(3)后序遍历按后序遍历左子树；按后序遍历右子树；访问根3．程序举例：#include<stdlib.h>#include<stdio.h>#defineMAX50#defineMAS20#defineCHAR1#ifCHARtypedefcharTElemType;TElemTypeNil='';#defineform"%c"#elsetypedefintTElemType;TElemTypeNil=0;#defineform"%d"#endiftypedefstructnode{TElemTypedata;structnode*left;structnode*right;structnode*parent;}BiTNode,*BiTree;BiTNode*InitBiTree(BiTNode*bt){bt=NULL;returnbt;}BiTNode*CreateBiTree(BiTNode*bt){TElemTypech;scanf(form,&ch);if(ch==Nil)bt=NULL;else{bt=(BiTNode*)malloc(sizeof(BiTNode));-9-软件技术基础if(!bt)exit(0);bt->data=ch;bt->parent=NULL;bt->left=CreateBiTree(bt->left);if(bt->left)bt->left->parent=bt;bt->right=CreateBiTree(bt->right);if(bt->right)bt->right->parent=bt;}returnbt;}voidPrintTree(BiTNode*bt,inti){if(bt!=NULL){PrintTree(bt->right,i+5);#ifCHARif(bt->data!=Nil)printf("%*c\n",i,bt->data);#elseif(bt->data!=Nil)printf("%*d\n",i,bt->data);#endifPrintTree(bt->left,i+5);i=i-5;}}voidProrder1(BiTNode*bt,void(*visit)(TElemType))/*先序遍历*/{if(bt!=NULL){visit(bt->data);Prorder1(bt->left,visit);Prorder1(bt->right,visit);}}voidProrder2(BiTNode*bt,void(*visit)(TElemType))/*中序遍历*/{BiTNode*p,*stack[MAS];inttop;top=0;p=bt;while(top!=0||p!=NULL){while(p!=NULL){stack[top]=p;top++;p=p->left;}if(top!=0)-10-软件技术基础{p=stack[top-1];top--;visit(p->data);p=p->right;}}}voidProrder3(BiTNode*bt,void(*visit)(TElemType))/*后序遍历*/{BiTNode*p,*stack[MAS];inttop;top=0;stack[top]=bt;top++;while(top>0){p=stack[top-1];top--;while(p!=NULL){visit(p->data);stack[top]=p->right;top++;p=p->left;}}}voidvisit(TElemTypee){printf(form"",e);}intSumLefts(BiTNode*bt,intsum){if(bt!=NULL){if(bt->left==NULL&&bt->right==NULL){printf("%4c",bt->data);sum++;}sum=SumLefts(bt->left,sum);sum=SumLefts(bt->right,sum);}return(sum);}intSumTree(BiTNode*bt){staticintsum=0;-11-软件技术基础if(bt!=NULL){printf("%4c",bt->data);sum++;sum=SumTree(bt->left);sum=SumTree(bt->right);}return(sum);}BiTNode*Findchar(BiTNode*bt,charch)/*二叉树查找结点*/{BiTNode*p;if(bt!=NULL)/*利用函数名返回结果*/{if(bt->data==ch)p=bt;p=Findchar(bt->left,ch);p=Findchar(bt->right,ch);}if(p!=NULL)return(p);elsereturn(NULL);}main(){intj,i,a,sum=0;BiTreebt;bt=InitBiTree(bt);#ifCHARprintf("请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)\n");#elseprintf("请先序输入二叉树(如:12000表示1为根结点,2为左子树的二叉树)\n");#endifbt=CreateBiTree(bt);printf("输入建立的二叉树