绪论第一章什么是数据结构数据的组织形式，具有特定关系的数据元素的集合。数据结构的内容包括：逻辑结构存储结构算法
1 第一章 绪论 ⚫ 什么是数据结构 数据的组织形式，具有特定关系的数据元素的 集合。 ⚫ 数据结构的内容 包括: 逻辑结构 存储结构 算法
逻辑结构逻辑结构：数据元素间的关系包括：线性结构、非线性结构线性结构：除了第一个数据元素和最后一个数据元素以外，其它的每一个数据元素，它的直接前驱和直接后继只有一个。（第一个数据元素没有直接前驱，最后一个数据元素没有直接后继）如：线性表、堆栈、队列、字符串，非线性结构：直接前驱和直接后继有若干个。如：树、图1
2 逻辑结构 ⚫ 逻辑结构：数据元素间的关系 包括：线性结构、非线性结构 ⚫ 线性结构：除了第一个数据元素和最后一个数据 元素以外，其它的每一个数据元素，它的直接前 驱和直接后继只有一个。（第一个数据元素没有 直接前驱，最后一个数据元素没有直接后继） 如：线性表、堆栈、队列、字符串 ⚫ 非线性结构：直接前驱和直接后继有若干个。 如：树、图
存储结构存储结构：数据结构在计算机中的表示（存储）。包括：J顺序存储、链式存储、索引存储和散列存储顺序存储：数据元素存放在连续的存储单元链式存储：数据元素存放在链表中。索引存储：通过索引表存放数据元素。散列存储：通过散列函数确定数据元素的存放地址即数据元素的关键字作为函数的变量，函数的值作为该数据元素的存放地址。3
3 存储结构 ⚫ 存储结构：数据结构在计算机中的表示（存储）。 包括：顺序存储、链式存储、索引存储和散列存储 ⚫ 顺序存储：数据元素存放在连续的存储单元。 ⚫ 链式存储：数据元素存放在链表中。 ⚫ 索引存储：通过索引表存放数据元素。 ⚫ 散列存储：通过散列函数确定数据元素的存放地址， 即数据元素的关键字作为函数的变量，函数的值作 为该数据元素的存放地址
算法算法的特性：有穷性、确定性、可行性、输入、输出如何评价算法：正确性可读性健壮性高效运行低存储量
4 算法 ⚫ 算法的特性：有穷性、确定性、可行性、 输入、输出 ⚫ 如何评价算法: 正确性 可读性 健壮性 高效运行 低存储量
算法分析算法分析：主要用时间复杂度和空间复杂度进行分析时间复杂度：T(n)=O(f(n))例如：两个N*N矩阵相乘C=A*BI/n+1次for (i=0;i<n;i++)I/n(n+1)for (j=0;j<n;j++)次I/n?次( c[]U]=;I/n(n+1)for (k=0;k<n;k++)次I/n3次C[i]U]=C[]U]+A[i][k]*B[k]U];1时间复杂度T(n)=2n3+3n2+2n+1=O(n3)空间复杂度：S(n)=O(f(n))（f(n)表示空间的函数）5
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)表示空间的函数）
抽象数据类型（本教材采用的方法）抽象数据类型abstractdata type（ADT）：一个数学模型和定义在该模型上的一组操作。可分为：原子类型、固定聚合类型、可变聚合类型用三元组表示（D，S，P）其中：D表示数据对象S是D上的关系集P是对D的基本操作集抽象数据类型的定义：ADT抽象数据类型名数据对象：数据关系：基本操作：1ADT抽象数据类型名6
6 抽象数据类型（本教材采用的方法） ⚫ 抽象数据类型 abstract data type（ADT）：一个数学模 型和定义在该模型上的一组操作。 可分为：原子类型、固定聚合类型、可变聚合类型 ⚫ 用三元组表示（D，S，P） 其中：D表示数据对象 S是D上的关系集 P是对D的基本操作集 ⚫ 抽象数据类型的定义： ADT抽象数据类型名{ 数据对象： 数据关系： 基本操作： } ADT抽象数据类型名
第一章作业设n为整数，利用大“O”记号，求下列程序段的时间复杂度1) i=0;k=0;2)i=1; j=0;Dowhile(i+jj) j++;}while (i13) x=n;while (x>=(y+1)*(y+1)y++;4)x=91;y=100;while (y>0)if (x>100) (x=x-10; y--;})else x++;
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++;