《数据结构》课程教学课件（PPT讲稿）第一章 绪论

1 第一章 绪论 ⚫ 什么是数据结构 数据的组织形式，具有特定关系的数据元素的 集合。 ⚫ 数据结构的内容 包括: 逻辑结构 存储结构 算法

2 逻辑结构 ⚫ 逻辑结构：数据元素间的关系 包括：线性结构、非线性结构 ⚫ 线性结构：除了第一个数据元素和最后一个数据 元素以外，其它的每一个数据元素，它的直接前 驱和直接后继只有一个。（第一个数据元素没有 直接前驱，最后一个数据元素没有直接后继） 如：线性表、堆栈、队列、字符串 ⚫ 非线性结构：直接前驱和直接后继有若干个。 如：树、图

3 存储结构 ⚫ 存储结构：数据结构在计算机中的表示（存储）。 包括：顺序存储、链式存储、索引存储和散列存储 ⚫ 顺序存储：数据元素存放在连续的存储单元。 ⚫ 链式存储：数据元素存放在链表中。 ⚫ 索引存储：通过索引表存放数据元素。 ⚫ 散列存储：通过散列函数确定数据元素的存放地址， 即数据元素的关键字作为函数的变量，函数的值作 为该数据元素的存放地址

4 算法 ⚫ 算法的特性：有穷性、确定性、可行性、 输入、输出 ⚫ 如何评价算法: 正确性 可读性 健壮性 高效运行 低存储量

5 算法分析 算法分析：主要用时间复杂度和空间复杂度进行分析 ⚫ 时间复杂度: T(n)=O(f(n)) 例如：两个N*N矩阵相乘 C=A*B for (i=0;i<n;i++) //n+1次 for ( j=0;j<n;j++) //n(n+1) 次 { C[i][j]=0; //n2次 for ( k=0;k<n;k++) //n2 (n+1) 次 C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n3次 } 时间复杂度T(n)=2n3+3n2+2n+1= O(n3 ) ⚫ 空间复杂度: S(n)=O(f(n)) （f(n)表示空间的函数）

6 抽象数据类型（本教材采用的方法） ⚫ 抽象数据类型 abstract data type（ADT）：一个数学模 型和定义在该模型上的一组操作。 可分为：原子类型、固定聚合类型、可变聚合类型 ⚫ 用三元组表示（D，S，P） 其中：D表示数据对象 S是D上的关系集 P是对D的基本操作集 ⚫ 抽象数据类型的定义： ADT抽象数据类型名{ 数据对象： 数据关系： 基本操作： } ADT抽象数据类型名

7 第一章作业 设n为整数，利用大“O”记号，求下列程序段的时间复杂度 1）i=0;k=0; 2)i=1; j=0; Do while(i+jj) j++; }while (i1 while (x>=(y+1)*(y+1)) y++; 4)x=91; y=100; while (y>0) if (x>100) {x=x-10; y- -;} else x++;