数据结构的设计报告.docVIP

数据结构实验报告 指导老师：陈明 学号： 姓名： 实验总要求及内容简介 一．实验总要求：?? 书写类C语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。 二．主要仪器设备：（所开实验的主要仪器设备） ?? 硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PⅢ及以上的微机。 三、实验项目内容简介 为了达到实验目的，本课程有四个实习单元，训练的重点在于基本的数据结构，而不是强调面面俱到。 1、线性表基本操作? （1)?熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现 （2)以线性表的各种操作（建立、插入、删除等）的实现为重点 （3)?通过本次实习帮助学生加深对高级语言C语言的使用（特别是函数参数、指针类型、链表的使用）。 2、栈、队列以及递归算法的设计 （1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们 （2)??训练的要点是“栈”的观点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法 ??3、树、图及其应用 （1)?????? 树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点。 （2)?????? 要求学生熟悉各种存储结构的特性，以及如何应用树和图结构求解具体问题。 （3)?????? 训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。 4、查找和排序 本次实习旨在集中对几个专门的问题做较为深入的探讨和理解 重点在掌握各种内部排序算法、查找算法的思想和实现，体会查找和内部排序算法思想，理解开发高效算法的可能性和寻找、构造高效算法的方法。 四、主要参考书 1、《数据结构题集》（C语言版）实习题部分，清华大学出版社,1999.11 2、《数据结构习题与解析》（C语言篇），李春葆 编著，清华大学出版社，2000.1 3、宁正元《数据结构习题解析与上机实验指导》 水利水电出版社（2003年） 4、《C++程序设计》，杨长兴 刘卫国主编，中国铁道出版社，2008.12 实验一 线性表的操作 一、实验目的 1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．会定义线性表的顺序存储结构。（链式存储结构） 3．熟悉对顺序表（单链表）的一些基本操作。 二、实验要求 1．认真阅读和掌握本实验内容所给的全部程序。 2．保存和打印出程序运行结果，并结合程序进行分析。 三、实验内容 1、顺序表的创建，在程序内部输入整形数据为主。 程序所能表达到的功能为：实现顺序表的创建、查找、插入、删除等功能。 程序运行后，输入数据并执行。 #includestdio.h #define MAXSIZE 100 /*线性表容量*/ typedef char ElemType; typedef struct { ElemType data[MAXSIZE]; int length; } SqList; void InintList(SqList L) /**初始化**/ { L.length=0; } int GetLength(SqList L) /**求长**/ { return L.length; } int GetElem(SqList L,int i,ElemType e) /**求值,i为下标**/ { if(i1||iL.length) return 0; else e=L.data[i-1]; return 1; } int Locate(SqList L,ElemType x) /**按值查找**/ { int i=0; while(L.data[i]!=x) { i++; } if(iL.length) return 0; else return i+1; } int InsElem(SqList L,ElemType x,int i) /**插入元素**/ { int j; if(i1||iL.length+1) return 0; for(j=L.length;ji;j--) { L.data[j]=L.data[j-1];