单链表-数据结构

单链表-数据结构

代码定义单链表
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
//typedef struct LNode LNode; //typedef关键字(数据类型重命名)
struct LNode{ //定义单链表节点类型
    ElemType data; //每个节点存放一个数据元素
    struct LNode *next; //指针指向下一个节点
}LNode,*LinkList; //数据类型重命名的另一种方式,等价于typedef
//新增节点,在内存中申请一个节点所需空间,并用指针p指向这个节点
struct LNode * p=(struct LNode *) malloc(sizeof(struct LNode));
//LNode * P=(LNode *)malloc(sizeof(LNode)) //重命名后写法

要表示一个单链表时,只需声明一个头指针L,指向单链表的第一个结点,这样可以使代码的可读性更强。

LNode * L //声明一个指向单链表第一个结点的指针
LinkList L //声明一个指向单链表第一个节点的指针

在定义单链表方法时,**LNode * 返回的结果是一个结点,并且在指定子函数形参时,LinkList**指明操作的对象是一个单链表,如代码所示。

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

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

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

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

  1. 首先,创建一个头结点并将其指向 NULL,表示初始为空链表。
  2. 然后,循环读取用户输入的数据,直到用户输入 9999 表示结束。
  3. 在循环中,创建一个新节点,并将用户输入的值赋给新节点的数据域。
  4. 将新节点插入到链表的头部,即将新节点的 next 指针指向原来头节点的下一个节点,并将头节点的 next指针指向新节点。
  5. 继续读取用户输入的数据,重复上述步骤,直到用户输入 9999。
  6. 最后,函数返回建立好的链表的头指针。
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>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LNode, *LinkList;
//初始化一个空的单链表

bool InitList(LinkList &L){
    L=NULL; //空表,暂时还没有任何结点(防止脏数据)
    return true;
}

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

int main()
{
    LinkList L; //声明一个指向单链表的指针(此时并没有创建一个节点)
    //初始化一个空表
    InitList(L);
    //...后续代码...
    return 0;
}
带头结点的单链表
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LNode, *LinkList;
//初始化一个空的单链表

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

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

int main()
{
    LinkList L; //声明一个指向单链表的指针(此时并没有创建一个节点)
    //初始化一个空表
    InitList(L);
    //...后续代码...
    return 0;
}

不带头节点,书写代码会更麻烦,对于第一个数据结点和后续数据结点的处理需要用不同的代码逻辑。对空表和非空表的处理需要用不同的代码逻辑。头结点不存储数据,但操作起来会更方便。

单链表的插入和删除
插入:

1、按位置插入

​ ①带头结点

​ ②不带头结点

2、指定结点的后插操作

3、指定结点的前插操作

删除:

1、按位序删除

2、指定结点的删除

按位序插入(带头结点)

定义子函数的名称为ListInsert(&L,i,e)。在表L的第i个位置插入指定元素e。思路:找到第i-1个结点,将新结点插入其后,头结点可以看作第0个结点。

typedef int ElemType;
typedef 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=L; //L指向头结点,头节点是第0个结点(不存储数据)
    while (p!=NULL && j<i-1) //循环找到第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; //将结点s链接到结点p之后
    return true; //插入成功
}

读者可以画图模拟代码的执行过程,链表的长度为5,头节点加4个数据结点,插入位置尝试1、5、7,观察代码的执行过程,尝试交换语句s->next=p->next;和p->next=s;观察代码是否还能正常执行。

按位序插入(不带头结点)

定义子函数的名称为ListInsert(&L,i,e)。在表L的第i个位置插入指定元素e。思路:找到第i-1个结点,将新结点插入其后,由于不存在第0个结点(头结点),因此在i=1时需要特殊处理。

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

typedef int ElemType;
typedef 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)
    {
        LNode *s=(LNode *) malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
    LNode *p; //指针p指向当前扫描到的结点
    int j=1; //当前p指向的是第几个结点
    p=L; //p指向第1个结点(不是头结点)
    while (p!=NULL && j<i-1) //循环找到第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; //将结点s链接到结点p之后
    return true; //插入成功
}
int main()
{
    return 0;
}

注意:p = L和 p->next = L是不等价的。

  • p = L 将指针 p 指向了链表的头节点 L,它只是将 p 指向了 L 所指向的内存地址,而没有改变原链表结构。
  • p->next = L 则是将 p 所指向的节点的指针域 next 指向了链表的头节点 L,这意味着它改变了链表结构,将 p 所指向的节点与头节点L 相连接,使得 L 成为了 p 所指向的节点的下一个节点。

在具体的插入操作中,p = L 用于将 p 指向链表中的某个位置,以便于遍历链表。而 p->next = L 用于将新节点插入到 p 所指向的节点的后面,以完成插入操作。这两个语句的作用不同,因此不是等价的。

提供一段测试代码,供读者调试,观察指针的变化过程。

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

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

int main()
{
    LNode *p;
    LNode *c;
    LNode *b;
    b=(LNode *)malloc(sizeof(LNode));
    p->next=b;
    c=p;
    return 0;
}

结果如图所示

指针调试

指定结点的后插操作
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
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;
}
int main()
{
    return 0;
}

完成指定节点后插操作的子函数后,可以将此模块进行封装,在其他程序内调用,简化代码。

指定结点的前插操作

在之前的实验中,都是使用的后插法,但是对于前插操作我们并不熟悉。

方法有二,其一是插入一个头结点,假如需要在 p 前插入结点,通过头结点,找到 p 的前驱结点q,再对结点q使用后插法,变相完成了前插操作。方法二是先后插,再交换节点中的内容,也是变相完成了前插操作。

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

typedef int ElemType;
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;
}
int main()
{
    return 0;
}

按位序删除(带头节点)

定义子函数的名称为ListDDelete(&L,i,e)。删除表 L 中第i个位置的元素,并用e返回删除元素的值,思路:找到第i-1个结点,将其指针指向第 i+1 个结点,并释放第 i 个结点,头结点可以看做第0个节点。

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

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

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)
    {
        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; //删除成功
}
int main()
{
    return 0;
}

读者可以思考,果是不带头结点,删除第一个元素时,是否需要特殊处理?下面附带代码供读者参考。

bool ListDelete(LinkList& L, int i, ElemType& e) {
    if (i < 1) {
        return false;
    }
    if (i == 1) { // 删除第一个节点
        if (L == NULL || L->next == NULL) { // 链表为空或只有一个节点
            return false;
        }
        LNode* q = L->next; // 待删除的节点
        e = q->data;        // 保存数据
        L->next = q->next;  // 更新头节点的下一个指针
        free(q);            // 释放节点
        return true;        // 删除成功
    }

// 删除非第一个节点的代码
LNode* p = L; // 指针p指向当前扫描到的结点
int j = 1;    // 当前p指向的是第几个结点
while (p != NULL && j < i - 1) {
    p = p->next;
    j++;
}
if (p == NULL || p->next == NULL) {
    return false; // 位置无效
}
LNode* q = p->next; // 待删除的节点
e = q->data;        // 保存数据
p->next = q->next;  // 将*q结点从链中"断开"
free(q);            // 释放节点删除空间
return true;        // 删除成功

}
指定结点的删除

需要删除某个结点,需要修改其前驱节点的next指针。实现的方法跟上面的前插法类似,插入头指针循环查找删除结点的前驱结点的next指针,或者是偷天换日,类似前插法的第二个方法。

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

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

//删除指定结点p
bool DeleteNode(LNode *p){
    if(p=NULL)
    {
        return false;
    }
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
    return true;
}
int main()
{
    return 0;
}

单链表的局限性:无法逆向检索。如果p是最后一个结点,上述代码会无法执行。每次寻找能从表头开始寻找p的前驱节点,时间复杂度为O(n)。

单链表的查找(按位查找、按值查找)

在上面的单链表的插入和删除代码中,已经有查找的操作,但是查找的是第i-1个节点,所以需要对代码进行修改。

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

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

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

代码需要考虑边界情况

1、查找 i=0,此时返回头结点地址。

2、查找 i=6 (超过链表长度),假设链表长度为 4,会出现p->next=NULL的情况,在循环结束时,p 会指向链表的末尾节点的下一个位置,也就是 NULL。因为在循环中 j 会递增到 4,而 p 会指向第 4 个节点的下一个位置(即空地址)。因此,返回的 p 将是 NULL。附带实验代码供读者参考。

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

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

// 创建一个只有头结点的链表
LinkList createList() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL; // 初始时链表为空
    return L;
}

// 在链表头部插入新节点
void insertNode(LinkList L, ElemType data) {
    LNode* newNode = (LNode*)malloc(sizeof(LNode));
    newNode->data = data;
    newNode->next = L->next;
    L->next = newNode;
}

// 获取链表中的第i个节点
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    int j = 0;
    LNode* p;
    p = L->next; // 头结点不存储数据,从第一个节点开始
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

int main() {
    // 创建链表
    LinkList L = createList();

    // 向链表中插入一些数据
    insertNode(L, 10);
    insertNode(L, 20);
    insertNode(L, 30);

    // 测试 GetElem 函数
    for (int i = 0; i <= 5; i++) {
        LNode* node = GetElem(L, i);
        if (node == NULL) {
            printf("Position %d: NULL\n", i);
        } else {
            printf("Position %d: %d\n", i, node->data);
        }
    }

    // 释放链表中的内存空间
    LNode* temp;
    while (L->next != NULL) {
        temp = L->next;
        L->next = temp->next;
        free(temp);
    }
    free(L); // 释放头结点内存

    return 0;
}
按值查找
#include <stdio.h>
#include <stdlib.h>

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

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

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

求表的长度
#include <stdio.h>
#include <stdlib.h>

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

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