数据结构教案(总32页)
-CAL-FENGHAI.-(YICAI)-Company One1
-CAL-本页仅作为文档封面，使用请直接删除
2015 至2016 学年第二学期
数 据 结 构 课程
教
案
课程编码： 1261D03
总学时／周学时： 80 / 5
开课时间： 2016年2 月 24日第 1 周至第 16
周
授课年级、专业、班级： 15级网工程2班
使用教材 严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.
系别/教研室： 信息工程学院 / 物联网工程
授课教师： 刘波 教学目标：
《数据结构》是物联网工程专业的一门专业必修课。用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。
通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。
教学要求:
本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。
学生通过学习该课程后主要应掌握以下内容：
1．了解数据结构及有关的基本概念；
期末复习
第一章 绪论 复习
1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。 基础知识 数据结构
算 法 概 念
逻辑结构
存储结构
数据运算 数据：计算机处理的信息总称
数据项：最小单位
数据元素：最基本单位
数据对象：元素集合
数据结构：相互之间存在一种或多种特定关系的数据元素集合。
概念：数据元素之间的关系
线性结构：一对一
非线性结构
树：一对多
图：多对多
顺序存储结构
链表存储结构
索引。。。
散列。。。
算法描述：指令的有限有序序列
算法特性 有穷性
确定性
可行性
输入
输出
算法分析 时间复杂度
空间复杂度 第二章 线性表 复习
1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针
2、线性表采用顺序存储，必须占用一片连续的存储单元
3、线性表采用链式存储，便于进行插入和删除操作
4、线性表采用顺序存储和链式存储优缺点比较。
5、简单算法
第三章 栈和队列 复习 线性表 顺序存储结构
链表存储结构 概 念 基本特点
基本运算 定义
逻辑关系：前趋 后继
节省空间
随机存取
插、删效率低
插入
删除
单链表
双向
链表 特点 一个指针域+一个数据域
多占空间
查找费时
插、删效率高
无法查找前趋结点
运算
特点：单链表+前趋指针域
运算 插入
删除
循环
链表 特点：单链表的尾结点指针指向附加头结点。
运算：联接
1、 栈和队列的异同点。
2、 栈和队列的基本运算
3、 出栈和出队
4、 基本运算
第四章 串 复习 栈 存储结构 栈的概念：在一端操作的线性表
运算算法 栈的特点：先进后出
LIFO
11
《数据结构》实验指导及报告书
/ 学年 第 学期
姓 名：______________
学 号：______________
班 级：______________
指导教师：______________
数学与统计学院
2011
22
预备实验 C语言的函数数组指针结构体知识
一、实验目的
1、复习C语言中函数、数组、指针、结构体与共用体等的概念。
2、熟悉利用C语言进行程序设计的一般方法。
二、实验预习
说明以下C语言中的概念
1、 函数：
2、 数组：
3、指针：
4、结构体
5、共用体
三、实验内容和要求
1、调试程序：输出100以内所有的素数（用函数实现）。
#include<>
int isprime(int n){ /*判断一个数是否为素数*/
int m;
for(m=2;m*m<=n;m++)
if(n%m==0) return 0;
return 1;
}
33
int main(){ /*输出100以内所有素数*/
int i; printf("\n");
for(i=2;i<100;i++)
if(isprime(i)==1) printf("%4d",i);
return 0;
}
运行结果：
2、 调试程序：对一维数组中的元素进行逆序排列。
#include<>
#define N 10
int main(){
int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp;
printf("\nthe original Array is:\n ");
for(i=0;i
printf("%4d",a[i]);
for(i=0;i
temp=a[i];
a[i]=a[N-i-1];
a[N-i-1]=temp;
数据结构严蔚敏ppt课件
数据结构（严蔚敏）版
●资料上传者：安徽大学研究生
●资料使用范围：各大学考研及本科教学●欢迎报考安徽大学研究生
●“星光考研书屋”祝您学习愉快
[学习目标]
掌握线性表的顺序存储结构和抽象数据类型中定义的每一种操作的含义，在顺序存储方式下
每一种操作的具体实现和相应的时间复杂度；
掌握链接存储的概念，线性表的单、双链接存储结构，对它们进行插入和删除结点的方法
，循环单、双链表和带表头附加结点的单、双
链表的结构和操作特点；
掌握每一种线性表操作在由动态结点构成的单链表上具体实现的算法以及相应的时间复杂度。
2
第2章线性表
线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：
① 存在一个唯一的被称为“第一个”的数据元素；
② 存在一个唯一的被称为“最后一个”的数据元素；
③ 除第一个元素外，每个元素均有唯一一个直接前
驱；
④ 除最后一个元素外，每个元素均有唯一一个直接
后继。
3
2.1 线性表的逻辑结构 线性表(Linear List ) ：是由n(n ≧0)个数据元素(结点)a 1，a
2， …a n 组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n 称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作： (a 1，a 2，…a n ) a 1称为线性表的第一个(首)结点，a n 称为线性表的最后一个(尾)结点。2.1.1 线性表的定义
4
a1，a2，…a i-1都是a i(2≦i≦n)的前驱，其中a i-1是a i的直接前驱;
a i+1，a i+2，…a n都是a i(1≦i ≦n-1)的后继，其中a i+1是a i的直接后继。
2.1.2线性表的逻辑结构
线性表中的数据元素a i所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。
