AI 助理
备案控制台
开发者社区 云计算 文章 正文

单链表相关操作（头插法和尾插法）

2024-05-14 58
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 单链表相关操作（头插法和尾插法）

头插法和尾插法最大区别在于，尾插法可以顺序输出用户输入的元素，头插法则是逆序输出的


1.尾插法建立单链表

带头结点

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *LinkList;
LinkList InitList(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) {
        return NULL;
    }
    L->next = NULL;
    return L;
}
bool ListInsert(LinkList &L, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    LNode* p = L;
    int j = 0;
    while (p != NULL && j < 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;
    return true;
}
int GetLen(LinkList &L) {
    int len = 0;
    LNode* p = L->next;
    while (p != NULL) {
        p = p->next;
        len++;
    }
    return len;
}
int main() {
    LinkList L=NULL;
    if (InitList(L) == NULL) {
        printf("链表初始化失败\n");
        return 0;
    }
    int length = GetLen(L);
    LNode* p = L;
    int e = 3;
    ListInsert(L, length, e);  // 将e元素插到链表的尾部
    printf("链表长度：%d\n", GetLen(L));
    // 释放链表所占用的内存
    p = L->next; // p指向第一个节点
    while (p != NULL) {
        LNode* q = p->next; // q指向下一个节点
        free(p); // 释放当前节点
        p = q; // 将p指向下一个节点
    }
 
    return 0;
}


不带头节点

只需要对i=1时做单独判断，即


if (i < 1) {
        return false;
    }
    if (i == 1) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }

最终代码为 


#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *LinkList;
LinkList InitList(LinkList &L) {
    L = NULL;
    return L;
}
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 = L;
    int j = 1;
    while (p != NULL && j < 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;
    return true;
}
int GetLen(LinkList &L) {
    int len = 0;
    LNode* p = L;
    while (p != NULL) {
        p = p->next;
        len++;
    }
    return len;
}
int main() {
    LinkList L=NULL;
    if (InitList(L) == NULL) {
        printf("链表初始化失败\n");
        return 0;
    }
    int length = GetLen(L);
    LNode* p = L;
 
    int e = 3;
    ListInsert(L, length+1, e);  // 将e元素插到链表的尾部
    printf("链表长度：%d\n", GetLen(L));
    // 释放链表所占用的内存
    p = L;
    while (p != NULL) {
        LNode* q = p->next; // q指向下一个节点
        free(p); // 释放当前节点
        p = q; // 将p指向下一个节点
    }
    return 0;
}


用户输入建立单链表

带头结点

LinkList(LinkList &L)
{
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode=*s,*r=L;
    scanf("%d",&x);
    while(x!=100)
    {
        s=(LNode*)malloc(sizeof(LNode));    
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}



r总是指向表尾节点，每输入一个新值，就存入s指向的新开辟的空间,即r指向的尾节点的后面当再输入下一个值时，令r=s；将r指向这个新开辟的空间作为新的尾节点，重复上一操作


不带头结点

LinkList ListInsert(LinkList &L) {
    int x;
    LNode *s, *r;
    scanf("%d", &x);
    if (x == 100) {
        L = NULL; // 若输入第一个元素为 100，则直接返回空链表
        return L;
    }
    L = (LNode*)malloc(sizeof(LNode));
    L->data = x;
    r = L;
    scanf("%d", &x);
    while (x != 100) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}


2.头插法建立单链表

头插法建立单链表其实是对头节点做尾插法


带头结点

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *LinkList;
LinkList InitList(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) {
        return NULL;
    }
    L->next = NULL;
    return L;
}
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->next = p->next;
    p->next = s;
    return true;
}
int main() {
    LinkList L = NULL;
    if (InitList(L) == NULL) {
        printf("链表初始化失败\n");
        return 0;
    }
    LNode* p = L; // 指向头节点
    int e = 3;
    InsertNextNode(p, e); // 将元素3插入到头节点
    p = L->next; // p指向第一个节点
    while (p != NULL) {
        printf("%d ", p->data); // 打印节点数据
        p = p->next; // 将p指向下一个节点
    }
    printf("\n");
    // 释放链表所占用的内存
    p = L->next; // p指向第一个节点
    while (p != NULL) {
        LNode* q = p->next; // q指向下一个节点
        free(p); // 释放当前节点
        p = q; // 将p指向下一个节点
    }
    return 0;
}


用户输入建立单链表

带头结点
LinkList ListInsert(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));  // 创建头节点
    L->next = NULL;  // 头节点的next指针置为空
    LNode *s;
    int x;
    scanf("%d", &x);
    while (x != 100) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}
不带头结点
LinkList ListInsert(LinkLinst &L)
{
    LNode *s;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;//在这里必须初始化
    int x;
    scanf("%d",&x);
    while(x!=100)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;    
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}


若不执行 L->next=NULL;



头插法插入的结果



可以看到头插法输入的元素是逆序输出的，尾插法则是顺序输出的


dulu~dulu
目录
相关文章
游客6z2krsj5iqmue
|
6月前
|
存储 Python
链表中插入节点
链表中插入节点
游客6z2krsj5iqmue
81 4
游客h2vchmlwqitbk
|
5月前
头插法和尾插法
头插法和尾插法
游客h2vchmlwqitbk
41 2
aliyun0193839942-27807
|
6月前
|
存储 编译器
单链表与双链表实现
单链表与双链表实现
aliyun0193839942-27807
45 4
xiaowang_lj
|
6月前
|
算法
链表的头插法和尾插法
链表的头插法和尾插法
xiaowang_lj
224 1
dulu~dulu
|
6月前
特殊链表（循环单链表，循环双链表，静态链表）
特殊链表（循环单链表，循环双链表，静态链表）
dulu~dulu
50 3
过分的规定
|
6月前
|
存储
链表的学习：链表的头插法和尾插法以及HashMap中链表结点的插入方式
链表的学习：链表的头插法和尾插法以及HashMap中链表结点的插入方式 链表是一种常用的数据结构，它采用链式存储结构存储数据，相对于数组具有更灵活的操作和更高的效率。链表插入元素的方式有头插法和尾插法。
过分的规定
564 0
zcx-yyds
|
存储
链表(一) 单链表操作详解
链表(一) 单链表操作详解
zcx-yyds
50 0
霸总爱吃鱿鱼虾
反转链表（头插法实现）
反转链表（头插法实现）
霸总爱吃鱿鱼虾
82 0
阿润菜菜
|
存储
【链表】单链表的实现
【链表】单链表的实现
阿润菜菜
68 0
在肯德基吃麻辣烫
|
存储 编译器
【链表之单链表】
什么是链表 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 通俗地讲，就是一个结构体有两个成员，一个是存放数据的成员，一个是指针成员，通常的单链表是第一个节点的指针成员存着下一个节点的地址，下一个节点的指针成员又存下一个节点的地址，这样每个节点之间连接起来，就叫做链表。 本文主要讲的是链表中的一种重要的形式：单链表。
在肯德基吃麻辣烫
79 0