顺序表，单链表，双链表，循环链表(01星球)

数据结构前导------C语言复习

程序为什么要被编译器编译之后才能运行

因为计算机能够识别的只有机器语言，机器语言就是由二进制0和1构成。所以为了让计算机执行我们写的程序，必须翻译成计算机能够识别的机器语言程序(目标程序)。

编译器把C语言程序转换成可以执行的机器码的过程做了什么

1).预处理:展开头文件/宏替换/去掉注释/条件编译

2).编译:检查语法，生成汇编代码

3).汇编:把汇编代码转化成二进制的机器码

4).链接合成可执行的程序，并对声明在其他目标文件找到对应的定义

宏定义

#define 定义宏，使用 #define 定义常量来增强可读性。
宏定义在C语言源程序中允许用一个标识符来表示一个字符串,称为“宏” ,被定义为“宏”的标识符称为“宏名”。
定义宏：#define 宏名 替换文本 （替换文本”可以是任意常数、表达式、字符串等。）

例如：

typedef 关键字

typedef 是 C 和 C++ 语言中的一个关键字，用于为现有的数据类型定义一个新的名称。
它通常用于简化复杂的类型声明或为某种类型创建更具描述性的名称。
typedef 并不创建新的数据类型，而是为现有的数据类型创建一个别名。

语法：typedef 原数据类型 新数据类型;

常用于结构体：

全局变量和局部变量

（1）在程序中，局部变量和全局变量的名称可以相同，但是在函数内，如果两个名字相同，会使用局部变量值，全局变量不会被使用。
（2）函数的参数，形式参数，被当作该函数内的局部变量，如果与全局变量同名它们会优先使用。
（3）当局部变量被定义时，系统不会对其初始化，必须自行对其初始化。定义全局变量时，系统会自动对其初始化，全局变量默认值 0（char：‘\0’,指针类型NULL）

常量

常量:是固定值，在程序执行期间不会改变。这些固定的值，又叫做字面量
使用#define或者const声明（const 声明常量要在一个语句内完成）

字符的输入输出

scanf()和printf()函数
注意读入字符变量：用getchar()吞回车或者空格

运算符

1. / 整除（向下取整）

2. ++ 自增 a++ ++a区别

3. – 自减 同上

4. 三目运算符 ？：

5. 位操作符：直接对二进制位进行操作

6. << 左移 a<<x a左移x位，左移一位相当于乘2

7. 右移

8. ~取反

9. |按位或 有1为1

10. &按位与 同1为1 通常用来对某些位清0或保留某些位
    例：a 的高八位清 0 ， 保留低八位， 可作 a&255 运算 ( 255 的二进制数为0000000011111111)

11. ^按位异或 不同为1
    实现两个值的交换，而不必使用临时变量。
    例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：
    　　　　a = a^b； 　　//a=10100111
    　　　　b = b^a； 　　//b=10100001
    　　　　a = a^b； 　　//a=00000110

冯诺依曼架构

机器语言：计算机可以将二进制代码存储在内存中，并且执行这些代码。
二进制位：也称为位(bit), 基数为2 的数字中的 0 或 1，它是信息的基本组成元素。
指令：计算机硬件所能理解并服从的命令（也是二进制位串）。

在计算机内部，指令和数据并没有本质的区别，它们都是以二进制形式存储的。

汇编语言：以助记符形式表示的机器指令。

高级语言：高级编程语言 C+ +、 Java 等可移植的语言，由一些单词和代数符号组成，可以由编译器转换为汇编语言。

存储器容量

在描述存储容量：1bit 1byte（1B） 1KB 1MB 1GB 1TB

在存储器，一个二进制位称为1bit。
1B：字节，1B=8bit

1B 1KB 1MB 1GB 1TB 由小到大，换算单位是2^10即1024

数据类型

数据类型：定义内存空间⼤⼩的⼀个代名词，⽅便编译器能够合理的转换为对应的指令来操作内存空间。

以64位系统为例：
char 1B
int 4B
long long 8B
float 4B
double 8B

一个特殊的数据类型，指针，是存放数据的内存单元地址。

指针

为了便于管理，在按字节编址的存储器中，以8位（1字节）的大小构成一个存储单元。
计算机系统的内存拥有大量的存储单元，若按字节编址，每个存储单元的大小为1字节，为了便于管理，必须为每个存储单元编号，该编号就是存储单元的“地址”，每个存储单元拥有一个唯一的地址。

内存地址通常以十六进制形式给出。

存储内存地址的变量就是指针类型的。

64位系统中 指针类型 占 8B 32位系统中 指针类型 占 4B

指针本质

1. 本质就是一个地址值（操作系统给的），变量。

2. 内存地址是什么？
   内存地址只是一个十六进制的数字（0x），表示内存区域。在计算机上，内存的容量以字节为基本单位。 也就是说，存储器地址表示1字节(8bit )的存储区域。

3. 指针指向的本质：地址赋值

4. 多重指针：间接寻址/指针链

5. ‘ &’：引用，取地址符
   ‘*’：解引用，取值符号

6. 指针变量除了可以存放变量的地址外，还可以存放其他数据的地址，例如可以存放数组和函数的地址。

为什么需要指针

1. 在不同区域之间的代码可以共享数据（直接通过指针指向相同的内存空间），特别是结构体，一个结构体中有很多数据，一个结构体变量就会占用大量空间。用指针去共享节省时间和内存。
2. 指针占用的字节数是相同的。在（硬件/操作系统）数据存储按字节存储的。指针不同于一般变量，存的是变量的地址，在同一架构下地址长度都是相同的，所有不同类型的指针长度都一样。一般32位系统，指针长度为4个字节，64位则是8个字节。
3. 一些操作必须使用指针， 例如申请内存。。。malloc
4. 可以用指针搞一些复杂的结构-链表/树/图。。多重指针（二级指针）

数组

数组（Array）也是一种复合数据类型，它由一系列相同类型的元素组成。
数组元素在内存中连续存放。

在 C 语言中，数组名是一个指向数组第一个元素的指针常量，也就是说，它存储的是数组第一个元素的地址，并且不能被修改。

数组名的两层含义：做数组名时 代指整个数组（空间）。做指针常量时，保存数组第一个元素的地址。

数组指针和指针数组

数组指针：一个指针保存着数组的地址

指针数组：数组中的每个变量是指针类型

看p是数组指针还是针数组，先看[] ，再看*, []比星号优先级更高

结构体

数组允许定义可存储相同类型数据项的变量。
结构体是C编程中另一种用户自定义的可用的数据类型，它允许存储不同类型的数据项。

• struct：声明结构体的关键字
• tag 是结构体标签，是一个可选的标志，它是用来引用该结构体的快速标记。
• member-list 是标准的变量定义，比如 int i; 或者 float f，或者其他有效的变量定义。
• 成员后面用分号;隔开，结构类型定义的末尾也有个分号;
• variable-list 结构变量，是可选的，定义在结构的末尾，最后一个分号之前，可以指定一个或多个结构变量。

结构体变量的声明/定义

1. 类型定义和变量声明分开

2. 类型定义的同时声明变量

使用typedef创建类型别名

结构体指针

结构体指针：结构体中的变量在内存中连续存放，结构体指针指向第一个变量。

type 指的是该结构体

type1 指的是结构体指针

访问成员变量：用“.”还是“->”？

通过结构体变量访问成员变量，用 “.”
通过结构体指针变量访问成员变量，用 “->”

函数：指针与函数

1．函数名是一个指针，保存函数地址入口。函数名是函数的入口地址。函数的入口地址称为函数指针。

传参–本质是创建副本

（1）实参与形参

（2）值传递，指针传递，引用传递
指针传递本质是值传递。
C语言无引用传递，引用传递是C++的。

函数调用–也可以理解为是创建副本

数据结构

数据结构：逻辑结构+存储结构

逻辑结构

线性逻辑结构：数据之间的关系是线性的（一对一）：线性表、栈、队列

非线性逻辑结构：树型结构（一对多）；图形结构（多对多）

存储结构

顺序存储：逻辑上相邻的元素，在存储器中的位置也是相邻的===》数组

链式存储：逻辑上相邻的元素，在存储器中的位置可以不相邻的，但是得实现逻辑上的相邻===》链表

索引存储，散列存储(Hash)

线性结构

如果⼀个数据元素序列满⾜：

1. 除第⼀个和最后⼀个数据元素外，每个数据元素只有⼀个前驱数据元素和⼀个后继数据元素；

2. 第⼀个数据元素没有前驱数据元素；

3. 最后⼀个数据元素没有后继数据元素；

我们称这样的结构就叫做 线性结构

顺序表

在计算机内存中，顺序表是以数组的形式保存的线性表。也就是⼀组地址连续的存储单元依次存储

数据元素的线性结构。

在数组中，我们会先申请⼀段连续的内存空间，然后把数组以此存⼊内存当中，中间没有⼀点空

隙。这就是⼀种顺序表存储数据的⽅式。对于顺序表的基本操作有：增（add），删（remove），改

（set），查（find），插（insert）。

代码

#include <iostream>
using namespace std;
#define MAXSIZE 100   //顺序表可能达到的最大长度
typedef struct {int* data;   //指针模拟开数组 int length;  //顺序表中元素实际个数
}SqList;
//初始化
SqList initial() {SqList s;s.data = (int*)malloc(sizeof(int)*MAXSIZE);if (s.data == NULL) { printf("内存分配失败！"); }s.length = 0;return s;
}
//增(顺序插入元素)
void add(SqList* L, int element) {//先判满if (L->length < MAXSIZE) {L->data[L->length] = element;L->length++;}else {printf("顺序表空间已满，不能插入！");}
}
//增(在指定下标插入元素)
void insert(SqList* L, int index, int element) {//先判满if (L->length < MAXSIZE) {//空出i下标位置，让其后数据往后移动for (int j = L->length - 1; j >= index; j--) {L->data[j + 1] = L->data[j];}L->data[index] = element;L->length++;}else {printf("顺序表空间已满，不能插入！");}
}
//查找，在线性表中查找元素element，若该元素不存在则，返回-1，存在则返回下标
int find(SqList* L, int element) {for (int i = 0; i < L->length; i++) {if (L->data[i] == element) {return i;}}return -1;
}
//删除指定元素element
void deleteList(SqList* L, int element) {int index = find(L, element);if (index == -1) {printf("被删除元素不存在");return;}for (int i = index; i < L->length; i++) {L->data[i] = L->data[i + 1];}L->length--;
}
//打印顺序表
void printSq(SqList L) {for (int i = 0; i < L.length; i++) {printf("%d ", L.data[i]);}printf("\n");
}
int main() {SqList L;L = initial();add(&L, 6);add(&L, 3);add(&L, 7);add(&L, 9);printSq(L);  //6 3 7 9insert(&L, 2, 1);  printSq(L);  // 6 3 1 7 9deleteList(&L, 9);printSq(L);  //6 3 1 7printf("%d", find(&L, 3));  // 1
}

优势

因为数据在数组中按顺序存储，可以通过数组下标直接访问，因此顺序表的查找定位元素很快。

劣势

插⼊和删除元素都需要⼤量的操作。

因为数组在声明的时候需要确定⻓度，因此顺序表的⻓度是确定的。若需要扩⼤顺序表⻓度，有

需要⼤量的操作，不够灵活。（要将该数组中的元素全部copy到另外⼀个数组）

由于数据⼤⼩的不可测性，有时会浪费掉⼤量的空间。

应⽤场景

总之，顺序表适⽤于那些不需要对于数据进⾏⼤量改动的结构。

顺序表的效率分析

综上所述，可以得出。顺序表对于插⼊、删除⼀个元素的时间复杂度是O(n)。

因为顺序表⽀持随机访问，顺序表读取⼀个元素的时间复杂度为O(1）。因为我们是通过下标访

问的，所以时间复杂度是固定的，和问题的规模⽆关。

最⼤的优点是空间利⽤率⾼。最⼤的缺点是⼤⼩固定。

单链表

概念

链表的每个节点只包含⼀个指针域。叫做单链表（即构成链表的每个节点只有⼀个指向后

继节点的指针）

头指针和头节点

单链表有带头节点和不带头节点两种结构。

链表中，第⼀个结点存储的位置叫头指针，如果链表有头结点，那么头指针就是指向头结

点的指针。

头指针所指的不存在数据元素的第⼀个结点就叫做头结点（⽽头结点⼜指向⾸元结点）。

头结点⼀般不放数据（有的时候也是放的，⽐如链表的⻓度，⽤做监视）。

存放第⼀个数据元素的结点叫做第⼀个数据元素结点，也叫做⾸元结点

带头结点的好处就是，⽅便对于链表的操作。对于空表、⾮空表的情况以及对于⾸元结点都可以

进⾏统⼀的处理。

不带头结点的单链表的插⼊操作

带头结点的单链表的插⼊操作

代码示例（带头节点）

#include <iostream>
using namespace std;
typedef struct Node {int data;      //数据域struct Node* next;      //指针域
}Node,*LinkList;//初始化
LinkList initial() {Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {cout << "分配内存失败！" << endl;exit(1);   //内存分配失败则退出程序}s->next = NULL;return s;
}//遍历单链表
void print(LinkList L) {Node* p = L->next;while (p != NULL) {cout << p->data<<" ";p = p->next;}cout << endl;
}//查找,查找指定元素的节点
Node* find(LinkList& L,int element) {Node* p = L->next;while (p != NULL) {if (p->data==element) {return p;}p = p->next;}cout << "查找失败！该元素不存在" << endl;return NULL;
}//头插
void head_insert(LinkList& L, int element) {Node* s = (Node*)malloc(sizeof(Node));  //申请一个节点s->data = element;   //把数据放入节点 s->next = L->next;L->next = s;
}//尾插
void rear_insert(LinkList&L, int element){Node* p = L->next;//遍历找出尾节点while(p!=NULL&&p->next!=NULL){p=p->next;}Node* s = (Node*)malloc(sizeof(Node));s->data = element;s->next =NULL;p->next = s;
}//中间插，在指定元素后插入元素
void middle_insert(LinkList& L, int elementUp ,int elementDown){Node* p = find(L,elementUp);if(p==NULL){cout<<"中间插入操作失败"<<endl;return;}Node* s = (Node*) malloc(sizeof(Node));s->data = elementDown;s->next = p->next;p->next = s;
}//删除
void deleteList(LinkList& L,int element){Node* p = L->next;Node* q =L;while(p!=NULL&&p->next!=NULL){//TODOif(p->data==element){break;}q=p;p=p->next;}if(q!=NULL&&p!=NULL){q->next = p->next;free(p);}
}
int main() {LinkList L = initial();head_insert(L, 1);head_insert(L, 3);head_insert(L, 6);cout<<"头插之后："<<endl;print(L);  //6 3 1rear_insert(L,9);rear_insert(L,0);cout<<"尾插之后："<<endl;print(L);  //6 3 1 9 0middle_insert(L,1,8);cout<<"中间插入之后："<<endl;print(L);  //6 3 1 8 9 0deleteList(L,1);cout<<"删除之后："<<endl;print(L);  //6 3 8 9 0
}

优劣势

优势

增删比顺序表高效

劣势

修查没顺序表高效

双向链表

代码实现(带头节点)

#include <iostream>
using namespace std;
//定义一个结构体，表示每个节点信息
typedef struct Node{int data;  //数据域struct Node* pre;  //指针域，指向前一个节点struct Node* next;  //指向后一个节点的地址
}Node,*LinkList;//初始化双链表
LinkList initial(){Node* s =(Node*)malloc(sizeof(Node));if(s==NULL){cout<<"初始化失败！"<<endl;exit(1);}s->next=s->pre=NULL;return s;
}//查找元素所在的节点
Node* find(LinkList& L, int element){Node* p = L->next;while(p!=NULL){if(p->data==element){return p;}p = p->next;}cout<<"你要查找的元素所在的节点不存在！"<<endl;return NULL;
}//遍历双链表
void print(LinkList L){Node* p = L->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;
}//头插
void head_insert(LinkList& L, int element){Node* s =(Node*) malloc(sizeof(Node));s->data = element;s->next = L->next;s->pre = L;L->next = s;if(s->next!=NULL){s->next->pre = s;}
}//尾插
void rear_insert(LinkList& L, int element){Node* p = L->next;while(p != NULL&&p->next!=NULL){p=p->next;}Node* s =(Node*)malloc(sizeof(Node));s->data = element;s->next = p->next;s->pre = p;p->next = s;}//中间插
void middle_insert(LinkList& L,int element1, int element){Node* p = L->next;Node* q = L;while(p!=NULL&&p->next!=NULL){if(p->data==element1){break;}q=p;p=p->next;}Node* s =(Node*)malloc(sizeof(Node));s->data = element;s->next = p;s->pre = q;q->next = s;p->pre = s;
}//删除指定元素的节点
void deleteLinkList(LinkList& L,int element){Node* s = find(L,element);Node* p = s->pre;p->next = s->next;if(s->next!=NULL){s->next->pre = p;}
}
int main(){//初始化LinkList L = initial();head_insert(L,1);head_insert(L,3);head_insert(L,6);print(L);  //6 3 1rear_insert(L,7);rear_insert(L,9);print(L);  //6 3 1 7 9middle_insert(L,1,8);print(L);  //6 3 8 1 7 9deleteLinkList(L,1);print(L);  //6 3 8 7 9
}

循环链表

代码实现（带头结点）

#include <iostream>
using namespace std;
//定义一个结构体，表示每个节点信息
typedef struct Node{int data;  //数据域struct Node* pre;  //指针域，指向前一个节点struct Node* next;  //指向后一个节点的地址
}Node,*LinkList;//初始化循环链表
LinkList initial(){Node* s =(Node*)malloc(sizeof(Node));if(s==NULL){cout<<"初始化失败！"<<endl;exit(1);}s->next=s->pre=s;return s;
}//查找元素所在的节点
Node* find(LinkList& L, int element){Node* p = L->next;while(p!=L){if(p->data==element){return p;}p = p->next;}cout<<"你要查找的元素所在的节点不存在！"<<endl;return NULL;
}//遍历双链表
void print(LinkList L){Node* p = L->next;while(p!=L){cout<<p->data<<" ";p=p->next;}cout<<endl;
}//头插
void head_insert(LinkList& L, int element){Node* s =(Node*) malloc(sizeof(Node));s->data = element;s->next = L->next;s->pre = L;L->next = s;s->next->pre = s;
}//尾插
void rear_insert(LinkList& L, int element){Node* p = L->next;while(p->next!=L){p=p->next;}Node* s =(Node*)malloc(sizeof(Node));s->data = element;s->next = p->next;s->pre = p;p->next = s;}//中间插
void middle_insert(LinkList& L,int element1, int element){Node* p = L->next;Node* q = L;while(p->next!=L){if(p->data==element1){break;}q=p;p=p->next;}Node* s =(Node*)malloc(sizeof(Node));s->data = element;s->next = p;s->pre = q;q->next = s;p->pre = s;
}//删除指定元素的节点
void deleteLinkList(LinkList& L,int element){Node* s = find(L,element);Node* p = s->pre;p->next = s->next;s->next->pre = p;
}
int main(){//初始化LinkList L = initial();head_insert(L,1);head_insert(L,3);head_insert(L,6);print(L);  //6 3 1rear_insert(L,7);rear_insert(L,9);print(L);  //6 3 1 7 9middle_insert(L,1,8);print(L);  //6 3 8 1 7 9deleteLinkList(L,1);print(L);  //6 3 8 7 9
}