第1章 绪论 1.2 基本概念和术语
一、数据、数据元素、数据项
1． 数据：凡能被计算机存储、加工的对象，通称为数据。
2． 数据元素：是数据的基本单位，通常具有完整、确定的实际意义。 3． 数据项：是数据不可分割的最小单位。
注意：数据、数据元素、数据项是数据组织的三个层次。 如：（80，90，100，110，120）、表格 二、数据的逻辑结构
1． 逻辑结构：数据元素之间的“邻接”关系 2． 四种逻辑结构
线性结构：数据元素之间存在“一对一”的关系 树形结构：数据元素之间存在“一对多”的关系 图状结构：数据元素之间存在“多对多”的关系 集合：数据元素之间没有邻接关系 三、数据的存储结构
1． 存储结构：数据元素在计算机内的存放方式 2． 两种存储结构
顺序存储：将数据元素依次存放到一组连续的存储单元中。
链式存储：将数据元素存放到非连续的存储单元中，并利用指针将各个存储单元链接起 来。
四、数据的基本操作
加工型操作：改变数据元素的个数或数据元素的内容 引用型操作：数据元素的个数或数据元素的内容均未改变 五、数据结构
1．含义：包括三方面的内容：
逻辑结构：反映数据元素之间的邻接”关系 存储结构：反映数据元素在计算机内的存放方式 数据的操作
2. 数据按结构分，可分为4类，每一类对应着一种逻辑结构
1
数据 线性表 树 图 查找表
1.3 算法描述
1． 算法：解决问题的方法和步骤。 2． 算法的描述方法 框图
非形式语言：如中文 类C语言程序 C语言程序
1.4 算法分析
逻辑结构 线性结构 树型结构 图状结构 集合 1． 对同一问题，可以设计多种不同的算法，但必有一种算法的时间效率最高。 2． 估算一个算法的运行时间
① 确定问题的输入规模n。
② 根据问题的特点，选择一种操作作为“标准操作”。 （通常以条件判断或赋值语句为标准操作）
③ 确定在给定输入下共执行多少次标准操作，从而算出运行时间T。 3． 算法的时间复杂度
对算法的运行时间T(n)，忽略所有的常数、低次项，忽略最高项的系数，称为算法的时间复杂度，以O表示。
运行时间 T(n)=c T(n)=cn T(n)=cn2 时间复杂度 常数阶O(1) 线性阶O(n) 平方阶O(n2) 指数阶O(2) 对数阶O(log2) nT(n)?c?2n T(n)?c?logn2
n1.5 指针和结构
2
一、什么是指针 1．存储单元的地址
每一个存储单元由一个或多个字节组成，存储单元中第一个字节的编号称为存储单元的地址。
2．什么叫指针？
指针总是指向某个变量。指针的值是所指向变量的地址，指针的类型是所指向变量的类型。 二、指针变量 1．指针变量的定义
类型 *指针变量名; 例：int *p;
解释：定义一个指针p，它只能指向int型变量。 2．两个运算符
&：取地址运算符，例&i *：指针运算符，例*p 例：int *p,i=3; p=&i;
printf(\说明：
① &和*互为逆运算，即：&*p=p，*&i=i
② 定义指针变量时，指针变量名前面的“*”不是指针运算符。 ③ 指针可以与整数进行加、减运算。 指针±n=指针的原值±sizeof(指针的类型)×n ④ 同类型的两个指针可以相互赋值。 三、指针与数组
1．数组名代表该数组的首地址，例a= =&a[0] 2．设int a[6]，则
a[i ]，*(a+i)是等价的 &a[i ]，a+i是等价的 3．表示数组元素的方法 下标法：例a[i] 指针法：例*(a+i)
4．设指针p指向数组a的某一个元素，则p++：使p指向数组的下一个元素；四、结构
3
1．定义结构类型 struct 结构名
{ 成员定义列表} 例：struct person { int no; char name[6]; };
2．定义结构变量
struct person x; 1． 引用结构变量的成员
结构变量名．成员名 2． 结构变量的初始化 3． 结构指针
例：已知struct person x,*p; p=&x;
则表示x 的no成员有三种形式：x.no，p->no，(*p).no
第2章 线性表 2．1 线性表的定义
1．线性表的表示形式：
L=（a1，a2，a3，?，an）
每种操作都采用一个函数来完成，这些函数是自定义函数，使用之前必须先定义。
2．2 线性表的顺序存储结构
2．线性表的基本操作
一、顺序表的类型定义
顺序表实际是一个结构变量，包括两个域：
datas：存放线性表的元素，last：存放线性表的长度。 typedef struct { 类型 datas[maxsize]; int last; } sequenlist; sequenlist L;
二、为线性表L=（'a'，'b'，'c'，'d'，??）创建一个顺序表，要求L的第1个元素存入数组的1号元素中。
4
typedef struct { char datas[20]; int last; } sequenlist; void main() { sequenlist L; char ch; int i=1; ch=getchar(); while(ch!='\\n') { L.datas[i]=ch; i++;
ch=getchar();
} L.last=i-1;
for(i=1;i<=L.last;i++)
printf(\
printf(\}
三、基本操作在顺序表上的实现
1．insert(a,x,i)：将元素x插入到顺序表a的第i号元素之前 2．delete(a,i)：删除顺序表a的第i号元素
第3章 链式存储结构 3．1 线性表的链式存储结构
一、顺序表的优缺点
优点：空间利用率高，可以随机读取表中任一元素。 缺点：插入、删除操作要移动大量的数据，时间性能差。二、单链表 1．单链表的组成
每个单链表由多个结点组成，每个结点包含两个域： 数据域data：存放线性表的元素 指针域next：存放下一个结点的地址 2．单链表的类型定义
typedef struct node
5