您申请加入课程:数据结构与算法(C++描述)
需要验证您的身份,请输入请求信息:
学 号: 
班级选择:
附注信息:
课程
引导

数据结构与算法(C++描述)

华南师范大学

软件工程专业

  • 创建者

    Creator

    潘家辉
  • 活跃度

    Activeness

  • 访问量

    Visits

    39359

课程简介/Introduction

《数据结构与算法》是软件工程专业和计算机专业中一门重要的专业基础课程。数据结构与算法主要讨论在应用计算机解决问题时,如何有效地组织数据;表示数据和处理数据, 以及如何设计正确的算法和评价算法的效率。课程介绍常见的数据结构及其应用,常用的数据处理技术和算法,以及算法效率估算的基本技术。

通过本课程的学习,要求学生掌握常用数据结构,掌握合理地组织数据结构和表示数据的方法,掌握有效地处理数据的方法,掌握评价算法性能的基本方法。通过本课程的训练,进一步提高学生的数据抽象能力;使学生较全面的掌握各种常用的数据结构与算法;提高运用数据结构解决实际问题的能力,进而提高学生设计高质量软件的能力。本课程也为学生学习后续课程《数据库系统原理与实践》、《操作系统》、《多核并行编程》、《软件构造》等后续课程奠定基础。


教学大纲/Syllabus

教学内容

( 72 学时)

知识点

学时分配

绪论:

1. 数据结构的基本概念;

2. 抽象数据类型;

3.算法描述和算法评价。

4学时

线性表:

1.线性表的概念及运算;

2.顺序表及基本运算。

4学时

链表:

1.单链表及基本运算;

2. 循环链表和双链表;

3.顺序存储结构与链式存储结构的比较。

4学时

栈:

1.栈的概念及运算;

2.栈的顺序、链接存储;

3.栈的插入、删除算法及其应用。

4学时

队列:

1. 队列的概念及运算;

2. 队列的顺序、链接存储;

3. 队列的插入、删除算法及其应用。

4学时

串:

1. 串的概念及其运算;

2. 串的存储结构;

3. 串的应用举例。

4学时

多维数组:

1. 数组的定义、基本运算和存储结构 ;

2. 特殊矩阵的压缩存储;。

3. 数组的应用举例。

4学时

树和二叉树:

1. 树的逻辑结构;

2. 树的存储结构;

3. 二叉树的逻辑结构;

4. 二叉树的存储结构;

5. 二叉树遍历。

6学时

树的应用:

1. 二叉树与树和森林的转换;

2. 二叉排序树、哈夫曼树及其应用。

4学时

图:

1.图的逻辑结构;

2.图的存储结构;

3.最小生成树;

4学时

图的应用:

1.最短路径;

2.图的应用举例。

2学时

查找:

1.查找的基本概念;

2.线性表的查找技术。

4学时

树表查找:

1. 二叉排序树定义及查找;

2. 二叉平衡树的定义。

2学时

插入排序:

1.排序的基本概念;

2.插入排序(直接插入排序、折半插入排序、希尔排序)。

3. 交换排序(冒泡排序、快速排序);

4学时

多种排序:

1.选择排序(简单选择排序、堆排序);

2. 归并排序(递归、非递归);

3.各种排序方法比较。

4学时

索引技术:

1. 索引的基本概念;

2. 线性索引技术;

3. 树形索引。

4学时

算法设计:

1. 递归算法;

2. 分治算法;

3. 动态规划算法。

6学时

算法分析:

1. 可计算性问题;

2. 实例研究。

2学时

复习: 课程总结与重点回顾。

4学时

实验内容

( 36 学时)

实验任务

学时分配

实验1:

1) VC++编程工具的使用。

2) 计算任意位数的∏。

2学时

实验2:

1) 顺序表的实现。

2) 单链表的实现。

2学时

实验3:

1) 约瑟夫环问题。

2) 用单链表实现集合的操作。

2学时

实验4:

一元多项式相加。

2学时

实验5:

1) 顺序栈的实现。

2) 链队列的实现。

2学时

实验6:

1) 汉诺塔问题。

2) 表达式求值。

2学时

实验7:

1) 串操作的实现。

2) 对称矩阵的压缩存储。

2学时

实验8:

1) 统计文本中单词的个数。

2) 近似串匹配。

2学时

实验9:

1) 二叉树的实现。

2) 树的实现。

2学时

实验10:

1) 求二叉树中叶子结点的个数。

2) 二叉表示树。

2学时

实验11:

1) 邻接矩阵的实现。

2) 邻接表的实现。

2学时

实验12:

哈密顿路径。

2学时

实验13:

1) 顺序查找的实现。

2) 折半查找的实现。

3) 散列查找的实现。

2学时

实验14:

1) 二叉排序树的查找性能。

2) 个人电话号码查询系统。

2学时

实验15:

1) 插入排序算法的实现。

2) 交换排序算法的实现。

3) 选择排序算法的实现。

2学时

实验16:

1) 直接插入排序基于单链表的实现。

2) 各种排序算法时间性能的比较。

2学时

实验17:

1) 采用分治策略求数组中元素的最大值。

2) N皇后问题。

2学时

实验18:

检查实践项目。

(本课程的实践项目为课外布置内容,让2-3个学生组队,选择其中的1个项目,并于期末检查上交。实践项目的成绩算作实验成绩的20%。)

2学时

实践内容

( 0 学时)

项目内容、项目环境

项目内容:

项目1 压缩软件

理解二叉树和哈夫曼编码,编写程序对已有文件进行重新编码,减少存储空间。使用面向对象的思想编程,利用哈夫曼构建功能分别构建类实现压缩和解压缩功能。

项目环境:

普通PC机(1G内存/奔腾E系列CPU以上)

不限开发语言和开发环境

项目内容:

项目2 华师南海校区导游系统

开发一个简单的华师南海校区导游系统,综合运用几种典型数据结构,如链表,栈,队列,以及图等,并实现最短路径的算法。

项目环境:

普通PC机(1G内存/奔腾E系列CPU以上)

不限开发语言和开发环境



留言板/Message Board

条留言  共

相关课程/Correlative courses

扫一扫二维码,快速加入本课程!

放大二维码 查看使用方法
关闭

© 2017 SCHOLAT 学者网

免责声明 | 关于学者网 | 联系我们