西南财经大学天府学院教学大纲任课教师：课程名称：数据结构任课班级：2007级本科计算机专业授课时间：2008-2009第一学期西南财经大学天府学院教务处制一、课程前言：数据结构是计算机及其相关专业的一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据(Data)的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下坚实的基础，同时也提供必要的技能训练。因此，数据结构课程在计算机及其相关专业中具有举足轻重的地位。本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。本课程的主要内容包括：⑴数据(Data)、数据元素(element)和数据项(item)的概念及其相互间的关系；数据结构的逻辑结构(Logicstructures)、存储结构(Storagestructures)的联系与区别以及在数据结构上施加的运算(Operations)及其实现(Implementations)。⑵线性表(LinearList)的定义及其运算；顺序表(SequentialList)和链表(LinkedList)的定义、组织形式、结构特征和类型说明以及在这两种表上实现的插入(Insert)、删除(Delete)和按值查找(Locate)的算法(Algorithms)。循环链表(CircularlyLinkedLists)、双(循环)链表(DoublyLinkedList)的结构特点和在其上施加的插入、删除等操作。⑶栈(Stack)和队列(Queue)的定义、特征及在其上所定义的基本运算，在两种存储结构上对栈和队列所施加的基本运算的实现。(4)树(Tree)的定义(Definition)、性质(Properties)及其存储方法；二叉树(BinaryTree)的二叉链表(BinaryLinkedList)存储方式、结点结构和类型定义；二叉树的遍历(Traverse)算法；树与二叉树间的相互转换；哈夫曼树(Huffmantrees)的构造方法。*(5)图(Graphs)的基本概念及术语；图的两种存储结构(邻接矩阵AdjacencyMatrix和邻接表AdjacencyList)的表示方法；图的遍历(Traversegraph)--深度优先搜索遍历(Depth-firstTraversal)和广度优先搜索遍历(Breadth-firstTraversal)--算法；最小生成树(MinimumSpanningTree)的构造；拓扑排序(Topologysort)、关键路径(CriticalPath)以及最短路径(ShortestPath)算法。(6)查找(Searching)的基本思想和基本概念；在顺序表(SequentialList)、有序表(OrderedList)、散列表(HashedList)等上的查找方法和算法(Algorithms)；二叉排序树(BinarySorttrees)、*平衡二叉树(AVLtrees)以及*B-树(B-trees)的概念和有关算法；散列表的构造。(7)排序的基本思想和基本概念；插入排序(InsertionSort)、选择排序(Selectionsort)、交换排序(Exchangesort)的基本思想、步骤及算法。本课程的教学重点及难点包括：⑴领会数据、数据元素和数据项的概念及其相互间的关系。清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现(Implementation)。会进行简单的算法分析(Algorithmefficiencyanalysis)。⑵理解线性表(LinearList)的定义及其运算。理解顺序表和链表LinkedList)的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入(Insert)、删除(Delete)和按值查找(Locate)的算法。了解循环链表(CircularlyLinkedLists)、双(循环)链表(DoublyLinkedList)的结构特点和在其上施加的插入、删除等操作。⑶理解栈(Stack)和队列(Queue)的定义、特征及在其上所定义的基本运算，掌握在两种存储结构上对栈和队列所施加的基本运算的实现。⑷深刻理解树(Trees)的定义、性质及其存储方法，熟练掌握二叉树(Binarytrees)的二叉链表(BinaryLinkedList)存储方式、结点(Node)结构和类型定义，并能画出给定二叉树