龙空技术网

数据结构|单链表表示的三种方法

小智雅汇 116

前言:

目前咱们对“头指针和头节点区别”大体比较看重,兄弟们都需要剖析一些“头指针和头节点区别”的相关内容。那么小编也在网络上收集了一些对于“头指针和头节点区别””的相关知识,希望小伙伴们能喜欢,大家一起来了解一下吧!

对于线性表来说, 总得有个头尾,头部做为基准地址,如数组的数组名,链表的头指针。尾部做为结束的标志,数组使用一个长度属性来标识数组的结束位置,字符串使用转义字符'\0',链表使用NULL指针来标识结束位置。

我们知道,数组的全部元素是集中存储,数组的基准地址是第一个元素的地址,也就是数组名的值,其它元素的索引都是一个整型常量,对元素的访问就是基准地址相对于索引的偏移,所以数组元素可以随机访问。

链式存储是分散存储,通过节点的指针域来建立一个节点与其下一个邻接节点的联系。链式存储的头指针虽然也是整个链式数据结构的基准地址,但要找到某一节点,需要顺序访问,从头节点开始,顺着每一个节点的指针域的值,一个节点一个节点地挼。

我们把链表中第一个节点的存储位置叫做头指针, 那么整个链表的存取就必须是从头指针开始进行了。之后的每一个节点, 其实就是上一个的后继指针指向的位置。有时,我们为了更加方便地对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头节点。头节点的数据域可以不存储任何信息,谁叫它是第一个呢,有这个特权。也可以存储如线性表的长度等附加信息,头节点的指针域存储指向第一个节点的指针。

头指针

头节点

1 头指针是指链表指向第一个节点的指针,若链表有头结点,则是指向头结点的指针

1 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)

2 头指针具有标识作用, 所以常用头指针冠以链表的名字

2 有了头结点,对在第一个元素节点前插入节点和删除第一节点,其操作与其它结点的操作就统一了

3 无论链表是否为空, 头指针均不为空。头指针是链表的必要元素

3 头结点不一定是链表必须要素

是否使用头节点,在实现链表的常用操作时代码的写法稍有区别,使用头节点的方法代码较为简洁。同时,也可以将这个表头节点指针封装到一个结构体中,并在结构体中增加链表长度等信息。

1 使用头节点的链表表示

加头结点的优点:

1)链表第一个位置的操作无需特殊处理;

2)将空表和非空表的处理统一。

#include <stdio.h>#include <malloc.h>typedef struct Node{    int data;    struct Node * next;}Node,*pNode;pNode createList()                  // 头节点是空节点{     pNode head = (pNode)malloc(sizeof(Node));    if(head==NULL)    {        printf("malloc failed!\n");        return head;    }    head->data = 0;    head->next = NULL;    return head;}int insert(pNode head, int data) // 头插法{     pNode newNode = (pNode)malloc(sizeof(Node));    if(newNode==NULL)    {        printf("malloc failed!\n");        return -1;    }    newNode->data = data;    newNode->next = head->next;    head->next = newNode;    return 0;}void printList(pNode head){    pNode cur = head->next;    while(cur){        printf("%d ",cur->data);        cur = cur->next;    }}void destroyList(pNode head){    pNode p = head;    pNode q = p->next;    while(q!=NULL)    {        free(p);        p=q;        q=p->next;    }    free(p);}int main(){    pNode head = createList();    for(int i=0;i<10;i++)        insert(head,i+1);    printList(head);    destroyList(head);    getchar();    return 0;}/*10 9 8 7 6 5 4 3 2 1*/

2 不使用头节点的链表表示

#include <stdio.h>#include <malloc.h>typedef struct Node{    int data;    struct Node * next;}Node,*pNode;int insert(pNode* head, int data) // 头插法,头部是一个实节点{     pNode newNode = (pNode)malloc(sizeof(Node));    if(newNode==NULL)    {        printf("malloc failed!\n");        return -1;    }    newNode->data = data;    if(head==NULL)        newNode->next=NULL;    else        newNode->next = *head;    *head = newNode;    return 0;}void printList(pNode head){    pNode cur = head;    while(cur){        printf("%d ",cur->data);        cur = cur->next;    }}void destroyList(pNode head){    pNode p = head;    pNode q = p->next;    while(q!=NULL)    {        free(p);        p=q;        q=p->next;    }    free(p);}int main(){    pNode head = NULL;    for(int i=0;i<10;i++)        insert(&head,i+1);    printList(head);    destroyList(head);    getchar();    return 0;}/*10 9 8 7 6 5 4 3 2 1*/

3 链表和链表节点用不同的结构体来表示

链表用一个结构体来描述,封装一个节点指针做表头,并增加一个链表长度变量,需要时也可以增加一个节点指针做表尾。

#include <stdio.h>#include <malloc.h>typedef struct Node{    int data;    struct Node * next;}Node,*pNode;typedef struct List{    pNode head;    int size;}List,*pList;pList createList(){    pList pl = (pList)malloc(sizeof(List));    if(pl==NULL)    {        printf("malloc failed!\n");        return pl;    }    pl->head = (pNode)malloc(sizeof(Node));    if(pl->head==NULL)    {        printf("malloc failed!\n");        return NULL;    }    pl->head->data = 0;    pl->head->next = NULL;    pl->size = 0;    return pl;}int insert(pList pl, int data) // 头插法,头部是一个空节点{     pNode newNode = (pNode)malloc(sizeof(Node));    if(newNode==NULL)    {        printf("malloc failed!\n");        return -1;    }    newNode->data = data;    newNode->next = pl->head->next;    pl->head->next = newNode;    pl->size++;    return 0; }void printList(pList pl){    pNode cur = pl->head->next;    while(cur){        printf("%d ",cur->data);        cur = cur->next;    }}void destroyList(pList* pl){    pNode p = (*pl)->head;    pNode q = p->next;    while(q!=NULL){        free(p);        p=q;        q=p->next;    }    free(p);    free(*pl);}int main(){    pList pl = createList();    for(int i=0;i<10;i++)        insert(pl,i+1);    printList(pl);    destroyList(&pl);        getchar();    return 0;}/*10 9 8 7 6 5 4 3 2 1*/

-End-

标签: #头指针和头节点区别