《数据结构与嵌入式软件设计》教学大纲

第页《数据结构与嵌入式软件设计》教学大纲课程编号：10140095英文名称：DataStructureandSoftwareDesignforEmbeddedSystems学分：3学时：总学时56学时，其中理论40学时，实践16学时先修课程：程序与算法设计课程类别：专业基础课程授课对象：电子信息工程专业学生教学单位：数理信息学院修读学期：第3学期一、课程描述和目标本课程是计算机程序设计的重要理论技术基础，是嵌入式软件算法实现的基础，是嵌入式系统开发中必不可少的重要组成部分。本课程从嵌入式系统的实际软硬件环境出发，主要介绍常见数据结构及其基本操作和存储结构，并适当介绍基于常见数据结构的典型应用和常见算法，提高学生程序设计能力，为今后的进一步学习、研究和工作打下扎实基础。本课程拟达到的课程目标:课程目标1：学生能较好地掌握各种常见数据结构及其实现等专业知识；树立实事求是、结构来源于生活的基本意识。课程目标2：学生能在深刻地理解数据结构的逻辑结构和存储结构的基础上，设计实现基于各种数据结构的相关算法和应用等专业能力。课程目标3：学生能综合运用所学数据结构设计解决常见典型问题，培养学生良好的数据抽象能力和嵌入式程序设计技能，具备初步分析问题和抽象建模能力以及嵌入式系统开发的综合能力。二、课程目标对毕业要求的支撑关系毕业要求指标点课程目标权重2.1能够将数学、自然科学和工程科学的基本原理运用到电子信息领域的复杂工程问题的适当表述中。课程目标10.5课程目标20.3课程目标30.22.2能够识别、判断电子信息领域复杂工程问题的关键环节和参数。课程目标10.5课程目标20.52.4.能够运用基本原理，分析过程的影响因素，证明方案的有效性。课程目标20.4课程目标30.6三、教学内容、基本要求与学时分配序号教学内容基本要求学时教学方式对应课程目标1数据结构概述：介绍数据结构含义及其基本概念和术语，逻辑结构及存储结构介绍；讲解算法和算法分析。了解数据结构的发展历史及其在计算机学科中的地位，类Ｃ语言的主要特点；了解常见逻辑结构和存储结构；理解时间复杂度概念和基本的估算方法，并在后面章节的学习中逐步掌握它。2集中讲授课程目标12线性表：介绍线性表的类型定义；讲解线性表的顺序表示和实现，线性表的链式表示和实现，一元多项式的表示及相加，线性表在嵌入式系统中的应用实例。了解线性表的结构特点；了解顺序的和链式的存储结构各自特色；熟练掌握线性表的操作，特别是指针运算和各种链表的操作。8集中讲授+讨论+实练课程目标1、2、33队列和栈：讲解队列及其结构和主要操作，循环队列、链队列概念和操作，队列应用实例；讲解栈及其结构和主要操作，顺序栈、链栈概念和操作，栈应用实例；介绍堆栈、队列在嵌入式系统中的应用实例。理解栈和队列的操作特点及递归程序的执行过程；掌握编写递归程序的基本方法和循环队列的应用。4集中讲授+讨论+实练课程目标1、2、34串：讲解串类型的定义及其结构，串的主要操作，基本模式匹配算法及串在嵌入式系统中的应用实例。掌握串的主要操作及常用模式匹配算法2集中讲授+讨论+实练课程目标1、2、35数组：讲解数组的定义，数组的顺序表示和实现，三元组顺序表压缩存储，数组在嵌入式系统中的应用实例。掌握计算给定元素在存储区中的地址；掌握矩阵的三元组压缩存储方法。4集中讲授+讨论+演示+实练课程目标1、2、36树和二叉树：介绍树的定义和基本术语；讲解二叉树，遍历二叉树，树的应用实例，哈夫曼树，二叉树在嵌入式系统中的应用实例。掌握树和二叉树的基本概念及存储结构；熟练掌握二叉树的性质和操作；掌握树和二叉树的互相转换、哈夫曼树和哈夫曼算法。8集中讲授+讨论+实练课程目标1、2、37图：介绍图的定义和术语；讲解图的存储结构，图的遍历，最小生成树，最短路径，图在嵌入式系统中的应用实例。理解图的概念；掌握图的几种存储结构、基本操作及应用特点，注意邻接点次序的确定；掌握几种典型的应用算法。6集中讲授+讨论+实练课程目标1、2、38排序：介绍排序概述；讲解插入排序、选择排序、快速排序等的算法实现以及排序在嵌入式系统中的应用实例。了解各种典型的内部排序算法的特点和适用范围；熟练掌握各排序算法。4集中讲授+讨论课程目标2、39查找：讲解顺序查找，折半查找，索引查找的算法实现；介绍查找在嵌入式系统中的应用实例。理解查找的基本概念；掌握典型的查找表的构造和查找算法及其应用特点。2集中讲授+讨论课程目标2、310循环链表理解并掌握循环链表概念及操作0自主学习课程目标1、211栈与递归了解栈与递归的联系及实现0自主学习课程目标1、2、312广义表了解广义表的概念及基本结构与操作0自主学习基本目标1、2、3合计40实验部分序号实验项目实验内容与要求学时类型对应课程目标1线性表基本操作实验内容：设计实现顺序存储的线性表插入与删除操作。实验要求：必修2验证课程目标1、22队列和栈的应用实验内容：设计实现通用数制转换程序：将一个十进制数转换成其他进制（二进制、八进制、十六进制）的数。实验要求：必修2验证课程目标1、23串的基本操作实验内容：设计实现计算字符串的长度、字符串的复制、字符串的比较、字符串的连接、字符串的插入等基本操作。实验要求：必修2验证课程目标1、24数组基本操作实验内容：稀疏矩阵的加法--假设稀疏矩阵A和B（具有相同的大小m*n）都采用三元组表示，编写一个函数计算C＝A+B，要求C也采用三元组表示。实验要求：必修2验证课程目标1、25树的遍历及应用实验内容：二叉树的遍历及其应用--采用二叉链表作为二叉树的存储结构，实现如下功能：输入二叉树的特殊先序序列，建立二叉树；实现二叉树的中序遍历；求二叉树的深度；求二叉树中叶子结点的数目。实验要求：必修2综合课程目标1、26图的遍历及应用实验内容：设计实现图的深度优先搜索。实验要求：必修2验证课程目标1、27排序实现实验内容：设计实现直接插入排序、简单选择排序、快速排序和堆排序的算法，并比较这几种算法的时间复杂度。实验要求：必修2验证课程目标1、2、38查找实现实验内容：分别利用顺序表查找法和二分查找的方法对有序顺序表进行查找。实验要求：必修2验证课程目标1、2、3合计16注：实验要求包括必修、选修；实验类型包括演示、验证、综合、设计等。四、课程教学方法以集中讲授为主，结合讨论、演示、实训练习等教学方式为辅的教学方法。五、学业评价和课程考核考核依据建议分值考核/评价细则对应课程目标平时成绩40%出勤0%缺课根据课程课时按比例扣分；若缺课累计超过课程本学期学时数三分之一及以上，取消考试资格。课程目标1阶段测验5%根据阶段测验情况计分课程目标1、2作业7%缺交作业根据课程作业次数按比例扣分；若缺交作业达三分之一及以上，取消考试资格课程目标1、2综合表现8%根据课程学习状态和活动参与情况计分课程目标1、2、3实验成绩20%实验操作60%；实验报告40%课程目标1、2、3期末考核60%根据期末考核成绩按百分制计分课程目标1、2、3六、教材与参考书（一）推荐教材《数据结构（C语言版）第2版》，严蔚敏主编，人民邮电出版社，2017年8月版；《嵌入式系统软件设计中的数据结构》，陆玲主编，北京航空航天大学出版社，2008年8月版。（二）参考资料《数据结构基础（C语言版）第2版》，朱仲涛（译）主编，清华大学出版社，2009年3月版；