小工具知识网

当前位置: 首页 > 行业知识 > 数据结构--带头结点的单向链表

行业知识

数据结构--带头结点的单向链表

2026-11-20 12:40:09 来源:互联网转载

��   经过学习我知道了线性表的顺序存储结构(顺序表),发现它有着明显的缺点:插入和删除元素时需要频繁的移动元素,运算效率低。必须申请堆空间。堆空间估计大了,造成浪费空间;估计小了,容易产生溢出,空间难以扩大。

    采用链式存储结构的线性表(链表)可以克服以上的不足。

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以节点来表示的,每个节点的构成:元素(存放的数据元素)+指针(指示下一个元素存储位置,单、双链表的最后一个节点除外,它们存储的是一个空指针NULL),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

 

1.节点的结构如下图所示:

 

2.单链表由多个节点依次连接而成,结构如下图:

 

 最开始的那个节点是头节点,头节点的数据域是不存放数据的,指针域指向链表的第一个节点。在单链表的定义中,带有头节点的称为带头节点单链表,不带头节点的称为不带头节点单链表。我们这次介绍的就是带头节点单链表。

目录

一.节点的初始化

1.1 创建数据节点管理结构体

1.2 创建头结点管理结构体

1.3 初始化数据节点

1.4 初始化头结点

二.链表的初始化

 2.1 头插法

 2.2 尾插法

三 判断链表是否空了

四 修改节点

五 删除节点

六 插入节点

七 摧毁链表

八 显示链表

九 全部代码

十 运行结果 

一.节点的初始化

1.1 创建数据节点管理结构体

// 定义输入数据类型typedef int dataType;// 定义数据节点struct node{    dataType data;// 数据域    struct node *next;// 指针域};

1.2 创建头结点管理结构体

// 定义头节点struct headNode{    struct node *first;// 头指针    struct node *last;// 尾指针    int nodeNumber;// 节点总个数};

1.3 初始化数据节点

// 创建数据节点struct node *create_Newnode(dataType data){    struct node *pnew = malloc(sizeof(struct node));    if(pnew == NULL)        return NULL;    pnew->data = data;    pnew->next = NULL;    return pnew;}

1.4 初始化头结点

// 创建头节点struct headNode *create_New_Nodehead(void){    struct headNode *head = malloc(sizeof(struct headNode));    if(head == NULL)        return NULL;    head->first = NULL;    head->last = NULL;    head->nodeNumber = 0;    return head;}

二.链表的初始化

链表的建立有两种方式,一种是头插法,一种是尾插法。由于单链表的头插和尾插性质,有时候常用来解决链表的逆置问题。

 2.1 头插法

头插法:把后建立的结点插在头部。用这种方法建立起来的链表的实际顺序与输入顺序刚好向反,输出时为倒序。

操作步骤:创建指针pnew指向头节点,用malloc函数申请空间给节点pnew,接下来让节点pnew的指针域等于头节点的指针域,头节点的指针域指向节点pnew。把这段代码放到循环里面,进行多次头插操作。

// 创建链表struct headNode *create_list(void){    struct headNode *head = create_New_Nodehead();    if(head == NULL)        return NULL;    printf("请输入数据:");    while(1)    {        // 输入数据        dataType data;        scanf("%d",&data);        if(data == 0)            break;        // 创建新节点        struct node *pnew = create_Newnode(data);        if(pnew == NULL)            return NULL;        // 从无到有        if(head->first == NULL)        {            head->first = pnew;            head->last = pnew;        }        else// 从少到多        {            // 头插法            pnew->next = head->first;            head->first = pnew;                   }        // 更新节点        head->nodeNumber++;    }    return head;}

 2.2 尾插法

尾插法就是在链表的尾部依次插入节点。

操作步骤:先找到链表的最后一个节点,然后在最后一个节点后面插入节点。接下来的操作和头插差不多了。

// 创建链表struct headNode *create_list(void){    struct headNode *head = create_New_Nodehead();    if(head == NULL)        return NULL;    printf("请输入数据:");    while(1)    {        // 输入数据        dataType data;        scanf("%d",&data);        if(data == 0)            break;        // 创建新节点        struct node *pnew = create_Newnode(data);        if(pnew == NULL)            return NULL;        // 从无到有        if(head->first == NULL)        {            head->first = pnew;            head->last = pnew;        }        else// 从少到多        {            // 尾插法            head->last->next = pnew;            head->last = pnew;                  }        // 更新节点        head->nodeNumber++;    }    return head;}

三 判断链表是否空了

这里可以通过头结点管理结构体中定义的节点总个数nodeNumber来判断

// 判断链表是否为空bool isNULL(struct headNode *head){    if(head->nodeNumber == 0)        return true;    return false;}

四 修改节点

不改变节点个数,在已经存在的节点上修改指定节点的数值。

// 修改节点struct headNode* reviseLink(struct headNode *head,int data1,dataType data2){struct node *p = head->first;while(p != NULL){if(p->data == data1)// 原始数据{p->data = data2;// 修改后的数据}p = p->next;}return head;}

五 删除节点

操作步骤:先找到要删除节点前面的那个节点,然后修改指针域,用free释放要删除节点的空间,删除操作完成。

// 删除节点struct headNode *deleteNode(struct headNode *head,dataType data){    struct node *p=head->first;    struct node *pre=NULL;    // 找节点    while (p)    {        // 找到了出来        if(p->data==data)        {            break;        }        // 没找到继续找        else        {            pre=p;            p=p->next;        }    }    // 如果删除节点为头节点    if(p->data==head->first->data)    {        head->first=p->next;        p->next=NULL;        free(p);          }    // 如果删除节点为尾节点    else if(p->next==NULL)    {        pre->next=NULL;        free(p);    }    // 如果删除节点为中间节点    else    {        pre->next=p->next;        p->next=NULL;        free(p);    }    // 更新节点个数    head->nodeNumber--;    return head;}

六 插入节点

在指定位置插入元素,我们只需要找到要插入元素位置的前一个节点就可以了,然后修改节点指针域即可。

// 插入节点struct headNode *interNode(struct headNode *head,int data,dataType newdata){    struct node *p = head->first;    struct node *per = NULL;    struct node *pnew = create_Newnode(newdata);    // 找节点    while(p)    {        // 找到了        if(p->data == data)        {            break;        }        // 没找到        else        {            per = p;            p = p->next;        }    }    // 如果需要插入的节点没找到,直接尾插到最后面    if(p==NULL)    {        head->last->next = pnew;        head->last = pnew;    }    // 如果需要插入的节点为头结点,直接头插到最前面    else if(head->first->data==p->data)    {        pnew->next = head->first;        head->first = pnew;    }    // 如果为中间节点,随便插    else    {        pnew->next = p;        per->next = pnew;    }    // 更新节点个数        head->nodeNumber++;    return head;}

七 摧毁链表

因为单链表的一个个节点是用malloc申请的空间,这一部分的空间在内存的堆区,系统不会自动回收堆区的空间,所以要用free函数去把一个个的节点释放空间。

// 摧毁链表struct headNode *distoryNode(struct headNode *head){    if(isNULL(head))    {        printf("no found data\n");        return NULL;    }        // 逐一删除节点    struct node *p = NULL;    for(struct node *tmp = head->first;tmp != NULL; tmp = p)    {        p = tmp->next;        tmp->next = NULL;        free(tmp);        head->nodeNumber--;    }    return head;}

八 显示链表

没什么好说的,就是将链表打印出来。

// 显示链表void printList(struct headNode *head){    if(isNULL(head))    {        printf("no found data\n");        return;    }    for(struct node *p = head->first;p != NULL;p = p->next)    {        printf("%d\t",p->data);    }    printf("\n");    printf("链表节点个数为;%d\n",head->nodeNumber);}

九 全部代码

#include #include #include // 定义输入数据类型typedef int dataType;// 定义数据节点struct node{    dataType data;    struct node *next;};// 定义头节点struct headNode{    struct node *first;    struct node *last;    int nodeNumber;};// 创建头节点struct headNode *create_New_Nodehead(void){    struct headNode *head = malloc(sizeof(struct headNode));    if(head == NULL)        return NULL;    head->first = NULL;    head->last = NULL;    head->nodeNumber = 0;    return head;}// 创建数据节点struct node *create_Newnode(dataType data){    struct node *pnew = malloc(sizeof(struct node));    if(pnew == NULL)        return NULL;    pnew->data = data;    pnew->next = NULL;    return pnew;}// 创建链表struct headNode *create_list(void){    struct headNode *head = create_New_Nodehead();    if(head == NULL)        return NULL;    printf("请输入数据:");    while(1)    {        // 输入数据        dataType data;        scanf("%d",&data);        if(data == 0)            break;        // 创建新节点        struct node *pnew = create_Newnode(data);        if(pnew == NULL)            return NULL;        // 从无到有        if(head->first == NULL)        {            head->first = pnew;            head->last = pnew;        }        else// 从少到多        {            #if 1            // 尾插法            head->last->next = pnew;            head->last = pnew;            #else            // 头插法            pnew->next = head->first;            head->first = pnew;            #endif        }        // 更新节点        head->nodeNumber++;    }    return head;}// 修改节点struct headNode* reviseLink(struct headNode *head,int data1,dataType data2){struct node *p = head->first;while(p != NULL){if(p->data == data1){p->data = data2;}p = p->next;}return head;}// 删除节点struct headNode *deleteNode(struct headNode *head,dataType data){    struct node *p=head->first;    struct node *pre=NULL;    while (p)    {        if(p->data==data)        {            break;        }        else        {            pre=p;            p=p->next;        }    }    if(p->data==head->first->data)    {        head->first=p->next;        p->next=NULL;        free(p);          }    else if(p->next==NULL)    {        pre->next=NULL;        free(p);    }    else    {        pre->next=p->next;        p->next=NULL;        free(p);    }    head->nodeNumber--;    return head;}// 插入节点struct headNode *interNode(struct headNode *head,int data,dataType newdata){    struct node *p = head->first;    struct node *per = NULL;    struct node *pnew = create_Newnode(newdata);    while(p)    {        if(p->data == data)        {            break;        }        else        {            per = p;            p = p->next;        }    }    if(p==NULL)    {        head->last->next = pnew;        head->last = pnew;    }    else if(head->first->data==p->data)    {        pnew->next = head->first;        head->first = pnew;    }    else    {        pnew->next = p;        per->next = pnew;    }        head->nodeNumber++;    return head;}// 判断链表是否为空bool isNULL(struct headNode *head){    if(head->nodeNumber == 0)        return true;    return false;}// 显示链表void printList(struct headNode *head){    if(isNULL(head))    {        printf("no found data\n");        return;    }    for(struct node *p = head->first;p != NULL;p = p->next)    {        printf("%d\t",p->data);    }    printf("\n");    printf("链表节点个数为;%d\n",head->nodeNumber);}// 摧毁链表struct headNode *distoryNode(struct headNode *head){    if(isNULL(head))    {        printf("no found data\n");        return NULL;    }        // 逐一删除节点    struct node *p = NULL;    for(struct node *tmp = head->first;tmp != NULL; tmp = p)    {        p = tmp->next;        tmp->next = NULL;        free(tmp);        head->nodeNumber--;    }    return head;}int main(int argc, char const *argv[]){    struct headNode *head = create_list();    if(head == NULL)        return -1;    printf("\n");    // 修改节点    printf("修改节点后:");    head = reviseLink(head,1,11);    head = reviseLink(head,5,55);    printList(head);    printf("\n");    // 删除节点    printf("删除节点后:");    head = deleteNode(head,11);    printList(head);    printf("\n");        // 插入节点    head = interNode(head,1,88);    head = interNode(head,2,88);    head = interNode(head,3,88);    head = interNode(head,4,88);    printf("插入节点后:");    printList(head);    printf("\n");        // 摧毁链表    distoryNode(head);    printf("销毁节点后:");    printList(head);    printf("\n");    return 0;}

十 运行结果 

假定输入数据为1,2,3,4,5,结果如下:

上一篇:独家秘籍,轻松将百度网盘小程序下载到电脑指南!

下一篇:GhostXP操作系统探秘,神秘面纱下的秘密世界