数据结构实验指导书C语言版罗先文样本.doc

——信息管理系《数据构造》实验指引书《DATASTRUCTURES》罗先文LUOXIANWEN西南大学信息管理系Iinformationdept.SouthWestUniversityJanuary24，写在上机实习之前上机实践是学生对本门课程所学知识一种全面、综合能力训练，是与课堂听讲、自学和练习相辅相成必不可少一种教学环节，也是对课堂教学与实践教学效果一种检查。普通，实习题中问题比平时习题复杂得多，也更接近实际。实习着眼于原理与应用结合，使学生学会如何把书上学到知识运用于解决实际问题过程中去，培养从事软件开发设计工作所必须基本技能；另一方面，能使书上知识变“活”，起到深化理解和灵活掌握教学内容目。平时练习较偏重于如何编写功能单一“小”算法，而实习题是软件设计综合训练，涉及问题分析，总体构造设计，顾客界面设计，程序设计基本技能和技巧，多人合伙，以至一整套软件工程规范训练和科学作风培养。此外，尚有很重要一点是：机器是比任何教师都严肃主考者。为了达到上述目，本篇安排了7个主实习单元，各单元训练重点在于基本数据构造，而不强调面面俱到。各实习单元与教科书各章具备紧密相应关系，在个别实习单元中安排有难度差别不等各种实习题，以便学生选做。此外，每个实习题采用了统一格式，实验目、实验内容、实验规定、程序实现、程序运营状况和源程序清单等5个某些构成。在每个实习单元都提供了一种完整实当代码，仅供同窗们参照，绝大多数同窗在上机实习时千万不要机械照抄本附录所提供范文。而是应当自己独立思考和设计你算法和程序，并争取在规定期间内如期完毕上机工作任务。对于个别成绩较差同窗，实在是没法完毕任务建议你不妨抄一遍附录中样题，以增强你感性结识，强化你实践基本，提高你实践能力。本附录样题所有用c语言编写，并所有上机调试通过，但由于时间比较仓促，样题中提供算法和程序并不是最佳算法和程序，相信不少同窗一定有能力设计出更好算法和程序。随着计算机学科不断发展，可以使用语言工具越来越丰富，在本篇中实习示例还只是应用面向过程语言进行设计和编写程序，同样实习题，读者也可以用面向对象语言来实现。咱们但愿实习报告示例能起到一种抛砖引玉作用，在通过同窗们努力学习和积极使用后来，更多更优良设计范例能不断涌现。文中存在不当之处，敬请各位不吝赐教！目录《数据构造》实验大纲4实验一、线性表操作2实验二、栈和队列应用6实验三、多维数组和串12实验四、树和二叉树操作17实验五、图操作23实验六、各种查找操作30实验七、各种排序操作37《数据构造》实验大纲一.课程名称：数据构造及算法分析课程编号：课程学时：70课程学分：3.5实验时数：20二.所属实验室名称：计算机中心三.实验教材及参照书：【1】数据构造题集（C语言版）清华大学出版社【2】DATASTRUCTURESWITHC++清华大学出版社【3】本材料之后附录四.实验内容和目：掌握四种基本数据构造：集合、线性构造、树形构造、网状构造在求解实际问题中应用，以及培养书写规范文档技巧。学习基本查找和排序技术。规定学生具备编制相称规模程序能力。养成一种良好程序设计风格。五.考核方式：上机考试、编程并运营通过。六.实验环境：硬件最低规定：586微型计算机，主频450MHZ以上，内存64MB以上，硬盘10G，有软驱。每个学生每次上机实验使用一台计算机。软件：C语言或VisualC++6.0七.实验项目及安排序号实验名称类别学时目与安排备注必选选开1链表、数组Ö4插入、删除、合并、排序、查找2栈与队列Ö43递规算法Ö4汉诺塔问题4树及应用Ö4递规、非递规遍历5图及应用Ö4遍历算法、最小生成树6排序查找Ö4排序、查找算法比较分析7串及应用Ö4匹配算法8线索树Ö4中序线索化操作实验一、线性表操作一、实验目1．掌握用C语言调试程序基本办法。2．掌握线性表基本运算，如插入、删除等。二、实验内容1．线性表在顺序存储构造上插入元素，删除元素运算2．线性表在链式存储构造上建链表，插入结点，删除结点运算三、实验规定1．C++/C完毕算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验成果和数据。3．分析算法，规定给出详细算法分析成果，涉及时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作算法（操作过程）五、程序运营状况写出输入数据及运营成果六、源程序清单。程序1：顺序存储线性表和运算#include<stdio.h>#defineMAXSIZE100intlist[MAXSIZE];intn;/*insertinaseqlist*/intsq_insert(intlist[]，int*p_n，inti，intx){intj;if(i<0||i>*p_n)return(1);if(*p_n==MAXSIZE)return(2);for(