数据结构：单链表的基本操作

快来打我* 2022-05-25 03:55 319阅读 0赞

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元可以是连续的，也可以是不连续的。链表中的数据是以结点来表示的，一个结点包含数据域和指针域，数据域用来存储结点的值，指针域用来存储数据域的直接后继的地址，单链表结点的而结构如下图：  
![这里写图片描述][Image 1]  
        一般情况下使用链表只关心链表中结点之间的逻辑关系，并不关心链表的每个结点的实际存储位置，通常用箭头来表示链域中的指针，链表的逻辑结构可以直观的画成用箭头链接起来的结点序列。  
![这里写图片描述][Image 1]

##### C语言描述单链表的存储结构 #####

typedef int DataType;
    
    typedef struct Node
    {
        DataType Data;
        struct Node* Next;
    }Node, *LinkList;

其中Node表示链表的结点类型，LinkList表示链表的指针类型，通常用Node\* 定义链表的结点指针，用LinkList定义链表的头指针。

--------------------

##### 单链表的基本操作 #####

**（1）单链表的初始化**

单链表的初始化就是把单链表初始化为空，带头节点的单链表的初始化需要为头结点分配存储空间，并将头节点的指针域置空。

void InitList(LinkList* PHead)
    {
        if ((*PHead = (LinkList)malloc(sizeof(Node))) == NULL)
        {
            printf("内存申请失败!\n");
            return;
        }
        (*PHead)->Next = NULL;
    }

**（2）判断单链表是否为空**

判断单链表是否为空，就是看单链表的头结点的指针域是否为空，即：`PHead->Next == NULL`是否为真。

int ListEmpty(LinkList PHead)
    {
        return  PHead->Next == NULL;
    }

**（3）头插法建表**

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志（-1）为止。

//头插法建表
    void CreatFormHead(LinkList PHead)
    {
        DataType data; 
        Node* s;             //要插入的结点指针
        scanf("%d", &data);
        while (data != -1)    //输入要插入的值以-1作为结束标志
        {
            s = (Node*)malloc(sizeof(Node));
            s->Data = data;
            s->Next = PHead->Next;
            PHead->Next = s;
            scanf("%d", &data);
        }
    }

**（4）尾插法建表**

尾插法建表是将新结点插入到当前链表的表尾上。为此必须增加一个尾指针tail，使其始终指向当前链表的尾结点。

//尾插法建表
    void CreatFormTail(LinkList PHead)
    {
        Node* s;
        Node* tail;             
        DataType data;
        tail = PHead;
        scanf("%d", &data);
        while (data != -1)
        {
            s = (Node*)malloc(sizeof(Node));
            s->Data = data;
            s->Next = tail->Next;
            tail->Next = s;
            tail = s;   //tail始终指向表尾
            scanf("%d", &data);
        }
    }

**（5）按序号查找**

按序号查找，即查找序号为i的元素对应的值，如果找到的话，返回结点的指针p，对应的值可以通过`p->Data`打印，定义一个指针p使其指向头指针`p = PHead;`从头指针开始，一直往后查找，定义一个变量j初始化为0，指针p每次后移一位，`j++`当j=i时跳出循环，返回指向第i个结点的指针p，在查找元素是要判断表是否为空，保证p的下一个结点不为空，否则，就没有办法保证执行循环体中的`p = p->Next;`

Node* Get(LinkList PHead, int i)
    {
        Node* p;   //结点指针
        int j = 0;
        p = PHead;
        if (ListEmpty(PHead))    //空表
        {
            printf("表为空！\n");
            return 0;
        }
        while (!ListEmpty(PHead) && j < i)
        {
            p = p->Next;
            j++;
        }
        if (j == i)
        {
            return p;   /*返回指向第i个结点的指针p*/
        }
        return NULL;
    }

**（6）按值查找**

按值查找，即查找单链表中与给定元素data相等的元素，并返回这个元素的下标。定义一个变量i赋初值为1，从第一个结点（头结点的下一个结点）`PHead->Next`开始一直往后查找，指针p每次后移一位`i++`当`p->Data != data`时跳出循环，返回i的值即为要查找的元素data在链表中的位置。

//按值查找
    int Locate(LinkList PHead, DataType data)
    {
        Node*p = PHead->Next;
        int i = 1;
        while (p)
        {
            while (`p->Data != data`)
            {
                p = p->Next;
                i++;
            }
            break;              //找到节点时退出循环
        }
        return i;
    }

**（7）求表长操作**

链表的长度即链表中元素的个数，定义一个变量`int len = 0;`定义一个指针`p = PHead;`从头结点开始依次遍历链表中的每个结点，指针每后移一次`len++;`，当链表为空即`p->Next != NULL`时跳出循环，返回len的值。

//求单链表的长度
    int length(LinkList PHead)
    {
        Node *p;
        p = PHead;
        int len = 0;
        while (p->Next != NULL)
        {
            len++;
            p = p->Next;
        }
        return len;
    }

**（8）插入操作**

在单链表的第i个位置插入一个元素data，首先需要找到要插入位置的前驱结点位置，即：第i-1个结点，定义一个指针p指向头结点，从头结点开始一直往后查找，当要插入的位置j=i-1时，跳出循环，指针p指向该节点。然后，创建一个新结点，使指针s指向新创建的结点，将要插入的数据data,赋给新创建的结点的数据域`s->Data = data;`将新结点的指针域指向第i个结点`s->Next = p->Next;`将第i-1个结点的指针域指向新结点`p->Next = s`；

//任意位置插入
    void InsList(LinkList PHead, int i, DataType data)
    {
        Node*p;
        Node*s;
        p = PHead;
        int j = 0;
        while (p->Next != NULL && j < i - 1)
        {
            p = p->Next;
            j++;
        }
        if (p == NULL)
        {
            return; //插入位置不合法
        }
        s = (Node*)malloc(sizeof(Node));  //新建一个结点
        s->Data = data;
        s->Next = p->Next;
        p->Next = s;
    }

**（9）删除操作**

将单链表的第i个结点删除，data用于存放删除结点的值，删除第i个结点同样也需要找到第i个结点的前驱结点，定义一个指针p指向头结点，从头往后查找第i-1个结点，如果找到则指针p指向要删除操作的前驱结点（第i-1个结点），s指向要删除的节点i`s = p->Next;`，将前驱结点的指针域指向要删除结点的下一个结点`p->Next = s->Next;`也就是让s指向的结点与单链表断开，然后释放s指向的结点，即释放要删除结点的空间，返回删除结点的值`*data`在删除操作时要判断删除的位置是否合法。

//任意位置删除
    int DelList(LinkList PHead, int i, DataType* data)
    {
        Node* p;
        Node* s;
        p = PHead;
        int k = 0;
        /*删除位置i小于0，或者删除位置大于元素个数， 比如链表中只有一个元素，i=2时*/
        if (i < 0 || i>length(PHead))
        {
            printf("删除位置不合法！\n");
            return 0;  //删除位置不合法
        }
        while (p->Next != NULL && k < i - 1)
        {
            p = p->Next;
            k++;
        }
        s = p->Next;
        *data = s->Data;
        p->Next = s->Next;
        free(s);
        return *data;
    }

**（10）销毁链表**

单链表的结点是动态申请的，在程序结束时将这些结点空间通过`free`函数释放。

//销毁链表
    void DestoryList(LinkList PHead)
    {
        Node* p;
        Node* q;
        p = PHead;
        while (p->Next != NULL)
        {
            q = p;
            p = p->Next;
            free(q);
        }
    }

**（11）打印表中元素**

依次打印顺序表中的元素。

void PrintList(LinkList PHead)
    {
        Node* p;
        p = PHead->Next;
        while (p)
        {
            printf("%d ", p->Data);
            p = p->Next;
        }
        printf("\n");
    }

##### 单链表的基本操作源代码 #####

**LinkList.h**定义链表的数据结构和链表 操作的函数声明

#ifndef __LinkList_H__
    #define __LincList_H__
    
    typedef int DataType;
    
    typedef struct Node
    {
        DataType Data;
        struct Node* Next;
    }Node, *LinkList;
    
    void InitList(LinkList* PHead);   //单链表的初始化
    int ListEmpty(LinkList PHead);    //判断单链表是否为空
    void CreatFormHead(LinkList PHead); //头插法建表
    void CreatFormTail(LinkList PHead); //尾插法建表
    Node* Get(LinkList PHead, int i);  //按序号查找
    int Locate(LinkList PHead, DataType data); //按值查找
    int length(LinkList PHead); //求表长操作
    void InsList(LinkList PHead, int i, DataType data); //插入操作
    int DelList(LinkList PHead, int i, DataType* data); //删除操作
    void DestoryList(LinkList PHead);  //销毁顺序表
    void PrintList(LinkList PHead);    //打印表中元素
    
    #endif

**LinkList.c** 单链表操作函数的具体实现

#include <stdio.h>
    #include <stdlib.h>
    #include "LinkList.h"
    
    //单链表的初始化
    
    void InitList(LinkList* PHead)
    {
        if ((*PHead = (LinkList)malloc(sizeof(Node))) == NULL)
        {
            printf("内存申请失败!\n");
            return;
        }
        (*PHead)->Next = NULL;
    }
    
    //判断单链表是否为空
    
    int ListEmpty(LinkList PHead)
    {
        return  PHead->Next == NULL;
    }
    
    //头插法建表
    void CreatFormHead(LinkList PHead)
    {
        DataType data; 
        Node* s;             //要插入的结点指针
        scanf("%d", &data);
        while (data != -1)    //输入要插入的值以-1作为结束标志
        {
            s = (Node*)malloc(sizeof(Node));
            s->Data = data;
            s->Next = PHead->Next;
            PHead->Next = s;
            scanf("%d", &data);
        }
    }
    
    //尾插法建表
    void CreatFormTail(LinkList PHead)
    {
        Node* s;
        Node* tail;             
        DataType data;
        tail = PHead;
        scanf("%d", &data);
        while (data != -1)
        {
            s = (Node*)malloc(sizeof(Node));
            s->Data = data;
            s->Next = tail->Next;
            tail->Next = s;
            tail = s;   //tail始终指向表尾
            scanf("%d", &data);
        }
    }
    
    //按序号查找
    
    Node* Get(LinkList PHead, int i)
    {
        Node* p;   //结点指针
        int j = 0;
        p = PHead;
        if (ListEmpty(PHead))    //空表
        {
            printf("表为空！\n");
            return 0;
        }
        while (!ListEmpty(PHead) && j < i)
        {
            p = p->Next;
            j++;
        }
        if (j == i)
        {
            return p;   /*返回指向第i个结点的指针p*/
        }
        return NULL;
    }
    
    
    //按值查找
    int Locate(LinkList PHead, DataType data)
    {
        Node*p = PHead->Next;
        int i = 1;
        while (p)
        {
            while (p->Data != data)
            {
                p = p->Next;
                i++;
            }
            break;              //找到节点时退出循环
        }
        return i;
    }
    
    //求单链表的长度
    int length(LinkList PHead)
    {
        Node *p;
        p = PHead;
        int len = 0;
        while (p->Next != NULL)
        {
            len++;
            p = p->Next;
        }
        return len;
    }
    
    //任意位置插入
    void InsList(LinkList PHead, int i, DataType data)
    {
        Node*p;
        Node*s;
        p = PHead;
        int j = 0;
        while (p->Next != NULL && j < i - 1)
        {
            p = p->Next;
            j++;
        }
        if (p == NULL)
        {
            return; //插入位置不合法
        }
        s = (Node*)malloc(sizeof(Node));  //新建一个结点
        s->Data = data;
        s->Next = p->Next;
        p->Next = s;
    }
    
    //任意位置删除
    int DelList(LinkList PHead, int i, DataType* data)
    {
        Node* p;
        Node* s;
        p = PHead;
        int k = 0;
        /*删除位置i小于0，或者删除位置大于元素个数， 比如链表中只有一个元素，i=2时*/
        if (i < 0 || i>length(PHead))
        {
            printf("删除位置不合法！\n");
            return 0;  //删除位置不合法
        }
        while (p->Next != NULL && k < i - 1)
        {
            p = p->Next;
            k++;
        }
        s = p->Next;
        *data = s->Data;
        p->Next = s->Next;
        free(s);
        return *data;
    }
    
    
    //销毁链表
    void DestoryList(LinkList PHead)
    {
        Node* p;
        Node* q;
        p = PHead;
        while (p->Next != NULL)
        {
            q = p;
            p = p->Next;
            free(q);
        }
    }
    
    
    //打印表中元素
    void PrintList(LinkList PHead)
    {
        Node* p;
        p = PHead->Next;
        while (p)
        {
            printf("%d ", p->Data);
            p = p->Next;
        }
        printf("\n");
    }

**main.c** 操作函数的简单测试代码

#include <stdio.h>
    #include <stdlib.h>
    #include <Windows.h>
    #include "LinkList.h"
    
    int main()
    {
        LinkList L;
        LinkList L1;
        DataType data;
        int num;   //需要操作的元素序号
        int val;   //插入元素值 
        InitList(&L);
        InitList(&L1);
        printf("头插法建表(L1)：");
        CreatFormHead(L1);
        printf("链表中的元素有:\n");
        PrintList(L1);
        printf("\n");
        printf("尾插法建表(L)：");
        CreatFormTail(L);
        //后面为对尾插法所建表的操作
        printf("链表中的元素有:\n");
        PrintList(L);
        printf("\n");
        printf("在链表中插入一个元素：\n");
        printf("请输入插入位置：");
        scanf("%d", &num);
        printf("请输入插入元素值：");
        scanf("%d", &val);
        InsList(L, num, val);
        printf("链表中的元素有:\n");
        PrintList(L);
        printf("\n");
        printf("删除链表中的元素:\n");
        printf("请输入删除位置：");
        scanf("%d", &num);
        DelList(L, num, &data);
        printf("删除元素的值为%d\n", data);
        printf("\n");
        printf("链表中的元素有:\n");
        PrintList(L);
        printf("\n");
        printf("链表的长度为：%d\n", length(L));
        printf("\n");
        printf("请输入要查找的元素序号：\n");
        scanf("%d", &num);
        Node* p = Get(L, num);
        printf("第%d 个元素值为：%d\n", num, p->Data);
        printf("请输入要查找的元素值：\n");
        scanf("%d", &val);
        printf("%d在表中的位置序号为：%d\n", val, Locate(L, val));
        printf("\n");
        system("pause");
    
        return 0;
    }

[Image 1]: