2010级《数据结构》实验指导书

《数据结构》实验指导书PAGEPAGE1数据结构实验指导书淮阴工学院计算机工程学院二O一一年八月

目录实验1线性表及其应用…………………1实验2栈和队列及其应用………………5实验3二叉树及其应用…………………10实验4图及其应用………13实验5查找………………14实验6排序………………16线性表及其应用实验目的加深对线性表的结构特性的理解；熟练掌握单链表类的描述方法及其C++实现；掌握线性表的链式存储结构的应用方法；从时间和空间的角度对操作算法进行分析；加强程序的设计能力和调试能力。实验学时：建议2~4学时实验内容内容1：制作体育彩票（10选7）的选号器类。【说明】体育彩票（10选7）的7个号可以重复；建议选号器类从单链表类继承。用首尾相连的链式结构，这样可以更逼真地模拟“摇奖”过程；而每个号的“摇动”次数可用随机数来确定。怎样产生随机数？可以利用C++语言中的种子函数srand()和产生伪随机数函数rand()来实现。（include<STDLIB.H>）首先，给srand(m)提供一个“种子”m，它的取值范围是从0～65535。然后，调用rand()，是伪随机数，它会根据提供给srand()的“种子”值返回一个随机数（在0～32767之间）。根据需要多次调用rand()，从而不断地得到新的随机数。无论何时，你都可以给srand()提供一个新的“种子”，从而进一步“随机化”rand()的输出结果。例如，取m=17，则执行了srand(17)之后，再执行rand()函数，将得到输出值94；第二次调用rand()，会得到26,……反复调用rand()就能产生一系列的随机数。注意：若m不变，则rand()的输出系列也不变，总是94,26,602,…等等。所以，建议摇号的“种子”选当前日期或时间，以保证每天的摇号值都不相同。【选做内容】实现摇奖和对奖操作。内容2：约瑟夫（Joseph）环问题【问题描述】约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从1起报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止。求最后剩下的人的编号。【说明】建议用循环链表存储方式，设计循环链表类和约瑟夫类。问题改进：在人数n、k及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码Ki（整数），留作其出圈后的报到Ki后出圈。密码Ki可用随机数产生。这样事前无法确定谁是最后一人。【选做内容】约瑟夫问题的改进算法。约瑟夫问题的报数方法若采用顺时针报数和逆时针报数交替进行，则如何设计数据结构？【实现提示】//结点结构和单循环链表类定义enumResultCode{Error,NoMemory,OutOfBounds,Underflow,Overflow};template<classT>structNode{ Node(){link=NULL;} Node(Te,Node*next) { data=e; link=next; } Tdata; Node*link;};template<classT>classLinkList{ private:intn;//表长 Node<T>*current,*front; public:LinkList(intmSize);//构造函数,不带表头结点单循环链表~LinkList();//析构函数TRemoveCurrent();//删除操作 voidmovenext(intn);//current后移n次 intCurrentPassword(){returncurrent->password;} TCurrentData(){returncurrent->data;}voidtoLocatioin(T&t);//将current指向元素为t的结点voidOutput()const;//输出链表};//ClassLinkList//单循环链表类部分成员函数实现template<classT>LinkList<T>::LinkList(intmSize)//构造函数{ inti; Node<T>*p; current=newNode<T>; current->data=n=mSize; front=current; for(i=mSize-1;i>0;i--) { p=newNode<T>(i,current); current=p; } front->link=current;} //Joseph类定义template<classT>classJoseph{ private: intnumOfBoy; intstartPosition; intInterval; public: Joseph(intboys=10,intstart=1,intm=3) { numOfBoy=boys; startPosition=start; Interval=m; } voidGetWinner();};//Joseph类//Joseph类实现template<classT>voidJoseph<T>::GetWinner(){ LinkList<T>boys(numOfBoy); boys.movenext(startPosition-1);//?? boys.Output(); cout<<endl<<"依次出列的小孩是："<<endl; for(inti=1;i<numOfBoy;i++) { boys.movenext(interval-1); cout<<boys.RemoveCurrent()<<""; } cout<<"\nThewinneris"<<boys.CurrentData()<<endl;}//主函数mainvoidmain(){ try { time_t time1=time(NULL); structtm*t; t=localtime(&time1); srand(t->tm_sec*t->tm_min+t->tm_hour); cout<<"请输入初始数据：小孩数，间隔数，起始小孩号码：\n"; inttotal,interv,startboy; cin>>total>>interv>>startboy; Joseph<int>jose(total,startboy,interv); jose.GetWinner(); } catch(enumResultCodeerr) { switch(err) { caseError:cout<<"LocationError!\n"; caseDeleteError:cout<<"DeleteError!\n"; } }}内容3：多项式的表示和相加【问题描述】建立链式多项式类，并设计算法实现多项式的相加。【要求】1）设计多项式链表类并实现。2）相加后可将原多项式销毁，也可以保留。【选做内容】多项式的减法、乘法及除法运算。【问题思考】建立的链表不带头结点与带头结点,则在操作实现上有何差异?

栈和队列及其应用实验目的加深理解栈和队列的特性；能根据实际问题的需要灵活运用栈和队列；了解递归算法的设计；掌握栈和队列的应用方法。实验学时：建议2~4学时实验内容内容1：设计算术表达式求值类【问题描述】表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个表达式类程序，演示用算符优先法算术表达式求值的过程。【基本要求】以字符序列的形式输入语法正确且不含变量的整数表达式。利用教材中给出的算符优先关系表，实现对算术四则混合运算表达式的求值。【实现提示】表达式类说明：classexpression{ private: char*str; doubleresult; intprior(char,char);//比较运算符优先级0-相等,1-大于,-1-小于 doublevalue(charop,doublea,doubleb);//a和b进行op运算 public: expression(char*ss);//构造函数 ~expression(){delete[]str;}//构造函数 voiddel_blank();//删除串str中所有空格 voidcalculate();//对表达式串str进行计算 doublegetResult()const{returnresult;}//获取表达式的值};//classexpressionclassexpression{ private: char*s;doubleresult public:expression(char*str);//构造函数voiddel_blank();//删除串str中所有空格intprior(char,char);//比较运算符优先级0—相等,1—大于,-1—小于doublevalue(charop,doublea,doubleb);//a和b进行op运算voidcalculate()//对表达式串str进行计算voidOutput()const;//输出计算结果};//classexpression顺序栈类说明template<classT>classSeqStack//线性表抽象类{private: T*s;//存储栈空间的首地址 inttop;//栈顶指针intmaxsize;//栈空间总规模public: SeqStack（intmSize）; ~SeqStack（）{delete[]s;} voidPush(constT&x);//入栈 voidPop();//出栈 TTop()const;//访问栈顶元素 boolIsEmpty()const;//判空 boolIsFull()const;//判满};设置运算符栈和运算数栈算符优先辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算。参考算法如下：voidexpression::calculate(){ SeqStack<double>opnd(100);//opnd为运算数栈 doublea,b; SeqStack<char>optr(100);//optr为运算符栈 charoperate; optr.Push('#'); char*s=str; intk=strlen(s); s[k]='#';//在表达式尾部加结束标志 s[k+1]='\0'; while(*s!='#'||optr.Top()!='#')//当前字符为'#'且栈顶也是'#'，则计算完毕 { if(*s>='0'&&*s<='9')//当前字符为运算对象 { opnd.Push(*s-'0'); s++; continue; } while(prior(optr.Top(),*s)==1)//当前运算符优先级低于与栈顶运算符 { operate=optr.Top(); optr.Pop(); b=opnd.Top(); opnd.Pop(); a=opnd.Top(); opnd.Pop(); opnd.Push(value(operate,a,b));//计算，结果入opnd栈 } if(*s==')'&&optr.Top()=='(')//左右括号配对 { optr.Pop(); s++; continue; } if(prior(optr.Top(),*s)==0)//当前运算符优先级高则入optr栈 { optr.Push(*s); s++; } } result=opnd.Top();//当前opnd栈顶元素为表达式的值}intprior(chart,charc){//计算t和c的优先级 switch(t) {case'+': case'-': if(c=='+'||c=='-'||c==')'||c=='#')return1;//t>c elsereturn0;//t<c case'*': case'/': if(c=='(')return0;//t<c elsereturn1;//t>c case'(': if(c==')')return-1;//相等 elsereturn0; case'#': if(c=='#')return-1;//相等 elsereturn0; } return-2;//无此运算符}//prior（3）在识别出运算数的同时，实现将数字字符转换成整数形式。（4）在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。（5）算法的原理见教材。【选做内容】扩充运算符集。如乘方、赋值等运算。运算分量可以是变量。运算分量可以是多位整数或实数类型。计算器的功能和仿真界面。内容2：航空客运订票系统【问题描述】航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，完成上述功能。【基本要求】（1）每条航线信息：终点站名、航班号、飞机号、飞行周日（星期几）、乘员定额、余票量、已定票的客户名单（包括姓名、定票量、舱位等级1，2或3）以及等候替补的客户名单。（2）作为模拟系统，全部数据可以只放在内存中。（3）系统功能：查询航线、客票预订和办理退票【实现提示】（1）已定票的客户名单可采用线性表及其链表结构存储，等候替补的客户名单可采用队列。（2）系统每条航线信息可采用线性表及其顺序结构存储。（3）每条航线信息结构：包括以上8个成员信息，其中已定票的客户名单成员为已定票的客户名单链表的头指针，等候替补的客户名单成员为分别指向队头和队尾的指针。内容3：回文判断问题【问题描述】顺读与逆读字符串一样（不含空格）。【基本要求】（1）回文判断借助于栈来实现。（2）对字符串中的空格要忽略，即不进行判断，当然也可以先对原串进行处理，去掉所有空格字符，再进行判断。【实现提示】（1）回文判断借助的栈可采用链栈方式。（2）系统每条航线信息可采用线性表及其顺序结构存储。（3）算法原理：1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文

二叉树及其应用实验目的加深对二叉树的结构特性的理解；熟练掌握二叉树的存储结构，特别是二叉链表类的描述及其实现方法；熟练掌握二叉树的遍历算法原理及实现；学会编写实现二叉树的各种算法；掌握二叉树的应用方法。实验学时：建议2~4学时实验内容内容1：二叉树及其操作【问题描述】设计二叉树的二叉链表类，操作主要有建二叉树、遍历二叉树、求该二叉树中、的结点个数等。【基本要求】（1）建立二叉树可用先序方式建立，也可根据二叉树的先序和中序序列建立。（2）对二叉树的遍历可采用递归或非递归的算法。【实现提示】二叉链表的结点结构描述structbtnode{//定义结点类型ElemTypedata;//数据域btnode*lchild，*rchild;//左、右指针域/};//btnode可设计以下功能函数：btnode*createbitree();//建立二叉链表voidpreorder(btnode*bt);//先序遍历二叉树intsum(btnode*bt);//求二叉树中的结点个数算法可用递归或非递归实现。建立二叉树可用以下两种算法实现：方案1：btnode*createBT()//前序建树{bitreeT;charch;cin>>ch;if(ch==’#’)returnNULL;//二叉树为空T=newBinTNode;//申请根结点T->data=ch;T->lchild=createBTpre();//创建根的左子树T->rchild=createBTpre();//创建根的右子树returnT;}方案2：btnode*createBT(char*preorder,char*midorder){//由前序preorder和中序midorder建树，返回根指针if(strlen(preorder)==0)returnNULL;//空二叉树T=newNode;//建立根结点T->data=*preorder;k=locate(midorder，*preorder);//找根在中序中的位置lmidorder=fetch(midorder,0,k);//左子树的中序lpreorder=fetch(preorder,1,k);//左子树的前序rmidorder=fetch(midorder,k+1);//右子树的中序rpreorder=fetch(preorder,k+1);//右子树的前序T->lchild=createBT(lmidorder,lpreorder);//建根的左子树T->rchild=createBT(rmidorder,rpreorder);//建根的右子树returnT;}intsum(btnode*bt)//求二叉树中的结点个数{if(!bt)return0;//二叉树为空returnsum(bt->lchild)+sum(bt->rchild)+1;}【选做内容】对二叉树进行层次遍历算法。求二叉树的深度、宽度等操作。复制二叉树，交换二叉树中左右子树的问题怎么实现?内容2：哈夫曼编码/译码器【问题描述】设字符集为26个英文字母，其出现频度如下表所示。先建哈夫曼树，再利用此树对报文“Thisprogramismyfavorite”进行编码和译码。5151481156357203251频度zyxwvut字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度iedcba空格字符【基本要求】算法具有以下功能：（1）CreateHuffmanTree：根据给定字符的出现频数，建立其哈夫曼树。（2）Encoding：对给定的原字符串进行编码。（3）Decoding：对给定的编码串进行译码（或解码）。ShowHuffmanTree：显示哈夫曼树【实现提示】用户界面可设计成模拟菜单方式。原字符串及编码串可从键盘输入。生成Huffman树的步骤如下：①由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合（即森林）F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。②在F中选取两棵根结点的权值最小的树做为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。③在F中删去这两棵树，同时将新得到的二叉树加入F中。④重复②和③,直到F只含一棵树为止。这棵树便是赫夫曼树。【选做内容】字符的出现频数能否从指定文件中统计而得？对指定的文件进行编码/解码。

图及其应用实验目的1.加深对图的结构的理解；2.熟练掌握图的存储结构，特别是图的邻接表结构；3.熟练掌握图的搜索算法原理及其实现；4.掌握图的常用的应用方法。实验学时：建议2~4学时实验内容内容1：图的搜索问题【问题描述】设计无向图的邻接表类并实现，演示在连通的无向图上访问全部结点的操作。【基本要求】（1）以邻接表作为存储结构，并对图进行深度优先和广度优先搜索。（2）以指定结点为起点，分别输出每种搜索方式下结点访问序列和相应生成树边集。【实现提示】（1）图的每个结点用一个编号表示（如1~n）。通过输入图的全部边来输入一个图，每个边是一个数对。（2）数据结构描述见教材。（3）无向图的邻接表类的主要成员函数：voidcreateadjlist()；//建立图的邻接表voiddesttraverse(intk)；//图的深度优先搜索voidbesttraverse(intk)；//图的广度优先搜索【选做内容】借助栈，用非递归算法实现深度优先搜索。内容2：教学计划编制问题【问题描述】教学计划中各课程之间必须满足先修关系。每门课程的先修课程是确定的，可以有任意多门，也可以没有。试在这样的前提下设计一个教学计划编制的程序。【基本要求】（1）输入数据：学期总数、一学期学分上限、课程号、课程学分和先修课程课程号。（2）编排策略：使每学期的总学分数尽量均匀。【实现提示】可设学期总数不超过12，课程总数不超过100。【选做内容】产生多种不同的方案，并使方案之间的差异尽可能大。

查找实验目的1．熟练掌握顺序表和有序表的查找方法及算法实现。2．熟悉常用查找算法的编写。3．理解静态查找和折半查找的关系。4．熟练掌握二叉排序树的构造