1 线性表

[1] 线性表

逻辑结构

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

[1-1] 顺序线性表

特点

随机访问，可以在 O(1)时间内找到第 i 个元素。
存储密度高，每个节点只存储数据元素
拓展容量不方便
插入、删除操作不方便，需要移动大量元素

[1-1-1] 静态表

{0} 结构体定义

//顺序表的实现--静态分配
#include<stdio.h>
#define MaxSize 10   // 定义表的最大长度

typedef struct{
	int data[MaxSize];// 用静态的"数组"存放数据元素
	int length; // 顺序表的当前长度
}SqList;        // 顺序表的类型定义（静态分配方式）

{0-1} 初始化

void InitList(SqList &L){
	 for(int i=0;i<MaxSize;i++){
	 	L.data[i]=0;  //将所有数据元素设置为默认初始值
	 }
	 L.length=0;
}

{0-1-1} main 操作

int main(){
	SqList L;//声明一个顺序表
	InitList(L);//初始化一个顺序表
	for(int i=0;i<MaxSize;i++){
		printf("data[%d]=%d\n",i,L.data[i]);
	}
	return 0;
}

{1-1-1} 插入操作

平均时间复杂度 O(n)

bool ListInsert(SqList &L, int i, int e){
    // 判断i的范围是否有效
    if(i<1||i>L.length+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
    L.length++;		// 长度加1
    return true;
}

{2-1-1}删除操作

平均时间复杂度 O(n)

bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数
    //判断i的范围是否有效
    if(i<1||i>L.length)
        return false;

    e = L.data[i-1]    //将被删除的元素赋值给e

    for(int j=L.length; j>=i; j--){    //将第i个后的元素前移
        L.data[j-1]=L.data[j];
    }
    L.length--;      //长度减1
    return true;
}

使用引用参数而不是使用函数返回值的方法的好处：
多值返回：C语言的函数只能有一个返回值。如果需要返回多个值，可以通过引用参数来实现。例如，一个函数可能需要返回一个数组的大小和数组的总和，这时可以将数组的大小通过指针参数返回。
大结构体返回：如果函数需要返回一个大型结构体，使用指针参数可以避免复制整个结构体的开销，提高效率。
数组返回：C语言的函数不能直接返回数组，但可以通过返回指向数组的指针来实现。
避免复制开销：对于较大的数据结构，如果通过值返回，C语言会进行复制操作，这可能导致性能问题。使用指针参数可以避免这种复制。
可变数据：通过指针参数，函数可以修改传入的数据，使其成为可变参数，这在某些情况下非常有用。
链表和树结构：在处理链表和树这样的复杂数据结构时，使用指针可以方便地返回新创建的节点或子树。
错误处理：指针参数可以用来指示函数是否成功执行，例如，如果指针参数被设置为NULL，则可能表示函数执行失败。
从软件工程角度看有如下好处：

模块化：软件设计强调模块化，即系统的各个部分应该是独立的，并且只通过定义良好的接口进行通信。使用指针参数可以减少模块间的耦合度，因为模块不需要知道返回数据的具体内容，只需要知道如何通过指针访问数据。
封装性：封装是隐藏对象的实现细节，只暴露操作接口的原则。通过使用指针参数，函数可以返回指向数据的引用，而不需要暴露数据的具体存储细节。
数据抽象：在面向对象的设计中，数据抽象是一种将数据和操作封装在一起的方法。使用指针参数可以返回一个对象的引用，而不是对象的副本，这样可以保持数据的完整性和一致性。
资源管理：在软件体系结构中，资源管理是一个关键问题。使用指针参数可以更有效地管理内存和其他资源，因为调用者可以控制数据的生命周期，避免不必要的复制和潜在的内存泄漏。
性能优化：在性能敏感的应用中，减少数据复制可以显著提高效率。通过指针参数，可以避免在函数调用过程中复制大型数据结构，从而减少CPU和内存的使用。
灵活性和扩展性：使用指针参数可以提供更大的灵活性，因为调用者可以选择如何存储和处理返回的数据。此外，这种设计也使得系统更容易扩展，因为添加新的数据类型或修改现有类型不会影响使用这些类型的函数。
错误处理：在某些情况下，使用指针参数可以提供更灵活的错误处理机制。例如，如果函数无法成功执行并生成所需的数据，它可以将指针设置为NULL，调用者可以检查这个指针来确定函数是否成功。
接口一致性：在某些情况下，使用指针参数可以保持API的一致性。例如，如果一个库或框架的多个函数都需要返回复杂的数据结构，使用指针参数可以确保所有这些函数都有一致的接口。

待整理

{3-1} 按位查找

(获取 L 表中第i个位置的值)
平均时间复杂度 O(1)

ElemType GetElem(SqList L, int i){
    // ...判断i的值是否合法
    return L.data[i-1];      //注意是i-1
}

{3-2} 按值查找

平均时间复杂度 O（n）

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

[1-2-1] 单链表

带不带头节点的区别

头结点：代表链表上头指针指向的第一个结点，不带有任何数据。

区别：

不带头结点：
- 写代码麻烦！
- 对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑
- 头指针指向的结点用于存放实际数据;
带头结点：
- 头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据

{0} 结构体定义

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

[1-2-1-0] 无头结点单链表

{0-1} 初始化

//初始化一个空的单链表
//注意用引用 &
bool InitList(LinkList &L){
	L = NULL; //空表，暂时还没有任何结点；
	return true;
}

{0-1-1}main 操作

void test(){
	LinkList L; //声明一个指向单链表的指针: 头指针
	//初始化一个空表
	InitList(L);
	//...
}

{1-1-1} 按位序插入

ListInsert(&L, i, e)

在表 L 中的第i个位置上插入指定元素 e = 找到第i-1个结点(前驱结点)，将新结点插入其后; 因为不带头结点，所以不存在“第 0 个”结点，因此！i=1 时，需要特殊处理——插入(删除)第 1 个元素时，需要更改头指针 L;

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

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;

    //插入到第1个位置时的操作有所不同！
    if(i==1){
        LNode *s = (LNode *)malloc(size of(LNode));
        s->data =e;
        s->next =L;
        L=s;          //头指针指向新结点
        return true;
    }

    //i>1的情况与带头结点一样！唯一区别是j的初始值为1
    LNode *p;       //指针p指向当前扫描到的结点
    int j=1;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    if (p==NULL)                 //i值不合法
        return false;

    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;

}

{5-2} 判空

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

[1-2-1-1] 带头结点单链表

{0-1} 初始化

//初始化一个单链表（带头结点）
bool InitList(LinkList &L){
    L = (LNode*) malloc(sizeof(LNode));  //头指针指向的结点——分配一个头结点（不存储数据）
    if (L == NULL)          //内存不足，分配失败
        return false;
    L -> next = NULL;       //头结点之后暂时还没有结点
    return true;
}

{0-1-1} main 函数操作

void test(){
    LinkList L;  //声明一个指向单链表的指针: 头指针
    //初始化一个空表
    InitList(L);
    //...
}

{1-1-1} 按位序插入

平均时间复杂度：O(n)
带头结点操作
ListInsert(&L, i, e)

在表 L 中的第i个位置上插入指定元素e

找到第i-1个结点(前驱结点)，将新结点插入其后

其中头结点可以看作第 0 个结点，故i=1时也适用

// 在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e)
{
	// 判断i的合法性, i是位序号(从1开始)
	if (i < 1)
		return False;

	LNode *p;  // 指针p指向当前扫描到的结点
	int j = 0; // 当前p指向的是第几个结点
	p = L;	   // L指向头结点，头结点是第0个结点（不存数据）

	// 循环找到第i-1个结点
	while (p != NULL && j < i - 1)
	{				 // 如果i>lengh, p最后会等于NULL
		p = p->next; // p指向下一个结点
		j++;
	}

	if (p == NULL) // i值不合法
		return false;

	// 在第i-1个结点后插入新结点
	LNode *newnode = (LNode *)malloc(sizeof(LNode)); // 申请一个结点
	newnode->data = e;
	newnode->next = p->next;
	p->next = newnode;

	return true;
}

{1-2-2} 指定结点的后插

InsertNextNode(LNode *p, ElemType e)

给定一个结点 p，在其之后插入元素 e

根据单链表的链接指针只能往后查找，故给定一个结点 p，那么 p 之后的结点我们都可知，但是 p 结点之前的结点无法得知

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;
}                         //平均时间复杂度 = O(1)


//有了后插操作，那么在第i个位置上插入指定元素e的代码可以改成：
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return False;

    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后4鸟会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    return InsertNextNode(p, e)
}

{1-2-1} 指定结点的前插

设待插入结点是newnode，将newnode插入到p的前面。

将newnode插入到p的后面。然后将p->data与newnode->data交换

时间复杂度为 O(1)

//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElenType e){
    if(p==NULL)
        return false;

    LNode *newnode = (LNode *)malloc(sizeof(LNode));
    if(newnode == NULL) // 内存分配失败
        return false;

    newnode->next = p->next;
    p->next = newnode;       // 新结点newnode连到p之后
    newnode->data = p->data; // 将p中元素复制到newnode
    p->data = e;       // p中元素覆盖为e

    return true；
}

若新的节点已经生成，则在指定结点的前插节点

bool InsertPriorNode(LNode *p, LNode *s){
    if(p==NULL || S==NULL)
        return false;

    s->next = p->next;
    p->next = s;  ///s连接到p
    ELemType temp = p->data;  //交换数据域部分
    p->data = s->data;
    s->data = temp;

    return true;
}

{1-3-1} 头插

平均时间复杂度 O(1)
每次都将生成的结点插入到链表的表头。

LinkList List_HeadInsert(LinkList &L, ElenType e)
{
	s = (LNode *)malloc(sizeof(LNode)); // 创建新结点
	s->data = e;
	s->next = L->next;
	L->next = s;
	return L;
}

{1-3-2} 尾插

时间复杂度 O（1）
每次将新节点插入到当前链表的表尾，所以必须增加一个尾指针 r,使其始终指向当前链表的尾结点。
生成的链表中结点的次序和输入数据的顺序会一致。

// 尾插法建立正向单链表
LinkList List_TailInsert(LinkList &L){
    int x;                                   //设ElemType为整型int
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)
    LNode *s, *r = L;                        //r为表尾指针
    scanf("%d", &x);                         //输入要插入的结点的值
    while(x!=9999){                          //输入9999表结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s                                //r指针指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;                          //尾结点指针置空
    return L;
}

{2-1-1} 按位序删除节点

带头结点
ListDelete(&L, i, &e)
平均时间复杂度：O(n)（最坏 O(n)最好 O(1)）
思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点

删除操作，删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值

头结点视为“第 0 个”结点

bool ListDelete(LinkList &L, int i, ElenType &e)
{
	if (i < 1)
		return false;

	LNode *p;  // 指针p指向当前扫描到的结点
	int j = 0; // 当前p指向的是第几个结点
	p = L;	   // L指向头结点，头结点是第0个结点（不存数据）

	// 循环找到第i-1个结点
	while (p != NULL && j < i - 1)
	{				 // 如果i>lengh, p最后会等于NULL
		p = p->next; // p指向下一个结点
		j++;
	}

	if (p == NULL)
		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;
}

{2-2-1} 指定结点的删除

bool DeleteNode(LNode *p){
    if(p == NULL)
        return false;

    LNode *q = p->next;      // 令q指向*p的后继结点
    p->data = p->next->data; // 让p和后继结点交换数据域
    p->next = q->next;       // 将*q结点从链中“断开”
    free(q);
    return true;
} //时间复杂度 = O(1)

如果他没有后继节点，是不是就要遍历一遍了

{3-1} 按位查找

平均时间复杂度 O（n）
GetElem(L, i)

按位查找操作，获取表 L 中第 i 个位置的元素的值;

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){  //循环找到第i个结点
        p = p->next;
        j++;
    }

    return p;               //返回p指针指向的值
}

{3-2} 按值查找

LocateElem(L, e)

// 按值查找操作，在表L中查找具有给定关键字值的元素;
LNode* LocateElem(LinkList L, ElemType e){
    LNode *P = L->next;    // p指向第一个结点
    // 从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data != e){
        p = p->next;
    }
    return p;           // 找到后返回该结点指针，否则返回NULL
}

{5-1} 求单链表的长度

时间复杂度为 O(n)
Length(LinkList L)

计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点

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

{5-2} 判空

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

{6-1} 链表的逆置

逆置链表初始为空，原表中结点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），直至原链表为空；

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;     //p指针指向第一个结点
	L->next = NULL;  //头结点指向NULL

	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;
		L->next = q;
	}
	return L;
}

[1-2-1-2] 循环单链表

单链表和循环单链表的比较

单链表：
- 从一个结点出发只能找到该结点后续的各个结点
- 对链表的操作大多都在头部或者尾部
- 设立头指针，从头结点找到尾部的时间复杂度=O(n)，即对表尾进行操作需要 O(n)的时间复杂度;
循环单链表：
- 从一个结点出发，可以找到其他任何一个结点
- 设立尾指针，从尾部找到头部的时间复杂度为 O(1)，即对表头和表尾进行操作都只需要 O(1)的时间复杂度
- 优点：从表中任一节点出发均可找到表中其他结点。
- 最后一个结点的指针不是 NULL,而是指向头结点

{0}

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}DNode, *Linklist;

{0-1}

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

{3-3-2} 判是否为表尾

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

{5-2}

//判断循环单链表是否为空（终止条件为p或p->next是否等于头指针）
bool Empty(LinkList L){
    if(L->next == L)
        return true;    //为空
    else
        return false;
}

[1-2-1-4] 静态链表

定义

单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址);
静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素 and 下一个结点的数组下标(游标)
- 其中数组下标为 0 的结点充当"头结点"
- 游标为-1表示已经到达表尾
- 若每个数据元素为 4B，每个游标为 4B，则每个结点共 8B；假设起始地址为addr，则数据下标为 2 的存放地址为：addr+8*2
- 注意：数组下标——物理顺序，位序——逻辑顺序；
- 优点：增、删操作不需要大量移动元素；
- 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

{0(-1-1)} - 1 结构体定义并使用的一种方式

#define MaxSize 10        //静态链表的最大长度

struct Node{              //静态链表结构类型的定义
    ElemType data;        //存储数据元素
    int next;             //下一个元素的数组下标(游标)
};
//用数组定义多个连续存放的结点
void testSLinkList(){
    struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node
    //...
}

{0(-1-1)} - 2

#define MaxSize 10        //静态链表的最大长度

typedef struct{           //静态链表结构类型的定义
    ELemType data;        //存储数据元素
    int next;             //下一个元素的数组下标
}SLinkList[MaxSize];

void testSLinkList(){
    SLinkList a;// 这里实际上定义了一个长度为MaxSize的数组
}

{0(-1-1)} - 3

#define MaxSize 10        //静态链表的最大长度

struct Node{              //静态链表结构类型的定义
    ElemType data;        //存储数据元素
    int next;             //下一个元素的数组下标(游标)
};

typedef struct Node SLinkList[MaxSize]; //重命名struct Node，用SLinkList定义“一个长度为MaxSize的Node型数组;

注意：SLinkList a 强调 a 是静态链表；struct Node a 强调 a 是一个 Node 型数组；

{0-1}

初始化静态链表：把a[0]的next设为-1

{1-1-1}

在位序为i上插入结点：
1. 找到一个空的结点，存入数据元素
2. 从头结点出发找到位序为i-1的结点
3. 修改新结点的next
4. 修改i-1号结点的next

{2-1-1}

删除某个结点：
1. 从头结点出发找到前驱结点
2. 修改前驱节点的游标
3. 被删除节点next设为-2

{3-1}按位序查找

查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序）的结点：
从头结点出发挨个往后遍历结点
时间复杂度为 O(n)

[1-2-2] 双链表

{0}

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

{0-1}

（带头结点）

typedef struct DNode{            //定义双链表结点类型
    ElemType 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;
}

void testDLinkList(){
    //初始化双链表
    DLinklist L;         // 定义指向头结点的指针L
    InitDLinkList(L);    //申请一片空间用于存放头结点，指针L指向这个头结点
    //...
}

//判断双链表是否为空
bool Empty(DLinklist L){
    if(L->next == NULL)    //判断头结点的next指针是否为空
        return true;
    else
        return false;
}

{1-2-2}

InsertNextDNode(p, s)

在 p 结点后插入 s 结点

bool InsertNextDNode(DNode *p, DNode *s){ //将结点 *s 插入到结点 *p之后
    if(p==NULL || s==NULL) //非法参数
        return false;

    s->next = p->next;
    if (p->next != NULL)   //p不是最后一个结点=p有后继结点
        p->next->prior = s;
    s->prior = p;
    p->next = s;

    return true;
}

{1-1-1}

思路：从头结点开始，找到某个位序的前驱结点，对该前驱结点执行后插操作；

{1-2-1}

思路：找到给定结点的前驱结点，再对该前驱结点执行后插操作；

{2-2-2}

删除 p 节点的后继节点

//删除p结点的后继结点
bool DeletNextDNode(DNode *p){
    if(p==NULL) return false;
    DNode *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;
}

{2-4} 清空双链表

//销毁一个双链表
bool DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while(L->next != NULL){
        DeletNextDNode(L);  //删除头结点的后继结点
    free(L); //释放头结点
    L=NULL;  //头指针指向NULL

    }
}

{5-1}后向遍历

while(p!=NULL){
    //对结点p做相应处理，eg打印
    p = p->next;
}

{5-2}前向遍历

while(p!=NULL){
    //对结点p做相应处理，eg打印
    p = p->prior;
}

概要

在这里插入图片描述

[1-2-2-2] 循环双链表

基本概念

和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。

在这里插入图片描述

表头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点

{0}

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior, *next;
}DNode, *DLinklist;

{0-1}

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

{1-2-1}插入

bool InsertNextDNode(DNode *p, DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;

{2-2-2}删除

//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);

{3-3-2}判尾

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

{5-2}判空

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

顺序表和链表的比较

1.逻辑结构

顺序表和链表都属于线性表，都是线性结构

2.存储结构

顺序表：顺序存储
- 优点：支持随机存取，存储密度高
- 缺点：大片连续空间分配不方便，改变容量不方便
链表：链式存储
- 优点：离散的小空间分配方便，改变容量方便
- 缺点：不可随机存取，存储密度低

3. 基本操作 - 创建

顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源；
- 静态分配：静态数组，容量不可改变
- 动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（malloc(),free()）
链表：只需要分配一个头结点或者只声明一个头指针

4. 基本操作 - 销毁

顺序表：修改 Length = 0

静态数组——系统自动回收空间

typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
}SeqList;

动态分配：动态数组——需要手动 free()

//创
L.data = (ELemType *)malloc(sizeof(ElemType) *InitSize)
//销
free(L.data);

//！malloc() 和 free() 必须成对出现

5.基本操作-增/删

顺序表
- 插入/删除元素要将后续元素后移/前移
- 时间复杂度=O(n)
- 时间开销主要来自于移动元素
链表
- 插入/删除元素只需要修改指针
- 时间复杂度=O(n)
- 时间开销主要来自查找目标元素

6.基本操作-查

顺序表
- 按位查找：O(1)
- 按值查找：O(n)，若表内元素有序，可在 O(log2n)时间内找到
链表
- 按位查找：O(n)
- 按值查找：O(n)

顺序/链式/静态/动态比较

四种存储方式的

顺序存储的固有特点：逻辑顺序与物理顺序一直，本质上是用数组存储线性表的各个元素（即随机存取）；存储密度大，存储空间利用率高。
链式存储的固有特点：元素之间的关系采用这些元素所在的节点的“指针”信息表示（插、删不需要移动节点）。
静态存储的固有特点：在程序运行的过程中不要考虑追加内存的分配问题。
动态存储的固有特点：可动态分配内存；有效的利用内存资源，使程序具有可扩展性。

[1-3] 广义表

https://blog.csdn.net/weixin_44289254/article/details/123693094

这玩意儿怎么这么像二叉树啊？

广义表的基础概念

什么是广义表

广义表也是一种线性表，结合了链式和顺序的存储方法
每个节点既可以存储不可再分的元素，也可以存储一个新的广义表

广义表的原子和子表

例如：广义表 LS = {1,{1,2,3}}，则此广义表的构成：广义表 LS 存储了一个原子 1 和子表 {1,2,3}。
广义表存储数据的一些常用形式： A = ()：A 表示一个广义表，只不过表是空的。 B = (e)：广义表 B 中只有一个原子 e。 C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。 D = (A,B,C)：广义表 D 中存有 3 个子表，分别是 A、B 和 C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。 E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

广义表的表头和表尾

当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。
除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

广义表的长度

广义表的长度，指的是广义表中所包含的数据元素的个数。
计算元素个数时，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。
- LS = {a1,a2,…,an} 的长度为 n；
- 广义表 {a,{b,c,d}} 的长度为 2；
- 广义表的长度为 1；
- 空表 {} 的长度为 0。
求广义表长度时，两种不同的存储方式求解也有所不同

在这里插入图片描述

对于图 1a) 来说，只需计算最顶层（红色标注）含有的节点数量，即可求的广义表的长度。同理，对于图 1b) 来说，由于其最顶层（蓝色标注）表示的此广义表，而第二层（红色标注）表示的才是该广义表中包含的数据元素，因此可以通过计算第二层中包含的节点数量，才可求得广义表的长度。

广义表的深度

广义表的深度，可以通过观察该表中所包含括号的层数间接得到

{0}-1 结构体

原子的节点由两部分构成，分别是 tag 标记位和原子的值
表示子表的节点由三部分构成，分别是 tag 标记位、hp 指针和 tp 指针。
tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1
子表节点中的hp 指针用于连接本子表中存储的原子或子表，tp 指针用于连接广义表中下一个原子或子表
除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表

typedef struct GNode{
    int tag;         // 标志域, 0表示原子, 1表示子表
    union{
        char atom;   //  原子结点的值域
        struct{
            struct GNode * hp, *tp;
        }ptr;   // 子表结点的指针域, hp指向表头, tp指向表尾
    }subNode;
}GLNode, *Glist;

在这里插入图片描述

{0}-2 结构体

另一种存储结构的原子的节点也由三部分构成，分别是： tag 标记位、原子值和 tp 指针构成；表示子表的节点由三部分构成，分别是： tag 标记位、hp 指针和 tp 指针

typedef struct GNode {
    int tag;                // 标志域, 0表示原子, 1表示子表
    union {
        int atom;          // 原子结点的值域
        struct GNode* hp;  // 子表结点的指针域, hp指向表头
    }subNode;
    struct GNode* tp;     // 这里的tp相当于链表的next指针, 用于指向下一个数据元素
}GLNode, *Glist;

在这里插入图片描述

{} 复制

广义表的复制思想 ：任意一个非空广义表来说，都是由两部分组成：表头和表尾。反之，只要确定的一个广义表的表头和表尾，那么这个广义表就可以唯一确定下来。因此复制一个广义表，也是不断的复制表头和表尾的过程。如果表头或者表尾同样是一个广义表，依旧复制其表头和表尾。

使用递归的方法不断复制表头和表尾

1 线性表 ​

[1] 线性表 ​

逻辑结构 ​

[1-1] 顺序线性表 ​

特点 ​

[1-1-1] 静态表 ​

{0} 结构体定义 ​

{0-1} 初始化 ​

{0-1-1} main 操作 ​

{1-1-1} 插入操作 ​

{2-1-1}删除操作 ​

{3-1} 按位查找 ​

{3-2} 按值查找 ​

[1-2-1] 单链表 ​

带不带头节点的区别 ​

{0} 结构体定义 ​

[1-2-1-0] 无头结点单链表 ​

{0-1} 初始化 ​

{0-1-1}main 操作 ​

{1-1-1} 按位序插入 ​

{5-2} 判空 ​

[1-2-1-1] 带头结点单链表 ​

{0-1} 初始化 ​

{0-1-1} main 函数操作 ​

{1-1-1} 按位序插入 ​

{1-2-2} 指定结点的后插 ​

{1-2-1} 指定结点的前插 ​

{1-3-1} 头插 ​

{1-3-2} 尾插 ​

{2-1-1} 按位序删除节点 ​

{2-2-1} 指定结点的删除 ​

{3-1} 按位查找 ​

{3-2} 按值查找 ​

{5-1} 求单链表的长度 ​

{5-2} 判空 ​

{6-1} 链表的逆置 ​

[1-2-1-2] 循环单链表 ​

单链表和循环单链表的比较 ​

{0} ​

{0-1} ​

{3-3-2} 判是否为表尾 ​

{5-2} ​

[1-2-1-4] 静态链表 ​

定义 ​

{0(-1-1)} - 1 结构体定义并使用的一种方式 ​

{0(-1-1)} - 2 ​

{0(-1-1)} - 3 ​

{0-1} ​

{1-1-1} ​

{2-1-1} ​

{3-1}按位序查找 ​

[1-2-2] 双链表 ​

{0} ​

{0-1} ​

{1-2-2} ​

{1-1-1} ​

{1-2-1} ​

{2-2-2} ​

{2-4} 清空双链表 ​

{5-1}后向遍历 ​

{5-2}前向遍历 ​

概要 ​

[1-2-2-2] 循环双链表 ​

基本概念 ​

{0} ​

{0-1} ​

{1-2-1}插入 ​

{2-2-2}删除 ​

{3-3-2}判尾 ​

{5-2}判空 ​

顺序表和链表的比较 ​

顺序/链式/静态/动态比较 ​

[1-3] 广义表 ​

广义表的基础概念 ​

什么是广义表 ​

广义表的原子和子表 ​

广义表的表头和表尾 ​

广义表的长度 ​

广义表的深度 ​

{0}-1 结构体 ​

1 线性表

[1] 线性表

逻辑结构

[1-1] 顺序线性表

特点

[1-1-1] 静态表

{0} 结构体定义

{0-1} 初始化

{0-1-1} main 操作

{1-1-1} 插入操作

{2-1-1}删除操作

{3-1} 按位查找

{3-2} 按值查找

[1-2-1] 单链表

带不带头节点的区别

{0} 结构体定义

[1-2-1-0] 无头结点单链表

{0-1} 初始化

{0-1-1}main 操作

{1-1-1} 按位序插入

{5-2} 判空

[1-2-1-1] 带头结点单链表

{0-1} 初始化

{0-1-1} main 函数操作

{1-1-1} 按位序插入

{1-2-2} 指定结点的后插

{1-2-1} 指定结点的前插

{1-3-1} 头插

{1-3-2} 尾插

{2-1-1} 按位序删除节点

{2-2-1} 指定结点的删除

{3-1} 按位查找

{3-2} 按值查找

{5-1} 求单链表的长度

{5-2} 判空

{6-1} 链表的逆置

[1-2-1-2] 循环单链表

单链表和循环单链表的比较

{0}

{0-1}

{3-3-2} 判是否为表尾

{5-2}

[1-2-1-4] 静态链表

定义

{0(-1-1)} - 1 结构体定义并使用的一种方式

{0(-1-1)} - 2

{0(-1-1)} - 3

{0-1}

{1-1-1}

{2-1-1}

{3-1}按位序查找

[1-2-2] 双链表

{0}

{0-1}

{1-2-2}

{1-1-1}

{1-2-1}

{2-2-2}

{2-4} 清空双链表

{5-1}后向遍历

{5-2}前向遍历

概要

[1-2-2-2] 循环双链表

基本概念

{0}

{0-1}

{1-2-1}插入

{2-2-2}删除

{3-3-2}判尾

{5-2}判空

顺序表和链表的比较

顺序/链式/静态/动态比较

[1-3] 广义表

广义表的基础概念

什么是广义表

广义表的原子和子表

广义表的表头和表尾

广义表的长度

广义表的深度

{0}-1 结构体