数据结构（笔记）

数据结构（笔记）"/>

数据结构（笔记）

数据结构

绪论

基本概念

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。（比如，在人类中，人就是数据元素）

数据项：一个数据元素可以由若干个数据项组成（数据项是数据不可分割的最小单位）

数据对象：是性质相同的数据元素的集合，是数据的子集。
ps：例如人有姓名、生日、性别等相同的数据项

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合
ps：在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。

逻辑结构

逻辑结构：是指数据对象中数据元素之间的相互关系。

逻辑结构分为四种：

• 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他的关系。ps：各元素都是平等的
• 线性结构：线性结构中的数据元素之间是一对一的关系
• 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系
• 图形结构：图形结构的数据元素是多对多的关系

物理结构

物理结构：是指数据的逻辑结构在计算机中的存储形式ps：有时候也叫存储结构

数据元素的存储结构形式有两种：

• 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
• 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。ps：数据元素的存储关系并不能反应其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

逻辑结构是面向问题的，而物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

抽象数据类型

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称

数据类型可以分为两种：

• 原子类型：是不可以分解的基本类型，包括整形、实型、字符型等
• 结构类型：有若干个类型组合而成，是可以再分解的。例如：整形数组是由若干个整型数据组成。

抽象是指抽取出事物具有的普遍性的本质

抽象数据类型：是指一个数学模型及在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

抽象的意义在于数据类型的数学抽象特性

抽象数据类体现了程序设计中问题分解、抽象和信息隐藏的特性。

描述抽象数据类型的标准格式：

ADT抽象数据类型

Data

​ 数据类型之间逻辑关系的定义

Operation

​ 操作1

​ 初始条件
操作结果描述

​ 操作2

​ …

​ 操作n

​ …

endADT

算法

###定义

算法：算法是解决特定问题求解步骤的描述，是在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作

###特性

算法具有五个基本特性：输入、输出、有穷性、确定性和可行性

• 输入输出：算法具有零个或多个输入 算法至少有一个或多个输出
• 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每个步骤在可接受的时间内完成
• 确定性：算法的每一步都具有确定的含义，不会出现二义性
• 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行在有限次数完成

###算法设计的要求

• 正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案
  • 1、算法程序没有语法错误
  • 2、算法程序对于合法的输入数据能够产生满足要求的输出结果
  • 3、算法程序对于非法的输入数据能够得出满足规格说明的结果
  • 4、算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输入结果
    ps：一般情况下我们把层次3作为一个算法是否正确的标准
• 可读性：算法设计的另一目的就是为了方便阅读、理解和交流
• 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
• 时间效率高和存储量低

算法效率的度量方法

事后统计方法：这种方法主要是通过设计好的程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低ps：缺陷很大，不太考虑

事前分析估算方法：在计算机程序编程前，依据统计方法对算法进行估算

一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

• 1、算法采用的策略、方法（算法好坏的根本）
• 2、编译产生的代码质量（由软件来支持）
• 3、问题的输入规模
• 4、机器执行指令的速度（看硬件性能）

算法时间复杂度

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也是算法的时间度量，记作：T(n)=O(f(n))。他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

推到大O阶：

• 1、用常数1取代运行中的所有加法常数。
• 2、再修改后的运行次数函数中，只保留最高阶项
• 3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。
• 得到的结果就是大O阶。

常见的时间复杂度所耗费的时间从小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)

算法空间复杂度

算法的空间复杂度通过计算算法所需要的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n)),其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

线性表

**线性表：**零个或多个数据元素的有限序列。

ps：在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的抽象数据类型定义如下：

ADT 线性表(List)

Data

​ 线性表的数据对象集合为{a1,a2,a3…,an}，每个元素的数据类型均为DataType。其中，出第一个元素a1外，每个元素有且只有一个直接前驱元素，除了最后一个元素an外，每个元素有且仅有一个直接后驱元素。数据元素之间的关系是一对一的关系。

Operation

​ InitList(*L); 初始化操作，建立一个空的线性表L

​ ListEmpty(L); 若线性表为空，返回true，否则返回false。

​ ClearList(*L); 将线性表清空

​ GetElem(l,i,*e); 将线性表中的第i个位置元素返回给e

​ LocateElem(L,e); 将线性表L中查找与给定e相等的元素，如果查找成功，返回该元素在表中的序号表示成功；否则，返回0表示失败。

​ ListInsert(*L,i,e); 在线性表中的第i个位置元素插入新元素e。

​ ListDelete(*L,i,*e); 删除线性表L中第i个位置元素，并用e返回其值。

​ ListLength(L); 返回线性表L的元素个数。

endADT

线性表的顺序存储结构

**顺序存储定义：**线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储的结构代码：

#define MAXSIZE 20 /存储空间初始分配量/

typedef int ElemType; /ElemType 类型根据实际情况而定,这里假设为int/

typedef struct

{

​ ElemType data{MAXSIZE}; /数组存储数据元素,最大值为MAXSIZE

​ int length; /线性表当前长度/

}SqList

描述顺序存储结构需要三个属性:

• 存储空间的起始位置:数组data,他的存储位置就是存储空间的存储位置
• 线性表的最大存储容量:数组长度MaxSize
• 线性表的当前长度:length

####顺序存储结构的插入和删除

插入算法：

Status ListInsert(SqList *L, int i, ElemType)

{

​ int k;

​ if(L->length==MAXSIZE)

​ return ERROR;

​ if(i<1||i > L->length+1)

​ return ERROR;

​ if(i<=L->length)

​ {

​ for(k=L->length-1;k>=i-1;k–)

​ L->data[k+1] = L->data[k];

​ }

​ L->data[i-1]=e;

​ L->length++;

​ return OK;

}

删除算法：

Status ListDelete(SqList *L, int i, ElemType *e)

{

​ int k;

​ if(L->length==0)

​ return ERROR;

​ if(i<1||i>L-length)

​ return ERROR;

​ *e=L->data[i-1];

​ if(i < L->length)

​ {

​ for(k=i; k<L->length;k++)

​ L->data[k-1]=L->data[k];

​ }

​ L->length–;

​ return OK;

}

线性表顺序存储结构的优缺点

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量的元素
• 当线性表长度变换比较大的时候，难以确定存储容量
• 造成存储空间的“碎片”

线性表的链式存储结构

定义：为了表示每个数据ai与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。n个结点链结成为一个链表，即为线性表的链式存储结构，因为链表的每个节点中只包含一个指针域，所以也叫作单链表。

• 链表中第一个结点的存储位置叫做头指针
• 在单链表的第一个结点前附设一个结点，称为头结点

头指针与头结点的异同：

头指针：

• 头指针是只链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前其数据与一般无意义(也可以存放链表的长度)
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
• 头结点不一定是链表必须要素

####单链表的读取

获得链表第i个数据的算法思路

• 声明一个结点p指向链表的第一个结点，初始化j从1开始；
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
• 若岛链表末尾p为空，则说明第i个元素不存在
• 否则查找成功，返回结点p的数据

代码算法实现：

Status GetElem(LinkList L, int i, ElemType* e)
{
int j;
LinkList p;
p = L->next;
j = 1;
while (p && j<i)
{
p = p->next;
++j;
}
if (!p || j > i)
{
return ERROR;
*e = p->data;
return OK;
}
}

单链表的插入

单链表第i个数据插入结点的算法思路：

• 声明一结点p指向链表第一个结点，初始化j从1开始；
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
• 若到链表末尾p为空，则说明第i个元素按不存在；
• 否则查找成功，在系统中生成一个空结点s；
• 将数据元素e赋值给s->data
• 单链表的插入标准语句s->next = p->next; p->next = s;
• 返回成功

实现代码算法如下：

/初始条件:顺序线性表L已存在，1≤i≤ListLength(L)，/
/操作结果:在工中第i个位置之前插入新的数据元素e,L的长度加1/

status ListInsert ( LinkList *L,int i,ElemType e)

{

​ int j;
LinkList p,s;
P = *L;
j=1;

​ while (p&& j<i) /寻找第i个结点/
{
p = p->next;
++j;
}
if(!pIj >i)
return ERROR; /第i个元素不存在/
s = (LinkList )malloc (sizeof (Node)); /生成新结点(（C标准函数)/
s->data = e;
s->next = p->next; /将p的后继结点赋值给 s的后继/
p->next = s; /将s赋值给p的后继/
return OK;
}

单链表的删除

单链表第i个元素删除结点的算法思路：

• 声明一点结点p指向链表第一个结点，初始化j从1开始；
• 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
• 若到链表末尾p为空，则说明第i个元素按不存在；
• 否则查找成功，将欲删除的结点p->next赋值给q
• 单链表的标准删除语句p->next = q->next
• 将q结点中的数据赋值给e，作为返回
• 释放q结点
• 返回成功

实现代码算法如下：

status ListInsert ( LinkList *L,int i,ElemType e)

{

​ int j;
LinkList p,s;
P = *L;
j=1;

​ while (p->next && j<i) /寻找第i个结点/
{
p = p->next;
++j;
}

​ if(!(p->next)|| j>i )
return ERROR;

​ q=p->next;

​ p->next=q->next;

​ *e=q->data;

​ free(q);

​ return OK;

}

####单链表的整表创建

单链表的整表创建算法思路：

• 声明一结点p和计数器变量i
• 初始化一空链表L
• 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
• 循环：
  • 生成一新节点赋值给p
  • 随机生成一数子赋值给p的数据域p->data;
  • 将p插入到头结点与前一新结点之间

实现代码算法如下：

头插法：

void CreateListHead(LinkList* L, int n)
{
LinkList p;
int i;
srand(time(0));/初始化随机种子/
*L = (LinkList)malloc(sizeof(Node));/先建立一个带头结点的单链表/
(*L)->next = NULL;
for(i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node));/生成新结点/
p->data = rand() % 100 + 1;/随机生成100以内的数字/
p->next = (*L)->next;
(*L)->next = p;/插入到表头/
}
}

尾插法：

void CreateListHead(LinkList* L, int n)
{
LinkList p,r;
int i;
srand(time(0));/初始化随机种子/
*L = (LinkList)malloc(sizeof(Node));/先建立一个带头结点的单链表/
r = *L;/*r为指向尾部的结点/
for(i = 0; i < n; i++)
{
p = (Node * )malloc(sizeof(Node));/生成新结点/
p->data = rand() % 100 + 1;/随机生成100以内的数字/
r->next = p;/表示当前的结点定义为表尾终端节点/
}
r->next = NULL;/表示当前链表结束/
}

单链表的整表删除

算法思路：

• 声明一个结点q和p
• 将第一个结点赋值给p
• 循环：
  • 将第一个结点赋值给q
  • 释放p
  • 将q赋值给p

实现代码算法如下：

Status ClearList(LinkList * L)

{

​ LinkList p,q;

}