《数据结构实验指导书及练习题曲.doc》由会员分享，可在线阅读，更多相关《数据结构实验指导书及练习题曲.doc（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验指导书自动化学院电子系 曲卫芬 编 实验指导教师 曲卫芬 于瑞涛2007年9月一前言1、 数据结构课程实验的地位与作用 “数据结构”是理工科专业一门重要的专业技术基础课程。是将来驾驭计算机，指挥计算机，为自己的工作服务的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大的难度：（1） 内容丰富，学习量大，给学习带来困难；（2） 贯穿全书的动态链表存储结构和递归技术是
2、学习中的重点也是难点；（3） 所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；（4）相关的程序设计基础C语言的学习尤其重要。但我们学生的C语言的学习是在大一就开设的，加上是公共课，对数据结构里用的指针和结构体等方面的知识讲解的很少，学生反映考试又不考相关内容，就没有足够的重视和学习，也可以说，就没学这部分的内容，这更加大了这门课的学习难度。（5） 隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据数据结构课程课程本身的技术特性，设置数据结构课程实验实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程
3、序的能力。由于学分的限制，安排上课40学时，实验安排9学时。2、 数据结构课程实验的目的和要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术，掌握数据结构中稍微复杂一些的算法设计中可能同时用到的多种技术和方法，
4、如算法设计的构思方法，链表、栈、队列、树等算法的编码，递归技术，与特定问题相关的技术等。在数据结构中要求重点掌握线性链表、二叉树和树、图、数组等结构相关算法的设计。在掌握基本算法的基础上，提高分析、解决实际问题的能力。3、 数据结构课程实验对相关课程的要求 要求认真复习C语言的程序设计，复习和自学数组，指针、结构体、函数等内容，建立起程序设计思想，锻炼独立编写程序的能力。二实验题目 实验一 约瑟夫环的程序实现【实验目的】（1）进一步掌握线性表的各种链式存储结构，包括单链表与循环链表，熟悉各种操作。（2）认真分析实际项目的内容，将其中的算法付诸实现，目的是练习利用线性表的链表结构来解决实际应用问
5、题的能力，掌握线性表的实际应用。【实验内容与要求】问题描述：编号是1,2,n(n0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。【知识要点】 关于单循环链表的概念请参见课本中所学的知识要点。循环链表上的运算与单链表上运算基本一致，区别只在于
6、最后一个结点的判断(即循环的条件不同)，但利用循环链表实现某些运算较单链表方便(从某个结点出发能求出它的直接前驱，而单链表是不行的，只能从头出发)。图1-1给出带头结点的循环链表的两种结构。 头 a1 a2 an head (b) 非空循环表 图1-1 带头结点的单循环链表示意图 (a) 空循环表 头 head 【实现提示】 由于该问题是由古罗马著名史学家Josephus提出的问题演变而来，所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表，先构造一个有n个结点的单循环链表，再给出一个报数上限值m(假设m1)，在链表的首结点开始从1计数，计到m时，对应的结点从链表中
7、删除，然后在被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。 本设计采用的是不带头结点的循环链表，问题简化成固定密码，从键盘上输入人数N和密码M，开始报数，出列，直到结束。其中循环链表中结点的结构如下： typedef struct int num; struct node *next; linklist;该问题可由两部分组成，分别由如下两个算法完成：（1）建立一个由头指针head指示的有n个结点的约瑟夫单循环链表函数creat。（2）寻找、输出和删除head所指的单循环链表的第m个结点函数select。该算法由如下具体步骤组成：在head中的第一个结点起循环记数找
8、第m个结点；输出该结点的num值；删除该结点；转去执行,直到所有结点被删除为止。【参考程序】 程序和定义内容如下： #includetypedef struct node int num; struct node *next; linklist; /* 建立单循环链表函数 */ linklist *creat(int n) int k; linklist *head, *r, *p; p=(linklist *)malloc(sizeof(linklist); head=p; p-num=1; r=p; p-next=p; for(k=2;knum=k; r-next=p; r=p; p-ne
9、xt=head;return(head); /* 选择出列编号 */linklist *select(linklist *head, int m) linklist *p,*q; int k;q=head;k=1;p=q-next; /q为p的前趋指针,p指向当前报数的人while(q!=p) k=k+1; /报一次数 if(k=m) printf(%d ，,p-num); q-next=p-next; /对应的结点从链表中删除 free(p); k=0; p=q-next; elseq=p; p=p-next; / p指向当前报数的人 head=p;return(head);void mai
10、n() int n,m;linklist *head;printf(Input N and M:n);scanf(%d%d,&n,&m);head=creat(n);head=select(head,m);printf(%dn,head-num);假设n=5,m=3,则程序的出列编号顺序为3，1，5，2，4 。【实验的具体要求】1.调试上面的程序，给出以下3组数据：n=5,m=3，n=7,m=20，n=15,m=9给出程序的执行结果。2.若输入的起始密码是1（如n=5,m=1）检查结果是否正确？若不正确，如何修改此程序？3.修改上面的问题要求：要求每个人手里都有一个密码，每次出列后，用此人手中
11、的密码继续报数，直到结束。写出数据结构的定义并编写程序，调试并写出实验数据和执行结果。实验测试数据假设n=7,m=20,7个人的密码依次为3,1,7,2,4,8,4,则程序的出列编号顺序为6,1,4,7,2,3,5。【问题的其他方法】1、定义循环链表采用“头结点”，程序又该怎样编写？请注意空表和非空表的界限。2、不用循环链表，采用顺序表结构编程实现上述问题。实验二 算术表达式求值【实验目的】（1）掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 （2）栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈。（3）认真分析实
12、际项目的内容，将其中的算法付诸实现，目的是练习利用顺序栈的结构来解决实际应用问题的能力，掌握栈的实际应用。【实验内容与要求】问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的一个典型应用实例。设计一个程序，实现用运算符优先法对算术表达式求值。基本要求：以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，只包含加、减、乘、除、括号运算，并且键盘中输入的表达式都是正确，以#作为结束符。编程实现对算术四则混合运算表达式的求值。【知识要点】关于栈的概念请参见课本中所学的知识要点。 栈是只能在某一端插入和删除的特殊线性表。一个栈可以用定长为StackSize的数组来表示，用一个栈指针
13、TOP指向栈顶。若TOP0，表示栈空，TOP=StackSize时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。栈指针在运算中永远指向栈顶。一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式计算是栈的典型应用之一。【实现提示】分析表达式要素包含有：运算符、操作数、界定符、运算符优先级关系。界定符有括号和表达式结束符（设为#）等。可设置两个栈：OPTR用于寄存运算符，OPND用于寄存操作数或运算结果。顺序栈的类型定义如下： # define StackSize 100 typedef int datatype; typedef struct datatype dataStackSize; int top; SeqStack;算法基本思想：先置操作数栈OPND为空栈，表达式起始符为运算符栈的栈底元素；依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。（即OPTR栈的栈顶元素和当前读入的字符均为#
