关于指针

在最开始的开始我们必须先搞清楚指针这个c语言中最具特色的工具,而数据结构中的诸多结构都用到了指针,我个人是这样理解的：

  • 指针就像是一张存储卡一样，比如我们拿走一个a变量的存储卡（指针），即便换了任意一个变量，我们只要将存储卡（指针）更新到新的变量中，我们访问的数据仍旧是原来
    的那个变量a中的数据。

指针的比喻

1. 指针是地址的代表

  • 在内存中，每个变量都占用一个存储空间，并且每个存储空间都有一个地址。指针实际上并不是直接存放数据，而是存放某个变量在内存中的地址。
  • 你可以将指针比作某个特定位置的“地址标签”，而这个位置存放的是实际的数据。

2. 更新指针指向的对象

  • 如果你有一个指针 p 指向某个变量 x，通过 *p（假设 p 是 int* 类型）可以访问 x 的值。此时，你可以认为指针像是指向存储卡的标签，指向某个特定存储区。
  • 如果你把指针 p 指向另一个变量 y，那么通过 *p 就可以访问变量 y 的值，即使之前指向的是 x。换句话说，虽然 p 指针本身是改变了指向的对象，但指针所指向的值也是随之更新的。

3. 对指针的理解

  • 指针的赋值: 当前指针 p 指向的地址可以改变，例如 p = &y;。这只是更新了指针指向，即“存储卡的标签”。p 现在指向的新地址（y 的地址）中的值会通过 *p 访问到，因而能够读取不同的数据。

  • 临时性与持久性: 重要的是要理解指针所指向的内容（数据）在内存中可能是临时的，也可能是持久的，具体取决于数据的生命周期。比如，当一个变量超出作用域时，该指针不再有效，访问它可能导致未定义行为（类似于拿着已不存在标签的卡）。

顺序表—— Sequence List

一、顺序表的定义

顺序表：线性表的顺序存储，它是用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。

二、顺序表的特点

①随机访问：可直接通过下标访问

②存储密度高：每个节点只能存数据元素

③拓展容量不方便：即便采用动态分配方式，迁移数据时时间复杂度也比较高

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

三、顺序表的实现方式

实现方式：静态分配和动态分配

四、静态分配的顺序表上的操作

静态分配的顺序表的优缺点

缺点：顺序表的表长确定后无法修改，存满了就存不了了

顺序表的类型描述

1
2
3
4
5
#define MaxSize 10;			 //定义最大长度
typedef struct{
    int data[MaxSize];       //“静态”的数组存数据，存int数据
    int length;              //顺序表的当前长度
}SqList;

初始化

1
2
3
4
5
6
7
//初始化
void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++){
        L.data=[i]=0;	     //将所有元素都设为默认值0
    }
    L.length=0;              //顺序表长度初始为0
}

插入

1
2
3
4
5
6
7
8
9
10
11
//插入操作：在顺序表L的第i个(位序)上插入x
bool ListInsert(SqList &L, int i,int e){
    if(i<1||i>L.length+1)		//判断i的范围是否有效
        return false;
    if(L.length>=MaxSize)		//当存储空间已满时，不能插入
        return false;
    for(int j=L.length; j>=i; j--)
        L.data[j]=L.data[j-1];  //将第i个及后面的元素后移
    L.data[i-1]=e;				//将e放到第i个位置
    L.length++;                 //长度+1
}
插入的时间复杂度：

最好情况：插到表尾，不需移动元素，循环0次，最好时间复杂度=O(1)

最坏情况：插到表头，移动n个元素，循环n次，最坏时间复杂度=O(n)

平均情况：设插入概率为p=1/n+1，则循环np+(n-1)p+…+1p=n/2，平均时间复杂度=O(n)

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
//删除操作：删除顺序表L中第i个元素并返回其元素值
bool ListDelete(SqList &L, int i,int &e){
    if(i<1||i>L.length+1){		       //判断i的范围是否有效
        return false;
    }else{
        e = L.data[i-1];               //将被删除的元素赋值给e
        for(int j=i; j<L.length; j++){
            L.data[j]=L.data[j-1];     //将第i个后面的元素前移
        }
    	L.length--;                    //长度-1
        return ture;
    }
}
删除的时间复杂度：

最好情况：删除表尾，不需移动元素，循环0次，最好时间复杂度=O(1)

最坏情况：删除表头，移动n-1个元素，循环n次，最坏时间复杂度=O(n)

平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n-1)/2，平均时间复杂度=O(n)

查找

按位查找
1
2
3
4
//按位查找：返回顺序表中第i个元素的元素值
int GetElem(Sqlist L, int i){
    return L.data[i-1];
}
按位查找的时间复杂度

时间复杂度=O(1)

按值查找
1
2
3
4
5
6
7
8
//按值查找：返回顺序表L中第一个值为x的元素的位置
int LocateElem(Sqlist L, int e){
    for(int i=0; i<L.length; i++){
        if(L.data[i] == e)
            return i+1;  //返回元素位置
    }
    return -1;  //查找失败，返回-1
}
按值查找的时间复杂度

最好情况：目标在表头，循环1次，最好时间复杂度=O(1)

最坏情况：目标在表尾，循环n次，最坏时间复杂度=O(n)

平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n+1)/2，平均时间复杂度=O(n)

无销毁

系统自动销毁

五、动态分配的顺序表上的操作

动态分配的顺序表的优缺点：

优点：可以动态增加长度

缺点：动态增加长度中的迁移工作时间开销大

顺序表的类型描述

1
2
3
4
5
typedef struct{
    int *data;         //指向“动态”分配的数组的指针
    int MaxSize;	   //顺序表的最大长度
    int length;        //顺序表的当前长度
}SqList;

初始化

1
2
3
4
5
6
7
//初始化
void InitList(SqList &L){
    //用malloc函数申请一片连续的存储空间
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.MaxSize=InitSize;
    L.length=0;              //顺序表长度初始为0
}

动态增加数组长度

方法：借用一个指针指向原来顺序表，新建一个更大的顺序表，将原数据迁移过来，并更改顺序表大小，最后释放原顺序表空间

1
2
3
4
5
6
7
8
9
10
//动态分配
void IncreaseSize(SqlList &L, int len){
    int *p=L.data;
    L.data=(int *)malloc((L.InitSize+len)*sizeof(int));
    for(int i=0; i<L.length; i++){
        L.data[i]=p[i];				//将数据迁移至新区域
    }
    L.MaxSize=L.MaxSize+len;		//顺序表最大长度+len
    free(p);						//释放原来的内存空间
}

插入

在静态分配的基础上，如果容量不够，则动态增加

1
2
3
4
5
6
7
8
9
10
11
//插入操作：在顺序表L的第i个(位序)上插入x
bool ListInsert(SqList &L, int i,int e){
    if(i<1||i>L.length+1)		//判断i的范围是否有效
        return false;
    if(L.length>=MaxSize)		//当存储空间已满时，动态增加数组长度
        IncreaseSize(L,10);
    for(int j=L.length; j>=i; j--)
        L.data[j]=L.data[j-1];  //将第i个及后面的元素后移
    L.data[i-1]=e;				//将e放到第i个位置
    L.length++;                 //长度+1
}
插入的时间复杂度：

最好情况：插到表尾，不需移动元素，循环0次，最好时间复杂度=O(1)

最坏情况：插到表头，移动n个元素，循环n次，最坏时间复杂度=O(n)

平均情况：设插入概率为p=1/n+1，则循环np+(n-1)p+…+1p=n/2，平均时间复杂度=O(n)

删除(与静态一样)

1
2
3
4
5
6
7
8
9
10
11
12
13
//删除操作：删除顺序表L中第i个元素并返回其元素值
bool ListDelete(SqList &L, int i,int &e){
    if(i<1||i>L.length+1){		       //判断i的范围是否有效
        return false;
    }else{
        e = L.data[i-1];               //将被删除的元素赋值给e
        for(int j=i; j<L.length; j++){
            L.data[j]=L.data[j-1];     //将第i个后面的元素前移
        }
    	L.length--;                    //长度-1
        return ture;
    }
}
删除的时间复杂度：

最好情况：删除表尾，不需移动元素，循环0次，最好时间复杂度=O(1)

最坏情况：删除表头，移动n-1个元素，循环n次，最坏时间复杂度=O(n)

平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n-1)/2，平均时间复杂度=O(n)

查找(与静态一样)

按位查找
1
2
3
4
//按位查找：返回顺序表中第i个元素的元素值
int GetElem(Sqlist L, int i){
    return L.data[i-1];
}
按位查找的时间复杂度

时间复杂度=O(1)

按值查找
1
2
3
4
5
6
7
8
//按值查找：返回顺序表L中第一个值为x的元素的位置
int LocateElem(Sqlist L, int e){
    for(int i=0; i<L.length; i++){
        if(L.data[i] == e)
            return i+1;  //返回元素位置
    }
    return -1;  //查找失败，返回-1
}
按值查找的时间复杂度

最好情况：目标在表头，循环1次，最好时间复杂度=O(1)

最坏情况：目标在表尾，循环n次，最坏时间复杂度=O(n)

平均情况：设删除概率为p=1/n，则循环(n-1)p+(n-2)p+…+1p=(n+1)/2，平均时间复杂度=O(n)

销毁

1
2
3
4
5
6
7
//销毁操作
void DestroyList(Sqlist &L){
    free(L.data);
    L.length = 0;
    L.MaxSize = 0;
    L.data = nullptr;  //令其为空指针
}

六、共同的操作

求表长

1
2
3
4
//求表长
int Length(Sqlist L){
    return L.length;
}

遍历

1
2
3
4
5
6
7
//遍历操作
void PrintList(Sqlist L){
    for(int i=0; i<L.length; i++){
        cout<<L.data[i]<<" ";
    }
    cout<<endl;
}

判空

1
2
3
4
//判空操作
int Empty(Sqlist L){
    return L.length==0? 1 : 0;
}

七、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//动态分配的顺序表的完整代码
#include<bits/stdc++.h>
using namespace std;

#define MaxSize 100   //定义线性表的最大长度
typedef struct Sqlist{
	int data[MaxSize];
	int length;
}Sqlist;

//初始化
void Init(Sqlist &L){
    L.length = 0;
}

//求表长
int Length(Sqlist L){
    return L.length;
}

//插入操作：在表中第i个位置上插入x
void Insert(Sqlist &L, int i, int x){
    if(i<1 || i>L.length+1 || L.length >= MaxSize){
        cout<<x<<" Insert failed."<<endl;
        return;
    }
    for(int j=L.length; j>=i; j--){  //第i个及以后的元素后移
        L.data[j] = L.data[j-1];
    }
    L.data[i-1]=x;
    L.length++;
}

//遍历操作
void PrintList(Sqlist L){
    cout<<"L: ";
    for(int i=0; i<L.length; i++){
        cout<<L.data[i]<<" ";
    }
    cout<<endl;
}

//按值查找：返回顺序表L中第一个值为x的元素的位置
int LocateElem(Sqlist L, int x){
    for(int i=0; i<L.length; i++){
        if(L.data[i] == x)
            return i+1;  //返回元素位置
    }
    return -1;  //查找失败，返回-1
}

//按位查找：返回顺序表中第i个元素的元素值
int GetElem(Sqlist L, int i){
    return L.data[i-1];
}

//删除操作：删除顺序表L中第i个元素并返回其元素值
int Delete(Sqlist &L, int i, int &x){
    if(i<1 || i>L.length){
        return -1;
    }else{
        x = L.data[i-1];
        for(int j=i; j<L.length; j++){
            L.data[j-1] = L.data[j];
        }
        L.length--;
        return x;
    }
}

//判空操作
int Empty(Sqlist L){
    return L.length==0? 1 : 0;
}

int main(){
    Sqlist L;
    Init(L); 
    Insert(L, 1, 50);
    Insert(L, 2, 60);
    Insert(L, 1, 40);
    Insert(L, 1, 666);
    Insert(L, 5, 70);
    Insert(L, 6, 40);
    Insert(L, 7, 100);
    cout<<"长度："<<Length(L)<<endl;
    PrintList(L);
    int x;
    cout<<"第三个元素是："<<GetElem(L,3)<<endl;
    cout<<"40在第"<<LocateElem(L,40)<<"位"<<endl;
    cout<<"删除"<<Delete(L,6,x)<<endl;
    PrintList(L);
    if(!Empty(L)){
        cout<<"L不为空"<<endl;
    }else{
        cout<<"L为空"<<endl;
    }
    return 0;
}

单链表—— Singly Linked List

一、单链表的定义

单链表：线性表的链式存储，它是通过一组任意的存储单元来存储线性表中的数据元素，不需要使用地址连续的存储单元，因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。

二、单链表的特点

①不能随机访问：遍历查找访问

②存储密度不高：每个节点既要存数据元素又要存指针

③拓展容量方便：直接用建立单链表拓展

④插入、删除操作方便：知道位置直接插入和删除

三、单链表的实现方式

实现方式：不带头结点和带头结点，一般带头结点比不带头结点好

带头结点：写操作代码方便，一般用带头结点，不明确的都是带头结点的

不带头结点：写操作代码麻烦，要区分第一个数据和后续数据的处理

注：这两种方式主要是：类型描述相同，初始化和判空不同

四、单链表上的操作

单链表的类型描述

1
2
3
4
typedef struct LNode{    //定义单链表结点类型
	int data;            //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next;  //指针域
}LNode, *LinkList;
不带头结点的初始化和判空
1
2
3
4
5
//初始化
void InitList(LinkList &L){
    L = NULL;
    L->next = NULL;
}
1
2
3
4
5
6
7
8
//判空操作
bool Empty(LinkList L){
    if(L == NULL){
        return true;
    }else{
        return false;
    }
}
带头结点的初始化和判空
1
2
3
4
5
//初始化
void InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LinkList));
    L->next = NULL;
}
1
2
3
4
5
6
7
8
//判空操作
bool Empty(LinkList L){
    if(L->next == NULL){
        return true;
    }else{
        return false;
    }
}

建立单链表

头插法建立单链表

用于链表的逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//头插法建立单链表
LinkList HeadInsert(LinkList &L){
    InitList(L); //初始化
    int x;
    cin>>x;
    while(x!=9999){ //输入9999表示结束
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin>>x;
    }
    return L;
}

头插法是指在单链表的头部插入新节点的一种常见方法。在使用头插法插入元素时，最终链表中的数据顺序将与原始数据的顺序相反。

插入步骤
  1. **插入 A**：链表为空，将 A 设为头节点。
    head -> A
  2. **插入 B**：将 B 插入到 A 之前。
    head -> B -> A
  3. **插入 C**：将 C 插入到 B 之前。
    head -> C -> B -> A
  4. **插入 D**：将 D 插入到 C 之前。
    head -> D -> C -> B -> A
    最终链表中的元素顺序为 D -> C -> B -> A，可见，这与原始插入顺序完全相反。
尾插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//尾插法建立单链表
LinkList TailInsert(LinkList &L){
    InitList(L);
    LNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999){
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        cin>>x;
    }
    r->next = NULL;
    return L;
}
插入步骤

尾插法是指在单链表的末尾插入新节点。在使用尾插法插入元素时，链表中的数据顺序将与原始数据的顺序一致。具体步骤如下：

  1. **插入 A**：链表为空，将 A 设为头节点。
    head -> A
  2. **插入 B**：找到最后一个结点 A，将 B 放到其后。
    head -> A -> B
  3. **插入 C**：找到最后一个结点 B，将 C 放到其后。
    head -> A -> B -> C
  4. **插入 D**：找到最后一个结点 C，将 D 放到其后。
    head -> A -> B -> C -> D

最终链表中的元素顺序为 A -> B -> C -> D，与原始插入顺序一致。因此，尾插法更适合在需要保留插入数据顺序的场景下使用。

总结
  • 头插法：得到的链表顺序与插入顺序相反。
  • 尾插法：得到的链表顺序与插入顺序一致。

插入

时间复杂度=O(1)

带头结点的插入
1
2
3
4
5
6
//将x插入到单链表L的第i个位置上
bool Insert(LinkList &L, int i, int e){
    if(i<1) return false;
    LNode *p = GetElem(L,i-1);    //查找第i个位置
    return InsertNextNode(p, e);  //用后插操作，插在p后面
}
不带头结点的插入
1
2
3
4
5
6
7
8
9
10
11
12
13
//将x插入到单链表L的第i个位置上
bool Insert(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;
        return true;
    }
    LNode *p = GetElem(L,i-1);    //查找第i个位置
    return InsertNextNode(p, e);  //用后插操作，插在p后面
}
指定结点的后插操作
1
2
3
4
5
6
7
8
9
10
//后插操作：在p结点之后插入元素e
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;
}
指定结点的前插操作

还是插在p后面，只不过让p和插入结点的值交换

1
2
3
4
5
6
7
8
9
10
11
//前插操作：在p结点之前插入元素e
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;
}

删除

按位序删除
1
2
3
4
5
6
7
8
9
10
11
//删除操作:将单链表中的第i个结点删除
bool Delete(LinkList &L, int i int &e){
    if(i<1 || i>Length(L))
        return false;
    LNode *p = GetElem(L,i-1);  //查找第i个位置
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}
按位序删除的时间复杂度：

最好情况：删除第一个，不需查找位置，循环0次，最好时间复杂度=O(1)

最坏情况：删除最后一个，需查找第n位，循环n次，最坏时间复杂度=O(n)

平均情况：删除任意一个，平均时间复杂度=O(n)

指定结点的删除

时间复杂度=O(n)

方法：p的后一个为q，p指向q的下一个，把q的值给p，最后释放q

1
2
3
4
5
6
7
8
9
//删除指定结点p
bool Delete(LNode *p){
    if(p==NULL) return false;
    LNode *q = p->next;
    p->data = q->data
    p->next = q->next;
    free(q);
    return true;
}

查找

按位查找

平均时间复杂度=O(n)

1
2
3
4
5
6
7
8
9
10
11
//按位查找：查找在单链表L中第i个位置的结点
LNode *GetElem(LinkList L, int i){
    int j=0;
    LNode *p = L;
    if(i<0) return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}
按值查找

平均时间复杂度=O(n)

1
2
3
4
5
6
7
8
//按值查找：查找e在L中的位置
LNode *LocateElem(LinkList L, int e){
    LNode *p = L->next;
    while(p && p->data != e){
        p = p->next;
    }
    return p;
}

求表长

平均时间复杂度=O(n)

1
2
3
4
5
6
7
8
9
10
//求表的长度
int Length(LinkList L){
    int len = 0;
    LNode *p = L;
    while(P->next){
        p = p->next;
        len++;
    }
    return len;
}

遍历

1
2
3
4
5
6
7
8
9
//遍历操作
void PrintList(LinkList L){
    LNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

五、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;

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

//初始化
void InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LinkList));
    L->next = NULL;
}

//遍历操作
void PrintList(LinkList L){
    LNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

//求单链表的长度
int Length(LinkList L){
    LNode *p = L->next;
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}

//头插法建立单链表
LinkList HeadInsert(LinkList &L){
    InitList(L); //初始化
    int x;
    cin>>x;
    while(x!=9999){
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        cin>>x;
    }
    return L;
}

//尾插法建立单链表
LinkList TailInsert(LinkList &L){
    InitList(L);
    LNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999){
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        cin>>x;
    }
    r->next = NULL;
    return L;
}

//按值查找：查找x在L中的位置
LNode *LocateElem(LinkList L, int x){
    LNode *p = L->next;
    while(p && p->data != x){
        p = p->next;
    }
    return p;
}1

//按位查找：查找在单链表L中第i个位置的结点
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 && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}

//将x插入到单链表L的第i个位置上
void Insert(LinkList &L, int i, int x){
    LNode *p = GetElem(L,i-1);
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
}

//删除操作:将单链表中的第i个结点删除
void Delete(LinkList &L, int i){
    if(i<1 || i>Length(L)){
        cout<<"delete failed: index is wrong."<<endl;
        return;
    }
    LNode *p = GetElem(L,i-1);
    LNode *q = p->next;
    p->next = q->next;
    free(q);
}


int main(){
    //初始化，尾插法建立单链表
    LinkList L = TailInsert(L);
    //插入：在第二个位置插入结点，数据域为888，并遍历单链表
    Insert(L,2,888);
    cout<<"在第二个位置插入888： ";
    PrintList(L);
    //删除：删除第四个结点
    Delete(L,4);
    cout<<"删除第四个结点后：";
    PrintList(L);
    //按位查找：查找第三个结点，并输出其数据域的值
    LNode *p = GetElem(L,3);
    cout<<"第三个结点的值为："<<p->data<<endl;
    //按值查找：查找数据域为2的结点的指针
    LNode *q = LocateElem(L,2);
    cout<<"数据为2的结点的下一个结点的值为："<<q->next->data<<endl;
    //输出单链表的长度
    cout<<"单链表的长度："<<Length(L)<<endl;
    return 0;
}

双链表—— Double Linked List

一、单链表的定义

单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。

双链表的结点中有两个指针prior和next，分别指向前驱结点和后继结点。

二、双链表的实现方式

实现方式：不带头结点和带头结点，一般带头结点比不带头结点好

带头结点：写操作代码方便，一般用带头结点，不明确的都是带头结点的

不带头结点：写操作代码麻烦，要区分第一个数据和后续数据的处理

三、双链表上的操作（带头结点）

双链表的类型描述

1
2
3
4
typedef struct DNode{
    int data;  //数据域
    struct DNode *prior,*next;  //前驱和后继指针
}DNode, *DLinkList;

初始化

1
2
3
4
5
6
7
8
//初始化
bool InitList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DLinkList));
    if(L == NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

判空

1
2
3
4
5
6
7
8
//判空操作
bool Empty(DLinkList L){
    if(L->next == NULL){
        return true;
    }else{
        return false;
    }
}

建立双链表

头插法建立双链表

用于链表的逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//头插法建立双链表
DLinkList HeadInsert(DLinkList &L){
    InitList(L); //初始化
    int x;
    cin>>x;
    while(x!=9999){
        DNode *s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        if(L->next == NULL){
            s->next = NULL;
            s->prior = L;
            L->next = s;
        }else{
            s->next = L->next;
            L->next->prior = s;
            s->prior = L;
            L->next = s;
        }
        cin>>x;
    }
    return L;
}
尾插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//尾插法建立双链表
DLinkList TailInsert(DLinkList &L){
    InitList(L);
    DNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999){
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL;
        s->prior = r;
        r->next = s;
        r = s;
        cin>>x;
    }
    return L;
}

插入

时间复杂度=O(1)

插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//将x插入到双链表L中*p结点的下一个结点
bool Insert(DNode *p, int x){
    DNode *s = (DNode *)malloc(sizeof(DNode));
    if(p == NULL||s==NULL) return false;
    s->data = x;
    s->next = p->next;  //1
    if(p->next != NULL) p->next->prior = s; //2
    s->prior = p;  //3
    p->next = s; //4
    return true;
}

//在双链表L中*p结点后插入s结点
bool Insert(DNode *p, DNode *s){
    if(p == NULL||s==NULL) return false;
    s->next = p->next;  //1
    if(p->next != NULL) p->next->prior = s; //2
    s->prior = p;  //3
    p->next = s; //4
    return true;
}

删除

按位序删除

时间复杂度=O(n)

删除操作

1
2
3
4
5
6
7
8
9
10
11
//删除操作:将双链表中的第i个结点删除
bool Delete(DLinkList &L, int i){
    if(i<1 || i>Length(L)) return false;
    DNode *p = GetElem(L,i-1);
    if(p == NULL) return false;
    DNode *q = p->next;
    p->next = q->next; //1
    if(p->next != NULL) q->next->prior = p; //2
    free(q);
    return true;
}
指定结点的删除

时间复杂度=O(1)

1
2
3
4
5
6
7
8
9
//删除操作:删除双链表中的p结点的后继结点
void DeleteNextNode(DNode *p){
    if(p == NULL) return false;
    DNode *q = p->next;
    if(q == NULL) return false;
    p->next = q->next; //1
    if(p->next != NULL) q->next->prior = p; //2
    free(q);
}

查找(与单链表完全一样)

按位查找

平均时间复杂度=O(n)

1
2
3
4
5
6
7
8
9
10
11
//按位查找：查找在单链表L中第i个位置的结点
DNode *GetElem(DLinkList L, int i){
    int j=0;
    DNode *p = L;
    if(i<0) return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}
按值查找

平均时间复杂度=O(n)

1
2
3
4
5
6
7
8
//按值查找：查找e在L中的位置
DNode *LocateElem(DLinkList L, int e){
    DNode *p = L->next;
    while(p && p->data != e){
        p = p->next;
    }
    return p;
}

求表长(与单链表完全一样)

平均时间复杂度=O(n)

1
2
3
4
5
6
7
8
9
10
//求表的长度
int Length(DLinkList L){
    int len = 0;
    DNode *p = L;
    while(P->next){
        p = p->next;
        len++;
    }
    return len;
}

遍历(与单链表完全一样)

1
2
3
4
5
6
7
8
9
//遍历操作
void PrintList(DLinkList L){
    DNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

销毁

1
2
3
4
5
6
7
8
9
//销毁操作
void DestoryList(DLinkList L){
    //循环释放各点的数据结点
    while(L->next != NULL){
        DeleteNextNode(L);
    }
    free(L); //释放头结点
    L = NULL;
}

四、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<bits/stdc++.h>
using namespace std;

typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}DNode, *DLinkList;

//初始化
void InitList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DLinkList));
    L->prior = NULL;
    L->next = NULL;
}

//遍历操作
void PrintList(DLinkList L){
    DNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

//求双链表的长度
int Length(DLinkList L){
    DNode *p = L->next;
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }
    return len;
}

//头插法建立双链表
DLinkList HeadInsert(DLinkList &L){
    InitList(L); //初始化
    int x;
    cin>>x;
    while(x!=9999){
        DNode *s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        if(L->next == NULL){
            s->next = NULL;
            s->prior = L;
            L->next = s;
        }else{
            s->next = L->next;
            L->next->prior = s;
            s->prior = L;
            L->next = s;
        }
        cin>>x;
    }
    return L;
}

//尾插法建立双链表
DLinkList TailInsert(DLinkList &L){
    InitList(L);
    DNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999){
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL;
        s->prior = r;
        r->next = s;
        r = s;
        cin>>x;
    }
    return L;
}

//按值查找：查找x在L中的位置
DNode *LocateElem(DLinkList L, int x){
    DNode *p = L->next;
    while(p && p->data != x){
        p = p->next;
    }
    return p;
}

//按位查找：查找在双链表L中第i个位置的结点
DNode *GetElem(DLinkList L, int i){
    int j=1;
    DNode *p = L->next;
    if(i==0)return L;
    if(i<1)return NULL;
    while(p && j<i){
        p = p->next;
        j++;
    }
    return p; //如果i大于表长，p=NULL,直接返回p即可
}

//将x插入到双链表L中*p结点的下一个结点
void Insert(DLinkList &L, DNode *p, int x){
    DNode *s = (DNode *)malloc(sizeof(DNode));
    s->data = x;
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}

//删除操作:将双链表中的第i个结点删除
void Delete(DLinkList &L, int i){
    if(i<1 || i>Length(L)){
        cout<<"delete failed: index is wrong."<<endl;
        return;
    }
    DNode *p = GetElem(L,i-1);
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
}

//判空操作
bool Empty(DLinkList L){
    if(L->next == NULL){
        cout<<"L is null"<<endl;
        return true;
    }else{
        cout<<"L is not null"<<endl;
        return false;
    }
}


int main(){
    //尾插法建立双链表，并遍历单链表
    DLinkList L = TailInsert(L);
    cout<<"L: ";
    PrintList(L);
    
    DNode *p;
    //按值查找
    p = LocateElem(L,2);
    cout<<"值为2的结点的下一个结点值是："<<p->next->data<<endl;
    cout<<"值为2的结点的上一个结点值是："<<p->prior->data<<endl;
    //按位查找
    p = GetElem(L,3);
    cout<<"第三个结点值是："<<p->data<<endl;
    
    //插入操作
    Insert(L,p,7);
    cout<<"在第三个结点后面插入值为7的结点后L： ";
    PrintList(L);
    
    //删除操作
    Delete(L, 5);
    cout<<"删除第五个结点后L： ";
    PrintList(L);
    
    //求表长
    cout<<"表长为："<<Length(L)<<endl;;
    
    //判空
    Empty(L);
    return 0;
}

栈—— Stack

一、栈的定义

栈是线性表结构的一种，但是栈结构的插入与删除操作都只能从同一端进行，所以栈结构是一种受限制的线性表结构，数据的插入与删除符合LIFO的原则（也就是后进先出，先进后出）。

二、栈的基本操作

注：参数代“&”表示：方法运行完后，对参数修改的结果要“带回来”

对数据的操作：创销，增删查改

1
2
3
4
5
6
7
8
9
10
InitStack(&S);     //初始化表：构造一个空的栈S，分配内存空间
DestoryStack(&S);  //销毁操作：销毁栈，并释放栈S所占用的内存空间

Push(&S,x);    //进栈，若栈S未满，则将x加入使之成为新栈
Pop(&S,&x);    //出栈，若栈S非空，则弹出栈顶元素，并用x返回

GetTop(S,&x);  //读栈顶元素，若栈S非空，则将x返回栈顶元素

//其它常用操作
StackEmpty(S);   //判空操作

三、存储结构

顺序存储和链式存储

四、栈分类

栈的顺序存储：顺序栈

栈的链式存储：链栈

顺序栈—— Sequence Stack

一、顺序栈的定义

顺序栈：栈的顺序存储。

二、顺序栈的实现方式

实现方式：静态分配和动态分配

三、静态分配的顺序栈上的操作

顺序栈的类型描述

1
2
3
4
5
#define MaxSize 10
typedef struct{
	Elemtype data[MaxSize];//静态数组存放栈中元素
	int top;               //栈顶指针
}SqStack;

初始化

1
2
3
4
//初始化一个栈
void InitStack(SqStack &S){
	S.top = -1;   //初始化栈顶指针
}

判栈空

1
2
3
4
5
6
7
bool StackEmpty(SqStack S){
    if(S.top == -1){
        return true;
    }else{
        return false;
    }
}

入栈

1
2
3
4
5
6
7
//向栈中压入元素e
bool Push(SqStack &S,Elemtype e){
	if(S.Top == MaxSize-1) return false;
	S.Top = S.Top + 1;  //栈顶指针向上移动
    S.data[S.top] = e;
	return true;
}

出栈

1
2
3
4
5
6
7
//栈顶元素出栈
bool Pop(Stack &S,Elemtype &e){
	if(S.Top == -1) return false;
	e = S.data[S.Top];   //x为栈顶元素，栈顶指针下移一个位置
	S.Top = S.Top - 1;
    return true;
}

获取栈顶元素

1
2
3
4
5
6
//获取栈顶元素e
bool GetTop(Stack &S,Elemtype &e){
	if(S.Top==S.Base) return false;
	e = S.data[S.Top];
	return true;
}

四、动态分配的顺序栈上的操作

顺序栈的类型描述

1
2
3
4
5
typedef struct Stack{
	Elemtype *Top;//指向栈顶元素的上一个
	Elemtype *Base;//指向栈底
	int stacksize;//当前栈的空间大小
}SqStack

初始化

1
2
3
4
5
6
7
8
//初始化一个栈
bool InitStack(SqStack &S){
	S.Base=(Elemtype *)malloc(MAXSIZE*sizeof(Elemtype));
	if(!S.Base) return false;
	S.Top=S.Base;
	S.stacksize=MAXSIZE;
	return true;
}

判栈空

1
2
3
4
5
6
7
bool StackEmpty(SqStack S){
    if(S.Top == S.Base){
        return true;
    }else{
        return false;
    }
}

入栈

1
2
3
4
5
6
7
//向栈中压入元素e
bool Push(SqStack &S,Elemtype e){
	if(S.Top-S.Base==S.stacksize) return false;
	*S.Top=e;
	S.Top++;	//栈顶指针向上移动
	return true;
}

出栈

1
2
3
4
5
6
//栈顶元素出栈
bool Pop(Stack &S,Eletype &x){
	if(S.Top==S.Base) return false;
	x=*--S.Top;		//x为栈顶元素，栈顶指针下移一个位置
	return true;
}

获取栈顶元素

1
2
3
4
5
6
//获取栈顶元素e
bool GetTop(Stack &S,Elemtype &e){
	if(S.Top==S.Base) return false;
	e = *(S.Top-1);
	return true;
}

链栈—— Linked Stack

一、链栈的定义

链栈：栈的链式存储。

二、链栈的实现方式

实现方式：不带头结点和带头结点，一般带头结点比不带头结点好

不带头结点：写操作代码麻烦，要区分第一个数据和后续数据的处理

带头结点：写操作代码方便，一般用带头结点，不明确的都是带头结点的

注：这两种方式：只有类型描述一样，初始化不一样，

​ 判空、入栈、出栈、取栈顶元素不一样，不带头节点是s，带头结点是s->next，因为链栈以链头为栈顶

三、不带头结点的链栈上的操作（与不带头结点的单链表一样）

链头为栈顶

链栈的类型描述

1
2
3
4
typedef struct LNode{    //定义单链表结点类型
	int data;            //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next;  //指针域
}LNode, *LinkStack;

初始化

1
2
3
4
5
//初始化
void InitStack(LinkStack &S){
    S = NULL;
    S->next = NULL;
}

判栈空

1
2
3
4
5
6
7
8
//判空操作
bool StackEmpty(LinkStack S){
    if(S == NULL){
        return true;
    }else{
        return false;
    }
}

入栈（与单链表插入一样）

1
2
3
4
5
6
7
8
9
10
bool push(LNode *s, int x){
    if(s==NULL) return false;
    LNode *p = (LNode*)malloc(sizeof(LNode));
    if(p==NULL) return false;
    p->next = NULL;
    p->data = x;
    p->next = s;
    s = p;
    return true;
}

出栈（与单链表删除一样）

1
2
3
4
5
6
7
8
bool Delete(LNode *s){
    if(s==NULL) return false;
    LNode *q = s;
    s->data = q->data
    s = q->next;
    free(q);
    return true;
}

获取栈顶元素（与单链表删除一样）

1
2
3
4
5
6
//获取栈顶元素e
bool GetTop(LNode &s,Elemtype &e){
	if(s == NULL) return false;
	e = s->data;
	return true;
}

四、带头结点的链栈上的操作

s都改为s->next，类型描述和初始化例外

链栈的类型描述

1
2
3
4
typedef struct LNode{    //定义单链表结点类型
	int data;            //数据域，可以是别的各种数据类型，本文统一用int类型
	struct LNode *next;  //指针域
}LNode, *LinkStack;

初始化

1
2
3
4
5
//初始化
void InitStack(LinkStack &S){
    S = (LNode*)malloc(sizeof(LNode));
    S->next = NULL;
}

判栈空

1
2
3
4
5
6
7
bool StackEmpty(LinkStack S){
    if(S->next == NULL){
        return true;
    }else{
        return false;
    }
}

入栈（与单链表插入一样）

1
2
3
4
5
6
7
8
9
10
bool push(LNode *s, int x){
    if(s==NULL) return false;
    LNode *p = (LNode*)malloc(sizeof(LNode));
    if(p==NULL) return false;
    p->next = NULL;
    p->data = x;
    p->next = s->next;
    s->next = p;
    return true;
}

出栈（与单链表删除一样）

1
2
3
4
5
6
7
8
bool Delete(LNode *s){
    if(s==NULL) return false;
    LNode *q = s->next;
    s->data = q->data
    s->next = q->next;
    free(q);
    return true;
}

获取栈顶元素

1
2
3
4
5
6
//获取栈顶元素e
bool GetTop(LNode &s,Elemtype &e){
	if(s->next == NULL) return false;
	e = s->next->data;
	return true;
}