浙江大学：《数据结构与算法》实验要求与指导

《数据结构与算法》实验要求与指导 (一)远程教育辅导教师基本条件(要求) 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语言的这些障碍严重影响了学生对数据 结构与算法的理解,也影响了学习数据结构的兴趣.所以实验指导教师在鼓励学生主动补习

《数据结构与算法》实验要求与指导 （一）远程教育辅导教师基本条件(要求) 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、 GotTo、Push和Pop 组算法等。这些算法是后面章节更复杂算法的基础(如树和图中的算法),算法的积累过程象 滚雪球,所以基础必不可少 调试这些算法要注意两点。一是适当修改教材算法中的非C语言的语句和增加部分局部 变量的定义。由于算法的描述是类C语言的,所以要改为完整的C语言的函数。不过需要修 改(增加)的地方不多。二是书写一个主程序来调用并调试描述算法的函数。主程序的设计 要根据算法的功能和调试需要来编写。 本实验教学计划的实验1至实验6的A实验是为完成该任务而设计的 三.完成习题中的算法设计题并书写实验报告 我们在《题集》的每章的算法设计题中选择少量“小问题”的算法设计练习,以培养和 提高学生自己动手写算法的能力。这些算法或者与教材中基本算法类似,或者是延伸,或者 是它们的应用 做这些算法设计题时,要注意过程的完整性:题目理解、功能分析、算法思想、描述算 法的C函数、调用算法的主程序、运行结果、调试过程的体会等等,都尽可能书写出来。养 成书写文档的好习惯。 本实验教学计划的实验1至实验6的B实验是为完成该任务而设计的 四.完成一个小的应用系统并规范书写实验报告,以进一步提高算法描述和算法分析的 能力 本实验教学计划没有列出相应的实验内容。有余力的学生可以选择一到二个《题集》中 的实习题做。 三)算法实验内容与指导 实验0:C语言中函数定义与调用、指针和类型的定义 与使用、结构的定义、动态内存的申请等预备知识 (1)实验目的:回顾复习C语言的重点与难点,熟悉C程序调试环境,掌握一个完整程 序的构成,为以后的实验打下基础。 (2)实验要求:熟练掌握C语言及其上机调试环境(如TC2.0或VC6.0)的操作使用。 (3)实验内容:根据学生基础,选择若干编程题(如C语言中函数定义与调用、指针 和类型的定义与使用、结构的定义、动态内存的申请等),进行编译、连接和运行调 试。掌握动态跟踪调试方法 (4)实验指导:可以选择简单的问题编程,不要求算法的难度,但要能使用相关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 语言中函数定义与调用、 指针和类型的定义 与使用、结构的定义、动态内存的申请等预备知识 (1) 实验目的：回顾复习 C 语言的重点与难点，熟悉 C 程序调试环境，掌握一个完整程 序的构成，为以后的实验打下基础。 (2) 实验要求：熟练掌握 C 语言及其上机调试环境(如 TC2.0 或 VC6.0)的操作使用。 (3) 实验内容：根据学生基础，选择若干编程题（如 C 语言中函数定义与调用、 指针 和类型的定义与使用、结构的定义、动态内存的申请等），进行编译、连接和运行调 试。掌握动态跟踪调试方法。 (4) 实验指导：可以选择简单的问题编程，不要求算法的难度，但要能使用相关 C 语言 成分。把注意力集中在编译和连接错误的修改，运行数据的输入输出和结果分析上

实验1:线性表的顺序表示与链式表示的插入与删除 1.A实验:算法调试 (1)实验目的:加深理解线性表的顺序表示与链式表示的意义和区别,理解用它们表 示时插入与删除操作的算法 (2)实验要求:理解 Initlist sq、 ListInsert Sq、 ListDelete Sq和 Initlist l、 ListInsert l、 ListDelete l等算法。 (3)实验内容:设计一组输入数据并编写主程序分别调用上述算法(顺序表示的算法 为 Initlist Sq、 ListInsert Sq、 ListDelete Sq等,链式表示的算法为 Initlist l、 ListInsert l、 ListDelete l等),调试程序并对相应的输出作出 分析:修改输入数据,预期输出并验证输出的结果,加深对有关算法的理解 (4)实验指导:顺序表示和链式表示可以分成两个程序来调试(见示例程序1和2) 教材中的算法一般要作少许修改才能运行,这些修改包括 1、算法函数中局部变量的定义,如 ListInsert sq中的i, newbase,p,q等; 2、可能出现的“类”C语言的语句,必须改为C语言语句,如数据交换语句x←>y 3、如果采用TC作为C语言调试环境,算法函数的“引用”类型参数要改为指 针类型参数并修改程序中的使用方法,如 ListInsert sq中的参数&要改为 L。程序中使用L方法的修改见示例程序1。 个简单程序通常主要由三部分构成 1、常量定义(# define),类型定义( typedef)及函数原型定义(# include) 2、算法函数,即 InitList Sq、 ListInsert Sq、 ListDelete Sq等 3、主函数 示例程序1, InitList Sq、 ListInsert Sq、 ListDelete Sq在TC2.0中的调试: #include stdio. h #include malloc. h #define true 1 #define false o #define ok #define error o #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 Status InitList Sq (sqList *L) L->elem=(Elem Type *)malloc(LIST_ INIT_ SIZE*s izeof(El em T ype))

实验 1：线性表的顺序表示与链式表示的插入与删除 1. A 实验: 算法调试 （1） 实验目的：加深理解线性表的顺序表示与链式表示的意义和区别，理解用它们表 示时插入与删除操作的算法。 （2） 实验要求：理解 InitList_Sq、ListInsert_Sq、ListDelete_Sq 和 InitList_L、 ListInsert_L、ListDelete_L 等算法。 （3） 实验内容：设计一组输入数据并编写主程序分别调用上述算法（顺序表示的算法 为 InitList_Sq、ListInsert_Sq、ListDelete_Sq 等，链式表 示的算法为 InitList_L、ListInsert_L、ListDelete_L 等），调试程序并对相应的输出作出 分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 （4） 实验指导：顺序表示和链式表示可以分成两个程序来调试（见示例程序１和２）。 教材中的算法一般要作少许修改才能运行，这些修改包括： 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=o L->listsize=LIST INIT SIZE return Status ListInsert_ Sq (SqList *L, int i, ElemType e)t ElemType **q, *p, *newbase if (i<ll l i>L->length+1)return ERROR if (L->length>=L->listsize)( newbase=(Elem Type*realloc(L-elem,(L->listsize+LISTINCREMENT)*sizeof (ElemType)) if (I newbase) return(OVERFLOW) L->elem=newbase: L->listsize+=LISTINcremeNt g=&(L->elem[i-lD) for(p=& (L->elem[L->length-1): p>=g: -p)*(p+1)=*p ++L->length; return OK Status ListDelete Sq(sqlist L, int i, ElemType *e)i ElemType *p,* if ((i<1)ll(i>L->length)) return ERROR p=&(L->elem[i-1) q=(L->elem+L->length-1) for(++p;p<=q;+p)*(p-1)=*p L->length: return OK: id ma i Sqlist lst int i, n=15 ElemType e if (InitList Sq(&Lst)=0K)( for(i=l: i<=n: i++) if (ListInsert Sq(&Lst, i, i)!=0K) break printf("\n") for (i=0;i<Lst. length i++)

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]) tcho if (ListDelete Sq(&Lst, 10, &e)==OK)( em=%d\n”,e) for (i=0 i<Lst.le printf("i, e=%d, %d\n", i, Lst elem[i]) Felse intf( delete el failed\n") 示例程序2, Initlist l、 ListInsert l、 ListDelete l在VC6.0中的调试: #include malloc. h #define error o #define true 1 #define flase o #define oK 1 #define infeasible -l #define overflow -2 typedef struct Lnode Nod Status ListInsert_L (LinkList &L, int i, Elem Type e) int J L; hile(p&&j<i-1)p=p->next: ++j:I if( lj>i-1)return ERROR s=(Lnode *)malloc(sizeof (Lnode)) if(!s) return OVERFLOW: s->next= p->next: p->next=s return Status List Delete L(LinkList &L, int i, Elem Type &e) t LinkList s, p

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;