数据结构课件李云清.pptxVIP

数据结构;课时安排：

课堂讲授——60学时

上机——12学时

教材与主要参考书：

教材

严蔚敏.《数据结构（C语言版）》.清华大学出版社

参考书目

王红梅.《数据结构（C++版）》(第2版）.清华大学出版社2011

王红梅.《数据结构（C++版）学习辅导预实验指导》.清华大学出版社

李云清.《数据结构（C语言版）》.人民邮电出版社

唐策善.《数据结构－用C语言描述》.高等教育出版社

(美)MarkAllenWeiss.《数据结构与算法分析-C语言描述》.机械工业出版社

陈慧南.《数据结构—使用C++语言描述（第2版）》.人民邮电出版社

严蔚敏.《数据结构题集》.清华大学出版社;第一章绪论;

计算机软件与理论学科的专业基础课程

后续专业课程学习的必要知识与技能准备

操作系统中用队列、存储管理表及目录树

数据库系统运用线性表、多链表及索引树编译技术

要使用栈、散列表及语法树

增强求解复杂问题的能力

;;;例2人机对弈问题;课程编号;例3多叉路口交通灯管理问题;数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。;1.2基本概念和术语;学号;数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合。它一般包括以下三方面的内容：数据的逻辑结构、数据的存储结构和该类数据上的操作（即运算）。

（1）数据的逻辑结构：数据元素之间的逻辑关系;（2）数据的存储结构：数据元素及其关系在计算机中的存储表示。

顺序存储结构：用一组连续的存储单元依次存储数据元素，借助数据元素在存储器中的相对位置来表示数据元素间的逻辑关系。例如

链式存储结构：用一组任意的存储单元存储数据元素，借助指针表示数据元素间的逻辑关系。例如;元素n;1536;（3）数据的操作（即运算）：是在该类数据上施加的一系列操作，给出了数据被使用的方式。

最常用的操作有：插入、删除、查找、更新等。

例：栈队列;数据结构的三个方面：;数据结构的三个方面：;实现一个数据结构，必须首先确定数据的存储表示，然后在给定的存储方式下实现相应的操作。;??据类型—是一组值的集合以及定义于这个值集上的一组运算的总称。;抽象数据类型可以通过固有的数据类型来表示和实现。

本教材采用类C语言描述抽象数据类型。类C语言精选了C语言的一个核心子集，同时作了若干扩充修改，增强了语言的描述功能。;作业;1.4算法和算法分析;二、算法设计的要求

正确性

可读性

健壮性

效率与低存储量需求

;三、算法效率的度量

执行算法所耗费的时间

执行算法所耗费的存储空间（辅助存储空间）

;算法效率的度量（续）

;

例1：求下列程序段的时间复杂度（N*N矩阵相乘）

for(i=1;i=n;i++)

for(j=1;j=n;j++)

{c[i][j]=0;

for(k=1;k=n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

} ;例２（a){++x;s=0;}

---该程序段的执行时间是与问题规模n无关的常数，所以算法的时间复杂度为常数阶T(n)=O(1)

(b)for(i=1;i=n;++i)

{++x;s+=x;}

(c)for(i=1;i=n;++i)

for(j=1;j=n;++j)

{++x;s+=x;};例3分析程序段的时间复杂度：

for(i=2;i=n;++i)

for(j=2;j=i-1;++j)

{++x;a[i，j]=x;}

语句频度为：(n-2+1)(n-2)/2

=(n-1)(n-2)/2

=(n2-3n+2)/2

∴时间复杂度为O(n2)

即此算法的时间复杂度为平方阶.;;有的情况下，即使问题规模相同，算法中基本操作重复执行的次数还随问题的输入数据不同而不同。例如：

;一个程序执行需要空间：

①程序(指令、常数、变量)

②输入数据所占空间----和算法