《数据结构与算法》实验要求与指导

1、数据结构与算法实验要求与指导（二）算法实验要求综述我们把实验要求分成四个层次 , 希望学生不断往更高层次要求自己 , 最终能达到本课程 的实验基本要求 .这四个层次的要求是：一. 以熟练使用 c 语言的开发环境 （如 TC2.0 或 VC6.0） 为主，进行简单问题的程序设计 和调试分析二 . 编写主程序调用调试教材中描述并在课堂中详细讲解过的算法三 . 完成习题中的算法设计题并书写实验报告四. 独立完成一个小的应用系统并规范书写实验报告， 以进一步提高算法描述和算法分 析的能力以上一至三层次作为本课程的基本实验要求，第四层次作为有能力的学生的提高要求。 实验辅导教师也可以根据当地学生的具体情

2、况 , 本着能提高学生两个能力 （C 语言的编程和 调试能力 , 算法设计和分析能力 ）的目的 , 循序渐进地引导学生掌握算法和程序的上机实验 , 并参考题集的实验报告范例书写实验报告。按教学计划， 本课程实验课时为 15学时，安排 6-7 次实验。由于课时数有限， 要求学生 在实验前作好充分准备，否则很难在两个学时内完成相关的上机与调试。上机前的准备工作 主要有两项：一是仔细阅读理解书中的相关算法，需要写解题算法的还要在纸上写好算法； 二是准备好要调试算法的数据，并写好调用算法的主程序。实验1至实验6都分为A、B两个实验。A实验对应第二层次的能力培养训练，B实验对应第三层次的能力培养训练。下

3、面就每一层次的要求作如下说明。一. 以熟练使用c语言的开发环境（如TC2.0或VC6.0）为主，进行一般问题的程序设计 和调试分析该能力实际上是预修课 C语言的要求，由于有相当部分学生C语言掌握不是很好，影响了 数据结构算法的描述和理解所以开始应该注意弥补C语言的能力根据经验，C语言中函数定义与调用（形参和实参的对应等） ， 指针， 类型定义与使用、结构的定义和使用、动态 内存的申请等难点却是数据结构算法描述的重点 ， C 语言的这些障碍严重影响了学生对数据 结构与算法的理解，也影响了学习数据结构的兴趣. 所以实验指导教师在鼓励学生主动补习C 语言知识的同时 ， 有意识安排一些符合学生基础的程

4、序设计练习作为本课程实验的前导补 充. 与本课程的相公的算法题目可以推后几周上机.本实验教学计划的预备实验（即实验0）是为完成该任务而设计的。如果学生的困难比较大，尽量在教学计划时间以外鼓励学生多做上机，打好基础。二. 编写主程序调用调试教材中描述并在课堂中详细讲解过的算法 为加深对课堂讲解的算法的理解，选择部分（尤其是基础部分，如线性表，堆栈与队列等的顺序和链式存储的最常用的基本操作）算法进行上机调试，如第二章的InitList_Sq 、Listlnsert_Sq 和 ListDelete_Sq 组算法和第三章的 InitStack 、GotTop、Push 和 Pop 组算法等。 这些算法

5、是后面章节更复杂算法的基础 （如树和图中的算法） ，算法的积累过程象 滚雪球，所以基础必不可少。调试这些算法要注意两点。一是适当修改教材算法中的非C语言的语句和增加部分局部变量的定义。由于算法的描述是类C语言的，所以要改为完整的 C语言的函数。不过需要修改（增加）的地方不多。二是书写一个主程序来调用并调试描述算法的函数。主程序的设计 要根据算法的功能和调试需要来编写。本实验教学计划的实验 1至实验6的A实验是为完成该任务而设计的。三. 完成习题中的算法设计题并书写实验报告我们在题集的每章的算法设计题中选择少量“小问题”的算法设计练习，以培养和 提高学生自己动手写算法的能力。这些算法或者与教材中

6、基本算法类似，或者是延伸，或者 是它们的应用。做这些算法设计题时，要注意过程的完整性：题目理解、功能分析、算法思想、描述算 法的C函数、调用算法的主程序、运行结果、调试过程的体会等等，都尽可能书写出来。养 成书写文档的好习惯。本实验教学计划的实验 1至实验6的B实验是为完成该任务而设计的。四完成一个小的应用系统并规范书写实验报告，以进一步提高算法描述和算法分析的能力本实验教学计划没有列出相应的实验内容。有余力的学生可以选择一到二个题集中 的实习题做。（三）算法实验内容与指导实验0: C语言中函数定义与调用、指针和类型的定义与使用、结构的定义、动态内存的申请等预备知识（1）实验目的：回顾复习C语

7、言的重点与难点，熟悉C程序调试环境，掌握一个完整程序的构成，为以后的实验打下基础。（2）实验要求：熟练掌握C语言及其上机调试环境（如TC2.0或VC6.0）的操作使用。（3）实验内容：根据学生基础，选择若干编程题（如 C语言中函数定义与调用、指针和类型的定义与使用、 结构的定义、动态内存的申请等），进行编译、连接和运行调 试。掌握动态跟踪调试方法。（4）实验指导：可以选择简单的问题编程，不要求算法的难度，但要能使用相关C语言成分。把注意力集中在编译和连接错误的修改，运行数据的输入输出和结果分析上。实验1 :线性表的顺序表示与链式表示的插入与删除1. A实验：算法调试（1）实验目的：加深理解线性

8、表的顺序表示与链式表示的意义和区别，理解用它们表 示时插入与删除操作的算法。（2）实验要求：理解 InitList_Sq、Listlnsert_Sq、ListDelete_Sq 和 InitList_L、Listlnsert_L 、ListDelete_L等算法。（3）实验内容：设计一组输入数据并编写主程序分别调用上述算法（顺序表示的算法为 In itList_Sq 、ListI nsert_Sq、ListDelete_Sq 等，链式表示的 算法为InitList_L、ListInsert_L 、ListDelete_L 等），调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的

9、结果，加深对有关算法的理解。(4) 实验指导：顺序表示和链式表示可以分成两个程序来调试(见示例程序1和2)教材中的算法一般要作少许修改才能运行，这些修改包括：1、算法函数中局部变量的定义，如ListInsert_Sq 中的 i,newbase,p,q 等；2、 可能出现的“类” C语言的语句，必须改为C语言语句，如数据交换语句x y;3、 如果采用TC作为C语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如List In sert_Sq 中的参数&L要改为*L。程序中使用L方法的修改见示例程序1。一个简单程序通常主要由三部分构成：1、常量定义( #define

10、 )，类型定义 (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 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define

11、LIST_INIT_SIZE 10#define LISTINCREMENT 4typedef int Status;typedef int ElemType;typedef structElemType *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

12、 OK;Status ListInsert_Sq(SqList *L,int i,ElemType e)ElemType *q,*p,*newbase;if (iL-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-elemi-1);for

13、(p=&(L-elemL-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 (iL-length) return ERROR; p=&(L-elemi-1);*e=*p; q=(L-elem+L-length-1);for (+p;plength;return OK;void main()SqList Lst;int i,n=15;ElemType e;if (InitList_Sq(&Lst)=OK)

14、 for(i=1;i=n;i+)if(ListInsert_Sq(&Lst,i,i)!=OK) break; printf(n);for (i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi); getch();if (ListDelete_Sq(&Lst,10,&e)=OK) printf(delete_elem=%dn,e); getch();for (i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi);else printf(delete_elem is failedn);在 VC6.0 中

15、的调试：示例程序2,InitList_L、Listlnsert_L 、ListDelete_L#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 -2typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;Status ListInsert_L(LinkList &L, int i

16、, ElemType e) LinkList s,p;int j; p = L; j = 0;while(p&jnext;+j; if(!p|ji-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

17、next;+j; if(!(p-next)|ji-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;elsereturn ERROR;int cmp(Event a, Event b);Status OrderInsert_L(LinkList &L, ElemType e, int (*cmp)(Even

18、t 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;St

19、atus DelFirst(LinkList L, LinkList &p)p = L-next;if(!p) return ERROR;L-next = p-next;return OK;void mai n()/主程序略2 . B实验：练习2.11(1) 实验目的：加深理解线性表的顺序表示的插入操作的算法，学会使用现有算法来解 决其他问题。(2) 实验要求：进一步理解Ini tList_Sq 、List In sert_Sq算法并在其他问题中的使用。(3) 实验内容：设计一组输入数据并编写主程序。调试程序并对相应的输出作出分析； 修改输入数据，预期输出并验证输出的结果。(4) 实验指导：第

20、一步，编写主程序，首先读入数据并保存在顺序表中(可以用ListI nsert_Sq进行逐个插入，也可以用循环语句直接读入数组中)，然后读入一个待插入的数x;再寻找x应该插入的顺序表中的位置i，然后调用List In sert_Sq插入第i个元素即可。第二步，设计调试数据，例如一组递增有序输入数据(1,3,5,6,7,9,12)以及一个待插入的数x=8。调试程序。能够正确插入后再考验算法的“健壮性”。第三步，再取x=0或x=15或x=6进行调试，以考验算法在“边界情况”下的正确性。即插入在表头，表尾以及有重复情况的插入是否正确。还可以再考虑一组递增有序输入 数据为空表时插入元素的正确性。实验2

21、:顺序栈的实现与插入删除操作1. A实验：基本算法调试及数制的转换算法(1) 实验目的：加深理解顺序栈的意义，理解用它的插入与删除操作的算法。(2) 实验要求：理解 In itStack 、StackEmpty、Push、Pop 和 con version 等算法。(3) 实验内容：用数制的转换算法调试顺序栈的基本操作算法。编写主程序调用数制的转换 con version 算法，再由 con version 调用 In itStack 、StackEmpty、Push、Pop 算法。用不同的数转换成不同的进制调试程序并对相应的输出作出分析；修改输入数据, 预期输出并验证输出的结果，加深对Pus

22、h和Pop算法的理解。(4) 实验指导： 建立程序的三部分构架:1、常量定义(#define ),类型定义(typedef)及函数原型定义(#include);2、算法函数，即 Ini tStack 、StackEmpty、Push 和 Pop con version 等；3、主函数。示例程序1,In itStack、StackEmpty、Push 和 Pop、con version 等在 VC6.0 中的调试:typedef int SElemType;typedef struct在栈构造之前和销毁之后,base 的值为 NULL*/SElemType *base; /*SElemType

23、*top; /*栈顶指针 */int stacksize; /*当前已分配的存储空间，以元素为单位*/SqStack;#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#define OK 1#define OVERFLOW -1#define ERROR 0typedef int Status;#include #include Status InitStack(SqStack &s) s.base=( SElemType *)malloc (STACK_INIT_SIZE * sizeof(SElemType); if(!s.bas

24、e) 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(OV

25、ERFLOW); 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;SEIemType e;In itStack(s);sca nf(%d %d,&N,&b);while(b=2 & N)Push(s, N%b);N = N/b;while(!StackEmpty(s)Pop(s, e);prin tf(%d,e); /* con vers ion */void main (void)con versi on();2 . B实验：练习3.15(1)