第一章-绪论

一              、数据结构的三要素

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); //释放原来的内存空间 }

第三章-栈 


 


 


 


 


 


 


 、队列和数组

第四章-串

第五章-树与二叉树

第六章-图

第七章-查找

第八章-排序