数据结构实验指导书.doc

备 课 本（ 学年第 学期 ） 系 专业 年级 班课程名称 数据结构实验 教材名称 数据结构实验指导书 主要参考书 数据结构题集 教材大纲类型 任课教师 15实验一 线性表的链式存储【实验时间】 2010年3月18日【实验地点】 【实验目的和要求】1掌握线性表的结构特点和表示方法；2掌握线性表链式存储结构特性和基本操作算法；3掌握用指针实现单链表的建立、输出、插入和删除的算法。【实验类型】 验证性【实验时数】 2学时【实验设备】 计算机【参考资料】 1数据结构题解2C程序设计【实验内容】 熟练掌握线性表的链式表示和实现方法，利用其定义具体的链表结点；利用链表的结构特点，建立单链表；利用链表结点间的指针关系，实现链表的插入和删除。具体要求(1) 建立单链表时，要首先输入链表长度，根据输入值来确定所建链表的结点个数；(2) 在单链表中插入新结点时，要给出结点的插入位置和数据域的值；(3) 在单链表中删除某个结点时，要给出要删结点的位置；(4) 要编写单链表的输出函数，以便能验证程序的执行结果。【实验分析】1、实验的第一步应该建立单链表结点类型和程序所需的宏或数据类型，例如：#define NULL 0 /宏定义NULL的值为0#define LEN sizeof(struct node) /宏定义LEN，为申请结点空间时做准备typedef struct int a; float b; elemtype; /定义elemtype类型，这里同学们可以根据自己的情况来自行定义。typedef struct node elemtype data; /data域为elemtype类型的，它应该包含两个子域：a和b struct node *next; NODE , *NODEPTR; /定义了单链表结点类型和单链表结点指针类型2、对单链表的四种操作进行实现。(1) NODEPTR creatlink() 建立单链表的函数很明显这个函数的返回值是结点指针类型的，所以这个函数应该返回的是建立的单链表的头指针。同学们可以根据自己的构思，从前往后或从后往前建立单链表。此外，提醒同学们最好建立带有附加头结点的单链表。(2) void print(NODEPTR Lh) 输出单链表的函数这个函数主要是将单链表中各结点的数据域的信息输出出来，输出数据的格式要根据同学们对于链表结点的data域所属的elemtype类型来设定。(3) void del(NODEPTR Lh,int i) 删除结点的函数这个函数完成的是在链表Lh中删除指定位置i的结点。i的值是在执行删除操作之前通过键盘输入的。(4) void insert (NODEPTR Lh, int i) 插入结点的函数 这个函数完成的是在链表Lh中在指定位置i的结点前或后面插入新建结点。i的值是在执行插入操作之前通过键盘输入的。同学们可以根据自己的情况选择是在结点前面插入还是在后面插入。3、第二步应该构思程序主界面。本实验要求实验单链表的建立、输出、插入和删除四种具体操作，因此可以主界面中可以给出相应的这四种操作的标题，用户在运行时可以根据自己的需要来选择要进行的操作，形式可以如下：*Creat: 1 Print: 2Delete: 3 Insert: 4Esc: 0*please input your choice (0-4):用户通过键盘输入各操作对应的数码，就可以进入相应的操作了。这是要使用一个变量(假设为operate_num)来接收用户输入的操作数码，在主函数中利用switch语句根据这个量的值来进行不同的操作。例如：switch (operate_num)case 1:进行单链表建立操作;break; case 2:输出单链表的数据信息；break; case 3:输入要删除的结点的位置；删除指定结点；break; case 4:输入要插入的位置；插入新建结点； break;【实验原理、数据(程序)记录】略。请同学们根据上面的步骤提示自己编程，不要互相抄袭。【实验结果】 根据具体执行的情况，写出相应的实验结果。同学们各自执行的结果应该不尽相同。【注意事项】1.学生上机时要严格遵守实验规章制度，若实验设备出现故障，应及时向实验指导教师反映，不要私自拆卸实验设备。2.独立完成实验要求的内容，仔细观察和记录实验结果，领会实验目的，并认真完成实验报告。实验二 简单运算器的实现【实验时间】 【实验地点】 【实验目的和要求】1掌握栈的结构特点、操作特征和表示方法；2掌握栈的存储结构特性和基本操作的算法；3掌握用栈实现简单四则运算的算法，从而设计和实现一个简单的运算器。【实验类型】 设计性【实验时数】 4学时【实验设备】 计算机【参考资料】 1数据结构题解2C程序设计【实验内容】 充分理解栈的操作受限的特点，利用先进先出的结构特性实现实际应用问题。具体要求(1)定义栈类型为“stack”。(2)输入一个包含、和括号简单四则运算表达式，程序可以得出正确结果； (3)仔细理解表达式的求解过程，归纳运算符优先级的表示方法并用程序实现。【实验分析】1、定义程序所需的栈类型“stack”，例如：typedef struct float s10; int top; stack; /*定义栈类型*/同学们可以起另外的类型名称。2、写出栈的基本运算void inistack(stack *st) /*置栈空,s-top应该为1*/float gettop (stack *st) /*取栈顶元素返回*/void push (stack *st,float x) /*元素x进栈,s-top应加1*/float pop(stack *st) /*元素出栈，并出栈的栈顶元素返回,s-top应减1*/用程序将它们实现，以备后面程序中使用。同学们可以定义另外的形式参数名。3、设计实现用于“出栈运算”的函数operatefloat operate (float a,char theta,float b) /*进行相应运算并得到结果*/若当前读入的算符优先级小于算符栈栈顶算符优先级时，就要进行相应的“出栈运算”。其中要让算符栈栈顶算符出栈，再让操作数栈连续两次出栈依次得到右操作数和左操作数。之后，就可以利用这个函数来进行相应的运算了。函数形参中的a和b分别表示左操作数和右操作数，theta表示此时要进行的算符。本实验是实现简单的四则运算，因此theta只可能是“、”。可以利用switch语句来判断theta，根据判断结果，做相应的运算。例如：Switch（theta） cast”+”: 做加操作，得a+b的和;break; case”-“: 做减操作，得a-b的差;break; case”*”: 做乘操作，得a*b的积;break;case”/”: 做除操作，得a/b的商;break;最后将运算结果返回即可。4、实现算符优先级的函数precede函数。char precede (char 1,char 2) /*比较相继出现的两个运算符2与2的优先级，返回字符*/根据四则运算的优先级可以得到书第53面表3.1的算符间的优先关系表。仔细观察这张表，可以得到一定的规律，由此可以编写precede函数。在看这张表时一定要记住1和2是相继出现的，也就是说1先出现，然后2再出现并与1比较优先级的高低。由此，可以说1是算符栈的栈顶算符，而2是当前读入的算符。仔细观察这张表，可以得到一些规律：(1) 1是“”和“”时，当2是“*”、“/”和“（”时，它们的优先级关系应该是“”；(2) 1是“*”和“/”时，当2是“（”时，它们之间的优先级是“”；(3) 1是“（”时，当2是表达式结束符时，它们之间的优先级是错误的可以用字符“e”表示，其余情况又可以分成两种：当2是“）”时，它们之间的优先级是相同的“”，2是其它字符时，它们之间的优先关系是“”；(5) 2是表达式结束符时，当2也是表达式结束符时，它们之间的优先关系时相等的用“”表示，其余情况又可分为两种：当2是“）”时，它们之间的优先级关系用“e”表示，2是其它字符时，它们之间的优先级关系都可以利用“”来表示。这五种情况就将相继出现的算符1和2之间的优先级关系总结完毕了。接下来，就是考虑用什么语句来实现它了。很显然，总共有5种情况，而这5种情况都是根据1的值来分的，即当1的值确定后，再根据2的值来判断，因此可以利用switch语句来实现：Switch(1) case +: case -: if (2是“*”或是“/”或是“（”） z=; break; case *: case /: if(2是“（”） z=; break; case (: if(2是表达式结束符） z=e else if(2是“)”） z= else z=; break; case ): case 表达式结束符: 最后将优先级比较的结果z的值返回即可。5、判断当前读入的字符是不是算符的in函数；int in(char ch,char opn) /*判断字符是否为算符*/字符数组opn中包含“”、“”、“*”、“/”、“（”、“）”和表达式结束符。只要将当前读入的字符w与数组元素值一一比对，当前读入的字符ch只要等于这些字符中的一个，就可以断定当前读入的是算符，返回1；如果都不等于，就返回0。6、最后来设计实现主函数。(1) 定义两个栈：算符栈optr和操作数栈opnd；(2) 初始化操作，主要包括：两个工具栈的初始化；表达式结束符进算符栈；输入表达式；(3) 不断读入字符到字符变量w，并对读入的字符w进行判断，看它是操作数还是算符； 注意：因为程序中的栈类型中存放的数据都是float类型，而输入读取的都是char类型，因此在用in函数判断当前读入的字符w是操作数时，应该让它进操作数栈opnd，但是在进栈之前应该先将当前读入的数字字符w转换为真正的数值（因为字符2与数值2是不同的）。转换的方法也很简单，只需将当前读入的字符w减去0即可，即w=w-0。至于是为什么，请同学们仔细体会。如果是操作数，将其转换为真正对应的数值进opnd栈，然后在继续读入下一个字符；如果是算符，应利用preced函数判断当前字符w与optr栈栈顶算符的优先级，即precede( (char)gettop(optr) , w )。然后再根据返回值(优先级高低)进行不同的操作。因为prcede函数的返回值不外乎是、和e，所以这部分又可以利用switch语句来实现：switch (precede(char)gettop(optr),w) ) case : /此时要进行出栈运算 将optr栈栈顶算符出栈给theta； 将opnd栈栈顶操作数出栈给b； / 出栈右操作数 将opnd栈栈顶操作数再次出栈给a；/ 出栈左操作数 利用operate函数即operate(a,(char)theta,b)计算出结果，将函数返回值进opnd栈； break； case e: 输出错误信息；结束程序。 (4) 最后将表达式的运算结果输出，即将最后的操作数栈opnd栈栈顶元素取出来输出。【实验原理、数据(程序)记录】 略。 请同学们结合上课时所讲算法和以上的实验提示，认真自主的完成实验，不要互相抄袭，自己完成程序的成就感时无可比拟的！【注意事项】1.学生上机时要严格遵守实验规章制度，若实验设备出现故障，应及时向实验指导教师反映，不要私自拆卸实验设备。2.独立完成实验要求的内容，仔细观察和记录实验结果，领会实验目的，并认真完成实验报告。实验三 Huffuma编码的构造【实验时间】 【实验地点】 【实验目的和要求】1理解和掌握树型结构的特点和基本操作；2利用数组存储哈夫曼编码并定义所需的属性结构；3掌握哈夫曼树的结构特点和哈夫曼编码的构造算法及应用。【实验类型】 验证性【实验时数】 4学时【参考资料】 1数据结构题解2C程序设计【实验内容】 理解哈夫曼树的结构特定，利用哈夫曼树的的构造算法进行哈夫曼编码的构造。(1) 定义程序所需各种数据类型； (2) 仔细理解和分析哈夫曼编码构造算法，编写程序；(3) 调试并修改程序，得到正确的实验结果。【实验分析】哈夫曼编码的算法：以文件中每个字符出现的频率作为叶结点的权值来设计哈夫曼树；求每个叶子结点的编码，从叶子到根通过依次找双亲来进行，得到的编码是反序的，进行转换之后方可得到对应编码。1、 假设要进行编码的字符也就是叶子是n个，用一维数组huftree来存储构成的哈夫曼树。哈夫曼树的结点类型定义为： typedef struct char ch; 表示结点的字符值； int weight; 结点的权值 int lchild,rchild,parent; 结点左、右孩子和双亲结点在数组中的下标值HTNODE; HTNODE huftree2n-1； 定义了一维数组huftree，数组长度为2n-1。2、 定义一个数组cd，专门用于存放各个叶子结点代表的字符值和各个叶子结点字符对应的编码。因此，该数组元素应该包含两部分： typedef struct char *code; 用于指向字符对应的编码字符串 char leaf; 叶子结点代表的字符值 CODE;所以，数组定义为：CODE cdn;3、用一个整型数组w来存放按升序排列的叶子的权值。 int wn;4、算法分析：(以a,b,c,d,e权值分别为1，2，3，4，5的字符为例)(1)用一维数组huftree来存储哈夫曼树(0号元素不用)，初始状态为：(2) 选取结点生成内部结点，一共要生成n-1个内点（用k来表示生成内点的个数）。每次都要选取从未用过的当前权值最小的两个结点来生成新的结点，则在数组中就要选取parent为0，权值最小的两个结点生成内点，通过课堂讲解可以知道符合条件的两个结点的下标s1和s2与当前生成的内点个数k之间存在关系：s1=2k-1；s2=s1+1；由它们产生的内点的权值： sum=huftrees1.weight+huftrees2.weight;然后，将生成的新内点按权值升序插入到数组huftree中，可以采取从后往前进行权值比较，直到找到合适的位置(j+1)将其插入，并且将产生的这个新内点与它的左右孩子结点(s1结点和s2结点)的关系进行体现： huftrees1.parent=j+1; huftrees2.parent=j+1; huftreej+1.lchild=s1; huftreej+1.rchild=s2;依次类推，最终的huftee数组为：至此，整棵产生的哈夫曼树已经全部完成，并存储在数组huftree中，产生的哈夫曼树为：由树中叶子结点开始向上回溯，从叶到根。若当前结点是左孩子，则得0，否则得1，得到了反序的编码字符串存入到字符数组temp中，然后根据得到的编码串的实际长度来开辟空间，由数组cd中code指针域指向，再存放各个叶结点代表的字符值，得到相应的编码对照表：【注意事项】1.学生上机时要严格遵守实验规章制度，若实验设备出现故障，应及时向实验指导教师反映，不要私自拆卸实验设备。2.独立完成实验要求的内容，仔细观察和记录实验结果，领会实验目的，并认真完成实验报告。实验四 拓扑排序【实验时间】 【实验地点】 【实验目的和要求】1理解和掌握图的基本概念，掌握图的两种存储结构邻接表和邻接矩阵；2掌握图的相关的定义和在实际应用中的不同特点；3通过构造邻接表，实现拓扑排序，并按邻接表形式输出结果。【实验类型】 验证性【实验时数】 4学时【实验设备】 计算机【参考资料】 1数据结构题解2C程序设计【实验内容】 用邻接表构造并存储图，并利用拓扑排序算法进行图中结点的拓扑排序。(1) 定义所需的各数据类型以实现图或网的构造，并用邻接表存储；(2) 按邻接表形式输出图；(3) 利用拓扑排序算法实现网结点的拓扑序列的输出。【实验分析】在一个有向图中找一个拓扑序列的过程称为拓扑排序。拓扑排序过程如下：（1） 从有向图中选择一个没有驱动（即入度为0）的顶点并且输出它。（2） 从网中删去该顶点，并且删去从该顶点发出的全部有向边。（3） 重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。为了实现拓扑排序算法，将邻接表表头结点增加一个入度如下：typedef struct Vnode 邻接表头结点的类型 ElemType data; 顶点信息int count; 存放顶点入度，专为拓扑排序设置ArcNode *firstarc; 指向第一条边Vnode;在生成图的邻接表时计算每个顶点的入度值。拓扑排序算法TopSort(G,Topsq)，当拓扑排序成功时，该算法返回1，并将排序结果存放到Topsq数组中；否则，该算法返回0。Int TopSort (Agraph *G, int Topsq) 拓扑排序结果存放到Topsq数组中 int I,j,n=0; int StMAXV,top= -1; 栈St的指针为top ArcNode *p; For (I=0;I-1) 栈不为空时循环 I=Sttop; top- -;