前言
毕业也没多久的我，发现大学好多东西都遗忘了或者没学好。自己打算从数据结构与算法开始，一点一滴在简书记录我的算法学习和巩固的历程。同时，希望能边和大家分享学习经历的同时，希望能够得到大家的多多指教~
数据结构与算法这一系列我的重点是在算法这一部分，数据结构的概念和基础在本节会解释一下，后期会不断的实验和更新一些基础经典和有趣的算法。其中使用的编程语言主要是C语言。
数据结构与算法概要
重新浏览了一遍书，如果让我来说数据结构与算法的一些印象。我清楚的记得是两个公式。这两个公式来告诉我们，什么是数据结构。
1、程序 = 算法 + 数据结构
2、数据结构 = 数据 + 关系
- 数据之前存在的基本关系就是数据结构了。首先，数据有一个类型的特性，一个是基础数据类型（DT），另一个是抽象的数据类型（ADT）。
基础的数据类型无非是看你处理的是字符还是数字，或者是什么精度的整数。抽象数据类型，有点类似类的思想，对一类事物的数据进行了封装。比如，一辆汽车就是一个抽象数据类型，其中包括车的颜色、型号、特征等信息，作为对象来研究车这个整体的数据集合。
我们最多研究的是抽象数据类型，对于抽象数据之间的关系，常常使用的基本结构是：
表（线性表和链表)、队列和栈。
根据一些生活常识，延伸出来一些常用的数据模型来表现一些逻辑结构：
树、图
另外，对于数据我们还有些常见的数据操作值得我们研究：
查找、排序
- 我们运行的程序处理的对象无非是数据，对于数据而言，算法决定着数据的处理方式。不同的处理方式有不同的效率。我们常见的算法有：
枚举、递归、递推、分治、贪心等
算法有两个重要的考量指标：时间复杂度 和 空间复杂度
时间复杂度是语句的频度之和的数量级，这和问题规模n有关，故T(n) = O(f(n))。算法的空间复杂度为算法在运行过程中临时占用存储空间的度量，记S(n)=O(g(n))。
数据结构中的线性表
数据结构中线性表是最基础、最简单的一种数据表示形式。主要用来表示数据之间存在着什么样的关系。主要分为顺序表和链表。
数据结构无非是数据和关系（D,R）。D是数据元素的集合，当D的数量是0的时候代表是空表。数据之间存在着一种前驱和后继的关系，a[i]，a[i+1]是前驱和后继的关系，表头是没有直接前驱元素的，表尾是没有后继元素的。
顺序表
顺序表中数据是用一组连续的存储单元一次存储线性表中的各个数据的。其中的关系如下表示:
Loc(ai) = L(a0) + i x d顺序表的存储结构
顺序表的存储结构：
#define Maxsize 100
#define ElemType int
typedef struct {
ElemType data[Maxsize]; //顺序表的元素
int length; //顺序表当前的长度
}Sqlist;
顺序表的基础操作：
//--------------------------->创建与销毁
//创建表
void createList (Sqlist *L, int *a , int n) {
//线性表不需要分配空间。
//L = (Sqlist*)malloc(sizeof(ElemType));
for ( int i = 0; i < n; i++) {
L->data[i] = a[i];
}
L->length = n;
}
//初始化空表
void initList(Sqlist *L) {
// L = (Sqlist*)malloc(sizeof(ElemType));
L->length = 0;
}
//销毁表
void destroyList(Sqlist *L) {
L->length = 0;
}
//------------------------------------>查询与遍历
//判断是否表空
int isEmpty(Sqlist *L) {
return L->length == 0;
}
//计算表长度
int lengthOfList(Sqlist *L) {
return L->length;
}
//输出表中数据（遍历顺序表）
void mapList(Sqlist *L) {
for (int i = 0 ; i < L->length; i++) {
printf("%d \n", L->data[i]);
}
}
//得到表中第N个元素的值
int getElemOfN(Sqlist *L, int n) {
if (n < 0 || n >= L->length) {
return 0;
} else {
n = L->data[n-1];
return n;
}
}
//判断某数据是否在顺序表中的位置
int findNumberList(Sqlist *L , ElemType e) {
for (int i = 0; i < L->length; i++) {
if (L->data[i] == e) {
return i+1;
}
}
return 0;
}
//----------------------------------->修改和删除
//在一个位置上插入一个数据（前插）
int insertDataList(Sqlist *L, int pos, ElemType e) {
if (pos < 0 || pos > L->length) {
return 0;
}
for (int i = L->length; i >= pos; i--) {
L->data[i] = L->data[i-1];
}
L->data[pos-1] = e;
L->length++;
return 1;
}
//删除某个位置上的一个数据
void deleteDataOfN(Sqlist *L, int n) {
for (int i = n; i < L->length; i++) {
L->data[i-1] = L->data[i];
}
L->length--;
}
顺序表优缺点
优点：
1、顺序表的逻辑结构和存储结构理解方便，编写也方便；
2、顺序表的因为是随机存取的存储结构，当我们知道起始位置，差值，很容易确定指定元素；
缺点：
1、由于这种存储结构需要系统提供连续的地址空间，对于系统紧缺的机器，可能会导致不能满足当前需求；
2、由于数据元素一般都是按照最大的数进行确定的，当实际应用中没有用到这么多数据，不必要的空间会导致资源的浪费；
3、由于表中是连续分布的，这使得我们在插入和删除做数据修改的过程中，需要把修改之后的数据进行大量的移动，极大的影响了系统的运行速度。
链表
链表的出现可以解决顺序表的一些不足。链表分为单链表、单向循环链表、双向链表、静态链表等。主要讲解单链表为主，首先单链表提出了节点的概念，一个节点存储一个数据单元并且占用一个存储块，这个节点除了存储数据元之外还有一个节点指针，这个指针对象是下一个链表元素。单链表也是通过这个节点指针对一系列的数据进行联系。
单链表节点和结构示意图
单链表的存储结构：
#define Maxsize 100
#define ElemType int
typedef struct LNode{
ElemType data;
struct LNode *next;
} LinkList;
单链表的基本操作：
//------------------------------>单链表的创建
LinkList* createLinkHead(LinkList *L) {
LinkList *t;
ElemType inputNum;
//先初始化一个空的链表
L = (LinkList*)malloc(sizeof(LinkList));
L->data = 999; //999代表的是头
L->next = NULL;
//开始添加
printf("please input:\n");
scanf("%d", &inputNum);
// 循环添加，只到“-1”结束
while (inputNum != -1) {
t = (LinkList*)malloc(sizeof(LinkList));
t->data = inputNum;
t->next = L->next;
L->next = t;
scanf("%d", &inputNum);
}
return L;
}
//------------------------------>单链表的查询
//得出第i个元素的值
LinkList* getValueLinklistOfPos(LinkList *L, int pos) {
LinkList *t = L;
int i = 0;
if (pos > lengthOfLinklist(L) || pos < 0) {
return 0;
}
while (pos > i) {
i++;
t = t->next;
}
return t;
}
//遍历
void mapLinklist(LinkList *L) {
LinkList *t = L;
while (t->next != NULL) {
printf("%d ", t->next->data);
t = t->next;
}
printf("\n");
}
//得出元素的长度
int lengthOfLinklist(LinkList *L) {
int l = 0;
LinkList *t = L;
while(t->next != NULL) {
l++;
t = t->next;
}
return l;
}
//------------------------------>单链表的添加
//尾插法
LinkList* createLinkTail(LinkList *L) {
LinkList *t, *r;
ElemType inputNum;
//先初始化一个空的链表
L = (LinkList*)malloc(sizeof(LinkList));
L->data = 999; //999代表的是头
r = L;
//开始添加
printf("please input:\n");
scanf("%d", &inputNum);
// 循环添加，只到“-1”结束
while (inputNum != -1) {
t = (LinkList*)malloc(sizeof(LinkList));
t->data = inputNum;
r->next = t;
r = t;
scanf("%d", &inputNum);
}
r->next = NULL;
return L;
}
//插入操作，将值e插入到单链表的第i个位置前面
int insertLinkList(LinkList *L, ElemType e, int pos) {
LinkList *t = L;
int i = 0;
if (pos > lengthOfLinklist(L) || pos < 0) {
return 0;
}
// 循环跳出，pos=i;
while (pos > i+1) {
t = t->next;
i++;
}
LinkList *s = (LinkList*)malloc(sizeof(LinkList));
s->data = e;
s->next = t->next;
t->next = s;
return 1;
}
//------------------------------>单链表的删除
//删除第i个元素的操作节点
int deleteLinkList(LinkList *L, int pos) {
if (pos > lengthOfLinklist(L) || pos < 0) {
return 0;
}
LinkList *p = getValueLinklistOfPos(L, pos-1);
p->next = p->next->next;
free(p->next);
return 1;
}
//------------------------------>单链表的修改
//修改第i个元素的操作节点
int alterLinkListFromPos(LinkList *L, int pos, ElemType e) {
if (pos > lengthOfLinklist(L) || pos < 0) {
return 0;
}
LinkList *t = getValueLinklistOfPos(L, pos);
t->data = e;
return 1;
}
//修改第一个值为e的元素的值
int alterLinkListFromValue(LinkList *L, ElemType e, ElemType ex) {
LinkList *t = L;
while (1) {
if (t->next == NULL) {
return 0;
} else {
if (t->data == e) {
t->data = ex;
return 1;
} else {
t = t->next;
}
}
}
}
链表的优缺点
优点：
1、最大的优点就是克服了顺序表的最大存储空间申请的特点，用数据的时候进行分配，不使用的时候就进行释放，相对的节省了一定的空间；
2、存储的时候是靠指针的链接来进行实现的，所以克服了插入和删除元素大量移动的缺点；
缺点：
1、每个节点的指针域也会带来一定的空间占用，当Data所占空间比较少的时候，指针域的比重相对较大。所以，当考虑使用顺序表还是链表所占空间的时候，还需要具体分析；
2、链表插入和删除相对简单了，带来的问题就是查找变的相对麻烦，往往需要从头结点进行查找，增加了算法的复杂程度。
线性表小结
顺序表和链表比较基础一节。我们可以通过比较优缺点，他们是相互取长补短的，优点和缺点都是相互对称的。我们可以通过实际情况来进行选取数据的存储方式。
本章小结
我想做的是记录算法的一个系列，各种基础的、经典的算法稍微偏重一些。线性表是比较基础的一节，但是牵扯到的思路都比较明显，不算太难。另外，链表这边还包括单向循环链表、双向链表和静态链表，这不再一一说明。我的Git上有单链表、顺序表、双向链表的测试代码，可以进行简单参考。
（PS：如果哪里写的不好和有误，还希望大家指出，及时改正，希望和大家一起进步~~ > _ < ~~ ！！！)
Git地址(仅供参考)
网友评论