一 课程体系
概念
顺序表，单链表，单向循环链表，双向循环链表，队列，栈，
树
图
算法：
查找算法，排序算法
二 为什么要学习数据结构
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 0 if(st->pos == N -1) { return 1; } else { return 0; } #endif return 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.6 按照位置插入数据
//按照位置插入数据 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.7 按照位置删除数据，并返回删除的数据
//按照位置删除数据，返回删除的数据 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.8 按照数据修改数据
//按照数据修改数据 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); } }
#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 0 if(st->pos == N -1) { return 1; } else { return 0; } #endif return 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]); } } }
