数据结构实验指导书学生.doc

数据结构课程实验指导书LIAOCHENG UNIVERSITY数据结构实验指导书聊城大学计算机学院2011年3月13目录数据结构课程实验教学大纲1实验一线性表3基本信息3实验预习3实验过程3实验数据和实验结果记录6实验结果分析7实验二栈和队列7基本信息7实验预习7实验过程8实验数据和实验结果记录9实验结果分析9实验三二叉树10基本信息10实验预习10实验过程10实验数据和实验结果记录11实验结果分析12实验四查找12基本信息12实验预习12实验过程13实验数据和实验结果记录14实验结果分析14数据结构课程实验教学大纲课程名称：数据结构英文名称：Data structure设置形式：非独立设课课程模块：专业核心课实验课性质：专业基础实验课程编号：509309课程负责人：大纲主撰人：大纲审核人：一、学时、学分 课程总学时：76实验学时：12课程学分：4二、适用专业及年级 计算机科学技术、计算机信息管理、电子商务、软件工程、网络工程二年级三、课程目标与基本要求数据结构是介于数学，计算机硬件和计算机软件三者之间的一门核心课程,它是一门综合性的专业基础课。上机实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅而成的必不可少的重要环节。通过本课程的实验，学生应学会如何把课本上的知识用于解决实际问题，培养软件工作所需的动手能力，即应学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择恰当的逻辑结构、存储结构以及其相应的算法，并初步掌握算法时间复杂度和空间复杂度的分析技术；另一方面，本课程实验是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，是复杂程序设计的训练过程，要求学生编写的程序正确且清晰易读，并具有较好的时间和空间效率。四、主要仪器设备 具有C+语言集成开发环境的计算机五、实验项目及教学安排序号实验项目名称实验基本方法和内容项目 学时项目类型每组人数教学 要求1线性表用C语言设计实现顺序表和链表的建立、插入、删除、显示功能4设计1必修2栈和队列用C语言设计实现栈（可选作队列）的初始化、入栈、出栈、判空等功能，并利用栈完成数制转换功能2综合1必修3二叉树用C语言设计实现二叉树的建立、遍历功能，需要完成先序遍历、中序遍历和后序遍历递归算法2综合1必修4查找用C语言设计实现顺序查找、二分查找4综合1必修5抽象数据类型定义复数为由两个相互之间存在次序的实数构成的ADT，利用实数操作实现复数的操作2基础1选修6停车场管理利用栈模拟停车场，利用队列模拟车场外的便道，实现停车场的模拟管理2综合1选修7文学研究助手的实现利用模式匹配KMP算法统计文学作品中特定词出现的次数和位置2设计1选修8校园导游咨询将整个校园平面设为一个无向网，利用Dijkstra算法或者Flod算法查询景点之间的最短路径2设计1选修六、考核方式及成绩评定七、实验教科书、参考书1实验教科书自编实验指导书。2实验参考书数据结构题集(第三版)，严蔚敏等，清华大学出版社,2009. 2数据结构(第三版)，严蔚敏等，清华大学出版社,2009.实验一线性表基本信息实验课程：数据结构设课形式：非独立课程学分：4实验项目：线性表项目类型：设计项目学时：4实验预习实验目的和要求：1、熟悉C语言集成开发环境；2、会定义线性表的顺序结构和链式结构；3、熟悉对线性表的基本操作，如插入、删除等。实验内容和原理或涉及的知识点：自己编写程序实现线性表的建立、插入、删除等功能。实验条件：具有C+语言集成开发环境的计算机实验设计方案：设计的顺序表算法有：1、初始化顺序表；2、顺序表的插入操作；3、顺序表的删除操作。设计的链表算法有：1、建立链表；2、链表的插入操作；3、链表的删除操作；4、链表数据元素的访问。实验过程1、根据实验预习阶段的实验设计方案，顺序表算法伪C代码如下。typedef struct ElemType *elem; int length; int listsize;SqList; status InitList(SqList &L) L.elem=(ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK;status ListInsert_Sq(SqList &L, int i, ElemType e) if (iL.length+1) return ERROR; if (L.length=L.listsize) newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType) ; if (!newbase) exit (OVERFLOW); L.elem = newbase; L.listsize=L.listsize+LISTINCREMENT; q=&(L.elemi-1); for (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) if (iL.length) return ERROR; p=&L.elemi-1; e=*p; q=L.elem+L.length-1; for (+p; pnext=NULL; for (i=n;i0;-i) p=(Linklist) malloc(sizeof(Lnode); scanf(%d,&p-data); p-next= L-next; L-next =p; return OK; /createList_L/*或者用下面的尾插法status CreateList_L(Linklist &L,int n) Linklist r; L=(Linklist) malloc(sizeof(LNode); L-next=NULL; r=L; for ( i=1;idata); r-next=p;r=p; ; r-next=NULL; /createList_L*/status ListInsert_L(Linklist &L, int i, ElemType e) p = L; j =0; while (p & jnext; +j; if (!p | ji-1) return ERROR; s=(Linklist)malloc(sizeof(Lnode); s-data = e; s-next = p-next; p-next = s; return OK; /ListInsert_Lstatus Listdelete_L(Linklist &L, int i, ElemType &e) p = L; j =0; while (p-next & jnext; +j; if (!(p-next) | ji-1) return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK; /Listdelete_L5、将算法细化为程序代码如下：6、编译、链接、运行程序。实验数据和实验结果记录（自己设计程序，给出结果，不需与指导书相同，下同）1、顺序表程序的一个运行实例如下。2、链表程序的一个运行实例如下。实验结果分析（需要自己写出，下面是给出的一个范例，下同）1、此程序的顺序表直接使用插入函数得到初始表，也可自己设计函数输入不同数值以得到顺序表；2、注意一些经常在算法使用的常量可在一个专门的head.h文件中定义；3、程序中的输入输出可使用C知识，也可使用C+中知识；4、分析思考算法改为程序时需要注意的问题；5、分析顺序表和链表的区别。扩展：课本算法2.1,2.2,2.12的实现数据结构题集：实习1实验二栈和队列基本信息实验课程：数据结构 设课形式：非独立课程学分：4实验项目：栈和队列项目类型：综合项目学时：2实验预习实验目的和要求：1、熟练掌握栈和队列的结构，以及这种数据结构的特点；2、会定义顺序栈、循环队列，能实现栈、队列的基本操作；3、会利用栈解决典型问题，如数制转换等。实验内容和原理或涉及的知识点：用C语言设计实现栈（可选作队列）的初始化、入栈、出栈、判空等功能，并利用栈完成数制转换功能。实验条件：具有C+语言集成开发环境的计算机实验设计方案：设计的算法有：1、初始化栈；2、入栈；3、出栈；4、判断栈是否为空；5、十进制转换为八进制。实验过程1、根据实验预习阶段的实验设计方案，编写顺序栈的伪C代码如下。typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;Status InitStack(SqStack &S) S.base = (SElemType *)malloc (STACK_INIT_SIZE*sizeof (SElemType);if (!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStackStatus Push(SqStack &S, SElemType e) if (S.top-S.base=S.stacksize) /栈满 S.base=(SElemType *)realloc (S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize+=STACKINCREMENT; / if *S.top+ = e; return OK; /PushStatus Pop(SqStack &S, SElemType &e) if(S.top = S.base)return ERROR; e = * - S.top; return OK; /Pop Status StackEmpty(SqStack S) if (S.base=S.top) return TRUE; return FALSE;2、将算法细化为程序代码。3、编译、链接、运行程序。实验数据和实验结果记录程序的一个运行实例如下。实验结果分析1、分析数制转换时后进先出的特点；2、分析如果将数转换为二进制， conversion函数的修改；3、分析如果没有初始化栈的操作时程序的运行结果；3、写出自己的心得体会。扩展：数据结构题集：实习2实验三二叉树基本信息实验课程：数据结构设课形式：非独立课程学分：4实验项目：二叉树项目类型：综合项目学时：2实验预习实验目的和要求：1、熟练掌握二叉树的结构，以及这种数据结构的特点；2、会定义二叉树的链式存储结构；3、能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法。实验内容和原理或涉及的知识点：自己编写程序实现二叉树的各种基本操作，如二叉树的建立，遍历等。实验条件：具有C+语言集成开发环境的计算机实验设计方案：设计的算法有：1、递归建立二叉树；2、先序遍历二叉树；3、中序遍历二叉树；4、后序遍历二叉树。实验过程1、根据实验预习阶段的实验设计方案，编写伪C代码如下。typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;status CreateBiTree(BiTree &T)/按先序次序输入二叉树中结点的值,空格表示空树/生成二叉树的二叉链表存储结构，T为根结点指针 scanf(%c,&ch); if (ch= ) T=NULL; else if (!(T=(BiTNode *) malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; /建立根结点 CreateBiTree( T-lchild); /建立左子树 CreateBiTree(T-rchild); /建立右子树 return OK; /CreateBiTreestatus PrintElement(TelemType e) printf(%c,e); /输出元素值 return OK;status PreorderTraverse(BiTree T, status(*visit)(TelemType e) /先序遍历根结点指针为T的二叉树if (T) if (visit(T-data) if (PreorderTraverse(T-lchild,visit)if (PreorderTraverse(T-rchild,visit) return OK; return ERROR; else return OK; /if (T) /PreorderTraverse2、将算法细化为程序代码。3、编译、链接、运行程序。实验数据和实验结果记录程序的一个运行实例如下。实验结果分析1、分析递归建立二叉树算法输入数据的格式和意义；2、分析先序、中序、后序遍历二叉树算法运行时后台栈的变化情况；3、分析指向函数的指针作为形参的作用；3、写出自己的心得体会。扩展：数据结构题集：实习5实验四查找基本信息实验课程：数据结构设课形式：非独立课程学分：4实验项目：查找项目类型：综合项目学时：4实验预习实验目的和要求：1、熟练掌握查找算法的基本思想，以及算法的适用条件；2、会定义静态查找表的顺序结构，能实现顺序查找、二分查找。实验内容和原理或涉及的知识点：自己编写程序实现顺序查找、二分查找。实验条件：具有C+语言集成开发环境的计算机实验设计方案：