单链表创建之--头插法创建带头结点的单链表

这篇具有很好参考价值的文章主要介绍了单链表创建之--头插法创建带头结点的单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

单链表常见的创建方法有头插法尾插法,这里记录头插法创建带头结点的单链表具体过程:
以C语言为例,
1)首先使用 typedef 关键字定义结点数据类型

typedef struct LNode{
    int var; //数据以整型为例
    struct LNode* next; //需要定义一个LNode结构体指针即结点指针来指向后继
 }LNode, *LinkList; 

4行的 LNode 和 *LinkList 可有可无,有的话后面定义结点变量和指针变量时更方便,不必须在LNode前面加 struct 关键字,可直接这样定义变量,

LNode l1, l2; //定义结点变量
LinkList p1, p2; //定义指针变量

与上面 typedef 关键字定义的单链表数据类型一样的定义方法:

struct LNode{
    int var;
    struct LNode* next;
}

若用这种方法定义链表结点类型,定义结点变量和指针变量时必须在LNode前带上struct关键字,即:

struct LNode l1, l2; //定义结点变量
struct LNode *p1, *p2; //定义指针变量

 

 

这两种定义方法效果是一样的,都是定义了包含 1个整型变量的数据域1个后继指针域的单链表结点类型

2)通过函数 头插构建链表,并返回 LinkList 类型表头指针变量 L
算法基本思想:带有头结点的单链表有两类结点,头结点元素结点,头结点通常不存储数据,用L表示,元素结点存储数据,用s表示

2.1 定义头结点指针变量L和元素结点s

LinkList s, L;

 2.2 定义了头结点之后,内存中尚未分配空间,此时头结点并不真实存在,需使用malloc关键字分配存储空间后,并使L指针指之,才真正创建了L头结点。由于此时仅有头结点,无后继结点,需将其指针域置空

 

L = (LinkList)malloc(sizeof(LNode)); 
L->next = NULL;

 

 头插法建立单链表,算法,数据结构

                                                                初始化头结点 

 这时设置一个整型变量x,通过不断输入其值,来初始化各结点数据域val,判断x=9999时为输入结束条件,先任意输入一个x,然后通过while循环来判断 x值决定是否进入添加结点过程

 

int x;
scanf("%d", &x);
while(x != 9999){ //进入添加结点过程
    ... //不断添加结点过程
}

 添加结点过程算法如下:
1, 初始化一个s元素结点,先初始化数据域var,然后初始化指针域next

 

s = (LinkList)malloc(sizeof(LNode));
s->var = x;
s->next = L->next;

 

先初始化数据域var,然后初始化指针域next头插法是这样插入新结点的,新的结点s始终在当前的表中第一个元素结点之前
,也就是L->next 之前插入,数据输入顺序与最终链表结点顺序是相反的,
所以在创建了一个新的元素结点s后,需要将其指针域置为L->next, 如图

头插法建立单链表,算法,数据结构
第一个待插入的元素结点s初始化后

 2, 初始化了一个元素结点s后,此时元素结点了,由于头结点L始终必须作为首个元素结点的前驱,所以需要头结点L的指针域,使当前元素结点s成为其后继

 

L->next = s;

 头插法建立单链表,算法,数据结构

                                                 头结点L指针域指向元素结点s

3, 这时,一个元素结点s就正式被插入到表中了,然后要插入第二个元素结点了,根据while循环的流程,再次判断x值需要再次输入一个x值,所以需要在while循环内最后一行输入x数据 

 

scanf("%d", &x);

 4,若输入的值非9999,则再次进入while循环,反复执行上述流程,不断插入元素结点扩大单链表长,这里赘述再添加一个元素结点的过程
又初始化了一个元素结点s,状态如图:

 头插法建立单链表,算法,数据结构

                                                      又初始化1个新的元素结点s

 

按照上述算法,头插法 新的元素结点s插入时始终插入在当前表中首个元素结点F之前,故需要将其后继指针域置为当前表中首个元素结点F,即s->next = L->next, 记住L->next始终指向首个元素结点,结果如图:

头插法建立单链表,算法,数据结构

                                                               插入新元素结点s

元素结点s被“半插入”到表中后,F已经不是绝对意义上的首个元素结点了,此时需要更改头结点L的后继指针域,将其后继指针域置为被“半插入”表中的新元素结点s,这样,新的元素结点s正式被插入表中,表长+1,如图

头插法建立单链表,算法,数据结构

                                                                插入新元素结点s

 2.3 上述插入过程的函数完整实现:

 

LinkList head_Insert(){
    int x;
    LinkList s, L; 
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while(x != 9999){
        s = (LinkList)malloc(sizeof(LNode));
        s->var = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

 3.用printList()函数遍历打印单链表,接收的形参为要打印的单链表,从首个结点开始打印

void printList(LinkList L){
    while(L != NULL){  
        printf("%d ", L->var);
        L = L->next; //向后遍历
    } 
}

 

4)主函数main() 流程
需要初始化一个head 指针变量,来接收head_Insert()函数所返回的已创建的链表头结点指针值, 然后将head传入printList()函数直接调用打印输入单链表数据,由于printList()是从首个结点开始打印,而头结点不存储数据,故传入第一个元素结点

int main(){
    LinkList head;
    head = head_Insert();
    printf("the linklist vars are: \n");
    printList(head->next); //由于printList()是从首个结点开始打印,而头结点不存储数据,故传入第一个元素结点
    return 0;
}

 程序最终运行结果如图,可以看到,头插法建立的单链表数据顺序与输入顺序相反:

 头插法建立单链表,算法,数据结构

                                                                程序运行结果文章来源地址https://www.toymoban.com/news/detail-735920.html

到了这里,关于单链表创建之--头插法创建带头结点的单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包