《数据结构与算法》实验要求与指导 （一）远程教育辅导教师基本条件(要求) 1. 熟练掌握C语言及其调试开发环境; 2. 具有用C语言编写调试中等规模以上(数百行源码)程序的经验; 3. 掌握《数据结构与算法》课程有关的知识, 具有较好的算法设计和分析的能力; 4. 有一定的教学经验。 （二）算法实验要求综述 根据目前远程教育计算机专业的学生的实际情况和他们的 C语言基础,严格按照本科教学要求进行算法实验上机并完成相应的实验报告, 对多数学生是有一定困难的. 为适应不同基础的学生循序渐进地学习，我们把实验要求分成四个层次, 希望学生不断往更高层次要求自己, 最终能达到本课程的实验基本要求. 这四个层次的要求是： 一. 以熟练使用c语言的开发环境(如TC2.0或VC6.0)为主，进行简单问题的程序设计和调试分析 二. 编写主程序调用调试教材中描述并在课堂中详细讲解过的算法 三. 完成习题中的算法设计题并书写实验报告 四. 独立完成一个小的应用系统并规范书写实验报告，以进一步提高算法描述和算法分析的能力 以上一至三层次作为本课程的基本实验要求，第四层次作为有能力的学生的提高要求。实验辅导教师也可以根据当地学生的具体情况, 本着能提高学生两个能力(C语言的编程和调试能力, 算法设计和分析能力)的目的, 循序渐进地引导学生掌握算法和程序的上机实验, 并参考《题集》的实验报告范例书写实验报告。 按教学计划，本课程实验课时为15学时，安排6-7次实验。由于课时数有限，要求学生在实验前作好充分准备，否则很难在两个学时内完成相关的上机与调试。上机前的准备工作主要有两项：一是仔细阅读理解书中的相关算法，需要写解题算法的还要在纸上写好算法；二是准备好要调试算法的数据，并写好调用算法的主程序。 实验1至实验6都分为A、B两个实验。A实验对应第二层次的能力培养训练，B实验对应第三层次的能力培养训练。 下面就每一层次的要求作如下说明。 一. 以熟练使用c语言的开发环境(如TC2.0或VC6.0)为主，进行一般问题的程序设计和调试分析 该能力实际上是预修课C语言的要求,由于有相当部分学生C语言掌握不是很好, 影响了数据结构算法的描述和理解. 所以开始应该注意弥补C语言的能力. 根据经验, C语言中函数定义与调用（形参和实参的对应等）, 指针, 类型定义与使用、结构的定义和使用、动态内存的申请等难点却是数据结构算法描述的重点, C语言的这些障碍严重影响了学生对数据结构与算法的理解，也影响了学习数据结构的兴趣. 所以实验指导教师在鼓励学生主动补习C语言知识的同时, 有意识安排一些符合学生基础的程序设计练习作为本课程实验的前导补充. 与本课程的相公的算法题目可以推后几周上机. 本实验教学计划的预备实验（即实验0）是为完成该任务而设计的。如果学生的困难比较大，尽量在教学计划时间以外鼓励学生多做上机，打好基础。 二. 编写主程序调用调试教材中描述并在课堂中详细讲解过的算法 　　为加深对课堂讲解的算法的理解，选择部分（尤其是基础部分，如线性表，堆栈与队列等的顺序和链式存储的最常用的基本操作）算法进行上机调试，如第二章的InitList_Sq、ListInsert_Sq和ListDelete_Sq一组算法和第三章的InitStack、GotTop、Push和Pop一组算法等。这些算法是后面章节更复杂算法的基础（如树和图中的算法），算法的积累过程象滚雪球，所以基础必不可少。 　　调试这些算法要注意两点。一是适当修改教材算法中的非C语言的语句和增加部分局部变量的定义。由于算法的描述是类C语言的，所以要改为完整的C语言的函数。不过需要修改（增加）的地方不多。二是书写一个主程序来调用并调试描述算法的函数。主程序的设计要根据算法的功能和调试需要来编写。 本实验教学计划的实验1至实验6的A实验是为完成该任务而设计的。 三. 完成习题中的算法设计题并书写实验报告 　　我们在《题集》的每章的算法设计题中选择少量“小问题”的算法设计练习，以培养和提高学生自己动手写算法的能力。这些算法或者与教材中基本算法类似，或者是延伸，或者是它们的应用。 　　做这些算法设计题时，要注意过程的完整性：题目理解、功能分析、算法思想、描述算法的C函数、调用算法的主程序、运行结果、调试过程的体会等等，都尽可能书写出来。养成书写文档的好习惯。 本实验教学计划的实验1至实验6的B实验是为完成该任务而设计的。 四. 完成一个小的应用系统并规范书写实验报告，以进一步提高算法描述和算法分析的能力 本实验教学计划没有列出相应的实验内容。有余力的学生可以选择一到二个《题集》中的实习题做。 （三）算法实验内容与指导 实验0：C语言中函数定义与调用、 指针和类型的定义与使用、结构的定义、动态内存的申请等预备知识  实验目的：回顾复习C语言的重点与难点，熟悉C程序调试环境，掌握一个完整程序的构成，为以后的实验打下基础。 实验要求：熟练掌握C语言及其上机调试环境(如TC2.0或VC6.0)的操作使用。 实验内容：根据学生基础，选择若干编程题（如C语言中函数定义与调用、 指针和类型的定义与使用、结构的定义、动态内存的申请等），进行编译、连接和运行调试。掌握动态跟踪调试方法。 实验指导：可以选择简单的问题编程，不要求算法的难度，但要能使用相关C语言成分。把注意力集中在编译和连接错误的修改，运行数据的输入输出和结果分析上。 实验1：线性表的顺序表示与链式表示的插入与删除  1. A实验:　算法调试 实验目的：加深理解线性表的顺序表示与链式表示的意义和区别，理解用它们表示时插入与删除操作的算法。 实验要求：理解InitList_Sq、ListInsert_Sq、ListDelete_Sq和InitList_L、ListInsert_L、ListDelete_L等算法。 实验内容：设计一组输入数据并编写主程序分别调用上述算法（顺序表示的算法为InitList_Sq、ListInsert_Sq、ListDelete_Sq等，链式表示的算法为InitList_L、ListInsert_L、ListDelete_L等），调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 实验指导：顺序表示和链式表示可以分成两个程序来调试（见示例程序１和２）。教材中的算法一般要作少许修改才能运行，这些修改包括： 1、算法函数中局部变量的定义，如ListInsert_Sq中的i,newbase,p,q等； 2、可能出现的“类”C语言的语句，必须改为C语言语句，如数据交换语句x(>y; 3、如果采用TC作为C语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如ListInsert_Sq中的参数&L要改为*L。程序中使用L方法的修改见示例程序１。 一个简单程序通常主要由三部分构成： 1、常量定义（#define），类型定义(typedef)及函数原型定义(#include)； 2、算法函数，即InitList_Sq、ListInsert_Sq、ListDelete_Sq等； 3、主函数。 　　　　示例程序１，InitList_Sq、ListInsert_Sq、ListDelete_Sq在TC2.0中的调试： #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 10 #define LISTINCREMENT 4 typedef int Status; typedef int ElemType; typedef struct{ ElemType *elem; int length; int listsize; }SqList; Status InitList_Sq(SqList *L){ L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L->elem) return(OVERFLOW); L->length=0; L->listsize=LIST_INIT_SIZE; return OK; } Status ListInsert_Sq(SqList *L,int i,ElemType e){ ElemType *q,*p,*newbase; if (i<1||i>L->length+1) return ERROR; if (L->length>=L->listsize){ newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) return(OVERFLOW); L->elem=newbase; L->listsize+=LISTINCREMENT; } q=&(L->elem[i-1]); for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L->length; return OK; } Status ListDelete_Sq(SqList *L,int i,ElemType *e){ ElemType *p,*q; if ((i<1)||(i>L->length)) return ERROR; p=&(L->elem[i-1]); *e=*p; q=(L->elem+L->length-1); for (++p;p<=q;++p) *(p-1)=*p; --L->length; return OK; } void main(){ SqList Lst; int i,n=15; ElemType e; if (InitList_Sq(&Lst)==OK){ for(i=1;i<=n;i++) if(ListInsert_Sq(&Lst,i,i)!=OK) break; printf("\n"); for (i=0;i<Lst.length;i++) printf("i,e=%d,%d\n",i,Lst.elem[i]); getch(); if (ListDelete_Sq(&Lst,10,&e)==OK){ printf("delete_elem=%d\n",e); getch(); for (i=0;i<Lst.length;i++) printf("i,e=%d,%d\n",i,Lst.elem[i]); }else printf("delete_elem is failed\n"); } } 　　　　示例程序２，InitList_L、ListInsert_L、ListDelete_L在VC6.0中的调试： #include "math.h" #include "malloc.h" #include "stdio.h" #define ERROR 0 #define TRUE 1 #define FLASE 0 #define OK 1 #define INFEASIBLE -1 #define OVERFLOW -2 typedef struct Lnode{ ElemType data; struct Lnode *next; }Lnode, *LinkList; Status ListInsert_L(LinkList &L, int i, ElemType e) { LinkList s,p; int j; p = L; j = 0; while(p&&j<i-1){p=p->next;++j;} if(!p||j>i-1) return ERROR; s = (Lnode *)malloc(sizeof(Lnode)); if(!s) return OVERFLOW; s->data = e; s->next = p->next; p->next = s; return OK; } Status ListDelete_L(LinkList &L, int i, ElemType &e) { LinkList s,p; int j; p = L; j = 0; while(p->next && j<i-1){p=p->next;++j;} if(!(p->next)||j>i-1) return ERROR; s = p->next; p->next = s->next; e = s->data; free(s); return OK; } Status InitList_L(LinkList &L) { L = (Lnode *)malloc(sizeof(Lnode)); if (L) { L->next = NULL; return OK; } else return ERROR; } int cmp(Event a, Event b); Status OrderInsert_L(LinkList &L, ElemType e, int (*cmp)(Event a, Event b)) { Lnode *p,*q; p=(Lnode *)malloc(sizeof(Lnode)); if(!p)return(OVERFLOW); p->data = e; q=L; while(q->next && cmp(e,q->next->data)>0) q=q->next; p->next = q->next; q->next = p; return OK; } int EmptyList(LinkList L) { if(!L->next) return 1; return 0; } LinkList GetHead(LinkList L) { if(!L->next) return NULL; return L->next; } Status DelFirst(LinkList L, LinkList &p) { p = L->next; if(!p) return ERROR; L->next = p->next; return OK; } void main(){ // 主程序略 } ２. B实验: 练习2.11 实验目的：加深理解线性表的顺序表示的插入操作的算法，学会使用现有算法来解决其他问题。 实验要求：进一步理解InitList_Sq、ListInsert_Sq算法并在其他问题中的使用。 实验内容：设计一组输入数据并编写主程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。 实验指导：第一步，编写主程序，首先读入数据并保存在顺序表中（可以用ListInsert_Sq进行逐个插入，也可以用循环语句直接读入数组中），然后读入一个待插入的数x；再寻找x应该插入的顺序表中的位置i，然后调用ListInsert_Sq插入第i个元素即可。 第二步，设计调试数据，例如一组递增有序输入数据（１，３，５，６，７，９，１２）以及一个待插入的数x=8。调试程序。能够正确插入后再考验算法的“健壮性”。 第三步，再取x=0或x=15或x=6进行调试，以考验算法在“边界情况”下的正确性。即插入在表头，表尾以及有重复情况的插入是否正确。还可以再考虑一组递增有序输入数据为空表时插入元素的正确性。 实验2：顺序栈的实现与插入删除操作   1. A实验:　基本算法调试及数制的转换算法 （１）实验目的：加深理解顺序栈的意义，理解用它的插入与删除操作的算法。 （２）实验要求：理解InitStack、StackEmpty、Push、Pop和conversion等算法。 （３）实验内容：用数制的转换算法调试顺序栈的基本操作算法。编写主程序调用数制的转换conversion算法，再由conversion调用InitStack、StackEmpty、Push、Pop算法。用不同的数转换成不同的进制调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对Push和Pop算法的理解。 （４）实验指导：建立程序的三部分构架： 1、常量定义（#define），类型定义(typedef)及函数原型定义(#include)； 2、算法函数，即InitStack、StackEmpty、Push和Pop、conversion等； 3、主函数。 　　　示例程序１，InitStack、StackEmpty、Push和Pop、conversion等在VC6.0中的调试： typedef int SElemType; typedef struct{ SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL*/ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -1 #define ERROR 0 typedef int Status; #include <malloc.h> #include <stdio.h> Status InitStack(SqStack &s) { s.base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType)); if(!s.base) return(OVERFLOW); s.top = s.base; s.stacksize = STACK_INIT_SIZE; return OK; } /* InitStack */ Status Push(SqStack &s, SElemType e) {SElemType *l_temp; if (s.top - s.base >= s.stacksize) /* 栈满，追加存储空间 */ { l_temp=(SElemType*)realloc (s.base,(s.stacksize+STACKINCREMENT) *sizeof(SElemType)); if (!l_temp) return(OVERFLOW); s.base = l_temp; s.top = s.base + s.stacksize; s.stacksize += STACKINCREMENT; } *(s.top++) = e; return OK; } /* Push */ Status Pop(SqStack &s, SElemType &e) { if (s.top == s.base)return ERROR; e = *(--s.top); return OK; } /* Pop */ int StackEmpty(SqStack s) { if(s.base == s.top) return 1; else return 0; } void conversion() { SqStack s; int N,b; SElemType e; InitStack(s); scanf("%d %d",&N,&b); while(b>=2 && N){ Push(s, N%b); N = N/b; } while(!StackEmpty(s)){ Pop(s, e); printf("%d",e); } } /* conversion */ void main(void) { conversion(); } ２. B实验: 练习3.15 (1) 实验目的：加深对堆栈理解，学会灵活运用已有知识，拓广思路。 (2) 实验要求：按照对InitStack、StackEmpty、Push、Pop等算法理解，理解双向栈的含义与意义，建立与调试对双向栈的基本操作算法。 (3) 实验内容：设计一组对双向栈的操作算法InitStackTws、StackTwsEmpty、PushTws、PopTws并编写一个主程序调试它们。设计一组输入数据并对相应的输出作出分析；着重调试空栈、满栈时的情况。 (4) 实验指导：第一步，理解双向栈的意义是为了节省空间，减少栈溢出（满栈）机会。第二步，写出双向栈的操作算法InitStackTws、StackTwsEmpty、PushTws、PopTws。第三步，编写主程序。第四步，设计若干组数据调试来算法。 实验3 ：链式队列与循环队列的实现与插入删除操作  A实验: 循环队列的实现算法 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： B实验：练习3.28 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 实验4 ：稀疏矩阵的三元组表示与矩阵加法运算  A实验: 算法5.1,5.2的实现与调试 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： ２. B实验: 练习5.21 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 实验5：二叉树的二叉链表示与三种递归遍历  A实验: 算法6.1,6.4的实现与调试 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： ２. B实验: 算法6.2 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 实验6：图的邻接矩阵表示及其深度（广度）优先搜索  A实验: 算法7.1,7.2,7.4,7.5的调试 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： ２. B实验: 算法7.6与习题7.5 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导：