《数据结构》大纲2523
贫而无谄，富而无骄
—— 子贡
西南财经大学天府学院
教学大纲
任课教师：
课程名称：数据结构
任课班级：2007级本科计算机专业
授课时间：2008-2009 第一学期
西南财经大学天府学院教务处制
一、课程前言：
数据结构是计算机及其相关专业的一门重要的专业基础课程
当用计算机来解决实际问题时，就要涉及到数据(Data)的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下坚实的基础，同时也提供必要的技能训练
因此，数据结构课程在计算机及其相关专业中具有举足轻重的地位
本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会
本课程的主要内容包括：
⑴数据(Data)、数据元素(element)和数据项(item)的概念及其相互间的关系；数据结构的逻辑结构(Logic structures)、存储结构(Storage structures)的联系与区别以及在数据结构上施加的运算(Operations)及其实现(Implementations)
⑵线性表(Linear List)的定义及其运算；顺序表(Sequential List)和链表(Linked List)的定义、组织形式、结构特征和类型说明以及在这两种表上实现的插入(Insert)、删除(Delete)和按值查找(Locate)的算法(Algorithms)
循环链表(Circularly Linked Lists )、双(循环)链表(Doubly Linked List)的结构特点和在其上施加的插入、删除等操作
⑶栈(Stack)和队列(Queue)的定义、特征及在其上所定义的基本运算，在两种存储结构上对栈和队列所施加的基本运算的实现
(4)树(Tree)的定义(Definition)、性质(Properties)及其存储方法；二叉树(Binary Tree)的二叉链表(Binary Linked List)存储方式、结点结构和类型定义；二叉树的遍历(Traverse)算法；树与二叉树间的相互转换；哈夫曼树(Huffman trees)的构造方法
*(5)图(Graphs)的基本概念及术语；图的两种存储结构(邻接矩阵Adjacency Matrix和邻接表Adjacency List )的表示方法；图的遍历(Traverse graph)--深度优先搜索遍历(Depth-first Traversal)和广度优先搜索遍历(Breadth-first Traversal)--算法；最小生成树(Minimum Spanning Tree)的构造；拓扑排序(Topology sort)、关键路径(Critical Path)以及最短路径(Shortest Path)算法
(6)查找(Searching)的基本思想和
基本概念；在顺序表(Sequential List)、有序表(Ordered List)、散列表(Hashed List)等上的查找方法和算法(Algorithms)；二叉排序树(Binary Sort trees)、*平衡二叉树(AVL trees)以及*B-树(B-trees)的概念和有关算法；散列表的构造
(7)排序的基本思想和基本概念；插入排序(Insertion Sort)、选择排序(Selection sort)、交换排序(Exchange sort)的基本思想、步骤及算法
本课程的教学重点及难点包括：
⑴领会数据、数据元素和数据项的概念及其相互间的关系
清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现(Implementation)
会进行简单的算法分析(Algorithm efficiency analysis)
⑵理解线性表(Linear List)的定义及其运算
理解顺序表和链表Linked List)的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入(Insert)、删除(Delete)和按值查找(Locate)的算法
了解循环链表(Circularly Linked Lists)、双(循环)链表(Doubly Linked List)的结构特点和在其上施加的插入、删除等操作
⑶理解栈(Stack)和队列(Queue)的定义、特征及在其上所定义的基本运算，掌握在两种存储结构上对栈和队列所施加的基本运算的实现
⑷深刻理解树(Trees)的定义、性质及其存储方法，熟练掌握二叉树(Binary trees )的二叉链表(Binary Linked List)存储方式、结点(Node)结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树的三种遍历(Traversal)方法，并能写出该三种遍历的算法；会完成树与二叉树间的相互转换；理解哈夫曼树(Huffman trees)的构造方法，并能对给定的数据集合构造出哈夫曼树
*⑸理解图(Graph)的基本概念及术语，掌握图的两种存储结构(邻接矩阵(Adjacency Matrix)和邻接表(Adjacency List))的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历(Depth-first Traversal)和广度优先搜索遍历(Breadth-first Traversal))的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树(Minimum Spanning Tree)的概念，能按Prim算法构造最小生成树；了解并掌握拓扑排序(Topology sort)、关键路径(Critical Path)、最短路径(Shortest Path)的算法思想
⑹理解查找(Search)的基本思想和基本概念，掌握在顺序表(Sequential List)、有序表(Ordered List)、散列表(Hashed List)等上的查找方法和算法，并能进行相应的效率分析
⑺理解排序(Sort)的基本思想和基本概念，理解和掌握插入排序(Insertion Sort)、选择排序(Selection sort)、交换排序(Exchange sort)的基本思想、步骤及算法
本课程的先修课程为离散数学和高级语言程序设计
学习本课程必须具
备高级语言程序设计(比如Pascal语言或C语言)的基础知识与基本技能
它的后续课程有操作系统、计算机网络和数据库系统等
本课程是为电子商务学院各专业一年级本科生开出的，课程学时推荐为54-64（讲课41-51，实验考核13）学时，共3学分，教材拟选用《数据结构的C++伪码实现 Data structures A Pseudocode Approach with C++》英文版，该书系"国外著名高等院校信息科学与技术优秀教材"
二、课程目录：
第1章 概论（Introduction）
1-1伪代码(Pseudocode)
1-2 抽象数据类型(Abstract data type)
1-3 一个抽象数据类型模型(A Model for an Abstract Data Type)
1-4 算法和算法分析(Algorithm efficiency)
第2章 查找(Searching)
2-1表的查找（List Searches）
2-2 C++查找算法(C++ Search Algorithms)
2-3 散列表查找(Hashed List Searches)
2-4 冲突解决(Collision Resolution)
第3章 链表(Linked Lists)
3-1线性表的基本概念(Linear List Concepts)
3-2 链表的基本概念(Linked List Concepts)
3-3 链表的算法(Linked List Algorithms)
3-4 链表的操作(Processing a Linked List)
3-5表的应用(List Applications)
3-6 复杂链表结构(Complex Linked List Structures)
第4章 栈(Stack)
4-1 栈的基本操作(Basic Stack Operations)
4-2 栈的链表实现(Stack Linked List Implementation)
4-3 栈的应用(Stack Applications)
第5章 队列(Queue)
5-1 队列的基本操作(Queue Operations)
5-2 链队列的实现(Queue Linked List Design)
5-3 排队论(Queuing Theory)
5-4 队列的应用(Queue Applications)
第6章 递归(Recursion
)
6-1 阶乘-一个递归的实例研究(Factorial-A Case Study)
6-2 递归的工作原理(How Recursion Works)
6-3 设计递归算法(Designing Recursive Algorithms)
6-4 递归算法的典型例子(Fibonacci Numbers & The Towers of Hanoi)
第7章 树(Introduction to Trees )
7-1树的基本概念(Basic Tree Concepts)
7-2 二叉树(Binary Trees)
7-3 二叉树的遍历(Binary Tree Traversals)
7-4 表达式树(Expression Trees)
7-5 一般树(General Trees)
7-6 Huffman编码(Huffman code)
第8章 查找树(Search trees)
8-1 二叉查找树(Binary Search trees) 或二叉排序树(Binary Sort trees)
8-2 二叉平衡树(AVL Trees)
*8-3 二叉平衡树的操作及平衡调整(AVL Trees Implementation)
*第9章 多路树(Multiway trees)
9-1 多路查找树(m-way search trees)
9-2 B-树(B-trees)；
9-3 B-树的变异-B*与B+树(B* & B+ Trees)
第10章 排序(Sorts)
10-1 排序的基本概念(General Sort Concepts)
10-2 插入排序(Insertion Sorts)
10-3 选择排序
(Selection Sorts)
10-4 交换排序(Exchange sorts)
*10-5 外部排序(External Sorts)
*第十一章 图(Graphs)
11-1 图的术语(Terminology)
11-2 图的操作(Operations)
11-3 图的存储结构(Graph Storage Structures)
11-4 图的算法(Graph Algorithms)
11-5 网(Networks)
三、教学内容：
第1章 概论（Introduction）
1、教学内容
(1)伪代码(Pseudocode)；
(2)数据结构的概念(Data structure)；
(3)抽象数据类型(Abstract data type)；
(4)算法和算法分析(Algorithm efficiency analysis)
2、教学目的及要求
⑴学习伪代码表示算法的方法
⑵领会数据、数据元素和数据项的概念及其相互间的关系；
⑶清楚数据结构的逻辑结构(logic structures)、存储结构(storage structures)的联系与区别，以及在数据结构上施加的运算及其实现(implementations)；
⑷理解抽象数据类型的概念；
⑸掌握进行简单算法分析的方法
3、教学重点
⑴用伪代码表示算法
⑵数据、数据元素、数据项；
⑶逻辑结构和数据结构在概念上的联系与区别；
⑷存储结构及其三个组成部分；
⑸抽象数据类型和数据抽象；
⑹评价算法优劣的标准及方法
4、教学难点
⑴区别算法与程序；
⑵逻辑结构、存储结构的联系与区别；
⑶抽象数据类型；
⑷算法的时间复杂度分析
5、教学时间分配及进度安排
2+1=3学时
第2章 查找(Searching)
1、教学内容
⑴线性表(linear List)查找；
⑵散列表(Hashed List)查找；
⑶冲突解决(Collision Resolution)
2、教学目的及要求
⑴了解查找的基本思想及查找成功和不成功的概念；
⑵掌握在顺序表(sequential List)、有序表(Ordered List)、散列表等上的查找方法和算法，并能求出相应的平均查找长度；
⑶掌握散列函数构造方法及冲突解决方案
3、教学重点
⑴查找表的基本概念及查找原理；
⑵查找算法在顺序存储表(sequential)的实现；
⑶查找算法在有序表（ordered）的实现（二分查找Binary search）
⑷散列表及散列存储和散列查找的基本思想；
⑸各种散列表的组织、解决冲突的方法
4、教学难点
⑴理解查找表的逻辑结构是集合，它的运算以查找为核心；
⑵散列表上的有关算法
5、教学时间分配及进度安排
2×3=6学时
第3章 链表(Linked List)
1、教学内容
⑴线性表及链表的基本概念；
⑵链表的操作(Operation)与算法；
⑶链表的应用(Applications)
2、教学目的及要求
⑴理解线性表的定义及其操作
；
⑵理解链表的定义、组织形式、结构特征和类型说明；
⑶掌握在链表上实现的插入(Insert)结点、删除(Delete)结点和按值查找(Locate)的算法；
*⑷了解循环(cycle)链表、双(Double)(循环)链表的结构特点和在其上施加的插入、删除等操作
3、教学重点
⑴线性表的定义及逻辑上的特点；
⑵单链表(singly linked list)
的结构特点及类型说明；
⑶头指针(Head Pointer)和头结点(Head Node)的作用及区别；
⑷定位(Locate)结点、删除结点、插入结点操作在单链表上的实现；
*⑸循环链表、双链表的结构特点；
*⑹循环链表、双链表上删除与插入操作的实现
4、教学难点
⑴线性表与线性结构的联系与区别；
⑵链表与链式结构的联系与区别；
⑶头结点在链表中的作用；指针操作；
⑷删除、插入运算中的指针操作顺序；
*⑸双链表上指针的操作顺序
5、教学时间分配及进度安排
2×3=6学时
第4章 栈(Stack)
1、教学内容
⑴栈的基本概念；
⑵栈的基本操作；
⑶顺序栈(Sequential Stack)及链栈(Linked Stack)的实现；
*⑷栈的应用
2、教学目的及要求
⑴理解栈的定义、特征及在其上所定义的基本操作；
⑵掌握在两种存储结构上对栈进行的基本操作的实现
3、教学重点
⑴栈的定义及逻辑特点；
⑵栈的基本操作；
⑶栈的顺序存储结构及操作实现；
⑷栈的链式存储结构；
⑸入栈(Push stack)、出栈(Pop stack)等操作在链栈上的实现；
*⑹栈的应用
4、教学难点
⑴顺序栈的溢出(Overflow)判断条件；
*⑵栈的应用
5、教学时间分配及进度安排
2×2=4学时
第5章 队列(Queue)
1、教学内容
⑴队列的基本概念；
⑵队列的基本操作；
⑶顺序队列(Sequential Queue)及链队列(Linked Queue)的实现；
*⑷队列的应用
2、教学目的及要求
⑴理解队列的定义、特征及在其上所定义的基本运算；
⑵掌握在两种存储结构上对队列所进行的基本操作的实现
3、教学重点
⑴队列的定义及逻辑特点；
⑵队列的基本操作；
⑶队列的顺序存储结构及操作实现；
⑷队列的链式存储结构；
⑸入队(Enqueue)、出队(Dequeue)等操作在链队列上的实现
4、教学难点
⑴循环队列(Cycle Queue)的队空(Empty Queue)、队满(Full Queue)判断条件；
⑵循环队列上的插入、删除操作
5、教学时间分配及进度安排
2×2=4学时
第6章 递归(Recursion
)
1、教学内容
⑴递归的定义；
⑵递归的工作原理；
⑶设计递归算法的思路；
⑷几种递归算法的典型例子
2、教学目的及要求
⑴理解递归的定义及工作原理；
⑵掌握设计递归算法的思路
3、教学重点
⑴递归的定义及工作原理；
⑵设计递归算法的基本思路；
⑶几种递归算法的典型例子
4、教学难点
⑴递归的工作原理；
⑵设计递归算法的基本思路
5、教学时间分配及进度安排
2×1=2学时
第7章 树 (Trees)
1、教学内容
⑴树的基本概念；
⑵二叉树；
⑶二叉树的遍历；
⑷表达式树(Expression Trees)；
⑸Huffman编码(Huffman code)
2、教学目的及要求
⑴理解树的定义及基本概念；
⑵深刻理解二叉树的定义、性质及其存储方法；
⑶熟练掌握二叉树的二叉链表(Binary Linked List)存储方式、结点结构和类型定义；
⑷理解并掌握二叉树的三种遍历算法；
⑸了解表达式的二叉树表示方法；
⑹掌握huffman编码的原理及实现方法
3、教学重点
⑴二叉树的定义、逻辑特点；
⑵二叉树的基本形态及性质；
⑶在二叉树上定义的基本运算；
⑷二叉树的链式存储结构及其类型说明；
*⑸二叉树的顺序存储结构及其类型说明；
⑹二叉树链式存储结构的组织方式；
⑺二叉树的三种遍历方法及其算法；
⑻一般树转化为二叉树的方法；
⑼Huffman树及Huffman编码
4、教学难点
⑴二叉树的递归定义；
⑵二叉树链式存储结构的组织方式；
⑶三种遍历的主要区别；
⑷哈夫曼编码
5、教学时间分配及进度安排
2×3=6学时
第8章 查找树(Search trees)
1、教学内容
⑴二叉查找树(Binary Search trees) 或二叉排序树(Binary Sort trees)的定义；
⑵二叉查找树的查找算法；
⑶二叉平衡树(AVL Trees)的定义；
*⑷二叉平衡树的操作及平衡调整
2、教学目的及要求
⑴理解并掌握二叉排序树的定义；
⑵掌握二叉排序树的基本操作
⑶理解二叉平衡树的定义；
*⑷了解二叉平衡树的操作及平衡调整
3、教学重点
⑴二叉排序树的定义、性质及各结点间的键值关系；
⑵二叉排序树的查找算法和基本思想；
⑶二叉平衡树的概念
4、教学难点
⑴二叉排序树上的插入和删除算法；
*⑵平衡二叉树的旋转平衡算法
5、教学时间分配及进度安排
2×2=4学时
*第9章 多路树(Multi-way trees)
1、教学内容
⑴多路查找树(m-way search trees)；
⑵B-
树(B-tree)；
⑶B*与B+树
2、教学目的及要求
⑴理解多路查找树的定义及基本概念；
⑵了解B-树的插入结点、删除结点、遍历树和查找等基本操作
⑶了解B*与B+树
3、教学重点
⑴多路查找树的定义及基本概念；
⑵B-树的插入结点、删除结点、遍历树和查找等基本操作
4、教学难点
⑴B-树的插入结点、删除结点、遍历树和查找等基本操作
5、教学时间分配及进度安排
2×2=4学时
第10章 排序(Sort)
1、教学内容
⑴排序的基本概念；
⑵插入排序(Insertion Sort)；
⑶选择排序(Selection Sort)；
⑷交换排序(Exchange sort)；
*⑸外部排序(External Sort)
2、教学目的及要求
⑴领会排序的基本思想和基本概念；
⑵理解并掌握插入排序、选择排序、交换排序的基本思想、步骤、算法及效率分析；
*⑶了解外排序的定义和基本方法
3、教学重点
⑴排序基本概念及内排序(Internal Sort)和外排序(External Sort)、稳定排序(Stable Sort)和非稳定排序(Unstable Sort)的区别；
⑵直接插入排序(Straight insertion sort )的基本思想、基本步骤和算法；
⑶Shell排序(Shell sort) 的基本思想、基本步骤和算法；
⑷直接选择排序(Straight selection sort )的基本思想、基本步骤和算法；
⑸冒泡排序(Bubble sort) 的基本思想、基本步骤和算法；
⑹快速排序(Quick sort) 的基本思想、基本步骤和算法；
*⑺堆排序(Heap sort ) 的基本思想、基本步骤和算法
4、教学难点
⑴快速排序算法；
*⑵堆排序方法
5、教学时间分配及进度安排
2×3=6学时
*第11章 图(Graphs)
1、教学内容
⑴图的基本概念；
⑵图的存储表示；
⑶图的遍历；
⑷图的连通性(connectedness)；
⑸最小生成树(Minimum Spanning Tree)；最短路径(Shortest Path)；
⑺有向(Directed )无环图及其应用
2、教学目的及要求
⑴理解图的基本概念及术语；
⑵掌握图的两种存储结构(邻接矩阵Adjacency Matrix和邻接表Adjacency List )的表示方法；
⑶熟练掌握图的两种遍历(Traverse graph)--深度优先搜索遍历(Depth-first Traversal)和广度优先搜索遍历(Breadth-first Traversal)--算法、思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；
⑷理解最小生成树(Minimum Spanning Tree)的概念，能按Prim算法构造最小生成树；
⑸领会并掌握拓扑排序(Topology sort)、关键路径(Critical Path)、最短路径(Shortest Path)的算法思想
3、教学重点
⑴理解图的定义、术语及其含义；
⑵掌握各种图的邻接矩阵表示法
及其类型说明；
⑶理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；
⑷领会生成树和最小生成树的概念；
⑸掌握由Prim算法思想构造最小生成树按Prim算法思想；
⑹领会拓扑序列和拓扑排序的概念；
⑺理解并掌握拓扑排序的算法思想；理解并掌握关键路径的算法思想；理解并掌握最短路径的算法思想
4、教学难点
⑴正确理解与区别图的常用术语；
⑵区别图的两种存储结构的不同点及其应用场合；
⑶关键路径的算法思想；
⑷最短路径的算法思想
5、教学时间分配及进度安排
2×3=6学时
四、教学参考书
1．严蔚敏,吴伟民：《数据结构》（C语言版），清华大学出版社.2002,9
2．Sartaj Sahni. Data Structure, Algorithms, and Application in C++. The McGraw-Hill Company Inc.1998(数据结构、算法与应用--C++语言描述.，机械工业出版社.1999)
3．Willan Ford,Willian Topp. Data Structures with C++. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996(数据结构--C++语言描述.北京:清华大学出版社，1997)
4．徐孝凯：《数据结构实用教程（C/C++描述）》，:清华大学出版社.1999,12
5．陈慧南：《数据结构（使用C++语言描述）》，东南大学出版社.2001,1
6．殷人昆,陶永雷,谢若阳等：《数据结构（用面向对象方法与C++描述）》，清华大学出版社.1999,7
西南财经大学天府学院教学大纲 TIANFU COLLEGE OF SWUFE
1
贫而无谄，富而无骄
—— 子贡