川师数据结构实验报告(含截图)

《数据结构》实验教学大纲学时课程总：64学分：4实验学时：24实验个数：7实验学分：1.5课程性质：必做适用专业：计算机科学与技术、软件工程、网络工程教材及参考书：数据结构（C语言版），严蔚敏吴伟民，清华大学出版社，2011年11月；数据结构题集（C语言版）实习题部分，清华大学出版社；数据结构实验教程，王玲刘芳贺春林等，四川大学出版社，2010年10月，大纲执笔人：刘芳大纲审定人：一、实验课的性质与任务计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。《数据结构》实验课程着眼于原理和应用的结合点，使读者学会如何将书上学到的知识用于解决实际问题，培养软件工作需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何老师更严厉的检查者。训练的重点在于基本的数据结构，而不是强调面面俱到。各实习单元与教科书的各章只具有粗略的对应关系，一个实习题常常涉及到几部分教学内容。二、实验课程目的与要求1.实验目的根据《数据结构》课程的任务与要求，帮助学生拓宽知识面。并达到以下教学要求：1)学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；掌握各种基本数据结构的逻辑结构和存储结构及相应算法。2)本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件过程的规范，从而培养学生的数据抽象能力；3)通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序做一些铺垫。2.实验要求1)熟悉各种基本数据结构的定义，性质和特点，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。2)会书写类C语言的算法，并将算法转变为程序实现。3)正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现，有较强的逻辑分析能力。4)针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。三、实验项目及内容提要数据结构实验课程（课程编号）序号实验项目编号实验名称学时必做选做学分数实验类型内容提要基本操作验证综合设计1抽象数据类型的表示与实现2√√√抽象数据类型的表示与实现2线性表实验4√√√线性表的存储实现及有关应用3栈和队列实验4√√√栈和队列的基本操作及其实现，以及典型应用举例4稀疏矩阵实验2√√稀疏矩阵的压缩存储5树和二叉树实验4√√树的两种种存储结构，及各种操作的算法实现（建立、遍历、线索化、最优二叉树）6图及其应用实验4√√图的两种基本存储结构，及各种操作的算法实现（建立、遍历、图的典型应用）7查找和排序实验4√√√各种基本的查找和排序算法及其实现分析四、实验内容安排：实验一抽象数据类型的表示与实现（验证性实验2学时）1.目的要求：1)熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现；2)理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）。3)认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。2.实验内容：1）编程实现抽象数据类型三元组的定义、存储、基本操作（最大值、最小值、平均值等的求解），并设计一个主菜单完成各个功能的调用。//////////////////////////////////////////////////////////////head.h//////////////////////////////////////////////////#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstruct{ElemType*T;}Triplet;StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3);StatusGet(TripletT,inti,ElemType&e);StatusPut(Triplet&T,inti,ElemTypee);StatusMax(TripletT,ElemType&e);StatusMin(TripletT,ElemType&e);StatusDestroy(Triplet&T);StatusPinJ(TripletT,ElemType&e);StatusPrin(TripletT);////////////////////////////////////////////////////////////function.cpp/////////////////////////////////////////////#includehead.h#includestdio.h#includestdlib.hStatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){T.T=(ElemType*)malloc(3*sizeof(ElemType));if(!T.T)exit(OVERFLOW);T.T[0]=v1;T.T[1]=v2;T.T[2]=v3;returnOK;}StatusGet(TripletT,inti,ElemType&e){if(i1||i3)returnERROR;e=T.T[i-1];returnOK;}StatusPut(Triplet&T,inti,ElemTypee){if(i1||i3)returnERROR;T.T[i-1]=e;returnOK;}StatusMax(TripletT,ElemType&e){e=(T.T[0]=T.T[1])?((T.T[0]=T.T[2])?T.T[0]:T.T[2]):((T.T[1]=T.T[2])?T.T[1]:T.T[2]);returnOK;}StatusMin(TripletT,ElemType&e){e=(T.T[0]=T.T[1])?((T.T[0]=T.T[2])?T.T[0]:T.T[2]):((T.T[1]=T.T[2])?T.T[1]:T.T[2]);returnOK;}StatusDestroy(Triplet&T){free(T.T);T.T=NULL;returnOK;}StatusPinJ(TripletT,ElemType&e){e=(T.T[0]+T.T[1]+T.T[2])/3;returnOK;}StatusPrin(TripletT){printf(三元组为：%d,%d,%d\n,T.T[0],T.T[1],T.T[2]);returnOK;}//////////////////////////////////////////////////////////main.cpp////////////////////////////////////////////////////#includehead.h#includestdio.h#includestdlib.hmain(){TripletT;inta,b,c,m,i,j,e;printf(1-------创建\n2-------查找\n3-------更换\n4-------最值\n5-------求平均\n6-------销毁\n);while(1){printf(请选择你想进行的操作：);scanf(%d,&m);switch(m){case1:printf(请输入三个数);scanf(%d%d%d,&a,&b,&c);InitTriplet(T,a,b,c);Prin(T);break;case2:if(T.T){printf(您想查找第几个数？);scanf(%d,&i);Get(T,i,e);printf(你想查找的数为：);printf(%d\n,e);Prin(T);}else{printf(没有相应对象，请重新创建。\n);}break;case3:if(T.T){printf(您想改变第几个数？);scanf(%d,&i);printf(您想将其变为：);scanf(%d,&e);Put(T,i,e);Prin(T);}else{printf(没有相应对象，请重新创建。\n);}break;case4:if(T.T){Max(T,e);printf(最大为：%d\n,e);Min(T,e);printf(最小为：%d\n,e);Prin(T);}else{printf(没有相应对象，请重新创建。\n);}break;case5:PinJ(T,e);printf(平均值为：%d,e);break;case6:Destroy(T);printf(销毁成功！);break;}}}3.主要仪器设备及药品1）PC机2）TurboC2.0或VisualC++实验二线性表实验（验证性实验4学时）1.目的要求：1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；2）以线性表的各种操作（建立、插入、删除等）的实现为重点；3）通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。4)认真阅读和掌握本实验的参考程序，上机运行本程序，保存和打印出程序的运行结果，并结合程序进行分析。按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。3.实验内容：编程实现线性表两种存储结构中的基本操作的实现（线性表的创建、插入、删除和查找），并设计一个主菜单完成各个功能的调用。////////////////////////////////////////////////////head1.h///////////////////////////////////////////////#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERLOW-2#defineINFEACIBLE-1#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefintStatus;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//定义这样一个指针类型的变量LinkList。StatusDeleteList_L(LinkList&L,inti,ElemTypee);StatusPutList_L(LinkList&L,inti,ElemTypee);StatusGetList_L(LinkListL,inti,ElemType&e);StatusDestoryList_L(LinkList&L);StatusCreateList_L(LinkList&L,intn);StatusInsertList_L(LinkList&L,inti,ElemTypee);StatusPrintfList_L(LinkListL);//////////////////////////////////////////////////////head2.h/////////