《应用数据结构》实验指导书2011.doc

应用数据结构实验指导书课程编号：课程名称：应用数据结构/Applied Data Structure实验学时：16适应专业：工科类承担实验室：管理学院实验中心一、实验目的和任务1实验教学的目的 本课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，其重要程度绝不亚于知识传授。实验的作用在于帮助学生深入理解教材内容，巩固基本概念，促使学生在动手过程中进一步体会C语言中数据结构的运用技巧，并锻炼学生在调试过程中分析和发现问题的能力。2实验教学的要求学生应掌握C语言基本编程能力并运用数据结构的原理和方法解决具体问题。除按时上机外，学生应具备构造算法并用程序实现的能力；在程序调试过程中，学生应能正确解读程序的错误提示并找到有效的解决办法。此外，规范书写算法也是一个值得高度重视的问题，教师有责任在教学过程中提醒学生，避免形成一系列难以纠正且贻害无穷的程序设计坏习惯。此外，本门课程设计的算法比较多，要求教师熟练掌握C语言和数据结构各类算法，并能准确理解和回答学生提出的编程问题。二、实验项目及学时分配序号实 验 项 目 名 称实验学时实验类型开出要求1线性数据结构算法验证4验证及演示必做2非线性数据结构算法验证4验证及演示必做3查找及排序4验证及演示必做4综合算法设计4综合必做三、参考资料李业丽、郑良斌编著，数据结构（C）实验教程，北京理工大学出版社，2005年12月出版严蔚敏，吴伟民编著，数据结构习题集（C语言版），清华大学出版社，1999年2月出版。四、单项实验的内容和要求（包括实验所用的主要仪器设备，实验所需主要耗材）实验一 线性数据结构算法验证1实验目的与意义1) 熟悉C语言的上机环境，进一步掌握C语言的结构特点2) 掌握线性表的顺序存储结构的定义及C语言实现3) 掌握线性表的链式存储结构单链表的定义及C语言实现4) 掌握线性表在顺序存储结构即顺序表中的各种基本操作5) 掌握线性表在链式存储结构单链表中的各种基本操作6) 掌握栈的顺序表示和实现7) 掌握栈的链式表示和实现8) 掌握队列顺序表示和实现9) 掌握队列链式表示和实现2基本原理和方法本实验涉及各类线性数据结构线性表、栈和队列等。单链表的各种操作，包括单链表的建立，结点的查找、插入、删除等基本运算。链表中插入结点的指针变化和删除p所指结点的指针变化参见讲义。栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为p-top=MAXNUM-1，栈满时，不能入栈；否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。注意： 顺序栈中元素用向量存放。 栈底位置是固定不变的，可设置在向量两端的任意一个端点。 栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置。队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将rear加1，出队时，删去front所指的元素，然后将front加1并返回被删除元素。顺序队列中的溢出现象： “下溢”现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 “真上溢”现象。当队列满时，做进找运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 “假上溢”现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空闻的规模时，也可能由于尾指针己超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。3主要仪器设备及耗材安装有Turbo C+ 3.0运行环境的电脑，无耗材要求。4实验方案或技术路线本实验含有三部分内容线性表、栈和队列。A线性表部分采取建立学生成绩表的方法实现。即建立学生成绩单链表，链表中每个结点由4个域组成，分别为：学号、姓名、成绩、存放下一个结点地址的next域、要求完成的四项功能可写成四个函数，登记学生成绩对应建立学生单链表的功能，后三个功能分别对应单链表的查询、插入与删除三大基本操作。该系统中的数据采用线性表中的链式存储结构即单链表来存储，用结构体类型定义每个学生记录，故该单链表中每个结点的结构可描述为：#define MAXLEN 100typedef struct node int num；/学号 char nameMAXLEN；/姓名 float score；/成绩 struct node *next; linklist;B栈部分此部分的算法独立性较强，因此可直接采用教材或讲义上的算法实现，但教材或讲义上的算法并非可执行的算法，故学生须自行进行算法上的转换。C队列部分本实验主要由教师课堂演示，以一个具体的实例机场事件模拟来实现。5实验内容及步骤A线性表部分学生成绩管理是学校教务管理的重要组成部分，其处理信息量很大，本实验是对学生的成绩管理作一个简单的模拟，用菜单选择操作方式完成下列功能： 登记学生成绩 查询学生成绩 插入学生成绩 删除学生成绩【参考程序】/*头文件hh.h的内容*/#include#include#include#define MAXLEN 100typedef struct node int num; char nameMAXLEN; int score; struct node *next; list;/*头文件creat.h的内容*/#includehh.hlist *create() list *head, *p, *r; int i, n; head=(list *)malloc(sizeof(list); head-next=NULL; r=head; printf(请输入学生人数:n); scanf(%d,&n); for(i=l; inum); printf(输入学生的姓名:n); scanf(%s, p-name); printf(输人李生的成绩:n); scanf(%d, &p-score); p-next=NULL; r-next=p; r=r-next; return(head);/*以下是头文件insert.h的内容*/list *insert(list *h) list *p,*q,*r,*head; head=r=h; p=h-next; q=(list *)malloc(sizeof(list); printf(输入待插入学生的学号:n); scanf(%d,&q-num); printf(输入姓名:n); scanf(%s, q-name); printf(输入成绩:n); scanf(%d, &q-score); q-next=NULL; while(p) r=p; p=p-next; r-next=q; r=r-next; return(head);/*以下是头文件find.h的内容*/void find(list *h) int k; list *p; p=h-next; printf(输入要查找学生的学号:n); scanf(%d, &k); while(p&p-num!=k) p=p-next; if(p) printf(学号t姓名t成绩n); printf(%dt%st%dn,p-num,p-name,p-score); else printf(没找到!n);/*以下是头文件del.h的内容*/list *del(list *h) int k; list *p, *q; q=h; p=h-next; printf(请输入待删除学生的学号:n); scanf(%d,&k); while(p&p-num!=k) q=p; p=p-next; if(p) q-next=p-next; free(p); else printf(没有这个学生成绩，无法删除!n); return(h);/*以下是头文件output.h的内容*/void output(list *h) list *p; p=h-next; while(p!=NULL) printf(学号t姓名t成绩tn); printf(%dt%st%dn,p-num,p-name,p-score); p=p-next; /*以下是主程序*/#includecreat.h#includefind.h#includeinsert.h#includeoutput.h#includedel.hmain() list *p; int k; /*控制循环的标志*/ while(1) printf( -n); printf( | 学生成绩管理 |n); printf( |n); printf( | 1.登记成绩 |n); printf( | 2.查询成绩 |n); printf( | 3:插入成绩 |n); printf( | 4.删除成绩 |n); printf( | 5.输出所有学生成绩 |n); printf( | 0.退出程序 |n); printf( -n); printf( 请输入你的选择n); scanf(%d,&k); switch(k) case 1: p=create(); break; case 2: find(p); break; case 3: p=insert(p); break; case 4: p=del(p); break; case 5: output(p); break; case 0: exit(0); default: printf(选择错误，重新开始!n); B栈部分编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能： 初始化顺序栈 插入元素 删除栈顶元素 取栈顶元 遍历顺序栈 置空顺序栈【参考程序】#include#include#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM; int top; SqStack;/*初始化顺序栈*/void InitStack(SqStack *p) if(!p) printf(Error); p-top=-l;/*入栈*/void Push(SqStack *p, ElemType x) if(p-topstack+p-top=x; else printf(Overflow!n);/*出栈*/ElemType Pop(SqStack *p) ElemType x; if(p-top!=O) x=p-stackp-top; printf(栈顶元%d已经被删除！n, p-stackp-top); p-top=-; return(x); else printf(Underflow!n); return(0); /*获取栈顶元素*/ElemType GetTop(SqStack *p) if(p-top!=0) return (p-stackp-top); else printf(Underflow!n); return(0); /*遍历顺序栈*/void OutStack(SqStack *p) int i; printf(n); if(p-toptop; i=O; i-) printf(第%d个数据是：%6dn, i, p-stacki);/*置空顺序栈*/void setEmpty(SqStack *p) p-top=-1; /*主函数*/main() SqStack *q; int y, cord; ElemType a; do printf(n第一次使用必须初始化！n); printf(n); printf(n 主菜单n); printf(n 1 初始化顺序栈n); printf(n 2 插入一个元素n); printf(n 3 删除栈顶元素n); printf(n 4 取栈顶元素n); printf(n 5 置空顺序栈n); printf(n 6 结束程序运行n); printf(n-n); printf(请输入您的选择( 1, 2, 3, 4, 5, 6): ); scanf(%d, &cord); printf(n); switch(cord) case 1: q=(SqStack*)malloc(sizeof(SqStack); InitStack(q); OutStack(q); break; case 2: printf(请输入要插入的数据元素：a=); scanf(%d,&a); Push(q, a); OutStack(q); break; case 3: Pop(q); OutStack(q); break; case 4: y=GetTop(q); printf(n栈顶元素为：%dn, y); OutStack(q); break; case 5: setEmpty(q); printf(n 顺序栈被置空！n); OutStack(q); break; case 6: exit(0); while (cord=6);C队列部分熟悉讲义中队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： 模拟一个机场飞机起降的过程 机场仅有一条跑道，要求起飞与降落不能同时进行 进场飞机若暂时没有跑道可用须在空中盘旋等候 离场飞机若暂时没有跑道可用须在地面排队等候 仅当空中无飞机等待降落时地面飞机方可起飞 飞机的申请进场、降落、申请离场和起飞分别视为独立事件 每个事件的发生占用一个时间单位。除降落和起飞外，各事件可以同时发生【参考程序】#define MAXQUEUE 5 /* use a small value for testing */#include #include #include #include #include #include #include typedef enum boolean False, True Boolean;typedef enum action ARRIVE, DEPART Action;typedef struct plane int id; /* identification number of airplane */ int tm; Plane; /* time of arrival in queue */typedef Plane QueueEntry;typedef struct queue int count; /* number of airplanes in the queue */ int front, rear; /* front and rear of the queue */ QueueEntry entryMAXQUEUE; Queue;/* CreateQueue: create the queue. Pre: None. Post: The queue q has been initialized to be empty. */void CreateQueue(Queue *q) q-count=q-front=0; q-rear=-1;/* Error: display an error message. Pre: message is the error message to display. Post: The error message has been printed to stderr and the program terminates. */void Error(char *message) fprintf(stderr, Error: %sn, message); exit (1);/* UserSaysYes: True if the user wants to continue execution. Pre: None. Post: Returns True if the users answer begins with either y or Y, False if the user responds with any response beginning with either n or N.*/Boolean UserSaysYes(void) int c; printf( (y/n)? ); do while (c=getchar()=n) ; /* Ignore new line character. */ if (c=y | c=Y | c=n | c=N) return (c=y | c=Y); printf(Please respond by typing one of the letters y or nn); while (1);/* Randomize: set staring point for pseudorandom integers. */void Randomize(void) srand(unsigned int)(time(NULL)%10000);/* Start: print messages and initialize the parameters. Pre: None. Post: Asks user for responses and initializes all variables specified as parameters. Uses: UserSaysYes. */void Start(int *endtime, double *expectarrive, double *expectdepart) Boolean ok; printf( This program simulates an airport with only one runway.n One plane can land or depart in each unit of time.n Up to %d planes can be waiting to land or take off at any time.n, MAXQUEUE); printf( How many units of time will the simulation run? ); scanf(%d, endtime); Randomize(); /* Initialize random number generation. */ do printf( Expected number of arrivals per unit time (real number)? ); scanf(%lf, expectarrive); printf( Expected number of departures per unit time? ); scanf(%lf, expectdepart); if (*expectarrive0.0 | *expectdepart1.0) printf( The airport will become saturated. Read new numbers?); ok=!UserSaysYes( ); else ok=True; while (ok=False); printf(n);/* PoissonRandom: generate a pseudorandom integer according to the Poisson distribution. Pre: None. Post: generate a random nonnegative integer according to a Poisson distribution with the expected value given as the parameter. Uses: exp, rand. */int PoissonRandom(double expectedvalue) int n=0; /* counter of iterations */ double limit=exp(-expectedvalue); /* e-v, v is the expected value */ double x=rand()/(double) INT_MAX; /* pseudorandom number */ while (xlimit) n+; x*=rand()/(double) INT_MAX; return n;/* NewPlane: make a new record for a plane, update nplanes. Pre: None. Post: Makes a new structure for a plane and updates nplanes. */void NewPlane(Plane *p, int *nplanes, int curtime, Action kind) +*nplanes; p-id=*nplanes; p-tm=curtime; switch(kind) case ARRIVE: printf( Plane %3d ready to land.n, *nplanes); break; case DEPART: printf( Plane %3d ready to take off.n, *nplanes); break; /* QueueEmpty: returns non-zero if the queue is empty. Pre: The queue q has been created. Post: It returns non-zero if the queue is empty, zero otherwise. */Boolean QueueEmpty(Queue *q) return q-countcount=MAXQUEUE;/* Append: append an entry to the queue. Pre: The queue q has been created and is not full. Post: The entry x has been stored in the queue as its last entry. Uses: QueueFull, Error. */void Append(QueueEntry x, Queue *q) if (QueueFull(q) Error(Cannot append an entry to a full queue.); else q-count+; q-rear=(q-rear+1)%MAXQUEUE; q-entryq-rear=x; /* Serve: remove the first entry in the queue. Pre: The queue q has been create and is not empty. Post: The first entry in the queue has been removed and returned as the value of x. Uses: QueueEmpty, Error. */void Serve(QueueEntry *x, Queue *q) if (QueueEmpty(q) Error(Cannot serve froman empty queue.); else q-count-; *x=q-entryq-front; q-front=(q-front+1)%MAXQUEUE; /* QueueSize: return the number of entries in the queue. Pre: The queue q has been created. Post: The function returns the number of entries in the queue q. */int QueueSize(Queue *q) return q-count;/* Land: process a plane that is actually landing. Pre: None. Post: Process a plane p that is actually landing. */void Land(Plane p, int curtime, int *nland, int *landwait) int wait=curtime-p.tm; printf(%3d: Plane %3d landed; stayed in queue for %d units.n, curtime, p.id, wait); +*nland; *landwait+=wait;/* Refuse: processes a plane when the queue is full. Pre: None. Post: Processes a plane wanting to use runway, but the queue is full.*/void Refuse(Plane p, int *nrefuse, Action kind) switch(kind) case ARRIVE: printf( Plane %3d directed to another airport.n, p.id); break; case DEPART: printf( Plane %3d told to try later.n, p.id); break; +*nrefuse;/* Fly: process a plane that is actually taking off. Pre: None. Post: Process a plane p that is actually taking off. */void Fly(Plane p, int curtime, int *ntakeoff, int *takeoffwait) int wait=curtime-p.tm; printf(%3d: Plane %3d took off; stayed in queue for %d units.n, curtime, p.id, wait); +*ntakeoff; *takeoffwait+=wait;/* Idle: updates variables for idle runway. Pre: None. Post: Updates variables for a time unit when the runway is idle. */void Idle(int curtime, int *idletime) printf (%3d: Runway is idle.n, curtime); +*idletime;/* Conclude: write out statistics and concludes simulation. Pre: None. Post: Writes out all the statistics and cincludes the simulation. */void Conclude(int nplanes, int nland, int ntakeoff, int nrefuse, int landwait, int takeoffwait, int idletime, int endtime, Queue *pl, Queue *pt) printf(nSimulation has concluded after %d time units.n, endtime); printf(Total number of planes processed: %3dn, nplanes); printf( Number of planes landed: %3dn, nland); printf( Number of planes taken off: %3dn, ntakeoff); printf( Number of planes refused use: %3dn, nrefuse); printf( Number left ready to land: %3dn, QueueSize(pl); printf( Number left ready to take off: %3dn, QueueSize(pt); if (endtime0) printf( Percentage of time runway idle: %6.2fn, (double) idletime/endtime)*100.0); if (nland0) printf( Average wait time to land: %6.2fn, (double) landwait/nland); if (ntakeoff0) printf( Average wait time to take off: %6.2fn, (double) takeoffwait/ntakeoff);void main( ) Queue landing, takeoff, *pl=&landing, *pt=&takeoff; Plane plane; int curtime; /* current time; one unit = time for take off or landing */ int endtime; /* total number of time units to run */ double expectarrive; /* number of planes arriving in one unit */ double expectdepart; /* number of planes newly ready to take off */ int i; /* loop control variable */ int idletime=0; /* number of units when runway is idle */ int landwait=0; /* total waiting time for planes landed */ int nland=0; /* number of planes landed */ int nplanes=0;