天津大学《算法与数据结构》课程教学大纲
课程代码：2160109 课程名称：数据结构
学时：64 学分： 3.5
学时分配：授课：40上机：24实验：实践：实践（周）：
授课学院：计算机科学与技术学院
适用专业：计算机科学与技术、软件工程
先修课程：离散数学、C语言程序设计、C++高级语言程序设计
一．课程的性质与目的
《数据结构》课程是计算机科学与技术专业以及软件工程专业的专业基础课程，通过学习这门课,使学生掌握各种基本数据结构及基于数据结构的基本运算和算法,能应用高级语言编写算法,为今后实际工程中软件算法的研究奠定基础。
二．教学基本要求
本课程介绍常用的数据表示和处理技术，包括顺序存储和链接存储的线性表；栈与队列的概念、存储结构、基本运算与应用、递归算法与实现；串的几种存储表示方法；广义表的定义及存储结构；二叉树的定义、性质及存储结构、遍历二叉树与线索二叉树、查找树、平衡树、树、森林与二叉数的转换、哈夫曼树与哈夫曼编码；图的存储结构、图的遍历、最小生成树、拓扑排序、关键路径、最短路径；静态表查找与动态表查找、哈希表的构造及处理冲突；内部排序的方法如插入排序、快速排序、选择排序、归并排序等、几种内排序的比较。
三．教学内容
(一)授课内容
第一章算法分析
1. 数据结构的基本概念和术语
2. 算法分析的基本概念
第二章线性表
1. 线性表
2. 顺序表（表示及其存储结构）
3. 链表（表示及其存储结构）
4. 线性表的应用
第三章栈和队列
1. 栈的存储表示和基本运算
2. 栈的应用
3. 链队列
4. 循环队列
5. 队列的应用
6. 特殊矩阵的压缩存储
第四章递归
1．递归概念
2．递归过程
3．递归算法
4．递归实现
第五章树和二叉树
1. 树、二叉树的概念及性质
2. 二叉树的顺序存储结构及链式存储结构
3. 遍历二叉树
4. 二叉树的应用
5. 线索二叉树
6. 树的存储结构
7. 树和森林与二叉树的转换
8. 树和森林的遍历
9. 哈夫曼树及其应用
第六章图
1. 图的定义和术语
2. 图的存储结构
3. 图的遍历
4. 最小生成树
5. 拓扑排序
6. 关键路径
7. 最短路径
第七章查找
1. 静态查找表
2. 动态查找表
3. 二叉排序树
4. 平衡二叉树
5. 哈希表
6. B+树、B-树及其基本操作
7. 查找算法的分析及应用
第八章排序
1. 插入排序
2. 冒泡排序
3. 快速排序
4. 选择排序
5. 堆排序
6. 归并排序
7. 基数排序
8. 内排序方法比较
9. 内部排序算法的应用
第九章字符串
1. 串的存储结构
2. 串的基本运算
(二)实验（或上机）内容
1、链表实验：用有序单链表表示集合，实现集合的交、并和差运算
实验要求：
对集合中的元素，用带头结点单链表进行存储。
●实现交、并、差运算时，不另外申请存储空间。
●充分利用单链表的有序性，算法有较好的性能。
●设计驱动程序（主程序）检验算法正确性并输出结果。
2、栈实验：用栈实现括号匹配的检验
实用要求：
●设计栈，存储括号。
●利用进栈、出栈操作实现括号匹配算法。
●不另外申请存储空间，算法有较好的性能。
●设计驱动程序、测试用例，并得出正确结果。
3、二叉树实验：在采用链式存储结构存储的二叉树上，以root指向根接点，p指向任一给定的接点，编程实现求出从根接点到给定接点之间的路径。
实验要求：
●采用二叉链表作存储结构。
●创建二叉树，并实例化有若干结点的二叉树。
●实现二叉树非递归后序遍历算法，并输出所需路径，算法要有较好的性能。
●设计驱动程序、测试用例，并得出正确结果。
4、排序实验：设计一个程序进行学生成绩管理。假设对某个班级的学生的5门课程的学习成绩进行管理。要求：1）、求每门课程的平均成绩。2）、输出每门课程成绩优秀的学生名单及成绩。3）、输出只要有1门课程不及格的学生名单及其每门成绩。4）、对5门课中可以指定某一门进行排序。
实验要求：
●设计学生顶点，至少包括id，name，成绩数组，平均分等域
●排序方法可以任选一种，注意算法的完整性和通用性。
●实现试验要求的所有算法，并使之性能较好。
●设计驱动程序，尽可能多的测试用例，按不同的单门课程成绩排序，观察输出结果。
5、图实验：建筑工程拓扑排序问题，建造一座办公楼，需要进行选择设计单位、楼房总体设计等活动。选择地点需要在建造地基之前完成，打地基必须在
建造楼房、楼房封顶和内部装修之前完成。
实验要求：
●设计邻接表作为存储结构，可用队列或者栈作为拓扑排序辅助存储结构。
●设计创建图算法，拓扑排序算法，算法要有较好的性能。
●创建存储上图中建造工程AOV网信息，并实现该图的拓扑排序，设计驱动程序、其他测试用例，并得出正确结果。
四．学时分配
教学内容授课上机实验实践实践(周)
第一章算法分析 2
第二章线性表 4 4
第三章栈和队列 4 4
第四章递归 4
第五章树和二叉树 6 4
第六章图 6 8
第七章查找 6
第八章排序 6 4
第九章字符串 2
总计：40 24
五．评价与考核方式
课后作业：10 %
实验作业：20 %
课堂测验：10 %
实验课练习及出勤：10 %
期末考试： 50 %。
六．教材与主要参考资料
教材:《数据结构》C语言版，严为敏吴伟民编，清华大学出版社，2009.
参考书目：
《Data Structures and Algorithm Analysis in C》 Mark Allen Weiss，陈越译，人民邮电出版社，2003.
《数据结构》(用面向对象方法与C++描述)，殷人昆等，清华大学出版社，2007.
Data Structures And Program Design In C++，Robert L.Kruse，Alexander J.Rybadeng等，Person Education 出版集团2001年5月出版.
《数据结构》题集，严为敏吴伟民编，清华大学出版社，2009.
《数据结构》许桌群等，清华大学出版社，1986.
制定人：
审核人：
批准人：
批准日期：年月日
TJU Syllabus for Algorithm and Data Structure
Code:
2160109 Title: Algorithm and Data Structure Semester Hours:
64
Credits:
3.5
Semester Hour Structure
Lecture ：40 Computer Lab ：24 Experiment ： Practice ： Practice (Week)：
Offered by:
School of Computer
Science and Technology
Date:
2011.12
for: Computer Science and Technology 、Software Engineering Prerequisite: Discrete Mathematics 、C language programming 、C + + high-level language programming
1. Objective
This course introduces common data representation and processing technologies, including sequence storage and linked storage of the linear list; the concept and storage structures and basic operations and applications of stack and queue, and implementation of recursive algorithms; several storage representation of string; definition and storage structures of generalized list; definition and nature and storage structure of binary tree, binary tree traversal and threaded binary tree, search tree, balanced binary tree, conversion between trees and forests and binary tree, Huffman tree with Huffman coding; storage structure of graph, graph traversal, minimum spanning tree, topological sort, the critical path, the shortest path; static and dynamic lookup table, structure and conflict of hash table; internal sorting methods such as insertion sort , quick sort, selection sort, merge sort, etc., comparison within a few sort.
2. Course Description
"Algorithm and Data Structures" is a major foundation course in computer science and technology and software engineering major. This course can enable
students to master a variety of basic data structures and basic operations and algorithms on data structures, and high-level language algorithms can be applied for the study of software algorithms in future practical engineering.
3. Topics
(A) Lecture
Chapter1 Algorithm analysis
1) The basic concepts and terminology of data structure
2) The basic concepts of algorithm analysis
Chapter2 Linear list
1) Linear list
2) Sequence list (representation and storage structure)
3) Linked list (representation and storage structure)
4) The application of the linear list
Chapter3 Stacks and queues
1) Storage representation and basic operations of stack
2) Applications of stacks
3) Linked queue
4) Circular queues
5) Queue applications
6) Compression storage of special matrix
Chapter4 Recursive
1) The concept of recursion
2) Recursive process
3) Recursive algorithm
4) Recursive Realization
Chapter5 Tree and binary tree
1) The concept and nature of tree and binary tree
2) Sequence and linked structure of binary
3) Traversal binary tree
4) Binary tree application
5) Threaded binary tree
6) Storage structure of tree
7) Conversion trees and forests to binary tree
8) Traversal of trees and forests
9) Huffman tree and its application
Chapter6 Graph
1) Definitions and terminology of graph
2) Storage structure of graph
3) Graph traversal
4) Minimum Spanning Tree
5) Topological sort
6) Critical Path
7) Shortest path
Chapter7 Finding
1) Static lookup table
2) Dynamic look-up table
3) Binary sorted tree
4) Balanced binary tree
5) Hash table
6) B + tree and B-tree and their basic operation
7) Analysis and application of search algorithm Chapter 8 Sorting
1) Insertion Sort
2) Bubble Sort
3) Quicksort
4) Select Sort
5) Heapsort
6) Mergesort
7) Radix Sort
8) Comparison of sorting methods
9) The application of the internal sorting algorithm
Chapter9 String
1) Storage structure of string
2）Basic operations of strings
(B) Experiments
1) Linked list experiment: An ordered one-way linked list represents set to achieve set intersection and difference operations.
Experimental requirements:
●Store set elements in one-way linked list with the head node.
●Achieve intersection, union and trim operation without another storage space.
●Take full advantage of the ordered nature of a one-way linked list, the algorithm has good performance.
●Design driver (main program) to test the correctness of algorithm and output.
2) Stack experiment: achieve matching brackets by stack
Experimental requirements:
●Design stack to store parentheses.
●Use push and pop operation to achieve parenthesis matching algorithm.
●The algorithm has good performance without another storage space.
●Design drivers and test cases, and get the right result.
3) Binary tree experiment: binary tree is stored in the linked structure and root points root node. A program should find the path from the root to a given node.
Experimental requirements:
●Binary list for storage structure.
●Create binary tree with several binary tree nodes.
●Achieve non-recursive post-order binary tree traversal algorithm, and output the desired path. The algorithm has better performance.
●Design drivers and test cases, and reach the right result.
4) Sorting experiment: design a program for student to achieve 5 courses score management. Requirements: (1) calculate the average scores for each course. (2)
output the student name and score with good score for each course. (3) output the student name and all score with a failed course. (4) sort the student according a specified course score.
Experimental requirements:
●design students vertices, including at least id, name, score array, the average grading domains
●Choose one sorting method, note that algorithm integrity and versatility.
●Any of sort algorithms to achieve test requirements, and make it better performance.
●Design driver, as many as test cases, sort by single-course results, observe the output.
5) Graph experiment: topological sorting in construction, to build up an office building, choose design units and the overall design of buildings and other activities should be achieved. Selecting a location needs to be completed before the construction of foundations, foundations must be completed before the construction of buildings and cap the buildings and the interior decoration.
Experimental requirements:
●Adjacency list as the storage structure, queue or stack as secondary storage structures for a topological sort.
●Design to create graph algorithms, topological sort algorithm, and the algorithm has better performance.
●Store above construction’s AOV network information, and to achieve a topological sort of the plan, and to design drive and the other test cases, and reach the right result.
4. Semester Hour Structure
Topics Lecture Computer
Lab.
Experiment Practice
Practice
(Week)
Algorithm analysis 2
Linear list 4 4
Stacks and queues 4 4
Recursive 4
Tree and binary tree 6 4
Graph 6
8
Finding 6
Sorting 6
4
String 2
Sum: 40
24
5. Grading
●Homework：10 %
●Experimental Work：20 %
●Tests：10 %
●Experimental Exercises and Attendance：10 %
●Final examination：50 %。
6. Text-Book & Additional Readings
Text-Book:
●"Data Structure (C-language)", Yan Weimin、Wu Weimin, Tsinghua, University Press, 2009.
Additional Readings
●"Data Structures and Algorithm Analysis in C", Mark Allen Weiss, translated by Chen Yue, Posts & Telecom Press, 2003.
●"Data Structure (Object-Oriented Methods and C++ Descriptions)", Yin Renkun, Tsinghua University Press, 2007.
●"Data Structures and Program Design In C++", Robert L. Kruse, Alexander J. Rybadeng, Person Education Publishing Group, published in May 2001.
●"Data Structure Exercises Sets", Yan Weimin、Wu Weimin, Tsinghua University Press, 2009.
●"Data Structure", Xu Zhuoqun, Tsinghua University Press, 1986.
Constitutor:
Reviewer:
Authorizor:
Date: