第一章-绪论
一、数据结构的三要素
1、逻辑结构
数据结构着重关注的是数据元素之间的关系,和对这些数据元素的操作,而不关心具体的数据项内容
- 集合结构
定义:各个元素同属于一个集合,别无其他关系;
- 线性结构(一对一)——>第二、三章
定义:
- 除了第一个元素,所有元素都有唯一前驱;
- 除了最后一个元素,所有元素都有唯一后继;
-
树形结构(一对多)——>第四章
-
图状结构(多对多)——>第五章
2、数据的运算
定义:针对于某种逻辑结构,结合实际需求,定义基本运算
基本运算:
- 查找第i个数据元素
- 在第i个位置插入新的数据元素
- 是删除第i个位置的数据元素
3、物理结构(存储结构)
- 顺序存储
- 链式存储
- 索引存储
- 散列存储(Hash存储)
总结:
- 若采用顺序存储,则各个数据元素在物理上必修是连续的;若采用非顺序存储,则各个数据元素在物理上可以是离散的;
- 数据的存储结构会影响存储空间分配的方便程度;
- 数据的存储结构会影响对数据运算的速度;
二、算法的基本概念
1、什么是算法
程序 = 数据结构 + 算法
算法(Algorithm)是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作;
2、算法的五个特征
- 有穷性:有穷步骤,有穷时间
- 确定性:相同输入——>相同输出
- 可行性:基本运算执行有限次
- 输入:有零个或多个输入
- 输出:有一个或多个输出
3、“好”算法的特质
- 正确性:算法能够正确地解决求解问题;
- 可读性:具有良好的可读性,以帮助人理解;
- 健壮性:输入非法数据时,算法能够做出反应,而不会产生莫名其妙的输出结果;
- 高效率与低存储量需求;
三、算法效率的度量
1、时间复杂度
事前预估算法时间开销T(n)与问题规模n的关系(T表示“time”)
例题:
// 算法1—— 逐步递增型爱你
void loveYou(int n) { //n 为问题规模
(1) int i=1; // 爱你的程度
(2) while(i<=n) {
(3) i++; // 每次+1
(4) printf("I Love You %d\n", i);
}
(5) printf("I Love You More Than %d\n", n);
}
int main(){
loveYou(3000);
}
语句频度
(1) ——1次
(2) ——3001次
(3)(4) ——3000次
(5) ——1次
T(3000) = 1 + 3001 + 2 * 3000 + 1
时间开销与问题规模n的关系:
T(n)=3n+3 只关注复杂度的数量级 ——> T(n) = O(n)
复杂度大小优先级排序:
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
口诀:常对幂指阶
例题:
// 算法1—— 嵌套循环型爱你
void loveYou(int n) { //n 为问题规模
(1) int i=1; // 爱你的程度
(2) while(i<=n) {
(3) i++; // 每次+1
(4) printf("I Love You %d\n", i);
(5) for (int j=1; j<=n; j++){
(6) printf("I am a man!\n") ;
}
}
(7) printf("I Love You More Than %d\n", n);
}
int main(){
loveYou(3000);
}
时间开销与问题规模n的关系:
T(n) = O(n) + O(n2) = O(n2)
例题:
// 算法3——指数增长型爱你
void loveYou(int n) {
int i=1;
while(i<=n0){
i=i*2; // 第一次循环 i=2;第二次循环 i=4;第三次循环 i=8......
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
通过上述循环可知 i = 2x
所以想要退出while循环,x = log2n + 1
所以上述算法的时间复杂度为T(n) = O(x) = O(log2n)
2、空间复杂度
空间开销S(n)与问题规模n的关系(S表示“Space”)
例题:
// 算法1——逐步递增型爱你
void loveYou(int n) {
int i=1;
while(i<=n){
i++;
printf("I Love You %d\n",i);
}
printf("I Love You More Than %d\n",n);
}
转入内存 程序代码 数据
综上所述,上述算法的空间复杂度为:S(n)=O(1)
算法原地工作——算法所需内存空间为常量;
函数递归调用带来的内存开销:
// 算法5——递归型爱你
void loveYou(int n) {
int a,b,c;
if (n > 1) {
loveYou(n-1);
}
printf("I Love You %d\n",n);
}
int main() {
loveYou(5);
}
上述代码的空间复杂度为:S(n)=O(n) O(n)空间复杂度 = 递归调用的深度
第二章-线性表
一、线性表的定义和基本操作
1、定义
线性表是具有相同数据类型的n(n>=0)个数据元素的有限 序列,其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表现为:
L = (a1, a2, ... , ai, ai+1, ... , an) 脚标从1开始计数
- 几个概念:
- ai是线性表中的“第i个”元素线性表中的位序; 位序是从1开始的,数组下标是从0开始的;
- a1是表头元素;an是表尾元素;
- 除第一个元素外,每个元素有且仅有一个直接前驱;
- 除最后一个元素外,每个元素有且仅有一个直接后继;
2、基本操作
InitList(&L): //初始化表。构造一个空的线性表L,分配内存空间;
DestroyList(&L): //销毁操作。销毁线性表,并释放线性表L所占用的内存空间;
ListInsert(&L,i,e): //插入操作。在表L中的第i个位置上插入指定元素e;
ListDelete(&L,i,&e): //删除操作,删除表L中第i个位置的元素,并用e返回删除元素的值;
LocateElem(L,e): //按值查找操作。在表L中查找具有给定关键字的元素;
GetElem(L,i): //按位查找操作。获取表L中第i个位置的元素的值;
Tips:
- 对数据的操作(记忆思路) --创销、增删改查;
- C语言函数的定义 --<返回值类型> 函数名(<参数1类型>参数1, <参数2类型>参数2,...)
- 实际开发中,可根据实际需求定义其他的基本操作
- 函数名和参数的形式、命名都可改变
二、顺序表的定义
1、顺序表的定义
用顺序存储 的方式实现线性表的顺序存储;把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现;
如何知道一个数据元素大小?
C语言 sizeof(ElemType)
sizeof(int) = 4B
sizeof(Customer) = 8B
2、顺序表的静态分配
#define MaxSize 10 //定义最大长度
typedef struct {
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(静态分配方式)
//基本操作---初始化一个顺序表
void InitList(SqList &L){
for(int i=0; i<MaxSize; i++)
L.data[i] = 0; //将所有数据元素设置为默认初始值
L.length=0; //顺序表初始长度为0
}
int main() {
SqList; //声明一个顺序表
InitList(L); //初始化顺序表
//尝试“违规”打印整个data数组
for(int i=0;i<MaxSize;i++)
printf("data[%d]=%d\n",i, L.data[i]);
return 0;
}
//注:
i<MaxSize这么写是违规的,不允许这么访问顺序表结构,应该写成
i<L.length
或者写成基本操作 GetElem(L,i)
3、顺序表的动态分配
#define InitSize 10 //顺序表的初始长度
typedef struct {
ElemType *data; //指针动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(动态分配方式)
key:动态申请和释放内存空间
malloc 和 free 函数:
L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
//malloc函数申请一整片连续空间
- 具体实现:
#define InitSize 10 //顺序表的初始长度
typedef struct {
ElemType *data; //指针动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SqList;
void InitList(SeqList &L){
//用malloc函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize = InitSize;
}
//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
int *p=L.data;
L.data=(int *)malloc((L.MaxSize + len)* sizeof(int));
for(int i=0;i<L.length; i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize + len; //顺序表最大长度增加len
free(p); //释放原来的内存空间
}