《数据结构与算法》实验大纲

数据结构与算法》实验大纲一、实验目的通过该课程的实验练习，使学生能够进一步掌握各种数据结构以及建立在此基础上的算法的基本知识；进一步理解各种基本数据结构的特点；进一步掌握数据结构与算法的关系；培养学生设计有效的算法及设计数据结构的能力。解决或者答疑同学们在理论课程学习过程中所遇到的问题。二、实验内容实验O：C语言中函数定义与调用、指针和类型的定义与使用、结构的定义、动态内存的申请等预备知识（1） 实验目的：回顾复习C语言的重点与难点，熟悉C程序调试环境，掌握一个完整程序的构成，为以后的实验打下基础。（2） 实验要求：熟练掌握C语言及其上机调试环境（如TC2.0或VC6.0）的操作使用。（3） 实验内容：根据学生基础，选择若干编程题（如C语言中函数定义与调用、指针和类型的定义与使用、结构的定义、动态内存的申请等），进行编译、连接和运行调试。掌握动态跟踪调试方法。（4） 实验指导：可以选择简单的问题编程，不要求算法的难度，但要能使用相关C语言成分。把注意力集中在编译和连接错误的修改，运行数据的输入输出和结果分析上。实验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语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如Listlnsert_Sq中的参数&L要改为*L。程序中使用L方法的修改见示例程序1。一个简单程序通常主要由三部分构成：1、 常量定义(#define),类型定义(typedef)及函数原型定义(#include)；2、 算法函数，即InitList_Sq、ListInsert_Sq、ListDelete_Sq等；3、 主函数。示例程序1,InitList_Sq、Listlnsert_Sq、ListDelete_Sq在VC6.0中的调试:#include"stdio.h"#include"malloc.h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_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;returnOK;}StatusListInsert_Sq(SqList*L,inti,ElemTypee){ElemType*q,*p,*newbase;if(i<1||i>L->length+1)returnERROR;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;returnOK;}StatusListDelete_Sq(SqList*L,inti,ElemType*e){ElemType*p,*q;if((i<1)||(i>L->length))returnERROR;p=&(L->elem[i-1]);*e=*p;q=(L->elem+L->length-1);for(++p;p<=q;++p)*(p-1)=*p;--L->length;returnOK;}voidmain(){SqListLst;inti,n=15;ElemTypee;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]);}elseprintf("delete_elemisfailed\n");}}示例程序2,InitList_L、Listlnsert_L、ListDelete_L在VC6.0中的调试:#include"math.h"#include"malloc.h"#include"stdio.h"#defineERROR0#defineTRUE1#defineFLASE0#defineOK1#defineINFEASIBLE-1#defineOVERFLOW-2typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;StatusListInsert_L(LinkList&L,inti,ElemTypee){LinkLists,p;intj;p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(Lnode*)malloc(sizeof(Lnode));if(!s)returnOVERFLOW;s->data=e;s->next=p->next;p->next=s;returnOK;}StatusListDelete_L(LinkList&L,inti,ElemType&e){LinkLists,p;intj;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;s=p->next;p->next=s->next;e=s->data;free(s);returnOK;}StatusInitList_L(LinkList&L){L=(Lnode*)malloc(sizeof(Lnode));if(L){L->next=NULL;returnOK;}elsereturnERROR;intcmp(Eventa,Eventb);StatusOrderInsert_L(LinkList&L,ElemTypee,int(*cmp)(Eventa,Eventb)){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;returnOK;}intEmptyList(LinkListL){if(!L->next)return1;return0;}LinkListGetHead(LinkListL){if(!L->next)returnNULL;returnL->next;}StatusDelFirst(LinkListL,LinkList&p){p=L->next;if(!p)returnERROR;L->next=p->next;returnOK;}voidmain(){//主程序略}B实验：练习2.11设数据表va中的数据元素递增有序，试写一个程序，将x插入到顺序表的适当位置，以保持该表的有序性。实验目的：加深理解线性表的顺序表示的插入操作的算法，学会使用现有算法来解决其他问题。实验要求：进一步理解InitList_Sq、ListInsert_Sq算法并在其他问题中的使用。实验内容：设计一组输入数据并编写主程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。实验指导：第一步，编写主程序，首先读入数据并保存在顺序表中(可以用ListInsert_Sq进行逐个插入，也可以用循环语句直接读入数组中)，然后读入一个待插入的数X；再寻找x应该插入的顺序表中的位置i,然后调用Listlnsert_Sq插入第i个元素即可。第二步，设计调试数据，例如一组递增有序输入数据(1,3,5,6,7,9,12)以及一个待插入的数x=8。调试程序。能够正确插入后再考验算法的“健壮性”第三步，再取x=0或x=15或x=6进行调试，以考验算法在“边界情况”下的正确性。即插入在表头,表尾以及有重复情况的插入是否正确。还可以再考虑一组递增有序输入数据为空表时插入元素的正确性。程序示例：#include"stdio.h"#include"malloc.h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_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;returnOK;}StatusListInsert_Sq(SqList*L,inti,ElemTypee){ElemType*q,*p,*newbase;if(i<1||i>L->length+1)returnERROR;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;returnOK;}StatusListDelete_Sq(SqList*L,inti,ElemType*e){ElemType*p,*q;if((i<1)||(i>L->length))returnERROR;p=&(L->elem[i-1]);*e=*p;q=(L->elem+L->length-1);for(++p;p<=q;++p)*(p-1)=*p;--L->length;returnOK;}intFindPos_Sq(SqListLst,ElemTypee)){//确定e在有序表中的位置(第i个元素之前)inti;for(i=Lst.langth-1;i>=0;i--)if(Lst.elem[i]<=e)returni+2;return1;}voidmain(){SqListLst;inti,n=15;ElemTypee;if(InitList_Sq(&Lst)==OK){printf("输入n个有序整数\n");for(i=1;i<=n;i++){scanf(“%d”,&e);if(ListInsert_Sq(&Lst,i,e)!=OK)break;}printf("n个有序整数为：\n");for(i=0;i<Lst.length;i++)printf("i,e=%d,%d\n",i,Lst.elem[i]);getch();printf("输入要插入的整数x:\n");scanf("%d",&e);if(i=FindPos_Sq(Lst,e)){ //确定e在有序表中的位置if(ListInsert_Sq(&Lst,i,e)!=OK)printf("Insertingelementisfailed\n");}else{printf("插入的数x以后，整数序列成为：\n");for(i=0;i<Lst.length;i++)printf("i,e=%d,%d\n",i,Lst.elem[i]);}}实验2：顺序栈的实现与插入删除操作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、 主函数。示例程序1,InitStack、StackEmpty、Push和Pop、conversion等在VC6.0中的调试：typedefintSElemType;typedefstruct{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineOVERFLOW-1#defineERROR0typedefintStatus;#include<malloc.h>#include<stdio.h>StatusInitStack(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;returnOK;}/*InitStack*/StatusPush(SqStack&s,SElemTypee){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;returnOK;}/*Push*/StatusPop(SqStack&s,SElemType&e){if(s.top==s.base)returnERROR;e=*(--s.top);returnOK;}/*Pop*/intStackEmpty(SqStacks){if(s.base==s.top)return1;elsereturn0;}voidconversion(){SqStacks;intN,b;SElemTypee;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*/voidmain(void){conversion();}三、实验选题、报告要求与评分一）实验选题本次的考核实验报告可以选择以下任一实验，也可以自拟题目的实验。1、第1个可选题目设计一个模拟简单整数计算器的程序。该程序可以接受整数数据，运算符可以接受包含（,）,+,-,*,/,%,和A（求幕运算符,aAb=ab）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“input.txt”.文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值（精确到小数点后两位），也可能是错误信息“ERRORININFIXNOTATION，输入例子：499+599+699*1(3*5*(4+8)%2)2人2人31+2(2/0(2-4)A32%22%5输出例子:1797256ERRORININFIXNOTATIONERRORININFIXNOTATION-8022、 第2个可选题目完成字符文章（长度可达数兆）进行Huffman编码的算法的完整程序。对给定的文本文件，进行编码和解码。具体的要求可以自主确定。3、 第3个可选题目有哪些排序算法，请设计相应的数据结构并实现排序算法，至少选择两种或以上的排序算法进行实现，分析其算法复杂度，通过实测数据对比其运行效率。二）实验报告格式与内容的要求：实验报告首先要求有一个清晰醒目的报告标题，例如：“《数据结构与算法》期末实验XXXXXXXXXX”。报告至少要求具备以下四部分内容：一、 简介这一部分需简单介绍题目内容，即该实验到底要做什么。如果涉及明确的算法，最好再简单介绍一下算法产生的背景。基本要求：实验内容必须覆盖完备。二、 算法说明这一部分需详细描述解决问题所需要用到的算法和重要的数据结构，即该实验到底应该怎么做。基本要求：所有处理问题中所用到的关键算法都要描述清楚，而不是仅描述主函数。算法和数据结构用伪码和图示描述，千万不要只写源代码加注释。这一部分的目的是让读者在短时间内对作者解决问题的整体思路有个清楚的了解，表达方式必须比源代码通俗易懂。如果读者感觉还不如直接读源代码来得明白，这一部分就失去了意义。三、 测试结果这一部分需根据题目类型设计提供相应