数据结构

表

线性表

线性表是具有相同数据类型的 n个数据元素的有限序列（有次序），其中n为表长，当n=0时线性表是一个空表。

若用L命名线性表，则其一般表示为

L = {a1,a2,…,ai,ai+1,…,an}

几个概念：

ai是线性表中的“第i个”元素线性表中的位序。（位序从1开始，数组下标从0开始）

a1是 表头元素，an是表尾元素。

除了第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

什么时候要传入参数的引用“&”–对参数的修改结果需要“带回来”

“&”指向的是对象本身，不占用对象的存储空间，而指针本身是一个变量，是需要分配存储空间的，里面存储对象的地址，通过对象地址就能访问，操作对象。所以引用和指针都可以访问对象，作用是类似的。

顺序表

顺序表–用顺序表存储的方式实现线性表顺序存储。

存储结构：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

typedef struct{
  int num;//号数
  int people;//人数
} Customer;

如何知道一个数据元素大小？

sizeof(ElemType)

顺序表的静态分配

流程：

①在内存中分配存储顺序表L各个数据元素的连续存储空间。包括：MaxSize*sizeof（ElemType）和存储length的空间

②把各个数据元素的值设为默认值

③将Length的值设为0

#include<stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType data[MaxSize];//用静态的“数组”存放数据元素
    int length;//顺序表的当前长度
}SqList;       //顺序表的类型定义（静态分配方式）

//基本操作--初始化一个顺序表
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;//将所有数据元素设置为默认初始值
    L.length=0;//顺序表初始长度为0
}

int main(){
    SqList L; //声明一个顺序表
    InitList(L);//初始化顺序表
    //....未完待续，后续操作
    return 0;
}

//不初始化数据元素，内存不刷0

#include<stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType data[MaxSize];//用静态的“数组”存放数据元素
    int length;//顺序表的当前长度
}SqList;       //顺序表的类型定义（静态分配方式）

//基本操作--初始化一个顺序表
//没有设置数据元素的默认值，内存中会有遗留的“脏数据”
void InitList(SqList &L){
    L.length=0;//顺序表初始长度为0
}

int main(){
    SqList L; //声明一个顺序表
    InitList(L);//初始化顺序表
    //尝试“违规”打印出整个data数组
    for(int i =0;i<L.length;i++)
        printf("data[%d]=%d\n",i,L.data[i]);
    return 0;
}

顺序表的静态分配过程中，如果“数组”存满了怎么办？

可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的）

顺序表的动态分配

key：动态申请和释放内存空间

c —— malloc、free函数

#include<stdlib.h>//malloc、free函数的头文件
L.data = (ElemType *) malloc(sizeof(ElemType)* InitSize);   
//第一个(ElemType *)，强制转换成所定义的数据类型所对应的指针
//malloc用于申请一整片连续的内存空间，这整片连续的内存空间有一个起始的内存地址。
//malloc执行结束之后，会返回一个指向这整片存储空间开始地址的指针

c++ —— new、delete关键字

#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件
#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType *data;//指示动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length;  //顺序表的当前长度
}SqList;         //顺序表的类型定义（动态分配方式）

//基本操作--初始化一个顺序表
//没有设置数据元素的默认值，内存中会有遗留的“脏数据”
void InitList(SqList &L){
    L.length=0;//顺序表初始长度为0
}

//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){
    int *p = L.data;
    L.data = (int *) malloc(sizeof(int)* InitSize);     for(int i=0; i<L.length; i++){
        L.data[i]=p[i]; //将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;//顺序表最大长度增加len
    free(p);//释放原来的内存空间
}

int main(){
    SqList L; //声明一个顺序表
    InitList(L);//初始化顺序表
    //....往顺序表中随便插入几个元素....
    return 0;
}

顺序表的特点

①随机访问，即可以在O(1)时间内找到第i个元素。代码实现：data[i-1];静态分配、动态分配都一样。

②存储密度高，每个节点只存储数据元素。

③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

④插入、删除操作不方便，需要移动大量元素。

顺序表的插入

ListInsert(&L, i, e): 插入操作。在表L中的第i个位置上插入指定元素e。

void ListInsert(SqList &L, int i, int e){
    for(int j=L.length; j>=i; j--)//将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;//在位置i处放入e，数组是从0开始，注意位序
    L.length++;   //长度加1
}

好的算法，应该具有“健壮性”。能处理异常情况，并给使用者反馈。

#include<stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType data[MaxSize];//用静态的“数组”存放数据元素
    int length;//顺序表的当前长度
}SqList;       //顺序表的类型定义（静态分配方式）


bool ListInsert(SqList &L, int i, int e){
    if(i<1||i>L.length+1)//判断i的范围是否有效（注意i从1开始算起，其为位序）
        return false;
    if(L.length>=MaxSize)//当前存储空间已满，不能插入
        return false;
    for(int j=L.length; j>=i; j--)//将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;//在位置i处放入e，数组是从0开始，注意位序
    L.length++;   //长度加1
    return true;
}

int main()
{
    SqList L; //声明一个顺序表
    InitList(L);//初始化顺序表
    //...此处省略一些代码，插入几个元素
    ListInsert(L,3,3);
    return 0;
}

顺序表的删除

ListDelete(&L, i, &e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

#include<stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType data[MaxSize];//用静态的“数组”存放数据元素
    int length;//顺序表的当前长度
}SqList;       //顺序表的类型定义（静态分配方式）

bool ListDelete(SqList &L, int i, int &e){
    if(i<1||i>L.length) //判断i的范围是否有效
        return false;
    e=L.data[i-1]; //将被删除的元素赋值给e
    for(int j=i;j<L.length;j++)//将第i个位置后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;    //线性表长度减1
    return true;
}

int main()
{
    SqList L; //声明一个顺序表
    InitList(L);//初始化顺序表
    //...此处省略一些代码，插入几个元素
    int e = -1; //用变量“e“把删除的元素"带回来"
    if(ListInsert(L,3,e))
        printf("已删除第3个元素，删除元素值为=%d\n",e);
    else
        printf("位序i不合法，删除失败\n");
    return 0;
}

顺序表的查找

按位查找

//GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素值。
#include<stdio.h>
#define MaxSize 10 //定义最大长度
//typedef struct{
//    ElemType data[MaxSize];//用静态的“数组”存放数据元素
//    int length;//顺序表的当前长度
//}SqList;      //顺序表的类型定义（静态分配方式）

typedef struct{
    ElemType *data;//指示动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length;  //顺序表的当前长度
}SqList;         //顺序表的类型定义（动态分配方式）


ElemType GetElem(SqList L, int i){
    return L.data[i-1];
}

按值查找

//LocateElem(L,e):按值查找操作。在表L中，从第一个元素开始依次往后检索，查找第一个元素值等于e的元素，并返回其位序。
#include<stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
    ElemType *data;//指示动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length;  //顺序表的当前长度
}SqList;         //顺序表的类型定义（动态分配方式）

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, ElemType e){
    for(int i=0; i<L.length; i++)
        if(L.data[i]==e)
            return i+1; //数组下标为i的元素值等于e，返回其位序i+1
    return 0;//退出循环，说明查找失败
}

基本数据类型：int、char、double、float等可以直接用运算符”==“比较。

结构类型的比较

typedef struct{
    int num;
    int people;
} Customer;
//注意：c语言中，结构体的比较不能直接用”==“，需要依次对比各个分量来判断两个结构体是否相等。
bool isCustomerEqual(Customer a, Customer b){
    if(a.num == b.num && a.people == b.people)
        return true;
    else
        return false;
}

单链表

顺序表：每个结点中只存放数据元素

优点：可以随机存取，存储密度高。

缺点：要求大片连续空间，改变容量不方便。

单链表：每个结点除了存放数据元素外，还要存放指向下一个结点的指针。

优点：不要求大片连续空间，改变容量方便。

缺点：不可以随机存取，要耗费一定空间存放指针。

struct LNode{            //定义单链表节点类型(结点)
    ElemType data;       //每个节点存放下一数据元素(数据域)
    struct LNode *next;  //指针指向下一个结点(指针域)
};

struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));//增加一个新的节点：在内存中申请一个结点所需空间，并用指针p指向这个结点。

//typedef关键字--数据类型重命名
typedef<数据类型><别名>
typedef struct LNode LNode;
LNode* p = (LNode *)malloc(sizeof(LNode));

用代码定义一个单链表

typedef struct LNode{  //定义单链表结点类型
    ElemType data;     //每个结点存放一个数据元素
    struct LNode *next;  //指针指向下一个结点
}LNode, *LinkList;//结点，单链表（结点指针）

struct LNode{       // 定义单链表结点类型
    ElemType data;  // 每个结点存放一个数据元素
    struct LNode *next; // 指针指向下一个结点
};

LNode *GetElem(Linklist L, int i){
    int j=1;
    LNode *p = L->next;
    if(i==0)
        return L;
    if(i<1)
        return NULL;
    while(p!=NULL && j<i){
        p=p->next;
        j++;
    }
    return p;
}

typedef struct LNode LNode;
typedef struct LNode *LinkList;

//要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个结点
LNode *L; //声明一个指向单链表第一个结点的指针。强调这是一个结点。
或：
LinkList L;//声明一个指向单链表第一个结点的指针。强调这是一个单链表。

头插法建立单链表的算法如下：

LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
    LNode *s; 
    int x;
    L=(LinkList)malloc(sizeof(LNode));//创建头节点
    L->next=NULL;               //初始为空链表
    scanf("%d",&x);             //输入结点的值
    while(x!=9999){             //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));//创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;  //将新节点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

不带头节点的和带头节点的单链表

#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件

typedef struct LNode{ //定义单链表结点类型
    ElemType data;     //每个结点存放一个数据类型
    struct LNode *next; //指针指向下一个结点
}LNode, *LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;//空表，暂时还没有任何结点，防止脏数据
    return true;
}

//初始化一个单链表(带头结点)
bool InitList1(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));//分配一个头节点
    if(L = NULL)  //内存不足，分配失败
        return false;
    L->next = NULL; //头结点之后暂时还没有结点
    return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
    if(L==NULL)
        return true;
    else
        return false;
    //return (L==NULL)
}

void test(){
    LinkList L; //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    InitList1(L);
    //....后续代码....
}

不带头节点V.S.带头结点：

不带头节点，写代码更麻烦，对第一个数据结点和后续数据点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。

头结点是链表里面第一个结点，他的数据域可以不存放任何信息（有时候也会存放链表的长度等等信息），他的指针区域存放的是链表中第一个数据元素的结点（就是传说中的首元结点）存放的地址。

带头结点，写代码更方便，用过都说好。

单链表的查找

单链表的查找分为按位查找和按值查找。

注意：由于带头结点的方便写代码，我们统一使用”双链表“。

GetElem(L, i):按位查找操作。获取表L中第i个位置的元素的值。

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

按位查找

LNode * GetElem(LinkList L, int i){
    if(i<0)
        return NULL;
    LNode *p;//指针p指向当前扫描到的结点
    int j=0; //当前p指向的是第几个结点
    p=L;     //L指向头结点，头结点是第0个结点（不存数据）
    while(p!=NULL && j<i){
        p=p->next;
        j++;
    }
    return p;
}

//时间复杂度：O（n）

按值查找

//找到数据域==e的结点
LNode *LocateElem(LinkList L,ElemType e){
    LNode *p = L->next;
    //从第一个结点开始查找数据域为e的结点
    while(p != NULL && p->data !=e)
        p=p->next;
    return p; //找到后返回该结点的指针，否则返回NULL
}

//时间复杂度：O（n）

求表长度

int length(LinkList L){
    int len = 0; //统计表长
    LNode *p= L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

//时间复杂度：O（n）

注意：单链表不具备”随机访问“的特性，只能依次扫描。

单链表的插入

按位序插入（带头结点）

ListInsert(&L,i,e): 插入操作。在表L中的第i个位置（从1开始）上插入指定元素e。找到第i-1个结点，将新节点插入其后。

//在第i个位置插入元素e（带头结点）
//在表L中的第i个位置（从1开始）上插入指定元素e。找到第i-1个结点，将新节点插入其后。
//即找到第i-1个结点，放在其后面
//边界情况：①i<1,即在头结点位置插入，显然不满足；②i=1，即在结点后面插入，即i-1，第0个结点插入（头结点），可行；③i为最后一个位置，即找到i-1的位置插入

typydef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p; //指针p指向当前扫描到的结点
    int j=0;//当前p指向的第几个结点,(注意：若要插入到表尾，则p指向最后一个结点，当p==NULL时，报错)
    p = L;//L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; //将结点s连到p之后
    return true; //插入成功
}

按位序插入（不带头结点）

不存在第0个结点，因此i=1时需要特殊处理。

typydef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){  //插入第1个结点的操作与其他结点操作不同【不带头结点与带头结点的主要区别】
        LNode * s =(LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L=s;  //头指针指向新结点。
    }
    
    LNode *p; //指针p指向当前扫描到的结点
    int j=0;//当前p指向的第几个结点,(注意：若要插入到表尾，则p指向最后一个结点，当p==NULL时，报错)
    p = L;//L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL) //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; //将结点s连到p之后
    return true; //插入成功
}

结论：不带头结点写代码更不方便，推荐用带头结点。

指定结点的后插操作

#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e) {
    if (p == NULL)
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) //内存分配失败||某些情况下有可能分配失败（如内存不足）
        return false;
    s->data = e;  //用结点s保存数据元素e
    s->next = p->next;
    p->next = s;  //将结点s连到p之后
    return true;
}

指定结点的前插操作

#include<stdio.h>
#include<stdlib.h>//malloc、free函数的头文件
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;

//前插操作：在p结点之前插入元素e。前插操作方法，先用后插操作，然后两个结点数据调换即可实现
bool InsertPriorNode(LNode* p, ElemType e) {
    if (p == NULL)
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) //内存分配失败||某些情况下有可能分配失败（如内存不足）
        return false;
    s->next = p->next;
    p->next = s;  //新结点s连到p之后
    s->data=p->data; //将p中元素复制到s中
    p->data=e;     //p中元素覆盖为e
    return true;
}

按位序删除（带头结点）

ListDelete(&L, i, &e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

头结点可以看成是”第0个“结点。

找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。

bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1)
        return false;
    LNode *p;//指针p指向当前扫描到的结点
    int j=0; //当前p指向的是第几个结点
    p=L;     //L指向头结点，头结点是第0个结点(不存数据)
    while(p!=NULL && j<i-1){// 循环找到第i-1个结点
        p = p -> next;
        j++;
    }
    if(p==NULL) //i值不合法
        return false;
    if(p->next == NULL) //第i-1个结点之后已无其他结点
        return false;
    LNode *q = p->next;//令q指向被删除结点
    e = q->data; //用e返回元素的值
    p->next=q->next; //将*q结点从链中“断开”
    free(q);
    return true;  //删除成功
    
 
}

单链表

#define _crt_secure_no_warnings
#include <stdio.h>
#include <stdlib.h>

/******************单链表**************************/

typedef struct LNode {  //定义单链表结点类型
	int data;     //每个结点存放一个数据元素
	struct LNode* next;  //指针指向下一个结点
}LNode, * LinkList;//结点，单链表（结点指针）

//初始化一个空的单链表(不带头结点)
bool InitList(LinkList& L) {
	L = NULL;//空表，暂时还没有任何结点，防止脏数据
	return true;
}

//初始化一个单链表(带头结点)
bool InitList1(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
	if (L = NULL)  //内存不足，分配失败
		return false;
	L->next = NULL; //头结点之后暂时还没有结点
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
	//return (L==NULL)
}

//求表长度
int length(LinkList L) {
	int len = 0; //统计表长
	LNode* p = L;
	while (p->next != NULL) {
		p = p->next;
		len++;
	}
	return len;
}

//按位查找
LNode* GetElem(LinkList L, int i) {
	if (i < 0)
		return NULL;
	LNode* p;//指针p指向当前扫描到的结点
	int j = 0; //当前p指向的是第几个结点
	p = L;     //L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}
	return p;
}

//按值查找，找到数据域==e的结点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;
	//从第一个结点开始查找数据域为e的结点
	while (p != NULL && p->data != e)
		p = p->next;
	return p; //找到后返回该结点的指针，否则返回NULL
}

//在第i个位置插入元素e（带头结点）
//在表L中的第i个位置（从1开始）上插入指定元素e。找到第i-1个结点，将新节点插入其后。
//即找到第i-1个结点，放在其后面
//边界情况：①i<1,即在头结点位置插入，显然不满足；②i=1，即在结点后面插入，即i-1，第0个结点插入（头结点），可行；③i为最后一个位置，即找到i-1的位置插入
bool ListInsertH(LinkList& L, int i, int e) {
	if (i < 1)
		return false;
	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)//i值不合法
		return false;
	LNode *s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//按位序插入，不带头结点
bool ListInsert(LinkList& L, int i, int e) {

	if (i < 1) {
		return false;
	}

	if (i == 1) {
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
	}

	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
		
	if (p == NULL)
		return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

/*指定结点的前插操作*/
bool InsertPriorNode(LNode* p, int e)
{
	if (p == NULL) {
		return false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->next = p->next;
	p ->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}
/*指定结点的后插操作*/
bool InsertNextNode(LNode* p, int e)
{
	if (p == NULL)
		return false;

	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
/* 按位序删除（带头结点）
ListDelete(&L, i, &e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
头结点可以看成是”第0个“结点。
找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。*/
bool ListDelete(LinkList&L, int i, int& e) {
	if (i < 1)
		return false;
	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode* q;
	q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}
bool DeleteNode(LNode* p) {
	if (p == NULL)
		return false;
	LNode* q;
	q = p->next;
	p->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
}

双链表

/**********************双链表*********************************/

typedef struct DNode { //定义双链表结点类型
	int data;          //数据域
	struct DNode* prior, * next;  //前驱和后继指针
}DNode, * DLinkList;

//初始化双链表
bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode)); //分配一个头结点
	if (L == NULL) //内存不足，分配失败
		return false;
	L->prior = NULL;//头结点的prior永远指向NULL
	L->next = NULL;//头结点之后暂时还没有结点
	return true;
}

//判断双链表是否为空（带头结点）
bool Empty(DLinkList L) {
	if (L->next == NULL)
		return true;
	else
		return false;
}

//在p结点之后插入s结点
bool InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL)//非法参数
		return false;
	s->next = p->next;//将结点*s插入到结点*p之后
	if (p->next != NULL)//如果p结点有后继结点
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

//删除p结点的后继节点
bool DeleteNextDNode(DNode* p) {
	if (p == NULL)
		return false;
	DNode* q;
	q = p->next; //找到p的后继节点q
	if (q == NULL)
		return false; //p没有后继节点
	p->next = q->next;
	if (q->next != NULL) //q结点不是最后一个结点
		q->next->prior = p;
	free(q); //释放结点空间
	return true;

}

void DestoryList(DLinkList& L) {
	//循环释放各个数据点
	while (L->next != NULL)
		DeleteNextDNode(L);
	free(L); //释放头结点
	L = NULL; //头指针指向NULL
}

void testDLinkList() {
	//初始链表
	DLinkList L;
	InitDLinkList(L);
	//后续代码
}

循环单链表

#define _crt_secure_no_warnings
#include <stdio.h>
#include <stdlib.h>
/*************************1、循环单链表**********************************************/
typedef struct LNode {
	int  data;
	struct LNode* next;
}LNode, * LinkList;

//初始化一个循环单链表
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode)); //分配一个头结点
	if (L == NULL)  //内存不足，分配失败
		return false;
	L->next = L;    //头结点next指向头结点
	return true;
}

//判断循环单链表是否为空
bool Empty(LinkList L) {
	if (L->next == L)
		return true;
	else
		return false;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode* p) {
	if (p->next == L)
		return true;
	else
		return false;
}

循环双链表

/*************************2、循环双链表**********************************************/

typedef struct DNode { //定义双链表结点类型
	int data;          //数据域
	struct DNode* prior, * next;  //前驱和后继指针
}DNode, * DLinkList;


//初始化空的循环双链表
bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode)); //分配一个头结点
	if (L == NULL)   //内存不足，分配失败
		return false;
	L->prior = L; //头结点的prior指向头结点
	L->next = L; //头结点的next指向头结点
	return true;
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(DLinkList L, DNode* p) {
	if (p->next == L)
		return true;
	else
		return false;
}

//在p结点之后插入s结点
bool InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL)
		return false;
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

//删除p的后继结点q
bool DeleteNextDNode(DLinkList L, DNode* p) {
	DNode *q;
	q = p->next;
	if (q == L)
		return false;
	p->next = q->next;
	q->next->prior = p;
	free(q);
	return true;
}

栈

只允许在一端进行插入或删除操作的线性表；一种操作受限的线性表，只能在栈顶插入、删除；

特点：先进后出；

术语：栈顶、栈底、空栈；

注意：初始化栈，需要分配内存空间；销毁栈，需要设防栈的内存空间。

队列

/*
* 栈Stack：是只允许在一端进行插入或删除操作的线性表
* 队列Queue：是只允许在一端进行插入，在另一端删除的线性表
* 特点：先进先出
*/
#include<stdio.h>
#include<stdlib.h>

#define MaxSize 10  //定义队列中元素的最大个数

typedef struct {
	int data[MaxSize]; //用静态数组存放队列元素
	int front, rear;   //队头指针（指向队头元素）和队尾指针（指向队尾元素的后一个位置，下一个应该插入的位置）
}SqQueue;

//初始化队列
void InitQueue(SqQueue& Q) {
	//初始时  队头、队尾指针指向0
	Q.rear = 0;
	Q.front = 0;
	Q.size = 0;
}

//判断队列是否为空：  队尾指针==队头指针时，队列为空
bool QueueEmpty(SqQueue Q) {
	if (Q.rear == Q.front) //队空条件
		return true;
	else
		return false;
}

//入队，只能从队尾入队：
bool EmQueue(SqQueue& Q, int x) {
	if (Q.size == MaxSize)
		return false;      //队满则报错
	Q.data[Q.rear] = x;    //新元素插入队尾
	Q.rear = (Q.rear + 1) % MaxSize;  //队尾指针加1取模，当队尾指针达到数组的末尾时，将其回到数组的开头，使得队列可以继续从头部插入元素。
}

/************************循环队列**********************************/
//用模运算将存储空间在逻辑上变成了“环状”


//判断队列是否为空
bool QueueEmpty(SqQueue Q) {
	if (Q.rear == Q.front)  //队空条件：队尾指针==队头指针
		return true; 
	else
		return false;
}

//入队
bool EnQueue(SqQueue& Q, int x) {
	if ((Q.rear + 1) % MaxSize == Q.front)
		return false;   //队满则报错，队列已满的条件：队尾指针的再下一个位置是队头，其代价是牺牲一个存储单元
	Q.data[Q.rear] = x;  //新元素插入队尾
	Q.rear = (Q.rear + 1) % MaxSize; //队尾指针加1取模，用模运算将存储空间在逻辑上变成了“环状”
	return true;
}

//出队，删除一个队头元素，并用x返回
bool DeQue(SqQueue& Q, int& x) {
	if (Q.rear == Q.front) //判断队空
		return false; //队空则报错
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize; //队头指针后移
	return true;
}

//获得队头元素的值，用x返回
bool GetHead(SqQueue Q, int& x){
	if (Q.rear == Q.front)
		return false;  //队空则报错
	x = Q.data[Q.front];
	return true;
}



//判断队列已满、已空的方法
/*
* 方案一：牺牲一个存储单元
*        队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear + 1) % MaxSize = Q.front;
*        队空条件：Q.rear = Q.front
* 方案二：增减辅助变量tag、size
*    ①增加辅助变量size
*        队满条件：Q.size = MaxSize
*        队空条件：Q.size = 0
*    ②增加辅助变量tag
*        每次删除操作成功时，都令Q.tag = 0；每次插入操作成功时，都令Q.tag = 1；
*        只有删除操作才导致队空，只有插入操作才可能导致队满；
*        队满条件： front == rear && tag = 1
*        队空条件： front == rear && tag = 0
*        
*/
#define MaxSize 10  //定义队列中元素的最大个数
typedef struct {
	int data[MaxSize]; //用静态数组存放队列元素
	int front, rear;   //队头指针（指向队头元素）和队尾指针（指向队尾元素的后一个位置，下一个应该插入的位置）
	int size; //队列当前长度
}SqQueue;

队列的链式实现

#include<stdio.h>
#include<stdlib.h>

typedef struct LinkNode {   //链式队列结点
	int data;
	struct LinkNode* next;
}LinkNode;

typedef struct {             //链式队列
	LinkNode* front, * rear; //队列的队头和队尾指针
}LinkQueue; 

//初始化（带头结点）
void InitQueue(LinkQueue& Q) {
	//初始时 front。rear都指向头结点
	Q.front = (LinkNode*)malloc(sizeof(LinkNode));
	Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
	Q.rear->next = NULL;
}

//判断队列是否为空（带头结点）
bool IsEmpty(LinkQueue Q) {
	if (Q.front == Q.rear)
		return true;
	else
		return false;
}

//入队（带头结点）
void EnQueue(LinkQueue& Q, int x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s; //新结点插入到rear之后
	Q.rear = s;  //修改表尾指针
}

//出队（带头结点），队头元素出队
bool Dequeue(LinkQueue& Q, int& x) {
	if (Q.front == Q.rear)
		return false; //空队
	LinkNode* p = Q.front->next;
	x = p->data;  //用变量x返回队头元素
	Q.front->next = p->next; //修改头结点的next指针
	if (Q.rear == p) //此次是最后一个结点出队
		Q.rear = Q.front; //修改rear指针
	free(p);   //释放结点空间
	return true;
}


//初始化（不带头结点）
void InitQueue(LinkQueue& Q) {
	//初始时 front。rear都指向头结点
	Q.front->next = NULL;
	Q.rear->next = NULL;
}

//判断队列是否为空（不带头结点）
bool IsEmpty(LinkQueue Q) {
	if (Q.front == NULL)
		return true;
	else
		return false;
}

//入队（不带头结点）
void EnQueue(LinkQueue& Q, int x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if (Q.front == NULL) { //在空队列中插入第一个元素
		Q.front = s;       //修改队头队尾指针
		Q.rear = s;        //不带头结点的队列，第一个元素入队时，需要特别处理
	}
	else {
		Q.rear->next = s; //新结点插入到rear结点之后
		Q.rear = s;  //修改rear队尾指针
	}
	
}


//出队（不带头结点），队头元素出列
bool Dequeue(LinkQueue& Q, int& x) {
	if (Q.front == NULL)
		return false; //空队
	LinkNode* p = Q.front; //p指向此次出队的结点
	x = p->data;  //用变量x返回队头元素
	Q.front = p->next; //修改front指针
	if (Q.rear == p) { //此次是最后一个结点出队
		Q.front = NULL; //Q.front指向NULL
		Q.rear = NULL; //Q.front指向NULL
	}
	free(p);   //释放结点空间
	return true;
}

//队满条件
/*
* 顺序存储--预分配的空间耗尽时队满
* 链式存储--一般不会队满，除非内存不足 
*/

数据结构C

数据结构

表

线性表

顺序表

顺序表的静态分配

顺序表的动态分配

顺序表的特点

顺序表的插入

顺序表的删除

顺序表的查找

结构类型的比较

单链表

单链表的查找

单链表的插入

指定结点的后插操作

指定结点的前插操作

按位序删除（带头结点）

单链表

双链表

循环单链表

循环双链表

栈

队列

队列的链式实现

相关文章

如何使用Python三方库CCXT

数组前缀和

gitlab代码merge或push事件触发jenkins job

单例模式（java）

doris回归测试

前端需要知道的三个不常用的函数式编程范式

【问题总结】Docker环境下备份和恢复postgresql数据库

Jenkins (一)