线性表 | Spencer

定义线性表

注意

1
2
3

对数组进行封装，在存储空间起始位置即为数组data，
设置最大存储容量，一般不会变
当前长度length，会变化

代码如下

typedef struct
{
    int data[MAXSIZE];
    int length;
}SqList;

变化的集合我们用*L，不变的集合我们参数才用L。下面是A = A并B的操作，所以我们知道A是要改变的，传入地址。

void unionL(List *La, list Lb)
{
	int La_len, Lb_len, i;
	ElemType e;
	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);
	for (i = 1; i <= Lb_len; i++)//也就是判断b中每一个元素是否在La中
	{
		GetElem(Lb, i, &e);
		if(!LocateElem(*La, e))
		{
			ListInsert(La, ++La_len, e);
		}
	}
}

插入操作

现在考虑加入我们要实现ListInsert(*L, i, e)即在表L的第i个位置插入新元素e，代码应该怎么写？

注意，这里表示变化的集合，所以用指针表示。

我们要先考虑插入思路：

如果插入位置不合理，抛出异常
如果线性表长度大于等于数组长度，则抛出异常或者动态增加数组容量。
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。
最后将要插入到元素填入位置i处。
线性表长度+1。

实现代码：

Status ListInsert(SqList *L, int i, ElemType *e)
{
	int k;
	if(L->length == MAXSIZE)//表满了
	{
		return ERROR;
	}
	if(i < 1 || i > L.length + 1)
	{
		return ERROR;//加一是因为可以在表尾插入，此时i = length + 1
	}
	if(i <= L->length)
	{//将要插入的后面的元素都向后移动一位。
		for(k = L->length - 1; k >= i-1; k--)//最后一位的索引是length-1，从最后开始遍历
		{
			L->data[k+1]=L->data[k];//将k位置给k+1位置的数
		}
	}
	
	L->data[i-1] = e;//插入元素
	L->length++;
	
	return OK;
}

删除操作

先来看设计思路：

判断表长是否为0
首先删除位置要合理，不合理的位置，没有元素，输出异常
删除之后，返回删除的值，用指针变量，被删除元素的后面都要往前补位
列表长度减一

下面来看代码实现

Status ListDelete(SqList *L, int i, int *e)//不用定义新的指针，因为没有新的变量
{
    int k;//要遍历的元素
    if(L->length == 0)
    {
        return ERROR;
    }
    if(i < 1 || i >= L->length)//被删除元素的条件要符合
    {
        return ERROR;
    }
    *e = L->data[i-1];//返回被删除的值
    if (i < L->length)
    {
        for(k = i; k <= L->length; k++)//从第i个元素开始,向前移动
        {
            L->data[i-1] = L->data[i];
        }
    }
    L->length --;
    return OK;
}

分析插入和删除的时间复杂度

如果两个操作刚好都作用在最后，那么不需要移动任何元素，因此时间复杂度就是O(1)。

最坏的情况：插入和删除的是第一个元素，所有元素都要向后或者向前移动，此时时间复杂度就是O(n)。

所以平均复杂度O((n-1)/2)简化之后也就是O(n)。

顺序存储结构在寸和读的时候都是O(1)，在插入删除都是O(n)。

注意啊上述是数组存储结构，也就是顺序存储结构。

优点：无需为表中元素之间的逻辑关系而增加额外的存储空间。（暗指链式）

可以快速存取表中任意位置的元素。

缺点：插入和删除操作需要移动大量元素。线性表变化较大时。难以确定存储空间容量，出现空间“碎片”。

原因就在于相邻元素存储位置具有邻居关系，在内存中紧挨着，中间没有间隙。

链式存储

存储数据元素信息的域为数据域，存储直接后继位置的为指针域。指针域中存储的信息称为指针或链。

两部分信息组成数据元素称为存储映像，称为结点(node)。

n个结点链接成一个链表，即为线性表(a1, a2, …, an)的链式存储结构。

因为此链表中的每个结点中只包含一个指针域，叫做单链表。

如图所示

头结点和头指针的异同

链表中第一个结点的存储位置叫做头指针，最后一个结点的存储指针为空(NULL)。

头结点的数据域一般不存储信息。

头指针是链表指向第一个结点的指针，若链表有头结点。

头指针具有标志作用，所以常用头指针冠以链表的名字（指针变量的名字）。

无论链表是否为空，头指针不为空，为空就没有链表了。

头指针是链表的必要元素。

头结点是为了操作的方便和统一而设立的，放在第一个元素的结点之前，数据域一般无意义。（可以放链表的长度）

有了头结点，就方便在第一结点前插入结点和删除结点了。

所以，头结点不是必要的。如图单链表：

如图空链表：

在C语言中用结构指针来描述单链表。

typedef int ElemType;
#include "struct_point_to_define.h"
typedef struct Node
{
    ElemType data;//数据域
    struct Node* Next;//指针域,指向结点。
} Node;
typedef struct Node* LinkList;//取struct Node*结构体指针的别名为LinkList

我们可以看到结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

举例子：假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data，其值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。

那么p->next指向谁呢，当然是第i+1个元素，也就是指向ai+1的指针。

问题：如果p->data = ai，那么p->next->data=？其实是下一个结点的数据即ai+1

单链表的读取

第i个元素到底在哪？我们先称其为GetElem。

思路

声明一个结点p指向链表第一个结点，初始化j从1开始。p显然是头结点，指向第一个结点。
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j+1
如果遍历到尾部，p为空，则说明i元素不存在
如果查找成功，就返回结点p的数据。

下面是代码实现

typedef int ElemType;
#define ERROR 0
#define OK 1
typedef struct Node
{
    ElemType data;//数据域
    struct Node* Next;//指向结点
} Node;
typedef struct Node* LinkList;//取结构体结点指针命名为LinkList

//然后进行读取操作

ElemType GetElem(LinkList L, int i, ElemType *e)
{
    int j;
    LinkList p;
    p = L->Next;//p指向链表的第一个结点
    j = 1;
    while (p && j < i)//也就是p不能为空，并且j < i
    {
        p = p->Next;
        ++j;//一直到等于，推出
    }
    if (!p || j>i)//也就是找到最后一个的时候，p为Null，没找到。
    {
        return ERROR;
    }
    *e = p->data;//返回找到的值
    return OK;
}

复杂度分析

1 2	说白了就是从头开始找找到第i个元素为止。所以复杂度取决于i的位置，当i=1时，不需要遍历，而i=n时遍历n-1次才可以。所以最坏情况时O(n)

因为没有定义表长，所以用while不用for。其核心思想为工作指针后移。

单链表的插入

每个结点需要两个存储空间分别存储数据和下一个结点的地址。

假设存储元素e的结点为s，我们要插入这个结点，如图所示，只需要

1 2	s->next = p->next; p->next = s;

注意不能反过来！反过来下一个结点的地址就会在第一步就丢掉！

所以，第i个数据插入结点的算法思路：

声明一结点p指向链表表头结点，初始化j从1开始。
当j<i时，遍历链表，让那个p的指针向后移动，如果到尾部仍然为空，则i不存在，否则i查找成功
查找成功时，在系统生成一个空结点s,
将数据元素e赋值给s->data
单链表的插入用刚才两个标准语句。

详细代码如下：

#include <stdio.h>
#include <string>
typedef int ElemType;
#define ERROR 0
#define OK 1

typedef struct Node
{
    ElemType data;
    struct Node* Next;
} Node;
typedef struct Node* LinkList;//上述还是定义了Node也就是结点和指向结点的指针LinkList

ElemType InsertElem(LinkList L, int i, ElemType e)
{
    LinkList p;
    p = L->Next;//先初始化指针p
    int j;
    while(p && j < i)
    {
        p = p->Next;
        ++j;
    }
    while(!p || j>i) {
        return ERROR;
    }
    LinkList s;//这里注意！我们要马上开辟空间！
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->Next = p->Next;
    p->Next = s;
}

单链表的删除

假设我们要删除结点q，只需要一步即可

1 2	p->next = p->next->next;也就是不指向q即可，直接指向下一个，同时让q指向空即可（省略了）或者这样一步也行q = p->next;p->next = q->next;

删除结点q算法思路：

声明结点p指向链表第一个结点，初始化j=1
当j<1时，遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
若到链表末尾为空，则说明第i个元素不存在
否则查找成功，则将欲删除结点p->next赋值给q
将被删除q结点数据赋值给e作为返回。
释放q结点。free函数。

代码实现

#include <string>
#include <stdio.h>
typedef int ElemType;
#define ERROR 0
#define OK 1

typedef struct Node
{
    ElemType data;
    struct Node* Next;
} Node;
typedef struct Node* LinkList;//定义了结点和结点指针。

ElemType DeleteElem(ElemType *e, int i, LinkList *L)//注意链表会变化！所以用链表的指针！*L
{
    LinkList p;
    //p = L->Next;//初始化p的值,注意链表会变化！不能这么写！
    p = *L;
    int j = 1;
    while(p->Next && j < i)
    {
        p = p->Next;
        ++j;
    }
    while(!(p->Next) || j > i)
    {
        return ERROR;
    }
    LinkList q;
    q = p->Next;
    *e = q->data;
    p->Next = q->Next;//直接跳跃指向后一个
    free(q);//成功
    return OK;
}

显然，我们分析其算法复杂度，最多为n，都是遍历的过程中实现的。

但是我们如果想在同一个位置插入10个元素，顺序存储结构每一次都需要移动n-i个位置，所以每一次都是O(n)

而我们的单链表只需要找到位置之后，每一次指针赋值即可，都是O(1)。

操作越频繁，单链表效率优势越明显。

单链表的整表创建

对于之前的顺序存储结构，我们对数组初始化来直观理解。

而单链表和顺序存储结构不一样，它的数据可以分散在各个角落，增长也是动态。

对于每个链表来说，其占用空间的大小和位置不需要预先分配划定的，可以根据系统情况和实际的需求即时生成。

人生就要向单链表一样，随机应变。

创建单链表的过程是一个动态生成链表的过程，从“空表”的初始状态起，依次建立各元素结点并逐个插入链表。

所以单链表整表创建的算法思路如下：

声明结点p和计数器变量i
初始化空链表L
让L的头结点的指针指向Null, 即建立一个带头结点的单链表。
循环实现后继结点的赋值和插入。

头插法建立单链表

从空表开始，每生成一个新的结点，存储数据之后，将新结点插入到当前链表的表头上，知道结束为止。

先让新结点的next指向头结点，再让表头的next指向新结点。

代码如下：

#include <string>
#include <stdlib.h>
#include <stdio.h>
#define ERROR 0
#define OK 1
typedef struct Node
{
    int data;
    struct Node* Next;
} Node;
typedef Node* LinkList;//定义了结点和结点指针
void CreateListHead(LinkList *L, int n)//因为链表会变化，所以用链表指针
{
    LinkList p;
    int i;
    srand(time(0));//初始化随机数种子
    *L = (LinkList) malloc(sizeof (Node));//分配地址空间
    (*L)->Next = NULL;//此时为空链表，链表内容为空
    for(i = 0; i < n; i++)
    {
        p = (LinkList) malloc(sizeof (Node));//创建结点，分配空间
        p->data = rand() % 100 + 1;
        p->Next = (*L)->Next;//任何的p都放在链表的头位置
        (*L)->Next = p;//并且链表指针指向p，不再指空了
    }
}

尾插法建立单链表

很简单，也就是每一个都插到最后。

代码如下；

#include <stdio.h>
#include <string>
#define OK 1
#define ERROR 0
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node * LinkList;//定义结点和结点指针

void CreateListTial(LinkList *L, int n)//注意，链表会变化，所以用链表指针，*L
{
    LinkList p, r;
    int i;
    srand(time(0));
    *L = (LinkList) malloc(sizeof (Node));//创建链表！
    r = *L;//这是尾指针，一开始都指向一点。
    for (i = 0; i < n;i++)
    {
        p = (Node *) malloc(sizeof (Node));
        p->data = rand()%100 + 1;
        r->next = p;//r指向当前尾部，r->next为新结点位置
        r = p;//尾指针指过去。
    }
    r->next= NULL;
}

整表删除

在内存中给它释放掉！

思路

1
2
3

声明结点p和q
将第一个结点赋值给p，下一个结点赋值给q
循环执行释放p和将q赋值给p的操作，然后q再指下一个，循环释放了。

代码实现

#include <stdio.h>
#include <string>
#define ERROR 1
#define OK 0

typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node* LinkList;
int ClearList(LinkList *L)//整表删除，要对链表作改动了，所以用链表指针，*L
{
    LinkList p, q;//定义两个结点指针
    p = (*L)->next;//第一个结点
    while(p)
    {
        q = p->next;
        free(p);
        p = q;//然后q再指向下一个。
    }
    (*L)->next = NULL;
    return OK;
}

单链表和顺序存储结构优缺点

存储分配：

1 2	顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能：

1 2	查找：顺序存储O(1)，单链表O(n) 插入和删除：顺序存储要平均移动一半多的元素,O(n)。单链表在计算出某位置指针后，插入和删除时间O(1)。

空间性能：

1 2	顺序存储空间需要预先分配单链表不需要分配存储空间，元素个数不受限制。

如果需要频繁查找，用顺序存储。

如果需要频繁插入，需要单链表结构。

静态链表

古人想出了用数组代替指针描述单链表。因为数组要事先声明，无法改变。

代码如下：

第一个元素是不存放东西的，最后一个数组的位置也是不存放的。

我们可以看到，第一个元素的游标，指向了第二个元素的下标。第二个元素的游标3，指向了第三个元素D的下标3。这就和单链表很像了。

我们对数组的第一个和最后一个元素做特殊处理，他们的data不存放数据。

我们通常把未使用的数组元素称为备用链表。

数组的第一个元素，即下标为0元素的cursor就存放备用链表的第一个结点的下标，即链接到备用链表。

数组的最后一个元素，即下标为MAXSIZE-1的元素的cursor存放第一个有数值的元素的下标，相当于单链表中的头结点作用。相当于把数据链接起来。

代码如下：

#define MAXSIZE 1000
#define OK 1
typedef struct
{
    int data;
    int cur;//cursor游标
}Component, StaticLinkList[MAXSIZE];//数组需要足够大空间
//其实相当于一个结点存储的是数组游标和数据，而游标就像指针，连接着下一个数据的下标。如笔记中图所示
int InitList(StaticLinkList space)//定义一个静态链表空间
{
    int i;
    for(i = 0; i < MAXSIZE - 1; i++)
    {
        space[i].cur = i + 1;//游标的数字记录的是下一个位置space[0].cur = 1, space[1].cur = 2
    }
    space[MAXSIZE - 1].cur = 0;//因为最后一个位置元素是空，所以游标即为0
    return OK;
}

静态链表中操作的是数组，不存在动态链表中结点的malloc申请和free释放的问题，所以我们需要自己实现申请者两个函数，达到插入和删除。

静态链表的插入操作

如图所示

也就是把B放到了E的后面，但是注意，我们想插入它到第二个元素，第一个元素是A，A的游标指向第二个元素，所以将A的游标指向5，也就是存放B，将B的游标指向2，也就是存放C，这样就插进去了。

我们来看代码，两部分组成。

//插入操作
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;//首先获得空数组的下标，也就是存放在第一个元素的游标中，比如这个空数组的下标是5
    if(space[0].cur)
    {
        space[0].cur = space[i].cur;//因为空数组5的位置，未来也会有元素，所以游标并不是6，而是指向下一个元素，我们只需要将其游标赋值给space[0]
        //即可，让其只要有元素就一直遍历，直到space[0].cur指向的位置中没有元素而停止。如图所示
    }
    return i;//接下来对空格位置再进行插入操作即可，编写插入函数
}

int InsertList(StaticLinkList L, int i, int e)
{
    int j, k, l;
    k = MAXSIZE - 1;
    if(i < 1 || i > ListLength(L) + 1)//i表示第i个元素，因为第i+1个元素不会报错，也就是在最后插入第i+1个，而i+2个会报错
    {
        return ERROR;
    }

    j = Malloc_SLL(L);//获取当前空闲位置，插入后修改游标
    if (j)
    {
        L[j].data = e;//插入成功
        for(l = 1; l <= i-1; l++)//i-1因为在第i个元素之前插入，比如在第二个元素前插入，也就是l<=1，执行一次
        {
            k = L[k].cur;//k是最后一个元素，也就是游标指向1，也就是k=1,第一个有元素的下标
        }
        L[j].cur = L[k].cur;//k=1下标的位置的游标本来是2，是1后面的元素，将2取出存放到插入元素的游标之中，链起来
        L[k].cur = j;//插入元素的位置5，这次存放到1的游标中，也就是L[k].cur中。链接起来了！
    }
}

静态链表的删除操作

如图所示，删除C元素之前

删除C元素之后：

可以看出我们B不再指向C而是指向D也就是B的游标改为C的游标是3，其实就是链表中的赋值操作。

并且我们将E也就是最后一个元素指向开头，这是约定俗成的，不变。

因为我们知道开头位置是用来指向第一个空位置的，所以先将B的游标改为原来开头的游标6，再将开头的游标改为2（原来B的位置），也就是链表的操作。

代码如下：

int DeleteList(StaticLinkList L, int i)//比如说删除第三个的元素，下面要执行两次循环
{
    int j, k;
    if(i < 1 || i > ListLength(L))
    {
        return ERROR;
    }
    k = MAXSIZE - 1;

    for(j = 1; j <= i - 1; j++)//循环进行两次,1, 2
    {
        k = L[k].cur;//k是位置999的元素，第一次循环游标指向1，再循环指向5，也就是k1=1, k2=5
    }
    j = L[k].cur;//j = 2，对应元素就是C1,因为2是指向3的，所以我们要将上一个直接指向3
    L[k].cur = L[j].cur;//上一个游标是5，现在变成3了。
    Free_SLL(L, j);
    return OK;
}

void Free_SLL(StaticLinkList space, int j)//回收到备用链表
{
    space[j].cur = space[0].cur;//原来备用链表/空闲链表的第一个索引存储在开头元素的游标，、
    // 所以我们要把原来空闲的第一个索引赋值到这个元素的游标也就是space[j].cur，并且让开头元素的游标指向我们，也就是把元素链到备用链表去了
    space[0].cur = j;
}

获取链表长度代码如下：

int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;//从结尾处开始。

    while (i)
    {
        i = L[i].cur;//将下标遍历下一个结点，也就是一个一个往前找。
        j++;//找一个加一下。
    }
    return j;
}

总结

优点：插入和删除只需要修改游标，不需要移动元素，从而改进了顺序存储中插入和删除时需要移动大量元素的缺点。

缺点：没有解决连续存储分配（数组需要的）带来的表长难以确定问题。并且不能随机存取。

这是为了没有指针的编程语言的单链表方法（其实很鸡肋）

面试题

快速找到未知长度单链表的中间节点。

首先我们需要遍历一遍单链表以确定长度L，也就是访问一个就让一个变量加一下。

然后再从头结点出发循环L/2次找到中间节点。

复杂度也就是L + L/2。

快慢指针原理：

设置两个指针search, mid都指向头节点。其中*search的移动速度是*mid的两倍。当*search指向末尾节点的时候，mid就刚好在中间了。这是标尺的思想。

代码如下：

#include <string>
#include <stdio.h>
#define OK 1
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node* LinkList;
int get_mid_node(LinkList L, int *e)
{
    LinkList search, mid;//定义两个结点指针
    mid = search = L;//指向开头
    while(search->next != NULL)
    {
        if(search->next->next != NULL)
        {
            search = search->next->next;//一次跳两下，跳到倒数第二个就不跳了
            mid = mid->next;//一次跳一下
        }
        else
        {
            search = search->next;//跳完
        }
    }
    *e = mid->data;
    return OK;
}

课后作业的答案代码如下：

#include <string>
#include <stdio.h>
#include <math.h>
#define OK 1
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node* LinkList;

int get_mid_node(LinkList L, int *e)
{
    LinkList search, mid;//定义两个指针同时开始跑，一个1一个一次跑两下
    mid = search = L;//L表示链表头部
    while (search->next != NULL)
    {
        if(search->next->next != NULL)
        {
            search = search->next->next;
            mid = mid->next;
        } else
        {
            search = search->next;
        }
    }
    *e = mid->data;
    return OK;
}

void CreateListTail(LinkList *L, int n)
{
    LinkList p, r;
    int i;
    srand(time(0));
    *L = (LinkList) malloc(sizeof (Node));//创建链表
    r = *L;//尾指针
    for(i = 0;i < n;i++)
    {
        p = (Node*) malloc(sizeof (Node));//逐个创建结点
        p->data = rand()%100 + 1;//给出数据，rand()返回0和RAND_MAX之间的整数，是一个伪随机数
        r->next = p;//也就是尾插法;
        r = p;//转移尾指针
    }
    r->next = NULL;//最后一个指向空。
}

void PrintList(LinkList L)
{
    LinkList p;//定义指针，就不用分配空间
    for(p = L; p->next != NULL; p = p->next)
    {
        printf("%d\n", p->data);
    }
}

int main()
{
    int n;
    int *mid_value;
    scanf("%d", &n);//输入链表长度
    LinkList *L;
    CreateListTail(L, n);
    PrintList(*L);//输出链表
    get_mid_node(*L, mid_value);
    printf("%d\n", *mid_value);
    return 0;
}

循环链表

事实上我们只需要将单链表中终端指针由空指针改变为指向头结点，就没问题了。

使得整个单链表形成一个环，头尾相接的单链表，成为单循环链表。

两种情况如图所示，哪怕是空表，也要有自己指向自己，成为循环。

其实循环链表与单链表主要差异在于判断空链表的条件上，原来判断head->next是否为null，现在则是head->next是否等于head。终端结点指针用rear表示，查找终端结点是O(1)，而开始结点是rear->next->next，当然也是O(1)。

下面代码是实现初始化链表，插入数据，删除数据和搜索数据等函数的代码集合：

//
// Created by Spencer Zhang on 26/7/2023.
//
#include <stdio.h>
#include <string>

typedef struct Node
{
    int data;
    struct Node* next;
}node;
void ds_init(node **pNode)//这是指向链表的，所以是最外边的，二维指针
{
    int item;
    node *temp;
    node *target;

    printf("输入结点的值，输入0完成初始化\n");

    while (1)
    {
        scanf("%d", &item);
        fflush(stdin);

        if (item == 0)
            return;
        if((*pNode) == NULL)//*pNode指向结点了，也就是第一个结点(就是空链表情况)
        {
            *pNode = (node*) malloc(sizeof(struct Node));//定义一个结点大小
            if(!(*pNode))
                exit(0);//分配空间失败就退出
            (*pNode)->data = item;
            (*pNode)->next = *pNode;//指向自己了，单结点循环了
        } else
        {
            //也就是链表不为空的时候，一直循环直到回来。
            for(target = (*pNode); target->next != (*pNode); target = target->next)
                ;
            //找到位置之后，开始插入结点
            temp = (node*) malloc(sizeof (struct Node));//生成新结点

            if(!temp)
                exit(0);//分配失败就意外退出
            temp->data = item;
            temp->next = *pNode;
            target->next = temp;//其实算尾插法
        }
    }
}

void ds_insert(node **pNode, int i)//插入会动链表，所以用二维指针
{
    node *temp;//插入结点
    node *target;//尾结点
    node *p;
    int item;
    int j = 1;
    printf("输入要插入结点的值:");
    scanf("%d", &item);

    if(i == 1)
    {
        //新插入的结点作为第一个结点，也就是新结点会成为首结点。
        temp = (node*) malloc(sizeof (struct Node));

        if(!temp)
            exit(0);
        temp->data = item;
        temp->next = (*pNode);
        for(target = (*pNode); target->next != (*pNode); target = target->next)//然后需要尾部指向头部，先遍历找到尾部。
            ;
        target->next = temp;
        *pNode = temp;//首结点变成了temp;
    }
    else
    {
        target = *pNode;
        for(; j < (i-1); ++j)//假设插入到第三个位置，i=3, j<2,因为下标2就是第三个结点，循环执行两次执行一次，指向第二个元素了
        {
            target = target->next;
        }
        temp = (node*) malloc(sizeof (struct Node));//准备插入
        if(!temp)
            exit(0);
        temp->data = item;//先赋值

        p = target->next;//原来第三个结点
        target->next = temp;//第二个结点指向temp了
        temp->next = p;//完成链接，这也不叫尾插法了，乱插的，都可以。
    }
}

void ds_delete(node **pNode, int i)//删除会动链表，所以用二维指针
{
    node *target;
    node *temp;
    int j = 1;

    if(i == 1)//如果删除第一个结点
    {
        for(target = *pNode; target->next != *pNode; target = target->next)//find the last node, we can just use "for"
            //without execution sentences
            ;
        temp = *pNode;//第一个结点就是指temp
        *pNode = (*pNode)->next;//因为要删除*pNode所在结点，所以先把它给temp，以后删除，然后把头指针向后推
        target->next = *pNode;//directly point to the lastest *pNode
        free(temp);
    } else
    {
        target = *pNode;//先放置头结点

        for(; j < (i-1); ++j)
        {
            target = target->next;//for example we wanna delete the third node, namely i = 3, j < 2,
            //the cycle will be executed for once, and the target will be the second node
        }
        temp = target->next;//we assign the node which will be deleted to "temp".
        target->next = target->next->next;//just jump the node to be deleted.
        free(temp);
    }
}

int ds_search(node *pNode, int elem)//链表不会改变，用*pNode即可
{
    node * target;
    int i = 1;
    for(target = pNode; target->data == elem && target->next != pNode; ++i)//一直到target->next找到，就跳出循环
    {
        target = target->next;
    }
    if(target->next == pNode && target->data != elem)//找了一圈找回来了，没发现元素
        return 0;
    else
        return -1;
}

约瑟夫问题

这个问题，在密码学的排列问题中也出现了，我们在密码代数中讨论的是排列循环问题，在这里则

下面通过编写循环链表，给出自杀的人的编号。

下面是代码：

#include <stdio.h>
#include <string>
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node* LinkList;

LinkList Create(int n)
{
    LinkList p = NULL;
    LinkList head;//创建头结点
    head = (LinkList) malloc(sizeof (struct Node));
    p = head;//指向头结点。
    LinkList s;

    int i = 1;//从1开始到41
    if(0 != n)
    {
        while(i <= n)//一共生成41个结点。
        {
            s = (LinkList) malloc(sizeof (struct Node));
            s->data = i++;//注意这里=先于++，也就是先赋值i，再++i。终于解决了我们的困惑
            p->next = s;//头结点指向当前结点
            //注意！这里s是第二个结点了，然而s的值才是1，所以这里我们的头结点只是一个没用的结点，最后要去掉
            p = s;//指针指过来。也相当于后插法。
        }
        s->next = head->next;//因为头结点无意义，所以去掉
    }
    free(head);
    return s->next;//返回结点。
}

int main()
{
    int n = 41;
    int m = 3;
    int i;
    LinkList p = Create(n);//p指向第一个结点。
    LinkList temp;

    m %= n;//余3

    while(p != p->next)//只要不到最后，空表的时候自己才指向自己。
    {
        p = p->next;//第二个， 第五个
        printf("%d->", p->next->data);//再向后一个正好是第三个

        temp = p->next;//准备删掉这个该死的结点了。现在temp是第三个， 第二轮正好是第6个
        p->next = temp->next;//删之前先把指针移到下一个。第二个直接指向第4个
        p = p->next;//现在是第四个
        free(temp);
    }
    printf("%d\n", p->data);//最后空表的时候剩下的数据。
    return 0;
}//成功！

循环链表特点

有了头结点时，访问第一个结点用O(1)的时间，访问最后一个需要O(n)的时间。

也就是无需增加存储量，通过灵活改变链接方式，就可以得到很好的处理。

比如链接两个链表！

1.若在单链表或者头指针表示的单链表循环上做这种链接，我们只需要遍历到an然后将b1链接到an后面！执行时间为O(n)

2.若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，时间O(1)。

可以看到，链接到b链表以后，把b的头结点可以扔掉了，因为一个链表只需要一个头结点。

代码如下：

#include <stdio.h>
#include <string>
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node* LinkList;

LinkList Connect(LinkList A, LinkList B)
{
    LinkList p = A->next;//如图中所示，保存A的头结点位置，因为A链表是尾指针代表的，所以要向下指一下。
    A->next = B->next->next;//B的第一个结点，链接到A的尾部的下一个，作为尾插。因为B也是尾指针，所以要向下两次，到第一个结点。
    free(B->next);//释放B的头结点
    B->next = p;//现在把B的下一个，链头结点。
    return B;//返回整个链表。
}//十分简洁！

通常我们用头插法创建无环链表，尾插法创建有环链表。

判断单链表中是否有环

有环的定义：链表的尾结点指向了链表中的某个节点。

方法一：使用p, q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。如图，当p从6走到3时，用了1步，此时若从q出发，用了两步，步数不相等了，存在环。

方法二：使用p, q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p==q，则存在环。

代码实现如下：

#define OK 1
#include <string>
#include <stdio.h>
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node * LinkList;

int HasLoop1(LinkList L)//因为不改变链表，所以用L
{
    LinkList cur1 = L;//结点
    int stp1 = 0;//步数
    while(cur1)
    {
        LinkList cur2 = L;//定义结点cur2
        int stp2 = 0;//cur2的步数
        while(cur2)
        {
            if(cur2 == cur1)//也就是都指向统一结点的时候
            {
                if(stp1 == stp2)//同步，说明没有环
                    break;
                else
                {
                    printf("The position of loop is in the %d node\n\n", stp2);
                    return 1;
                }
            }
            cur2 = cur2->next;//没发现环就继续下一个结点，cur2步数自增。也就是对于每一个cur1，比如cur1到第三个结点了
            //cur2就要从头开始按照箭头走到第3个结点的位置,并且记录走的步数，可以知道，如果有环，步数是不一样的！，
            //如果走到cur2与cur1经历的步数相同！那么就继续向下看下一个结点！
            stp2++;
        }
        cur1 = cur1->next;
        stp1++;
    }
    return 0;
}

用快慢指针判断

代码如下：

int HasLoop2(LinkList L)
{
    int step1 = 1;
    int step2 = 2;
    LinkList p = L;
    LinkList q = L;

    while(p != NULL && q != NULL && q->next != NULL)//因为q是快指针
    {
        p = p->next;
        if(q->next->next !=NULL)
            q = q->next->next;

        printf("p:%d, q:%d\n", p->data, q->data);

        if(p == q)
            return 1;//能到一块，一定有环。
    }
    return 0;
}

魔术师发牌问题

一个很简单的问题，先抽一张牌，保证正好是1，放最后。然后再抽两张牌，第一张放最后，第二张保证是2，放最后。然后再抽三张牌，第一二张放最后，第三张保证为3。用循环链表来实现吧！

图片示例如下：

初始化

执行完两次for循环之后，赋值之后

当第一行1234都被赋值过后，也就是如图所示

4再向下应该找5个，并且再向下的第5个位置数据为5。此时已经遍历回来了。当遍历到1时，也就是p->data != 0

1	因为回到1的时候，1这个牌已经被抽走放下面去了，所以应该不算这次，故用j--抵消j++的自增。同时p向后一个

代码如下：

//
// Created by Spencer Zhang on 2/8/2023.
//
#include <string>
#include <stdio.h>
#include <math.h>

#define CardNumber 13
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
typedef struct Node * LinkList;//定义结点指针

LinkList CreateLinkList()
{
    LinkList head = NULL;//
    LinkList s, r;//表示新结点和指针
    int i;
    r = head;//指针指向头结点

    for(i = 1; i <= CardNumber; i++)
    {
        s = (LinkList) malloc(sizeof(struct Node));//定义新结点
        s->data = 0;

        if (head == NULL)//头结点为空代表空表
            head = s;
        else
            r->next = s;//如果不是空表，那么在添加新结点。
        r = s;//指向新结点。
    }
    r->next = head;//因为是循环，构建了13个元素的循环链表。
    return head;
}

void Magician(LinkList head)//发牌顺序计算，因为对链表无改动，直接放入头结点
{
    LinkList p;
    int j;
    int Countnumber = 2;

    p = head;//头结点看作第一个结点，也就是头结点存放或者不存放数据，都可以！
    p->data = 1;//第一张牌放1

    while(1)
    {
        for(j = 0; j < Countnumber; j++)//第一个循环执行两次，因为
        {
            p = p->next;
            if(p->data != 0)//该位置有牌的话，下一个位置，而第一遍到此只有第一个位置有牌1，所以到这里执行两次后指向3位置，应该存放牌2.
                //第二轮向下指三个，当然仍然都是0，遍历第一遍，都同理。
                //一直到，如图所示的1234都被赋值了，开始遍历回来的时候
            {
                p = p->next;//因为回到1的时候，1这个牌已经被抽走放下面去了，所以应该不算这次，故用j--抵消j++的自增。同时p向后一个
                j--;
            }
        }
        if (p->data == 0)//第一遍后面都是0，所以上面遍历两次之后，指3的位置，放牌2。并且Countnumber++
        {
            p->data = Countnumber;
            Countnumber++;//现在是3了，继续回去循环。

            if(Countnumber == 14)//加多了就退出所有循环。
                break;
        }
    }
}

//销毁工作
void DestoryList(LinkList* list)//因为对链表有改动，所以用链表指针
{

}

int main()
{
    LinkList p;
    int i;

    p = CreateLinkList();
    Magician(p);
    printf("按如下顺序排列：\n");
    for(i = 0; i < CardNumber; i++)
    {
        printf("黑桃%d", p->data);
        p = p->next;
    }

    DestoryList(&p);//&p也就是p的外层，结点的外层，就是链表
    return 0;
}

拉丁方阵问题

其实就像数独！同样用循环链表来解决！比如n=3时，我们可以打印如下

只需要一行一行打印，下一行向后错一个即可！

双向链表

比如我们的铁路，一定设计成双向的，从A到B到C，比如从B想去A就可以直接B->A而不是通过环B->C->A很麻烦。所以双向链表很重要。

结点结构

代码如下：

#include <stdio.h>
#include <string>

typedef struct DualNode
{
    int data;
    struct DualNode *prior;//前驱结点
    struct DualNode* next;//后继结点
}DualNode;

typedef struct DualNode* DuLinkList;//双向链表指针

可以看到也就是在每个结点多了一个域，指向后面的。并且可以看到空链表的双循环链表。

下图是非空的双循环链表。

双向链表的插入操作

如图所示

代码实现，注意图中画的箭头（1）的部分应该指在P结点中间，箭头有些歪了。

s->next = p;
s->prior = p->prior;#也就是先把新结点的箭头都钩上，再将其插进原来两个结点中间去。
p->prior->next = s;
p->prior = s;

双向链表的删除操作

如图所示，我们也是先将两个最后要链接在一起的结点连到一起，之后再释放中间的结点，这样不会出错。

代码如下：

1
2
3

p->prior->next = p->next;#把上一个连给下一个
p->next->prior = p->prior;#把下一个连回上一个
free(p);#释放中间的

双向循环链表实践

要求实现用户输入一个数使得26个字母的排列发生变化，比如用户输入3，输出结果：

DEFG…..ABC

同时需要支持负数，比如用户输入-3，输出结果

XYZABC….UVW

下面开始从0实现，如图所示。

我们可以看出，生成的时候，每生成一个新结点，就

代码如下：生成B的时候

q->prior = p;
q->next = p->next;//这里其实是null指针
p->next = q;//就链上了。
p = q;一直循环下去就可以生成链表

我们只需要用p, q两个指针循环生成即可。

全部代码如下：

//
// Created by Spencer Zhang on 4/8/2023.
//
#include <string>
#include <stdio.h>
#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;

typedef struct DualNode
{
    ElemType data;
    struct DualNode *prior;
    struct DualNode *next;
}DualNode, *DuLinkList;

Status InitList(DuLinkList *L)//初始化链表L，所以用链表指针
{
    DualNode *p, *q;//定义两个指针
    int i;

    *L = (DuLinkList ) malloc(sizeof (struct DualNode));
    if (!(*L))
        return ERROR;//也就是分配失败

    (*L)->next = (*L)->prior = NULL;//初始化都是null，因为没有值
    p = (*L);//也就是此时p指向头结点，是没有元素的！

    for(i = 0; i < 26; i++)
    {
        q = (DualNode*) malloc(sizeof (struct DualNode));//分配空间，也就是新结点
        if(!q)
            return ERROR;
        q->data = 'A' + i;//ascii形式赋值，下一次就是‘B’

        q->prior = p;
        q->next = p->next;
        p->next = q;//下面让p, q都指向q所在新结点，链起来了
        p = q;
    }//形成循环，不断生成新结点。
//现在p,q都在最后一个结点
    p->next = (*L)->next;//指向形成正循环！
    (*L)->next->prior = p;//这里写p,q都一样，指回来了
    return OK;
}

void Caesar(DuLinkList *L, int i)
{
    if(i > 0)//也就是整个链表向后移动，输出从CD等开始
    {
        do
        {
            (*L) = (*L)->next;
        }while(--i);
    }
    if(i < 0)
    {
        do
        {
            (*L) = (*L)->prior;
        }while(++i);//这里为什么都用do while为什么用--i和++i
    }
}

int main()
{
    DuLinkList L;//生成结点
    int i, n;
    printf("请输入一个整数；");
    scanf("%d", &n);
    printf("\n");

    InitList(&L);//传入的是链表指针
    Caesar(&L, n);

    for(i = 0; i < 26; i++)
    {
        L = L->next;
        printf("%c", L->data);//打印出各个字母
    }
    return 0;
}