【Day8 数据结构学习-1】

一、课程体系

概念
顺序表，单链表，单向循环链表，双向循环链表，队列，栈，树，图
算法：
查找算法，排序算法

二、为什么要学习数据结构

1.程序 = 数据结构 + 算法

数据结构体是写代码非常重要的东西，也是一门基础课程

2.任何一门编程语言，数据结构都是非常重要的组成部分。

比如 c++里面的STL(标准模板库)；
数据库的本质就是数据结构的内容编写的；
数据的图的遍历算法就是人工智能的基础；
红黑树会在驱动中体现。

3.之前学习过的c语言基础，难度较大的几个地方：指针，数组，结构体，函数，而数据结构这门课会常常使用这些东西，算是对这些知识点的深入理解。

三、数据结构的概念

3.1 基本概念

数据结构：
数据：研究对象
结构：数据之间的关系

数据结构主要就是研究数据与数据之间的关系
在实际开发中，数据结构体主要用于搞清楚数据之间的关系之后在内存中临时存储数据。

3.2 数据结构的定义

数据结构主要研究的是数据的逻辑关系和存储关系以及操作

3.3 逻辑关系

逻辑关系主要指的是数据之间在逻辑上的关系，主要指的是领接关系。
逻辑关系在考虑数据之间关系的时候会涉及到直接前驱和直接后继的概念

线性关系：一对一的关系，任何一个数据只能有一个直接前驱和一个直接后继
例如：线性表，栈，队列

树形关系：一对多的关系，任何一个数据只能有一个直接前驱，但是可以有多个直接后继
例如：树，二叉树

图形关系：（网状关系）：多对多的关系，任何一个数据都有多个直接前驱和多个直接后继。
例如：图

3.4 存储关系

存储关系指的就是数据在内存中是如何存储的

顺序存储：
数据在内存中会开辟一段连续的内存空间进行存储，一般使用数组来存储数据

链式存储：
数据在内存中存储时不需要开辟一段连续的空间。

索引存储（一般不用）
哈希存储（一般不用）

注意：理论上任何一种逻辑结构都可以用两种存储方式实现。

3.5 操作

增 删 改 查

四、顺序表（线性表的顺序存储）

4.1 概念

线性表：数据和数据之间的一对一的关系
顺序存储：需要在内存中开辟一段连续的内存空间存储数据，一般使用数据来存储数据，为了方便对数据进行操作，通常会定义一个变量来保存最后一个元素的下标。

4.2 对顺序表的操作

4.2.1 创建一个空的顺序表

#include <stdio.h>
#include <stdlib.h>
//为了提高代码的拓展性，对数据类型取别名，方便对表中的数据类型进行修改
typedef int DataType;
#define N 32
//定义一个结构体
typedef struct
{DataType data[N];int pos;  //数组下标
}seqlist;
//顺序表的创建
seqlist * SeqlistCreate();
//判断顺序表是否为满
int SeqlistIsFull(seqlist *st);
int main(int argc, char const *argv[])
{seqlist *st = SeqlistCreate();return 0;
}
//顺序表的创建
seqlist *SeqlistCreate()
{//在堆上申请空间seqlist *st = (seqlist *)malloc(sizeof(seqlist));//初始化，标识当前顺序表中没有元素st->pos = -1;//返回顺序表的首地址return st;
}

4.2.2 判断顺序表是否为满

//判断顺序表是否为满
int SeqlistIsFull(seqlist *st)
{
#if 0if(st->pos == N -1){return 1;}else{return 0;}
#endifreturn st->pos == N -1 ? 1 : 0;
}

4.2.3 插入数据

//插入数据
void SeqlistInsert(seqlist *st,DataType value)
{if(SeqlistIsFull(st) == 1){printf("插入失败，顺序表为满！\n");return;}//保存最后一个元素的变量pos自增st->pos++;//将数据插入到pos的位置st->data[st->pos] = value;printf("插入成功!\n");
}

4.2.4 遍历顺序表

//遍历顺序表
void SeqlistPrint(seqlist *st)
{int i;for(i = 0 ;i <= st->pos;i++){printf("%d ",st->data[i]);}putchar(10);
}

4.2.5 判断顺序表是否为空

//判断顺序表是否为空
int SeqlistIsEmpty(seqlist *st)
{return st->pos == -1 ? 1 : 0;
}

4.2.6删除数据并返回删除的数据

//删除数据并且返回要删除的数据
DataType SeqlistDelete(seqlist *st)
{if(SeqlistIsEmpty(st) == 1){printf("删除失败，顺序表为空！\n");return (DataType)-1;}DataType value = st->data[st->pos];st->pos--;printf("删除成功！\n");return value;
}

4.2.7 按照位置插入数据

//按照位置插入数据
void SeqlistInsertByPos(seqlist *st,int p,DataType value)
{if(SeqlistIsFull(st)){printf("插入失败，顺序表为满！\n");return;}if(p < 0 || p > st->pos + 1){printf("插入失败，插入位置有误！\n");return;}int i;if(p == st->pos + 1){st->data[p] = value;st->pos++;}else{for(i = st->pos;i >= p;i--){st->data[i + 1] = st->data[i];}//将插入的数据放在P的位置st->data[p] = value;st->pos++;}printf("按照位置插入数据成功！\n");return;
}

4.2.8 按照位置删除数据，并返回删除的数据

//按照位置删除数据，返回删除的数据
DataType SeqlistDeleteByPos(seqlist *st,int p)
{if(SeqlistIsEmpty(st)){printf("顺序表为空，按照位置删除失败！\n");return (DataType)-1;}if(p < 0 || p > st->pos){printf("删除失败，输入位置有误！\n");return (DataType)-1;}//将要删除的数据保存在value中DataType value = st->data[p];//将p往上的数据向下移动int i;for(i = p;i < st->pos;i++){st->data[i] = st->data[i + 1];}st->pos--;printf("按照位置删除数据成功\n");return value;
}

4.2.9 按照数据修改数据

//按照数据修改数据
void SeqlistUpdateByData(seqlist *st,DataType OldValue,DataType NewValue)
{int i,flags = 0;for(i = 0 ; i <= st->pos;i++){if(st->data[i] == OldValue){st->data[i] = NewValue;flags = 1;}}if(flags == 0){printf("修改数据失败，%d不存在\n",OldValue);}
}

4.2.10 按照位置修改数据

//按照位置修改数据
void SeqlistUpdateByPos(seqlist *st,int p,DataType value)
{if(p < 0 || p > st->pos){printf("修改失败，位置有误！\n");return;}st->data[p] = value;printf("按照位置修改数据成功！\n");
}

4.2.11 按照数据查找位置

//按照数据查找位置
int SeqlistSearchPos(seqlist *st,DataType value)
{int i;for(i = 0 ; i <= st->pos;i++){if(st->data[i] == value){printf("按照数据查找位置成功！\n");return i;}}printf("查找失败，数据%d不存在\n",value);return -1;
}

4.2.12 按照位置查找数据

//按照位置查找数据
DataType SeqlistSearchData(seqlist *st,int p)
{if(p < 0 || p > st->pos){printf("按照位置查找数据失败，位置有误！\n");return (DataType)-1;}printf("按照位置查找数据成功！\n");return st->data[p];
}

练习：

1.删除重复数据

（将先出现的数据和后面的数据进行对比，如果有重复的将后面的数据删除）
s1: 1 2 2 2 1 1 3 4 2 4 5 4 1

。。。。。（一顿操作之后）

s1:1 2 3 4 5

//删除重复数据
void SeqlistDeleteRepeat(seqlist *st)
{int i,j;for(i = 0 ; i < st->pos;i++){for(j = i + 1;j <= st->pos;j++){if(st->data[i] == st->data[j]){//按照位置删除j的数据SeqlistDeleteByPos(st,j);//j--目的防止删除位置的数据不作比较j--;}}}
}

2.合并表

要求：将s2里面与s1不一样的数据保存在s1的后面
s1: 1 2 3 4 5
s2: 1 3 5 7 9
…
s1:1 2 3 4 5 7 9

//合并表
void SeqlistMerge(seqlist *s1,seqlist *s2)
{int i;for(i = 0 ; i <= s2->pos;i++){if(SeqlistSearchPos(s1,s2->data[i]) == -1){SeqlistInsert(s1,s2->data[i]);}}
}

五、整体代码

#include <stdio.h>
#include <stdlib.h>
//为了提高代码的拓展性，对数据类型取别名，方便对表中的数据类型进行修改
typedef int DataType;
#define N 32
//定义一个结构体
typedef struct
{DataType data[N];int pos;  //数组下标
}seqlist;
//顺序表的创建
seqlist * SeqlistCreate();
//判断顺序表是否为满
int SeqlistIsFull(seqlist *st);
//插入数据
void SeqlistInsert(seqlist *st,DataType value);
//遍历顺序表
void SeqlistPrint(seqlist *st);
//判断顺序表是否为空
int SeqlistIsEmpty(seqlist *st);
//删除数据并且返回要删除的数据
DataType SeqlistDelete(seqlist *st);
//按照位置插入数据
void SeqlistInsertByPos(seqlist *st,int p,DataType value);
//按照位置删除数据，返回删除的数据
DataType SeqlistDeleteByPos(seqlist *st,int p);
//按照数据修改数据
void SeqlistUpdateByData(seqlist *st,DataType OldValue,DataType NewValue);
//按照位置修改数据
void SeqlistUpdateByPos(seqlist *st,int p,DataType value);
//按照数据查找位置
int SeqlistSearchPos(seqlist *st,DataType value);
//按照位置查找数据
DataType SeqlistSearchData(seqlist *st,int p);
//删除重复数据
void SeqlistDeleteRepeat(seqlist *st);
//合并表
void SeqlistMerge(seqlist *s1,seqlist *s2);
int main(int argc, char const *argv[])
{seqlist *st = SeqlistCreate();if(st == NULL){printf("顺序表初始化失败！\n");return -1;}int i;for(i = 1 ; i <= 32;i++){SeqlistInsert(st,i);}SeqlistPrint(st);for(i = 0 ; i < 10;i++){SeqlistDelete(st);}SeqlistPrint(st);SeqlistInsertByPos(st,7,777);SeqlistPrint(st);SeqlistDeleteByPos(st,9);SeqlistPrint(st);SeqlistUpdateByData(st,10,999);SeqlistPrint(st);SeqlistUpdateByPos(st,17,1001);SeqlistPrint(st);printf("位置为：%d\n",SeqlistSearchPos(st,999));printf("按照位置查找的数据为：%d\n",SeqlistSearchData(st,19));SeqlistInsert(st,1);SeqlistInsert(st,2);SeqlistInsert(st,3);SeqlistInsert(st,1);SeqlistInsert(st,3);SeqlistInsert(st,4);SeqlistInsert(st,5);SeqlistPrint(st);SeqlistDeleteRepeat(st);SeqlistPrint(st);seqlist *s1 = SeqlistCreate();seqlist *s2 = SeqlistCreate();SeqlistInsert(s1,1);SeqlistInsert(s1,2);SeqlistInsert(s1,3);SeqlistInsert(s1,4);SeqlistInsert(s1,5);SeqlistInsert(s2,1);SeqlistInsert(s2,3);SeqlistInsert(s2,5);SeqlistInsert(s2,7);SeqlistInsert(s2,9);SeqlistMerge(s1,s2);SeqlistPrint(s1);return 0;
}
//顺序表的创建
seqlist *SeqlistCreate()
{//在堆上申请空间seqlist *st = (seqlist *)malloc(sizeof(seqlist));if(NULL == st){return NULL;}//初始化，标识当前顺序表中没有元素st->pos = -1;//返回顺序表的首地址return st;
}
//判断顺序表是否为满
int SeqlistIsFull(seqlist *st)
{
#if 0if(st->pos == N -1){return 1;}else{return 0;}
#endifreturn st->pos == N -1 ? 1 : 0;
}
//插入数据
void SeqlistInsert(seqlist *st,DataType value)
{if(SeqlistIsFull(st) == 1){printf("插入失败，顺序表为满！\n");return;}//保存最后一个元素的变量pos自增st->pos++;//将数据插入到pos的位置st->data[st->pos] = value;printf("插入成功!\n");return;
}
//遍历顺序表
void SeqlistPrint(seqlist *st)
{int i;for(i = 0 ;i <= st->pos;i++){printf("%d ",st->data[i]);}putchar(10);
}
//判断顺序表是否为空
int SeqlistIsEmpty(seqlist *st)
{return st->pos == -1 ? 1 : 0;
}
//删除数据并且返回要删除的数据
DataType SeqlistDelete(seqlist *st)
{if(SeqlistIsEmpty(st) == 1){printf("删除失败，顺序表为空！\n");return (DataType)-1;}DataType value = st->data[st->pos];st->pos--;printf("删除成功！\n");return value;
}
//按照位置插入数据
void SeqlistInsertByPos(seqlist *st,int p,DataType value)
{if(SeqlistIsFull(st)){printf("插入失败，顺序表为满！\n");return;}if(p < 0 || p > st->pos + 1){printf("插入失败，插入位置有误！\n");return;}int i;if(p == st->pos + 1){st->data[p] = value;st->pos++;}else{for(i = st->pos;i >= p;i--){st->data[i + 1] = st->data[i];}//将插入的数据放在P的位置st->data[p] = value;st->pos++;}printf("按照位置插入数据成功！\n");return;
}
//按照位置删除数据，返回删除的数据
DataType SeqlistDeleteByPos(seqlist *st,int p)
{if(SeqlistIsEmpty(st)){printf("顺序表为空，按照位置删除失败！\n");return (DataType)-1;}if(p < 0 || p > st->pos){printf("删除失败，输入位置有误！\n");return (DataType)-1;}//将要删除的数据保存在value中DataType value = st->data[p];//将p往上的数据向下移动int i;for(i = p;i < st->pos;i++){st->data[i] = st->data[i + 1];}st->pos--;printf("按照位置删除数据成功\n");return value;
}
//按照数据修改数据
void SeqlistUpdateByData(seqlist *st,DataType OldValue,DataType NewValue)
{int i,flags = 0;for(i = 0 ; i <= st->pos;i++){if(st->data[i] == OldValue){st->data[i] = NewValue;flags = 1;}}if(flags == 0){printf("修改数据失败，%d不存在\n",OldValue);}
}
//按照位置修改数据
void SeqlistUpdateByPos(seqlist *st,int p,DataType value)
{if(p < 0 || p > st->pos){printf("修改失败，位置有误！\n");return;}st->data[p] = value;printf("按照位置修改数据成功！\n");
}
//按照数据查找位置
int SeqlistSearchPos(seqlist *st,DataType value)
{int i;for(i = 0 ; i <= st->pos;i++){if(st->data[i] == value){printf("按照数据查找位置成功！\n");return i;}}printf("查找失败，数据%d不存在\n",value);return -1;
}
//按照位置查找数据
DataType SeqlistSearchData(seqlist *st,int p)
{if(p < 0 || p > st->pos){printf("按照位置查找数据失败，位置有误！\n");return (DataType)-1;}printf("按照位置查找数据成功！\n");return st->data[p];
}
//删除重复数据
void SeqlistDeleteRepeat(seqlist *st)
{int i,j;for(i = 0 ; i < st->pos;i++){for(j = i + 1;j <= st->pos;j++){if(st->data[i] == st->data[j]){//按照位置删除j的数据SeqlistDeleteByPos(st,j);//j--目的防止删除位置的数据不作比较j--;}}}
}
//合并表
void SeqlistMerge(seqlist *s1,seqlist *s2)
{int i;for(i = 0 ; i <= s2->pos;i++){if(SeqlistSearchPos(s1,s2->data[i]) == -1){SeqlistInsert(s1,s2->data[i]);}}
}

六、顺序表的优缺点

优点：
操作简单，本质就是一个数组
缺点：
需要开辟一段连续的内存空间，所有说，如果存储的数据多，则很不方便，在插入或者删除数据的时候，会出现内存数据成片移动的现象，效率非常低。

七、单链表

7.1 概念

单链表：线性表的链式存储
线性表：一对一的关系
链式存储：不需要在内存中开辟一段连续的内存看空间，所以每一个数据不再是一个基本数据，而是由两部分组成，数据域和指针域，数据域保存数据，指针域保存下一个结点的地址。

单链表：就是单向链表，前者结点可以找到后者结点，但是后者无法找到前者。

7.2 单链表的操作

7.2.1 定义结点结构体

#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int DataType;
//定义结点结构体
typedef struct linklist
{DataType data; //数据域struct linklist *next; //指针域，为了能够操作后面结点//所以指针的类型为当前结构体的类型
}linklist;#endif

7.2.2 创建一个空的单链表

（1）

图（1）的数据域为0x100，指针域为空

（2）

//创建一个空的单链表
linklist* LinkListCreate()
{//定义一个头结点，在堆区开辟空间linklist *head = (linklist *)malloc(sizeof(linklist));//初始化指针域标识为空head->next = NULL;return head;
}