还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
LIAOCHENGUNIVERSITY数据结构实验指导书聊城大学计算机学院2011年3月目 录TOC\o1-3\h\z《数据结构》课程实验教学大纲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《数据结构》课程实验教学大纲课程名称数据结构英文名称Datastructure设置形式非__设课课程模块专业核心课实验课性质专业基础实验课程编号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代码如下typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;statusInitListSqListL{L.elem=ElemType*__llocLIST_INIT_SIZE*sizeofElemType;if!L.elemexitOVERFLOW;L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}statusListInsert_SqSqListLintiElemTypee{ifi1||iL.length+1returnERROR;ifL.length=L.listsize{newbase=ElemType*reallocL.elemL.listsize+LISTINCREMENT*sizeofElemType;if!newbaseexitOVERFLOW;L.elem=newbase;L.listsize=L.listsize+LISTINCREMENT;}q=L.elem[i-1];forp=L.elem[L.length-1];p=q;--p*p+1=*p;*q=e;L.length++;returnOK;}statusListDelete_SqSqListLintiElemTypee{ifi1||iL.lengthreturnERROR;p=L.elem[i-1];e=*p;q=L.elem+L.length-1;for++p;p=q;++p*p-1=*p;--L.length;returnOK;}//ListDelete_Sq
2、将算法细化为程序代码如下省略,但实验报告中需给出,下同
3、编译、链接、运行程序
4、链表伪C代码如下typedefstructLnode{ElemTypedata;structLnode*next;}Lnode*Linklist;statusCreateList_LLinklistLintn{L=Linklist__llocsizeofLnode;L-next=NULL;fori=n;i0;--i{p=Linklist__llocsizeofLnode;scanf%dp-data;p-next=L-next;L-next=p;}returnOK;}//createList_L/*或者用下面的尾插法statusCreateList_LLinklistLintn{Linklistr;L=Linklist__llocsizeofLNode;L-next=NULL;r=L;fori=1;i=n;++i{p=Linklist__llocsizeofLNode;scanf%dp-data;r-next=p;r=p;};r-next=NULL;};//createList_L*/statusListInsert_LLinklistLintiElemTypee{p=L;j=0;whilepji-1{p=p-next;++j;}if!p||ji-1returnERROR;s=Linklist__llocsizeofLnode;s-data=e;s-next=p-next;p-next=s;returnOK;}//ListInsert_LstatusListdelete_LLinklistLintiElemTypee{p=L;j=0;whilep-nextji-1{p=p-next;++j;}if!p-next||ji-1returnERROR;q=p-next;p-next=q-next;e=q-data;freeq;returnOK;}//Listdelete_L
5、将算法细化为程序代码如下
6、编译、链接、运行程序实验数据和实验结果记录(自己设计程序,给出结果,不需与指导书相同,下同)
1、顺序表程序的一个运行实例如下
2、链表程序的一个运行实例如下实验结果分析(需要自己写出,下面是给出的一个范例,下同)
1、此程序的顺序表直接使用插入函数得到初始表,也可自己设计函数输入不同数值以得到顺序表;
2、注意一些经常在算法使用的常量可在一个专门的head.__件中定义;
3、程序中的输入输出可使用C知识,也可使用C++中知识;
4、分析思考算法改为程序时需要注意的问题;
5、分析顺序表和链表的区别扩展课本算法
2.
12.
22.12的实现《数据结构题集实习1》实验二 栈和队列基本信息实验课程数据结构设课形式非__课程学分4实验项目栈和队列项目类型综合项目学时2实验预习实验目的和要求
1、熟练掌握栈和队列的结构,以及这种数据结构的特点;
2、会定义顺序栈、循环队列,能实现栈、队列的基本操作;
3、会利用栈解决典型问题,如数制转换等实验内容和原理或涉及的知识点用C语言设计实现栈(可选作队列)的初始化、入栈、出栈、判空等功能,并利用栈完成数制转换功能实验条件具有C++语言集成__环境的计算机实验设计方案设计的算法有
1、初始化栈;
2、入栈;
3、出栈;
4、判断栈是否为空;
5、十进制转换为八进制实验过程
1、根据实验预习阶段的实验设计方案,编写顺序栈的伪C代码如下typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStackSqStackS{S.base=SElemType*__llocSTACK_INIT_SIZE*sizeofSElemType;if!S.baseexitOVERFLOW;S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPushSqStackSSElemTypee{ifS.top-S.base=S.stacksize//栈满{S.base=SElemType*reallocS.baseS.stacksize+STACKINCREMENT*sizeofSElemType;if!S.baseexitOVERFLOW;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}//if*S.top++=e;returnOK;}//PushStatusPopSqStackSSElemTypee{ifS.top==S.basereturnERROR;e=*--S.top;returnOK;}//PopStatusStackEmptySqStackS{ifS.base==S.topreturnTRUE;returnFALSE;}
2、将算法细化为程序代码
3、编译、链接、运行程序实验数据和实验结果记录程序的一个运行实例如下实验结果分析
1、分析数制转换时后进先出的特点;
2、分析如果将数转换为二进制,conversion函数的修改;
3、分析如果没有初始化栈的操作时程序的运行结果;
3、写出自己的心得体会扩展《数据结构题集实习2》实验三 二叉树基本信息实验课程数据结构设课形式非__课程学分4实验项目二叉树项目类型综合项目学时2实验预习实验目的和要求
1、熟练掌握二叉树的结构,以及这种数据结构的特点;
2、会定义二叉树的链式存储结构;
3、能实现二叉树的建立、遍历等功能,需要完成先序遍历、中序遍历和后序遍历递归算法实验内容和原理或涉及的知识点自己编写程序实现二叉树的各种基本操作,如二叉树的建立,遍历等实验条件具有C++语言集成__环境的计算机实验设计方案设计的算法有
1、递归建立二叉树;
2、先序遍历二叉树;
3、中序遍历二叉树;
4、后序遍历二叉树实验过程
1、根据实验预习阶段的实验设计方案,编写伪C代码如下typedefstructBiTNode{TelemTypedata;structBiTNode*lchild*rchild;}BiTNode*BiTree;statusCreateBiTreeBiTreeT{//按先序次序输入二叉树中结点的值空格表示空树//生成二叉树的二叉链表存储结构,T为根结点指针scanf%cch;ifch==T=NULL;else{if!T=BiTNode*__llocsizeofBiTNodeexitOVERFLOW;T-data=ch;//建立根结点CreateBiTreeT-lchild;//建立左子树CreateBiTreeT-rchild;//建立右子树}returnOK;}//CreateBiTreestatusPrintElementTelemTypee{printf%ce;//输出元素值returnOK;}statusPreorderTr__erseBiTreeTstatus*visitTelemTypee{//先序遍历根结点指针为T的二叉树ifT{ifvisitT-dataifPreorderTr__erseT-lchildvisitifPreorderTr__erseT-rchildvisitreturnOK;returnERROR;}elsereturnOK;//ifT}//PreorderTr__erse
2、将算法细化为程序代码
3、编译、链接、运行程序实验数据和实验结果记录程序的一个运行实例如下实验结果分析
1、分析递归建立二叉树算法输入数据的格式和意义;
2、分析先序、中序、后序遍历二叉树算法运行时后台栈的变化情况;
3、分析指向函数的指针作为形参的作用;
3、写出自己的心得体会扩展《数据结构题集实习5》实验四 查找基本信息实验课程数据结构设课形式非__课程学分4实验项目查找项目类型综合项目学时4实验预习实验目的和要求
1、熟练掌握查找算法的基本思想,以及算法的适用条件;
2、会定义静态查找表的顺序结构,能实现顺序查找、二分查找实验内容和原理或涉及的知识点自己编写程序实现顺序查找、二分查找实验条件具有C++语言集成__环境的计算机实验设计方案
1、建立静态查找表;
2、顺序查找;
3、建立有序的静态查找表;
4、二分查找实验过程
1、根据实验预习阶段的实验设计方案,编写顺序查找伪C代码如下typedefstruct{ElemType*elem;//0号单位不用intlength;}SSTable;intSearch_SeqSSTableSTElemTypekey{//从尾部依次比较关键字和数据元素的关键字,//当比到0下标才成功则查找不成功,返回0//否则返回下标iST.elem
[0]=key;fori=ST.length;!EQST.elem[i]key;--i;returni;}//Search-SeqintSearch_BinSSTableSTElemTypekey{low=1;high=ST.length;whilelow=high{mid=low+high/2;ifEQkeyST.elem[mid]returnmid;elseifLTkeyST.elem[mid]high=mid-1;elselow=mid+1;}return0;}
2、将算法细化为程序代码
3、编译、链接、运行程序实验数据和实验结果记录一个程序运行实例如下实验结果分析
1、分析顺序查找时,从头到尾查找和从尾到头查找时间复杂度的区别;
2、分析顺序查找时监视哨的作用;
3、分析二分查找时对静态查找表的要求;
4、写出自己的心得体会扩展《数据结构题集实习6》。