单链表相关操作（头插法和尾插法）_单链表的建立中,头插法建表和尾插法建表分别怎么做?

目录

1.尾插法建立单链表

带头结点

不带头节点

用户输入建立单链表

带头结点

不带头结点

2.头插法建立单链表

带头结点

用户输入建立单链表

带头结点

不带头结点

---

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

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;

头插法插入的结果

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

如有错误请大佬们不吝赐教！