数据结构与分析.docVIP

课程名称：数据结构原理与分析 课程代码：01343 第一部分 课程性质与目标 课程的性质与特点： 《数据结构》是信息技术专业计算机专业的一门重要的专业基础课用计算机解决任何实际问题都离不开数据表示和数据处理而数据的表示和处理的核心问题之一数据结构及其实现正是数据结构课程的基本内容从这个意义上说数据结构课程在知识学习和技能培养两个方面都处于关键性地位本课程不仅为数据库及其应用操作系统概论面向对象程序设计软件工程等后继软件课程提供了必要的知识基础也为计算机及应用的专业人员提供了必要的技能训练 数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言（或C++）实现的，故要求较熟练地掌握C语言（或C++）。 【课程修读对象】 第二部分 考核内容与考核目标 第一章 绪论 一、学习目的和要求 通过本章学习，学生需要掌握常用的基本概念，了解本书涉及的逻辑结构和存储结构，对本教材的体系有一个大致的了解。 二、考核知识点与考核目标 （一）基本概念和术语（重点） 数据,数据,数据元素数据结构,数据的逻辑结构与物理结构,逻辑结构与物理结构间的关系。 数据类型、抽象数据类型、数据抽象和信息隐蔽原则，了解什么是面向对象。数据算法的定义、算法的特性、算法的时间代价、算法的空间代价。C语言，能够使用C语言编写程序。链表动态链表和静态链表单链表的结构、特点。带表头结点的单链表和类定义及相应操作的实现。单链表的类定义、构造函数、单链表的插入与删除算法。循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法。双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。 一、教学目的　 试验目的在于更深入的理解和掌握课程教学中的有关基本概念，将知识转化为能力，通过解决实际问题，来提高分析和解决问题的能力。因此明确试验的目的，以保证达到课程所指定的基本要求。 实验一 顺序存储的线性表 （一）实验目的： 1、了解线性表的逻辑结构特征。 2、熟练掌握线性表的顺序存储结构的描述方法及在其上实现各种基本运算的方法。 3、掌握和理解本实验中出现的一些基本的C语言语句。 4、体会算法在程序设计中的重要性。 （二）实验内容： 1、将一顺序表中的元素逆置，要求算法仅用一个辅助结点。 2、求顺序表中的元素的最大值和次最大值。 3、设一顺序表中元素值递增有序。试设计一算法，将元素x插入到表中适当的位置上，并保持顺序表的有序性。 实验二 单链表 （一）实验目的 1、熟练掌握线性表运用链表存储时的各种运算的算法实现。 2、掌握和理解本实验中出现的一些基本的C语言语句。 3、体会算法在程序设计中的重要性。 （二）实验内容 1、设计一算法，逆置带头结点的动态单链表，要求用原表的结点空间。 2、设一链表表中元素值递增有序。试设计一算法，将元素x插入到表中适当的位置上，并保持顺序表的有序性。 3、在无表头结点、也无头指针的非空单循环链表中，指针S指向该链表中的任一结点，试写一算法删除结点S的直接前驱结点。 4、设有两个按元素值递增有序的单链表A和B，编一程序将A表和B表归并成一个新的递增有序的单链表C（值相同的元素均保留在C表中），并要求利用原表的空间。 实验三 栈和队列 （一）实验目的 1、掌握栈和队列的数据结构的特点。 2、熟练掌握在两种存储结构上实现栈和队列的基本运算。 3、学会利用栈和队列解决一些实际问题。 4、掌握和理解本实验中出现的一些基本的C语言语句。 5、体会算法在程序设计中的重要性。 （二）实验内容 1、写一算法将一顺序栈中的元素依次取出，并输出元素值。 2、写一算法将一链栈中的元素依次取出，并输出元素值。 3、写一算法将一顺序队列中的元素依次取出，并输出元素值。 4、写一算法将一链队列中的元素依次取出，并输出元素值。 实验四 串 （一）实验目的 1、掌握串的顺序和链式存储结构的实现方法。 2、了解串的模式匹配算法。 （二）实验内容 1、写出取子串运算的算法。 2、写出替换运算的算法。 实验五 二叉树 （一）实验目的 1、熟悉二叉树的各种存储结构及使用范围。 2、掌握建立二叉树的存储结构的方法。 3、熟练掌握二叉树的三种遍历方式的递归算法。 4、掌握递归的方式。 （二）实验内容 1、以二叉链表作存储结构，设计求二叉树高度的算法。 2、以二叉链表作存储结构，编写递归的中序遍历算法。 实验六 图 (一)实验目的 1、掌握图的两种存储结构的实验方法。 2、掌握遍历图的递归算法。 （二）实验内容