C语言单链表基本操做,很是全面

2022年05月10日 阅读数:3
这篇文章主要向大家介绍C语言单链表基本操做,很是全面,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

单链表的基本操做分享:node

/********************* 单链表的常规操做 ****************************/

LinkList CreateHeadListH();            // 头插法建立单链表
LinkList CreateHeadListT();            // 尾插法建立单链表
int      ListEmpty();                  // 单链表判空
int      ListLength();                 // 求单链表长度
void     Travel();                     // 遍历单链表
int      InsertNode();                 // 插入结点
int      DeleteNode();                 // 删除结点
ElemType GetElem();                    // 按址查值
int      GetLocate();                  // 按值查址
int      RemoveRepeat();               // 去除重复的值

/*****************************************************************/

定义单链表结构体

单链表是由多个结点连接组成,它的每一个结点包含两个域,一个数据域和一个连接域(地址域)。git

  • 数据域 data 用来存放具体的数据。
  • 地址域 next 用来存放下一个节点的位置。
#include "stdio.h"
#include "malloc.h"


#define TRUE  1
#define FALSE 0

typedef int ElemType;        // 单链表存储元素的数据类型

// 定义单链表结构体
typedef struct Node(){
    ElemType data;            // 单链表结点数据域
    struct Node *next;        // 单链表结点地址域(指向下一个结点)
}*LinkList, Node;

构造单链表

头插法实现

/*
 *    头插法建立单链表(带头结点)
 *    datas 接收数组,用于赋值链表的结点数据
 *    len datas数组的长度,便于遍历
*/
LinkList CreateHeadListH(ElemType *datas, int len){
    // 建立头结点
    LinkList head, new_node;
    head = (LinkList)malloc(sizeof(Node));
    // head -> data = len;    // 能够把链表长度存在头结点的数据域中
    head -> next = NULL;

    // 分配新节点并用头插法连接起来
    for(int i=0;i<len;i++){
        new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = head -> next;
        head -> next = new_node;
    }
    return head;
}

头插法构造单链表时一直往单链表的头部插入结点github

尾插法实现

/*
 *    尾插法建立单链表(带头结点)
 *    datas 接收数组,用于赋值链表的结点数据
 *    len datas数组的长度,便于遍历
*/
LinkList CreateHeadListT(ElemType *datas, int len){
    // 建立头结点
    LinkList head, p, new_node;
    head = (LinkList)malloc(sizeof(Node));
    head -> next = NULL;
    p = head;

    // 分配新节点并用尾插法连接起来
    for(int i=0;i<len;i++){
        new_node = (LinkList)malloc(sizeof(Node));
        new_node -> data = datas[i];
        new_node -> next = NULL;
        p -> next = new_node;
        p = new_node;
    }
    return head;
}

尾插法构造单链表时一直往单链表的尾部插入结点数组

单链表的头尾插法详解

为了避免让文章篇幅过长,关于单链表头尾插法的更多具体内容请观看个人另外一篇博客 单链表的头尾插法详解post

单链表判空

/*
 *    单链表判空
 *    list 接收单链表
*/
int ListEmpty(LinkList list){
    return (list == NULL || list -> next == NULL);
}

计算单链表长度

/*
 *    计算单链表的长度
 *    list 接收单链表
*/
int ListLength(LinkList list){
    LinkList p = list;
    int len = 0;
    if(ListEmpty(list)){
        return len;
    }
    p = p -> next;
    while(p != NULL){
        len ++;
        p = p -> next;
    }
    return len;
}

遍历单链表

/*
 * 遍历单链表
 * list 单链表
*/
void Travel(LinkList list){
    LinkList p = list;
    if(!ListEmpty(list)){    // 单链表非空状况下才遍历
        p = p -> next;        // 由于带头结点单链表因此要先走一步
        while(p != NULL){
            printf("%d\t", p -> data);
            p = p -> next;
        }
        printf("\n");
    }
}

单链表头、尾插法构造效果

int main(int argc, char const *argv[])
{
    int datas[] = {2, 4, 6, 8, 10};
    // 动态计算datas数组的长度
    // 数组长度 = 数组的总空间大小 / 数组中每一个元素所占空间大小
    int len = sizeof(datas) / sizeof(datas[0]);

    printf("头插法构造单链表\n");
    LinkList list_h = CreateHeadListH(datas, len);
    printf("ListEmpty():%d\n", ListEmpty(list_h));        // 判空
    printf("ListLength():%d\n", ListLength(list_h));    // 求长
    printf("Travel():");                                
    Travel(list_h);                                        // 遍历

    printf("\n尾插法构造单链表\n");
    LinkList list_t = CreateHeadListT(datas, len);
    printf("ListEmpty():%d\n", ListEmpty(list_t));
    printf("ListLength():%d\n", ListLength(list_t));
    printf("Travel():");
    Travel(list_t);
    return 0;
}

由于数组是在连续的地址上存储元素,因此能够动态的计算数组的长度,方便遍历。ui

输入结果以下:3d

头插法构造单链表
ListEmpty():0
ListLength():5
Travel():10     8       6       4       2

尾插法构造单链表
ListEmpty():0
ListLength():5
Travel():2      4       6       8       10

请按任意键继续. . .

单链表指定位置插入结点

代码实现指针

/*
 * 单链表指定位置插入结点
 * list 单链表
 * data 要插入的结点的数据
 * pos  结点插入的位置(逻辑位置(1,2,3,...))
*/
int InsertNode(LinkList list, ElemType data, int pos){
    LinkList p = list, new_node;
    if(ListEmpty(list)){
        printf("空单链表\n");
        return FALSE;
    }

    // 判断插入位置是否合理
    if(pos <= 0 || pos > ListLength(list) + 1){
        printf("插入位置不合理\n");
        return FALSE;
    }
     
    // 寻找到要插入位置的前一个结点
    for(int i = 0; i < pos - 1 && p != NULL; i++){
        p = p -> next;
    }

    // 准备新结点
    new_node = (LinkList)malloc(sizeof(Node));
    new_node -> data = data;

    // 此时p就是要插入位置的前一个结点,p -> next就是要插入位置的结点
    new_node -> next = p -> next;    
    p -> next = new_node;
    return TRUE;
}

详细图解code

假设原单链表为:head --> 2 --> 6 ,要插入的结点值为 4,插入位置为 2。blog

只需找要插入位置的前一个结点就行,由于插入位置的前一个结点的地址域保存着要插入位置的结点

此时找到的结点是 new_code1,而 new_code1 -> next 就是结点 new_code2

因此咱们只要

new_code3 -> next = new_code1 -> next;
new_code1 -> next = new_code3; 

先让待插入结点的地址域指向插入位置的结点

后让插入位置的前一个结点的地址域指向待插入结点。

1, 2, 3表明单链表结点位置

①,②,③表明插入操做的执行步骤顺序

注意:千万不能先让插入位置的前一个结点的地址域指向待插入结点,后让待插入结点的地址域指向插入位置的结点

new_code1 -> next = new_code3;
// 此时new_code1 -> next 等于 new_code3, now_code3 -> next = new_code3 没有达到连接
new_code3 -> next = new_code1 -> next;    

单链表指定位置删除结点

代码实现

/*
 * 单链表指定位置删除结点
 * list 单链表
 * *val 用来存储删除结点的数据
 * pos  结点删除的位置(逻辑位置(1,2,3,...))
*/
int DeleteNode(LinkList list, ElemType *val, int pos){
    LinkList p = list, r;
    if(ListEmpty(list)){
        printf("空单链表\n");
        return FALSE;
    }

    // 判断删除位置是否合理
    if(pos <= 0 || pos > ListLength(list)){
        printf("删除位置不合理\n");
        return FALSE;
    }

    // 寻找到要删除结点的前一个位置
    for(int i = 0; i < pos - 1 && p != NULL; i++){
        p = p -> next;
    }

    r = p -> next;            // 记录要删除的结点
    *val = r -> data;        // 把删除结点的数据利用指针返回去
    p -> next = r -> next;    // 把链表从新连接起来
    free(r);                // 释放删除结点的资源
    return TRUE;
}

详细图解

假设原单链表为:head --> 2 --> 4 --> 6 ,删除第 2 个结点。

仍是跟插入同样只需找要删除位置的前一个结点就行

此时找到的结点是 new_code1,而 new_code1 -> next 就是结点 new_code2 ,就是要删除的结点。

r = new_code1 - > next;                
new_code1 -> next = r -> next;        // new_code1 -> next = new_code2 -> next;
free(r);    

先让变量 r 等于要删除的结点 ,

r = new_code1 - > next; --> r = new_code2;

后让删除位置的前一个结点的地址域指向要删除结点的后一个结点。

new_code1 -> next = r -> next;            // 此时r -> next 等于 new_code2
            ↓↓     
new_code1 -> next = new_code2 -> next;    // new_code2 -> next 等于 new_code3
            ↓↓
new_code1 -> next = new_code3;

最后释放删除结点空间 free(r)

删除第二个位置节点后的单链表:head --> 2 --> 6

按址求值

/*
 *    根据指定位置求结点的值(没有找到返回 0 )
 *    list 单链表
 *    pos  结点位置(逻辑位置(1,2,3,...))
*/
ElemType GetElem(LinkList list, int pos){
    LinkList p = list;
    if(ListEmpty(list)){
        printf("空单链表\n");
        return FALSE;
    }
    if(pos <= 0 || pos > ListLength(list)){
        printf("位置不合理\n");
        return FALSE;
    }

    for(int i = 0; i < pos && p !=NULL; i++){
        p = p -> next;
    }
    return p -> data;
}

按值求址

/*
 *    根据指定的值寻找结点的位置
 *    (若是有多个值相同返回第一个找到的结点的位置, 没找到则返回 0)
 *    list 单链表
 *  data 要查找的值
*/
int GetLocate(LinkList list, ElemType data){
    LinkList p = list;
    int pos = 0;
    if(ListEmpty(list)){
        return FALSE;
    }
    p = p -> next;
    while(p != NULL){
        pos ++;
        if(p -> data == data){
            return pos;
        }
        p = p -> next;
    }
    return FALSE;
}

单链表去重

/*
 *    去除单链表中重复的值(重复的值只保留一个)
 *    list 单链表
 *  返回值:对单链表进行了去重操做返回 1,不然返回 0
*/
int RemoveRepeat(LinkList list){
    LinkList p = list, q, r;
    int flag = 0;
    if(ListEmpty(list)){
        return FALSE;
    }

    p = p -> next;

    while(p != NULL){
        q = p;
        while(q != NULL && q -> next != NULL){
            if(p -> data == q -> next -> data){
                r = q -> next;    // 记录值相同的结点
                q -> next = r -> next;
                free(r);
                flag = 1;
            }else{
                q = q -> next;
            }
        }
        p = p -> next;
    }
    return flag;
}

原理就是每次拿没有比较过的结点跟单例表中的每个结点进行比较,遇到相同的就删除其中一个结点。

例如:单链表序列为 2 4 2 8 8 6 6 8 12

首先拿第一个结点 2 跟单链表的其余结点比较
2      4       2       8       8       6       6       8       12
↑
                        ↓↓
遇到相同的就删除
2      4       8       8       6       6       8       12
    
                        
2比完了一轮去重了2,而后用第二个结点 4 跟单链表的其余没有比较过的结点比较
2      4       8       8       6       6       8       12  
         ↑ 
                        ↓↓
2      4       8       8       6       6       8       12 
                        
                        
4比完了一轮去重了4,而后用第三个结点 8 跟单链表的其余没有比较过的结点比较
2      4       8       8       6       6       8       12 
               ↑
                        ↓↓
2      4       8       6       6       12
    
循环类推
2      4       8       6       6       12
                       ↑
                    ↓↓
2      4       8        6       12 
    
最后一步    
2      4       8        6       12
                                ↑
                ↓↓
2      4       8        6       12

看看去重效果

去重前的单链表
ListLength():9
Travel():2      4       2       8       8       6       6       8       12

去重后的单链表
ListLength():5
Travel():2      4       8       6       12

源代码

源代码已上传到 GitHub Data-Structure-of-C,欢迎你们来访。