c 数据结构线性表链表头插法/尾插法算法思想及代码实现

57 阅读 0 评论 38 点赞

我是靠谱客的博主烂漫柜子，最近开发中收集的这篇文章主要介绍c 数据结构线性表链表头插法/尾插法算法思想及代码实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

c 数据结构线性表链表头插法尾插法算法思想及代码实现

数据结构专业课大部分高校是大二开设（有些高校大一也开设）

线性表的链式（后称为链表），它只要求逻辑存储相邻而不需要物理位置上相邻，所以在进行插入或删除操作并不需要移动大量元素，本篇博客就来阐述下链表中头插法与尾插法的算法思想和代码实现
首先我们介绍结点的概念
一个结点由两个信息构成，一个是数据域，另一个是指针域，通过指针指向后继结点从而构成一个链表
请添加图片描述

定义链表

typedef struct LNode //结点分为数据域与指针域
{
    int data;
    struct LNode *next;

}LNode, *LinkList;

头插法

请添加图片描述

由于每次都是在头结点后插入后继结点，所以会造成是链表的各元素顺序和输入的顺序是反的：输入结果如下：在这里插入图片描述
代码：

void CreateList_L_head(LinkList &L,int n)//头插法
{
    L = (LinkList) malloc (sizeof(LNode)); //初始化头指针同时也是整个链表的地址
    L -> next = NULL; 
    LNode *p;
    for(int i = 0;i<n;i++)
    {
        p = (LinkList) malloc (sizeof(LNode));
        p -> data = i;
        p -> next = L ->next;
        L -> next = p;
    }//核心算法
}

尾插法

请添加图片描述
尾插法需要我们提前定义一个工具人指针q，本质上来说区别于头插法，我们尾插法需要将后继结点插入在尾指针q上，这就是算法思想唯一的区别，上代码：

void CreateList_L_tail(LinkList &L,int n)//尾插法
{
    L = (LinkList) malloc (sizeof(LNode)); //初始化头指针同时也是整个链表的地址
    LNode *s,*q=L;
    for(int i = 0;i<n;i++)
    {
        s = (LinkList) malloc (sizeof(LNode)); //每次创建新的结点
        s -> data = i;
        q -> next = s;
        q = s;
    }

    q ->next = NULL;
}

通过尾指针q，数据在链表的存储顺序就和用户输入的数据一致。
在这里插入图片描述

算法思想总结

都说c语言的核心就是关于指针的应用，笔者觉得也有一定的道理，这链表中头插法与尾插法的核心思想就是定义一个尾指针从而可以让后继元素插入在表尾，进而实现了存储顺序就和用户输入的数据一致，这些算法细心体会能让人感受到巧妙之处，我们一定不要只成为一个敲代码的代码奴，可以透过代码研究它背后的数学原理，数据结构，算法思想，这样我们才能提高，也是高等教育需要能带给我们的。

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
// SWU tony
typedef struct LNode //结点分为数据域与指针域
{
    int data;
    struct LNode *next;

}LNode, *LinkList;

void CreateList_L_head(LinkList &L,int n);//头插法
void CreateList_L_tail(LinkList &L,int n);//尾插法
void Print_list(LinkList &L);

int main(void)
{
    LinkList L;
    CreateList_L_tail(L,10);
    //CreateList_L_head(L,10);
    Print_list(L);
}


void CreateList_L_head(LinkList &L,int n)//头插法
{
    L = (LinkList) malloc (sizeof(LNode)); //初始化头指针同时也是整个链表的地址
    L -> next = NULL; 
    LNode *p;
    for(int i = 0;i<n;i++)
    {
        p = (LinkList) malloc (sizeof(LNode));
        p -> data = i;
        p -> next = L ->next;
        L -> next = p;
    }//核心算法
}

void CreateList_L_tail(LinkList &L,int n)//尾插法
{
    L = (LinkList) malloc (sizeof(LNode)); //初始化头指针同时也是整个链表的地址
    LNode *s,*q=L;
    for(int i = 0;i<n;i++)
    {
        s = (LinkList) malloc (sizeof(LNode)); //每次创建新的结点
        s -> data = i;
        q -> next = s;
        q = s;
    }

    q ->next = NULL;
}

void Print_list(LinkList &L)
{
    LinkList p;
    p = L -> next;
    while(p)
    {
        printf("%in",p->data);
        p = p-> next;
    }
}