“数据结构”课程总结
计算机科学与技术专业从1994年开始为我校专科生开设“数据结构”课程，20##年开始为本科生开设这门课程。由于本门课程的教学从教材、讲授、实验指导都体现了先进的教育理念，该课程的教学体系科学、完整，教学手段与方法先进，课程特色鲜明，20##年被评为赤峰学院本科层次精品课。几年来，数据结构课题组成员从以下几个方面对本门课程进行了建设和改革。
一、课程建设指导思想、定位和特色
1．学科地位
“数据结构”是计算机科学与技术专业的一门学科基础课，是本专业和相关专业必修课。本课程的教学目标是培养学生通过理解、分析和研究计算机处理的数据对象的特性，从而选择适当的数据结构、存储结构和相应的算法，并熟练掌握算法的时间分析和空间分析技巧。“数据结构”还是计算机科学与技术专业部分专业课的先导课，如“数据库原理与应用”、“计算机操作系统”、“计算机编译原理”和“面向对象的程序设计”等。所以本课程的教学效果将直接影响到学生对其它后续专业课的学习，因此，该课程在专业建设的地位十分重要。
“数据结构”是一门应用性很强的课程，本课程要求学生在掌握各种数据结构，特别是存储结构和有关算法的基础上，通过大量的上机实例把难以理解的、抽象的概念转化为计算机能够正确运行的程序，从而提高学生运用所学知识解决实际问题的能力。
2．课程特色
根据课程建设的规划和我系实际，我们针对《数据结构》课程教学开展讨论，并就实验、图书资料等方面进行建设。在不断的教学实践中，我们按照精品课建设要求，积极探索，积累了丰富的教学经验。
采用国内经典教材，结合前沿的研究领域和最新科研动态，丰富教学内容，让学生了解数据结构的实际应用价值。
采用课堂教学与大作业相结合，上机实践为补充的教学模式，培养学生的创业创新素质和团队协作精神。
二、教师队伍建设
1．良好的学缘结构
任课教师的业务水平和教学水平是影响课程建设质量的重要因素。为此，我们不断加强师资队伍建设，特别注重青年教师和实验指导教师的培养。在担任该课程教学任务的5名教师中，教授1名、副教授2名、讲师2名，学历结构为硕士4人、学士1人，45岁以下3人，35岁以下2人。本教师梯队学历层次较高，职称、年龄结构合理，便于本门课程的建设和发展。
2．加强学术交流，不断提高团队整体教学和科研水平
在教学过程中，我们采取了互相听课，举行公开课、观摩课等方式，经常交流教书育人和教学改革方面的经验，不断提高任课教师的教学水平和学术水平。
以范体贵教授为学科带头人的教学研究梯队，具有丰富的教学经验和高昂的教学热情，同时具备较高的教学研究和科学研究水平。教学梯队成员在搞好教学的同时，积极申报承担各级各类教学研究和科学研究课题，并参加国内外相关学科的科研、教学等方面的学术交流活动。选派范体贵、门爱华两位老师参加全国计算机年会和全国数据库学术会议，与国内其他高校著名学者进行了教学、科研等方面的交流，学到许多宝贵的经验和方法。
注重与其他高校的合作和交流，学习其他院校好的教学经验和方法。选派主讲教师门爱华老师到清华大学计算机系做访问学者，访学期间门老师听取了本课程的讲授，经常与讲授本门课程的资深教授严蔚敏老师、殷仁昆老师进行交流、学习。二位老师都给予了具体的指导和建议，为我校本门课程的改革和发展提供了有利的帮助。请国内著名高校学者来我系讲学传授经验，在教学、科研等方面给予具体的指导。20##年10月清华大学著名数据库专家冯建华教授来我系讲学，课题组成员与 冯教授进行了深入的交流，在教学和科研方面都有很大的收获。
3．开展科学研究，积极申请科研立项
数据结构课题小组成员积极进行相关领域的科学研究，几年来发表相关论文30余篇，承担自治区级科研项目四个，赤峰市科技局科研项目一个，院级项目一个，其中3个项目已经完成并通过验收。目前在研的一个科研项目是与清华大学合作申请的计算机前沿领域研究课题，相信通过该项目的研究和合作，对我系的科研工作会起到极大的促进作用，同时能够使我系科研水平上一个新的台阶。课题组成员经过几年的努力，在各方面都取得了一些成绩。范体贵、门爱华、张国祥、王玉红四位教师分别获得“赤峰学院课堂教学质量优秀奖” ，范体贵、门爱华两位教师多次获得“赤峰学院科研成果优秀奖”的奖励。王玉红老师获得“毕业实习优秀指导教师“称号，门爱华老师20##年、20##年连续获得“毕业论文优秀指导教师”奖励。
建立了良好的人才培养制度，在学校和系里的大力支持下，鼓励现有教师提高学历与引进高学历教师相结合，经过几年的建设，已经形成了一支以中青年为主的学科梯队。积极鼓励中青年教师到国内名校进修或攻读硕士、博士学位， 门爱华、董洁、王玉红分别考取了东北大学和辽宁工程技术大学的硕士研究生，已圆满完成学业并获得硕士学位。
三、教学内容、教材建设
1．理论环节教学内容及学时分配
“数据结构”是计算机科学课程体系中核心课程之首，作为学科的专业基础课，具有承上启下的重要作用。对应于学科中问题求解的理论、抽象和设计的方法论，本课程内容体系结构分为概念表述、构建数据模型、设计算法三个层面，突出数据组织方法与处理技术，贯穿程序设计和软件工程新思想和新观点。理论学时设置为72学时。
2. 实践环节教学内容及学时分配
上机实践和课程设计重在培养学生软件设计的综合能力。在基本的课程实习基础上,自20##年起开设了数据结构课程设计，使课程的实践环节总学时数增加到60学时。提出了课程设计的规范要求，突出关键技术要点，贯穿基本技能训练主线，加强实践能力培养。
通过课程设计的训练，突出构造性思维训练的特征，提高了学生组织数据与进行编写大型程序能力，使学生更好地理解和掌握了算法设计所需的技术，为专业学习打下良好的基础。课程设计题目（动态更新、完善）：航空客运订票系统；电梯模拟；简单行编辑程序；工资管理系统；医院排队看病活动的模拟；学籍管理系统；图书管理系统等。
3．教材建设
教材建设是课程建设的重要环节。为此，根据教学大纲和本课程的发展需要，在本课程教材的选用上注重教材的先进性和科学性，我们选用了清华大学出版社严蔚敏教授等编写的《数据结构》（C语言版）作为教材，本书内容丰富、体系结构严谨、概念清晰、易学易懂，也是多所院校指定的考研参考教材，完全适合我系计算机科学与技术、信息与计算科学专业学生的需要。任课教师则多方面参考相关教材，选择部分编写精彩的内容充实到教案中。任课教师们广泛阅读相关文献，了解该领域前沿知识，并且在授课过程中介绍给学生，以开阔学生的视野，拓宽学生的知识面。同时，根据教材内容和实际教学要求，编写了《数据结构上机指导与习题就解答》，并正式出版了《数据结构实验教程》一书，该书作为自治区教育厅统编教材已在各高校广泛使用。
四、教学方法和教学手段
1．教学方法
在教学方法上，讲课、讨论和专题讲座等多种形式并用，以科学、生动灵活的讲授方式传授知识，培养学生的创造思维。教师在认真组织课堂讲授，注意各环节正常运行的同时，还针对不同的教学内容采取不同的方法进行讲解，做到课程内容既条理清晰、深入浅出，又重点突出、特色鲜明。教学内容灵活，既有必讲的内容，也有针对不同专业需要和特点选讲的内容。
通过布置适量的课后习题，使学生能够进一步巩固和提高对课上所学知识的领悟和应用能力。我们在选择习题时，一方面注重三基（基本理论，基本方法，基本技能）知识的掌握，另一方面也充分考虑知识的灵活应用，使学生能多角度、多方法地解决问题，既锻炼他们的系统性思维，又提高分析解决问题的能力。每两周安排一次习题课，由指导教师集中解决同学课上课下遇到的问题。
上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成必不可少的一个教学环节，也是对课堂教学效果的一种检验。通常，实习题中的问题比平时的习题复杂得多，也更接近实际。实习题注重原理与应用的结合，目的让学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能。同时，通过实践能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的作用。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，可以多人合作，有利于一整套软件工程规范的训练和科学作风的培养。此外，实践环节中有很重要的一点，就是机器是比任何教师都严格的主考官。
2．教学手段
为了适应现代化教学的需求，我们在传统教学的基础上，充分利用现代科学技术，广泛应用多媒体教学课件和教学软件。将授课内容制作成了图文并茂的多媒体课件，利用多媒体技术对数据结构辅之以形象的动画，动态演示抽象的复杂数据结构的变化，用板书补充某些推导过程并完成和学生互动的内容，改变了以前课堂教学单调的弊病，激发了学生的学习兴趣。使用多媒体技术还可以直接在课堂上演示算法的实现过程，让学生熟悉算法实现的环境和方法，增强了该门课的实践性，提高了课堂授课效率和教学质量，取得了满意的教学效果。教师们为了更好地适应社会的发展和改革的需要，本着强化算法的思想，在现有数据结构内容的基础上，补充了新的算法，拓宽了学生的知识面。
五、课程建设取得的成果
1．教学科研论文
1）The Boundary Element Analysis for The Thermal Conduction of The Thermal Equipment。 Proceedings of International Conference on Computational Physics, Rinton Press, US, (2005) 199-202（SCI）
2）基于访问控制列表的路由器防火墙在网络安全中的应用研究。计算机与网络 24,(2004) 52-53 (核刊)
3）信息系统在企业现代化管理中的应用。 《商场现代化（学术版）》，2005.2
25-26(核刊)
4）可信网络基本概念与基本属性研究。《赤峰学院学报 》2007.5
5）基于包过滤技术路由器防火墙在网络安全中的研究。《计算机应用研究》,2007,vol23
6）Research on The Architecture of Tru-Network。2008 International Symposium on Information science and Engineering
7）路由器防火墙对冲击波、震荡波病毒的过滤研究。《赤峰学院学报》 2005.1
67-68
8）菲涅耳圆孔衍射的数值模拟。《赤峰学院学报》 2006.1
9）复杂轴承流体动力学特性的边界元分析。《润滑与密封》 2006.3 (核刊 EI核心刊源)
10）三叶轴承流体动力学特性的边界元分析。《润滑与密封》 2006.5 (核刊 EI核心刊源)
11）164-182Hf核的低能谱和电磁跃迁的相互作用玻色子模型。《高能物理与核物理》 28(12),(2004)119-122 (核刊, SCI收录)
12）基于访问控制列表的路由器防火墙在网络安全中的应用研究。《计算机与网络》 2004.24
13）赤峰学院校园网路由器、交换机的选型及远程登录。《赤峰教育学院学报》2004.5 81-82
14）《XML数据库存储策略综述》 《计算机科学》 20##年9月（核刊）
15）《XML数据库结构连接算法之研究》《计算机科学》 20##年6月（核刊）
16）《XML中XPath包含关系判定算法》《内蒙古大学学报》20##年10月（核刊）
17）《基于关系数据库的XML数据的存储研究》《赤峰学院学报》 20##年 3 月
18）《XML数据库模式匹配算法研究》 《赤峰学院学报》 20##年 5月
19）《Internet蠕虫的分析与研究》 《赤峰学院学报》 20##年 4月
20）《如何防止外部网络的攻击》 《赤峰学院学报》 20##年2月
21）《射频IC卡消费系统的设计与实现》 《赤峰学院学报》 20##年10月
22）《XPath片断的分析与研究》 《赤峰学院学报》 20##年1月
23）《一种基于层次结构的XML编码技术》 中国教育信息化》 20##年4月（核刊）
24）《VC++实现图形、数据库应用系统的思路》赤峰教育学院学报 20##年第2月
25）《基于IP组播的多媒体会议系统的设计》 赤峰教育学院学报 20##年6月
26）论文《个性化WINDOWS系统“开始”菜单》赤峰教育学院学报 20##年4月
27）浅谈DEBUG程序的主要命令用法 赤峰学院学报 20##年5月
28）powerpoint技巧在课件制作中的妙用 赤峰学院学报 20##年1月
29）浅谈用MASM运行汇编程序 赤峰学院学报 20##年 1月
30）XML数字签名浅析 赤峰学院学报 20##年 5月
31）《网络层的静态路由选择综述》 赤峰学院学报 20##年3月
32）《离散数学在计算机教学中的作业》 赤峰学院学报 20##年1月
33）《基于模拟退火算法的油井工矿数据挖掘的应用研究》
赤峰学院学报20##年1月
2. 教研课题
1）赤峰学院校园网项目 赤峰学院 20##年-20##年 （已验收）
2）基于IP网QOS动态控制研究 内蒙教育厅 20##年-20##年（已结题）
3）基于结构索引XML模式匹配方法研究 内蒙教育厅 20##年—20##年（已结题）
4）XML数据库研究 赤峰学院 20##年—20##年（已结题）
5）CAI系统中知识个性化组织与导航研究 内蒙教育厅 20##年-20##年（已结题）
6）XML安全数据发布关键问题研究 内蒙教育厅 20##年—20##年（在研）
3. 教学获奖
1）范体贵、门爱华、张国祥、王玉红分别获赤峰学院20##、20##年、20##年、20##年“课堂教学质量优秀奖”；
2）门爱华20##年、20##年连续获的“毕业论文优秀指导教师”奖励；
3）王玉红20##年获院级“毕业实习优秀实习指导教师”奖励；
4）20##年《数据结构课程教学和实践》课题”获赤峰学院“优秀教学成果二等奖”。
数据结构课程组
20##年5月14日
第二篇：数据结构——课程总结new
课程总结(提要)
一、 数据结构和抽象数据类型ADT
定义：一个数学模型以及定义在该模型上的一组操作。
构成一个抽象数据类型的三个要素是：
数据对象、数据关系、基本操作
数据结构(非数值计算程序设计问题中的数学模型)
·逻辑结构（描述数据元素之间的关系）
线性结构—— 线性表、栈、队列、串、数组、广义表
非线性结构 —— 树和森林、二叉树、图
集合结构 —— 查找表、文件
·存储结构
（逻辑结构在存储器中的映象）
按“关系”的表示方法不同而分：
顺序结构—以数据元素在存储器中的一个固定的相对位置来表示“关系”
链式结构—以指针表示数据元素的“后继”或“前驱”
·基本操作(三类)
结构的建立和销毁
查找——引用型操作（不改变元素间的关系）
按“关系”进行检索
按给定值进行检索
遍历——访问结构中的每一个数据元素，且对每个元素只访问一次
修改 —— 加工型操作（改变元素间的关系）
插入
删除
更新（删除+插入）
二、线性结构
·线性表和有序表
—— 不同存储结构的比较
顺序表：可以实现随机存取；O(1)
插入和删除时需要移动元素；O(n)
需要预分配存储空间;
适用于“不常进行修改操作、表中元素相对稳定”的场合。
链表：只能进行顺序存取；O(n)
插入和删除时只需修改指针; O(1)
不需要预分配存储空间;
适用于“修改操作频繁、事先无法估计最大表长”的场合。
—— 应用问题的算法时间复杂度的比较
例如，以线性表表示集合进行运算的时间复杂度为O(n2),
而以有序表表示集合进行运算的时间复杂度为O(n)
·栈和队列——数据类型的特点及其应用范畴
·串——和线性表的差异：
数据对象不同（数据元素限定为单个字符）、基本操作集不同（串整体作为操作对象）、存储结构不同
¾¾ 串的模式匹配算法
·数组——只有引用型的操作，∴只需要顺序存储结构
多维到一维的不同映象方法：
以行序为主序（低下标优先）
以列序为主序（高下标优先）
三、非线性结构
¾¾ 树和森林、二叉树、图
· 数据类型的定义(结构特点和基本操作)
· 存储结构
· 二叉树的特性及其证明方法
· 遍历
·何谓“遍历”？对结构中的每个元素都访问到，且只被访问一次
·对非线性结构的遍历需要确定一条搜索路径
·两条搜索路径:深度优先搜索和广度优先搜索
·逻辑定义
深度优先搜索—— 以结构中的某个数据元素为起始点，首先访问该数据元素，然后依次以它的各个“后继”为起始点进行“深度优先搜索遍历”。
其特点为：在访问了起始数据元素之后，沿着某一条“路径”(后继)向前，直至“到底”，然后退回一步找另一个后继，再向前继续，……，直至所有通路都走遍。
广度优先搜索——以结构中的某个数据元素为起始点，首先访问该数据元素，然后先访问其所有后继；之后其它结点的访问次序由已被访问的结点的访问次序决定：先被访问的结点的后继“优先于”后被访问的结点的后继。
其特点为：在访问了起始数据元素之后，先访问它的所有后继，然后再依这些后继被访问的先后次序访问它们的后继，……，直至没有后继未被访问为止。
·算法的形式描述
深度优先搜索——通常采用递归的形式
二叉树（先序、中序、后序）、树/图（先根、后根）
一般形式算法的描述:
void DFSearch(ADT DS, ElemType v)
{ // 从v开始，对DS进行深度优先搜索遍历
if (DS) {
visit(v); (visited[v]=true;)
w=FirstSucc(v);
while (w) {
if (!visited[v]) DFSearch(DS, w);
w=NextSucc(DS, v, w);
}//while
}//if
}//DFSearch
不同数据结构(逻辑和存储)有不同写法。
例如对森林，起始点只有一个(第一棵树的根)，只有两个后继，且各棵树互不相交，按搜索路径上的访问次序有先序遍历和中序遍历之分。
void PreOrder_F(CSTree T) {
// 对以T为根指针的森林进行先序遍历
if (T) {
visit(T->data);
PreOrder_F( T->firstchild ); // 先序遍历第一棵树的子树森林
PreOrder_F( T->nextsibling ); // 先序遍历其余树构成的森林
}//if
} // PreOrder_F
或者从森林是树的集合角度来看遍历(依次从左至右依次先根遍历各棵子树) while(树) do PreOrder_T(树);
void PreOrder_T(CSTree T) {
// 对以T为根指针的树进行先根遍历
if (T) {
visit(T->data); p=T->firstchild;
while(p) {
PreOrder_T(p);
// 对以 p 为根指针的子树进行先根遍历
p=p->next;
}//while
} // PreOrder_T
·由“访问”操作的不同可以实现不同的操作
具体问题具体分析，按分割求解的思想:
“递归基”考虑最简单的结构（“空集”/“只含一个元素”）
“归纳项”分析原问题和子问题之间的关系
·不同的问题要求不同的搜索路径
·“线索化”的过程即为在遍历过程中建立结点之间的线性关系
广度优先搜索——不能用递归（先进先出）
必须利用“队列”记下访问次序，以便由此确定以后的元素的访问次序
·对不同的存储结构，算法的差异
不同的存储结构表现在表示“后继”的方法不同
二叉树 —— 二叉链表（静态、动态）、顺序表(只适用于完全二叉树)
树 —— 孩子-兄弟链表、孩子链表(≡≡图的邻接表)、双亲链表
图 —— 邻接表、邻接矩阵
具体算法采用何种存储结构由算法需要解决的问题而定
四、查找表—— 集合结构
·根据查找表所需进行的操作种类和期望达到的ASL来选择构造查找表的方法
顺序表、有序表(静态查找树)、索引顺序表 —— 静态查找表
二叉排序树、B-树和B+树、键树 —— 查找树
哈希表 —— 动态查找表也可用于表示静态查找表
各自的特点、操作的实现方法，注意 它们之间的相同点和不同点
例如：顺序表的特点是：结构简单，便于插入但不便于删除；平均查找长度较大ASL=O(n)，查找树？哈希表？
—— 平均查找长度的计算公式对任何查找表都适用
一般情况下只考虑查找成功的平均查找长度，即
，关键在于如何计算Ci
·判定树和ASL的计算方法
——判定树用于描述查找方法，关键字在判定树上的层次恰为找到它时和给定值进行比较的次数。注意判定树的画法取决于查找方法的本身而不是具体的算法。
判定树非程序流图
·哈希表的特点
是在关键字和记录的存储地址之间建立了一个映象关系，以此减少查找的盲目性，哈希表的最大特点是它的平均查找长度不是表长的函数，因此利用它可以设计出使平均查找长度控制在期望值范围内的查找表。
——如何构造哈希表以及如何计算它的Ci。
——在特殊的情况下，可以做到ASL=0
—— 无法画出它的判定树
—— 掌握各种构造哈希表的方法以及处理冲突的方法
五、内部排序
·进行排序的目的：得到有序表
排序和查找相互关联，有时排序的过程也可以看成是一个动态造表的过程，如：插入排序；二叉查找树
·了解各种排序方法的特点以便灵活应用
例如：直接插入排序适用于“近似有序序列”；
快排的思想可用以“调整”；
选择排序、起泡排序和堆排序可用以“选出若干满足条件元素”；
各种排序方法的混合使用
·排序算法的描述
例如：一次划分、建堆
算法和存储结构的关系
·排序算法的时间复杂度及其简单分析方法
·各种排序方法的综合比较
时间性能——平均情况、最坏情况、最好情况
(从关键字的比较和记录的移动两个方面进行分析)
空间性能——需要的辅助空间
八、图
¾¾各种存储结构的定义、各个应用问题算法的执行过程
九、算法时间复杂度的分析
掌握系统分析的方法。