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

《数据结构与算法》实验要求与指导 (一)远程教育辅导教师基本条件(要求) 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 (iL->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 ((iL->length)) return ERROR p=&(L->elem[i-1) q=(L->elem+L->length-1) for(++p;plength: 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 (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->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 ((iL->length)) return ERROR; p=&(L->elem[i-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){ 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 inext: ++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;inext;++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;

while(p->next & jnext: ++j: F if(!(p->next)Lj>i-1)return ERROR p->next=s->next turn o Status InitList L(LinkList &L) L =(Lnode *)malloc(sizeof (Lnode)) if (L)I L->next= NULL return OK int cmp(Event a, Event b) Status Order Insert_L(LinkList &L, ElemType e, int (*cmp)(Event a, Event b)) Lnode *p, *q (Lnode *)malloc(sizeof(Lnode)) if(! p)return(OVERFLOW) while(g->next & cmp(e, g->next->data)>0) q=q->next int EmptyList(LinkList L) t)return 1 return o LinkList Get Head (LinkList L)

p = L; j = 0; while(p->next && jnext;++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->nex return OK void maino( //主程序略 2.B实验:练习2.11 (1)实验目的:加深理解线性表的顺序表示的插入操作的算法,学会使用现有算法来解 决其他问题。 (2)实验要求:进一步理解 Initlist Sq、 ListInsert sq算法并在其他问题中的使用。 (3)实验内容:设计一组输入数据并编写主程序。调试程序并对相应的输出作出分析 修改输入数据,预期输出并验证输出的结果 (4)实验指导:第一步,编写主程序,首先读入数据并保存在顺序表中(可以用 ListInsert_Sq进行逐个插入,也可以用循环语句直接读入数组中),然后读入一个 待插入的数x;再寻找x应该插入的顺序表中的位置i,然后调用 ListInsert Sq插 入第i个元素即可。 第二步,设计调试数据,例如一组递增有序输入数据(1,3,5,6,7,9 12)以及一个待插入的数ⅹ=8。调试程序。能够正确插入后再考验算法的“健壮性 第三步,再取x=0或x=15或κ=6进行调试,以考验算法在“边界情况”下的正确性 即插入在表头,表尾以及有重复情况的插入是否正确。还可以再考虑一组递增有序输入 数据为空表时插入元素的正确性。 实验2:顺序栈的实现与插入删除操作 1.A实验:基本算法调试及数制的转换算法 1)实验目的:加深理解顺序栈的意义,理解用它的插入与删除操作的算法 (2)实验要求:理解 InitStack、 StackEmpty、Push、Pop和 conversion等算法 〔3)实验内容:用数制的转换算法调试顺序栈的基本操作算法。编写主程序调用数制 的转换 conversion算法,再由 conversion调用 Initstack、 StackEmpty、Push、Pop算 法。用不同的数转换成不同的进制调试程序并对相应的输出作出分析:修改输入数据, 预期输出并验证输出的结果,加深对Push和Pop算法的理解, (4)实验指导:建立程序的三部分构架:

{ 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 (1) 实验目的：加深理解线性表的顺序表示的插入操作的算法，学会使用现有算法来解 决其他问题。 (2) 实验要求：进一步理解 InitList_Sq、ListInsert_Sq 算法并在其他问题中的使用。 (3) 实验内容：设计一组输入数据并编写主程序。调试程序并对相应的输出作出分析； 修改输入数据，预期输出并验证输出的结果。 (4) 实验指导：第一步，编写主程序，首先读入数据并保存在顺序表中（可以用 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等 主函数。 示例程序1, InitStack、 Stack Empty、Push和Pp、 conversion等在C60中的调试: typedef int SElemType typedef struct i SElemType*base;/*在栈构造之前和销毀之后,base的值为NUL*/ SElemType /*栈顶指针*/ int stacksize;/*当前已分配的存储空间,以元素为单位*/ I SqStack #define stacK INIt size 100 #define StacKincrement 10 #define oK 1 #define overflow-1 #define error o typedef int Status #include #include Status InitStack(SqStack &s) (STACK INIT SIZE sizeof(SElem Type)) if(!s base) return(OVERFLOW) s. stacksize= STACK INIT Size 1/* InitStack * Status PushSqStack &s, SElemType e) ISElemT if (s top -s base /*栈满,追加存储空间*/ (s base, (s stacksize+STACKINCREMENT) *sizeof (SElem Type)) f(!l temp) return(OVERFLOW) s top s base+s. stacksize s. stacksize + STACKIncrement *(s top++)=e: return OK

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 #include 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)

I if (s top = s base)return ERROR return OK int StackEmpty(SaStack s top) return 1 else return o void conversion o f("%d%d",&N,&b) while(b>=2&& N)I Push(s, N%b) printf( %d e) 1/* conversion */ void main (void) conversion 2.B实验:练习3.15 (1)实验目的:加深对堆栈理解,学会灵活运用已有知识,拓广思路。 (2)实验要求:按照对 Initstack、 StackEmpty、Push、Pop等算法理解,理解双向栈的 含义与意义,建立与调试对双向栈的基本操作算法 3)实验内容:设计一组对双向栈的操作算法 InitstackTws、 StackTwsEmpty、 Pushtws、 PopTws并编写一个主程序调试它们。设计一组输入数据并对相应的输出作出分析:着重 调试空栈、满栈时的情况。 4)实验指导:第一步,理解双向栈的意义是为了节省空间,减少栈溢出(满栈)机会。 第二步,写出双向栈的操作算法 InitstackTws、 StackTwsEmpty、 Pushtws、 PopTws。第 三步,编写主程序。第四步,设计若干组数据调试来算法

{ 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:链式队列与循环队列的实现与插入删除操作 1.A实验:循环队列的实现算法 (1)实验目的 (2)实验要求: (3)实验内容 (4)实验指导: 2.B实验:练习3.28 (1)实验目的: (2)实验要求: (3)实验内容: (4)实验指导: 实验4:稀疏矩阵的三元组表示与矩阵加法运算 1.A实验:算法5.1,5.2的实现与调试 (1)实验目的: (2)实验要求 (3)实验内容 (4)实验指导 2.B实验:练习5.21 (1)实验目的: (2)实验要求 (3)实验内容 (4)实验指导: 实验5:二叉树的二叉链表示与三种递归遍历 1.A实验:算法6.1,6.4的实现与调试 (1)实验目的 (2)实验要求 (3)实验内容 (4)实验指导: 2.B实验:算法6.2 (1)实验目的 (2)实验要求 (3)实验内容: (4)实验指导: 实验6:图的邻接矩阵表示及其深度(广度)优先搜索

实验 3 ：链式队列与循环队列的实现与插入删除操作 1. A 实验: 循环队列的实现算法 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 2. B 实验：练习 3.28 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 实验 4 ：稀疏矩阵的三元组表示与矩阵加法运算 1. A 实验: 算法 5.1,5.2 的实现与调试 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： ２. B 实验: 练习 5.21 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 实验 5：二叉树的二叉链表示与三种递归遍历 1. A 实验: 算法 6.1,6.4 的实现与调试 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： ２. B 实验: 算法 6.2 (1) 实验目的： (2) 实验要求： (3) 实验内容： (4) 实验指导： 实验 6：图的邻接矩阵表示及其深度（广度）优先搜索