大学实验指导书.docx

《大学实验指导书.docx》由会员分享，可在线阅读，更多相关《大学实验指导书.docx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导书实验一抽象数据类型2实验二线性表及其应用3实验三栈和队列及其应用5实验四串及其应用8实验五数组及其应用9实验六树及其应用12实验七图及其应用15实验八查找与排序算法18实验报告撰写指导22韶关学院信息工程学院计算机系教师：陈正铭2007-9-10实验一抽象数据类型【实验目的】熟悉抽象数据类型的表示和实现方法，重温高级语言的使用方法。【实验内容】设计-个可进行复数四则运算的演示程序，要求实现下列六种基本运算:1)由输入的实部和虚部生成一个复数；2)两个复数求和；3)两个复数求差；4)两个复数求积；5)从已知复数中分离出实部；6)从已知复数中分离出虚部。运算结果以相应的复数或实数

2、的表示形式显示。【实验指导】为实现上述程序功能，应以实数二元组表示复数。抽象数据类型复数定义如下：ADT Complex 数据对象：D=el,e2 I el,e2GRealSet 数据关系：Rl =lel是复数的实数部分,Ie2是复数的虚数部分基本操作：InitComplex(&Z, vl, v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数vl和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal( Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。Getlmag( Z,&ImagPart)初始条件：复数已存在。

3、操作结果：用ImagPart返回复数Z的虚部值。Add( z 1,z2,&sum )初始条件：zl,z2是复数。操作结果：用sum返回两个复数zl,z2的和值。Sub(zl,z2,&dif)初始条件：zl,z2是复数。操作结果：用dif返回两个复数zl,z2的差值。Mul( zl,z2,&pro)初始条件：zl,z2是复数。操作结果：用pro返回两个复数zl,z2的积值。Div( zl,z2,&quo)初始条件：zl,z2是复数。操作结果：用quo返回两个复数zl,z2的商值。1 .定义复数为两个相互之间存在次序关系(实部、虚部)关系的实数构成的抽象数据类型,则可把复数运算转换为实数运算实现；

4、2 .掌握ADT的定义方法3 .注意C语言中结构体的使用方法。【算法要点】struct Complex/复数类型ElemType real,imag;复数的实部 real,虚部 imagstatus CreateComplex(Complex *T)生成一个复数status OutputComplex(Complex T)输出复数status AddComplex(Complex *T,Complex A,Complex B)计算复数和 T=A+BTLimag=A.imag+B.imag;T-real=A.real+B .real;return OK;实验二线性表及其应用【实验目的】掌握线性表

5、的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用为主要内容。【实验内容】约瑟夫(Joseph)问题的一种描述是：编号为1,2,，n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【实验指导】为实现上述程序功能，应以循环单链表表示约瑟夫环。抽象数据类型复数定义如下：ADT CLinkList数据对象：D=出 I ai ElemSet

6、,n20数据关系：Rl =lai，i ,ajD, i=2,n；基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L0ListEmpty( L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE,否则FALSE。ListLength( L)初始条件：线性表L已存在。操作结果：返回L中元素个数。PriorElem( L, cur_e,&pre_e)初始条件：线性袤L已存在。操作结果：若cur_e是L的元素，但不是第个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(

7、 L, cur_e,&next_e )初始条件：线性袤L已有在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElem( L, i,&e )初始条件：线性表L已存在，且iWiWLengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem( L, e, compare()初始条件：线性表L已存相，e为给定值，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为00ListTraverse(L, visit()初始条件：线

8、性表L已存在。Visit()为某个访问函数。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem( L, i,&e )初始条件：线性表L已存在，且liLengthList(L)。操作结果：把e值赋到L中第i个元素。Listlnsert(&L, i, e )初始条件：线性表L已存在，且liLengthList(L)+l操作结果：在L的第i个元素之前插入新的元素e, L的长度增1。ListDelete(&L, i,&e)初始条件：线性表L已存在且非空，且iSiWLengt

9、hList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。)1、使用单向循环链表进行模拟出列顺序；2、注意链表中不需设头结点；3、注意空表和非空表的界限和判断条件。【算法要点】typedef struct Node结点类型ElemType member, key;顺时针排列的人member,人持的密码keyNode *next;指向下个结点的指针*PNobe;typedef struct CirLinkList/循环链表类型PNobe tail;/循环链表的表尾指针int len;链表的长度*Link;struct JosephCirclel约瑟夫环类型ElemType fi

10、rstkey，第一个任选上限值int num;约瑟夫环围坐的人数CirLinkList List;用循环链表表示人按顺时针围坐一个圈)；int ListEmpty(CirLinkList L)判断循环链表是否为空，若是返回1,否则返回0return L.len=O;status DeJosephCirclel(JosephCirclel &J)按约瑟夫问题描述顺序出列ElemType e=J.firstkey;PNobe p;coutvv”按约瑟夫问题描述顺序出列为:1,endl;while(!ListEmpty(J.List)Remove(p,e%J.List.len,J.List);Out

11、putMem(p);GetKey(e,p);FreeNode(p);return OK;)实验三栈和队列及其应用【实验目的】深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们，同时巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。【实验内容】设停车场是一个可停放n辆汽车的通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，一次由北向南排列，若车场内已停满n辆车，这后来的汽车只能在门外的便道上等候，一旦有车开车，则排在便道的第一辆车即可进入；当停车场内某辆车要离开时，在它之后的必须先退出车场为它让路，待该车开出大门外，其他车辆再按原次序进入车场，每辆停放

12、在停车场的车在它离开停车场时必须按他停留的时间长短交纳费用。试为停车场编制按上要求进行管理的模拟程序。【实验指导】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包含三个数据项：汽车“到达”或“离去”信息，汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。栈以顺序结构实现，队列以链表结构实现。抽象数据类型栈定义如下：ADT Stack 数据对象：D= ai I ai ElemSet, i=l,2,.,n, n2

13、0数据关系：Rl =1 ai-1, aiGD, i=2,.,n )约定 an 端为栈顶，al 端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈SoDestroyStack(&S)初始条件：栈s已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈s已存在。操作结果：若栈S为空栈，则返回TRUE,否则FALEoStackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push

14、(&S, e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。抽象数据类型队列定义如下：ADT Queue 数据对象：D=ai I ai ElemSet, i=l,2,n, n20数据关系：Rl = I ai-1, ai G D, i=2,.,n约定其中al端为队列头，an端为队列尾基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：

15、若Q为空队列，则返回TRUE,否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。EnQueue(&Q, e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。1、以栈模拟停车场，以队列模拟停车场外的便道；2、栈以顺序结构实现，队列以链表结构实现；3、设计时为了临时停

16、放为要离开的汽车让路而从停车场倒出来的车，需另设一个临时栈(可用顺序结构实现)；注意输入数据需要按到达或离开的时刻有序。【算法要点】struct ElemType定义表示汽车属性的类型int number,arrtime,deptime;汽车的车号 number,到达时刻 arrtime,离开时刻 deptimestruct Stack/定义栈的类型ElemType *base,*top;栈的基指针 base,栈顶指针 topint len;栈的长度len；typedef struct QNobe定义队列的结点数据类型ElemType data;QNobe *next;*PQNobe;stru

17、ct Queue定义队列的类型PQNobe front,rear;队头指针 front,队尾指针 rearint len;队列的长度；struct PostStack S1,S2;栈SI用来模拟停车场，栈S2用来临时停放给离开的车让道的场地Queue Q;模拟便道停车；status ArrPost(Post &P,ElemType e)车进入停车场if(!StackFull(P.Sl)Push(P.Sl,e);coutvv请您把车放在车场第vvP.S 1.lenvv”号位 vvendl;elsecoutvv”请您把车放在便道第”vRQ.len+lvv”号位“vvendl;EnQueue(P.Q

18、,e);return OK;)status DepPost(Post &P,ElemType e)车退出停车场ElemType equal,temp;int time;doPop(equal,P.S 1);if(equal.number!=e.number)Push(P.S2,equal);while(equal.number!=e.number);while(! StackEmpty(P.S2)Pop(temp,P.S2);Push(P.Sl,temp);)if(!QueueEmpty(P.Q)DeQueue(temp,P.Q);temp.arrtime=e.deptime;Push(P.S

19、l,temp);)time=e.deptime-equal.arrtime;cout您的车在停车场停了time个小时，应收取您的停车费time*PRICE元3 nendl;return OK;)实验四串及其应用【实验目的】熟悉串类型的实现方法和文本模式匹配的方法，熟悉般文字处理软件的设计方法以及较复杂问题的分解求精方法。【实验内容】文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。写一个实现这一目标的文字统计系统，称为“文学研究助手二【实验指导】参看数据结构题集P1231、基本要求只需处理英文文档；2、约定英文文档中单词不跨行；3、单词出现位置所在行号可用链表存储，若某行出现某单词

20、不止一次，则只需存一次。【算法要点】struct ElemType单词类型String data;单词串int len;单词的长度；int MatWord(ElemType S,ElemType T)单词的匹配，若相等则返回0,否则返回非0for(int i=O;iS.len&inext;while(ps)遍历待搜索的单词链表的每个结点pr=RL.head-next;int leap=l;while(pr)遍历本文中一行单词链表的每个结点if(! MatWord(pr-data,ps-data)ps-cout+;if(leap=l)判断待搜索单词是否第一次出现if(ps-RMhead=NULL

21、)判断是否是第一个结点MakeRowNumNobe(ps-RMhead);生成一个行结点ps-RMhead-elem=i;ps-RMtail=ps-RMhead;elseMakeRowNumNobe(psRMtail-next);生成个行结点ps-RMtai l-nex t-elem=i;ps-RMtail=ps-RMtail-next;leap=0;)pr=pr-next;ps=ps-next;DestroyRLink(RL);车肖毁链表 RLreturn OK;实验五数组及其应用【实验目的】深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。【实验内容】稀疏矩阵是指那些多数元素为零

22、的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。输入以三元组表示，输出以通常的阵列形式列出。【实验指导】ADT Array 数据对象：D =aij IOibl-1,0 WjWb2，l数据关系：R = ROW, COL ROW =l OWiWbl-2,0WjWb2-lCOL =l OWiWbLl, OW j Wb2-2基本操作：CreateSMatrix(&M);操作结果:仓U建稀疏矩阵M.Print SMatrix(M);初始化条件：稀疏矩

23、阵M存在.操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);初始化条件：稀疏矩阵M与N的行数和列数对应相等.操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);初始化条件：稀疏矩阵M与N的行数和列数对应相等.操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);初始化条件：稀疏矩阵M的列数等于N的行数.操作结果:求稀疏矩阵的乘积Q=M*N. ADT Array1、掌握“带行逻辑链接信息”的三元组顺序表存储稀疏矩阵的方法；2、注意矩阵运算的法则，如两矩阵相加则要求其行列数均相等才能进行；3、三元组输入注意要求按次序进行，如行优先；4、两矩

24、阵相乘的结果矩阵可用二维数组存储。【算法要点】struct Treple/三元组int row,col;ElemType elem;；structTSMatrix/“带行逻辑链接信息”的三元组顺序表Treple dataMAXSIXE+l;int mrow,mcol,mu;intrpotMAXSIXE+l,cpotMAXSIXE+l;；Status AddSMatrix(TSMatrix &Q,TSMatrix M,TSMatrix N)求稀疏矩阵的加 Q=M+Nint i j,mumMAXSIXE=0,cnumMAXSIXE=0;if(M.mrow!=N.mrow&M.mcol!=N.mco

25、l)cout错误!矩阵的行数、列数不相等endl;exit(FALSE);Q.mcol=M.mcol;Q.mrow=M.mrow;for(i=l,j=l,Q.mu=l;i=M.mu&jN.datai.col)Q.dataQ.mu=N.dataj;j+;elseQ.dataQ.mu=M.datai;i+;else if(M.datai.rowN.dataj.row)Q.dataQ.mu=N.dataj;j+；elseQ.dataQ.mu=M.datai;i+;mumQ.dataQ.mu.row+;cnumQ.dataQ.mu.col+;Q.mu+;)if(iM.mu)for(;jv=N.mu;j

26、+,Q.mu+)Q.dataQ.mu=N.dataj;j+；mumfQ.dataQ.mu.row+;cnumQ.dataQ.mu.col+;if(jN.mu)for(;i=M.mu;i+,Q.mu+)Q.dataQ.mu=M.datai;i+；mumfQ.dataQ.mu.row+;cnumQ.dataQ.mu.col+;Q.mu;Q.cpot1=1;Q.rpot1=1;for(i=2;i=Q.mrowlli=Q.mcol;i+)Q.cpoti=Q.cpoti-1+cnumi-1;Q.rpoti=Q.rpoti-1+mumi-1;return OK;)Status MultSMatrix(TS

27、Matrix &Q,TSMatrix M,TSMatrix N)求稀疏矩阵的积 Q=M*Nint i,j,k,t,tl,cnumMAXSIXE=0;if(M.mcol !=N.mrow)coutvv”错误!矩阵M的行数和矩阵N的列数不相等”endl;exit(FALSE);Q.mrow=M.mrow;Q.mcol=N.mcol;Q.mu=0;for(i=l ;i=M.mrow;i+)Q.rpoti=Q.mu+1;int tempMAXSIXE=0;if(i=M.mrow)t=M.mu+l;else t=M.rpoti+l;for(j=M.rpoti;jt;j+)if(M.dataj.col=N

28、.mrow)tl=N.mu+1;else 11=N.rpotM .dataj.col+1;fbr(k=N.rpotM.dataj .col;kt 1;k+)tempN.datak.col+=M.dataj.elem*N.datak.elem;)for(k=l ;k=N.mcol;k+)if(tempk!=0)Q.mu+;Q.dataQ.mu.elem=tempk;Q.dataQ.mu.col=k;Q.dataQ.mu.row=i;cnumQ.dataQ.mu.col4-+;Q.cpotl=l;for(i=2;il时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每棵子集本身又

29、是一棵符合本定义的树，称为根root的子树。基本操作：Status initHTree(HuffmanTree &T,int n)初始化一个n个字符集的哈夫曼树Status DestroyHTree(HuffmanTree &T)销毁哈夫曼树Status Select(int &sl,int &s2,int n,PHTNode H)从二叉树位置从0n集合中找到2个根结点的权值最小的位置Status HEncoding(char stringSIZE)哈夫曼编码，并把结果保存在string文件中Status HDecoding(char stringSIZE)哈夫曼译码，并把结果保存在strin

30、g文件中 ADT Array1、掌握哈夫曼编码的原理，简单说就是“最小权值两两合并二2、哈夫曼树采用孩子双亲顺序表存储；【算法要点】typedef char *EIemType;typedef struct HTNode哈夫曼树结点类型int weight;结点的权值int parent,lchild,rchild;结点的双亲parent,结点的左子树Ichild,结点的右子树rchiid *PHTNode;struct HuffmanTree/哈夫曼树类型HTNode *HT;哈夫曼树ElemType ch;哈夫曼树的字符集int n;虫夫曼树的字符集个数)；Status CreateHTr

31、ee。/创建哈夫曼树并把结果保存在string为文件名的文件里int i,sl,s2;FILE *fp,*cfp;char c,stringSIZE;HuffmanTree T;int n;cout请输入字符集的大小(n)/; cinn;initHTree(T,n);初始化一个n个字符集的哈夫曼树cout请输入字集的保存路径名称:;cinstring;OpenReadFile(cfp,string);cout请输入字符集对应的权值/endl;for(i=l ;i=T.n;i+)c=getc(cfp); coutc:; T.chi=c; cinT.HTil.weight;T.HTi.parent

32、=O; T.HTi.rchild=O; T.HTi.lchild=O;)for(;i2*T.n;i+)T.HTi.weight=O; T.HTi.parent=O; T.HTi.rchild=O; T.HTi.lchild=O;for(i=T.n+l ;i2*T.n;i+)SelectsI,s2,i-1,T.HT);从二叉树位置从0n集合中找到2个根结点的权值最小的位置T.HTi.lchild=sl;T.HTi.rchild=s2;T.HTs 1.parents ;T.HTs2.parent=i;T.HTi.weight=T.HTsl.weight+T.HTs2.weight;cout请输入哈

33、夫曼树的保存路径名称:;ci ns tri ng;OpenWriteFile(fp,string);fwrite(&T.n,sizeof(int),1,fp);fwrite(T.HT,sizeof(HTNode),2*T.n,fp);fwrite(T.ch,sizeof(char),T.n+ l,fp);fclose(fp);fclose(cfp);DestroyHTree(T);return OK;Status HEncoding(char stringSIZE)哈夫曼编码，并把结果保存在string文件中HuffmanTree T;FILE *fp,*hfp,*cfp;int i,j,k;

34、char chSIZE,c,*cd;cout请输入保存哈夫曼树的保存路径名称；cinch;OpenReadFile(hfp,ch);cout请输入要编码文件的保存路径名称:;cinch;OpenReadFile(fp,ch);cout请输入代码文件的保存路径名称:;cinstri ng;OpenWriteFile(cfp.string);fread(&T.n,sizeof(int),1,hfp);if(!(cd=new charT.n)cout编码工作空间分配失败endl;exit(ERROR);initHTree(T,T.n);fread(T.HT,sizeof(HTNode),2*T.n,

35、hfp);fread(T,ch,sizeof(char),T.n+1,hfp);c=getc(fp);while(!feof(fp)for(i=l ;i=T.n&c!=T.chi;i+);j=T.n;k=i;while(T.HTk.parent)if(T.HTT.HTk.parent.lchild=k)cd-j=O；k=T.HTk.parent;elsecd-j=l；k=T.HTk.parent;for(j；jT.n;j+)putc(cdj,cfp);c=getc(fp);DestroyHTree(T);delete(cd); fclose(cfp); fclose(hfp); fclose(

36、fp);return OK;)Status HDecoding(char stringSIZE)哈夫曼译码，并把结果保存在string文件中HuffmanTree T;char chSIZE,c;FILE *fp,*hfp,*cfp;cout请输入保存哈夫曼树的保存路径名称:;cinch;OpenReadFile(hfp,ch);fread(&T.n,sizeof(int),1,hfp);initHTree(T,T.n);fread(T.HT,sizeof(HTNode),2*T.n,hfp);fread(T.ch,sizeof(char),T.n+l,hfp);void PrintHTree

37、(HuffmanTree T);cout请输入代码文件的保存路径名称:;cinch;OpenReadFile(cfp,ch);cout请输入库码上件的保存路径名称:;cinstring;OpenWriteFile(fp,string);c=getc(cfp);while(!feof(cfp)for(int i=2*T.n-1;T.HTi.lchild&!feof(cfp);c=getc(cfp) if(c=O)i=T.HTil，lchild;else i=T.HTi.rchild;putc(T.chi,fp);fclose(cfp); fclose(hfp); fclose(fp); DestroyHTree(T);return OK;实验七图及其应用【实验目的】熟悉图的各种存储结构及其构造、遍历算法，掌握各种图的应用算法，如求最短路径等。【实验内容】设计一个校园导游程序，为来访的客人提供各种信息查询服务。要求学校所含景点不少于10个，图中顶点表述景点，边表示景点间的路径。【实验指导】ADT Array 数据对象：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：Graph =(V, R ),其中，VR =l v,w V 且 P(v,w)表示从V到W的一条弧，并称V为弧头，W为弧尾。谓词P(v,w)定义了弧的意