【数据结构】头结点到底是什么？

程序员周同学

发布于 2019-07-27 19:54:41

3.9K0

发布于 2019-07-27 19:54:41

文章被收录于专栏：程序员周同学

内容目录

一. 有无头结点，是什么意思？二. 有无头结点的优劣势无头结点的数据插入数据删除数据有头结点的链表插入数据删除数据三. 总结

一. 有无头结点，是什么意思？

首先我们来看一下有无头结点链表的图示，均以保存三个数据为标准

无头结点的链表图示如下：

有头结点的链表图示如下：

通过上面两张示意图，你是否懂了有无头结点的意思呢？

有头结点表示第一个结点不保存数据，与其他数据节点区别开来
无头结点表示第一个节点保存数据，与其他节点除了位置不同，其余一模一样

二. 有无头结点的优劣势

两种链表在查询更改的方式是一样的，存在区别的是插入数据和删除数据

无头结点的数据

插入数据

在不存在头结点的情况，一条完整链表中中插入数据时，我们必须分两种情况去讨论，一种是第一个节点，另一种是其他节点。

我们现在看一下在中间节点处插入数据。分为三步：

创建新结点

将新结点指向被插入结点的指针域

将被插入结点的指针域指向新结点

但如果在第一个节点之前添加数据，步骤就与上面的步骤有所不同：

创建新结点

将新结点的指针域指向第一个节点head

将新结点设置为第一个节点

下面看一下不带头结点的链表如何插入数据

 1//此处为不带头结点的链表
 2//因为在头结点处插入数据时需要改变head的值，而head是指针，所以必须传入双重指针
 3void insertLinkedList(linkedList**head,int i,DataType data){
 4    linkedList*node,*p = *head;
 5    int count = 0;
 6    //将P定位到指定结点的前一个结点（第一个结点除外）
 7    while(count < i-1 && p->next !=NULL) {
 8        p = p->next;
 9        count++;
10    }
11    //当输入的 i 不符合要求时直接退出函数
12    if (i < 0|| p == NULL)
13        return;
14    //判断是否在第一个结点处插入数据
15    if(i == 0){
16        node = (linkedList*)malloc(sizeof(linkedList));
17        node->data = data;
18        node->next = *head;
19        *head = node;
20    }else{
21        node = (linkedList*)malloc(sizeof(linkedList));
22        node->data = data;
23        node->next = p->next;
24        p->next = node;
25    }
26}

删除数据

同样删除第一个数据时也需要判断删除的是否为第一个结点:

 1void deleteNode(linkedList**head, int i, DataType *data){
 2    linkedList*node,*p = *head,*q;
 3    int count = 0;
 4    while(count < i-1 && p->next !=NULL) {
 5        p = p->next;
 6        count++;
 7    }
 8    //当输入的 i 不符合要求时直接退出函数
 9    if (i < 0|| p == NULL)
10        return;
11    if(i==0) {
12        *head = (*head)->next;
13        *data = p->data;
14        free(p);
15    } else{
16        node = p->next;
17        p->next = node->next;
18        *data = node->data;
19        free(node);
20    }
21}

有头结点的链表

这个链表在上一篇文章中已经说过了，所以这里不做过多描述，再次将代码贴出来，给大家看一下

插入数据

 1void insertLinkedList(linkedList *head,int i,DataType data){
 2    linkedList*node = head,*tail;
 3    int j = -1;
 4    //循环判断i是否合理，若合理，则跳出循环后node指向第i-1个结点，且j == i+1
 5    while (node->next != NULL && j<i-1){
 6        node = node->next;
 7        j++;
 8    }
 9    if (j!=i-1){
10        printf("插入位置有误！");
11        return;
12    }
13    tail= (linkedList *) malloc(sizeof(linkedList));
14    tail->data = data;
15    tail->next = node->next;
16    node->next =tail;
17}

删除数据

 1//删除第i个元素,被删除的值由data带回，无需返回值
 2//主体思路和插入元素类似
 3void deleteLinkedList(linkedList*head,int i,DataType* data){
 4    linkedList *p = head,*s;
 5    int j = -1;
 6    while(p->next !=NULL && p->next->next !=NULL && j<i-1){
 7        p = p->next;
 8        j++;
 9    }
10    if (j != i-1){
11        printf("删除位置错误！");
12        return;
13    }
14    s = p->next;
15    *data = s->data;
16    p->next = p->next->next;
17    free(s);
18}

三. 总结

很容易看出带头结点的链表操作起来比不带头结点更为方便，所以我们平时使用的时候更多的去使用带头结点的链表，这样方便自己写相关操作

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

其他

本文分享自程序员周同学微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

其他

登录后参与评论

0 条评论

热度