C 创建链表的四种方式

xiaoxiao2021-02-28  15

C语言数据结构-创建链表的四种方法

结点类型:

typedef int datatype;

typedef struct NODE{

  datatype data;

  struct NODE *next;

  

}Node,*LinkList;

1、不带头结点的头插入法创建链表。

  每创建一个结点,都使该结点成为头结点,这样头结点不断地向前移动,就可以创建一个没有特定头结点的链表。

  首先创建的结点,会出现在整个链表的最末端,所以数据的写入是逆序的。

  【开始的时候,head要初始化为NULL】

LinkList LinkListCreate(const int n) { int i; LinkList head; Node *p; head = NULL; for(;i<n;i++) { p = (Node*)malloc(sizeof(Node)); if(NULL == p) perror("ERROR");      scanf("%d",&p->data); p->next = head; head = p; } }

开始时候,head 是一个空指针,创建一个结点p。现在head是指向一个链表的头结点,创建了一个新的结点p,向前插入。所以要p->next = head;然后再使head成为新链表的头结点。

2、不带头结点的未插入法创建链表。

  创建这样的链表,首先指向头结点的指针不能移动,所以需要创建一个一直指向尾结点的指针rear。

  

LinkList LinkListCreate(const int n) { int n= 0; //创建一个一直指向头结点,一直指向尾结点的指针。 LinkList head; Node *p,*rear; rear = head = NULL; for(;i<n;i++) { p = (Node*)malloc(sizeof(Node)); scanf("%d",&p->data); if(NULL == head) //创建的第一个结点。 else rear->next = p;//链表非空 rear = p;//移动尾指针 }   rear->next = NULL;//最后将链表的结尾设置为NULL。 }

【值的注意的就是,最后设置链表的结尾为NULL】

3、创建带结点的头插入链表。

  所谓的头结点是不存储数据的,他只是个指针结点。可以在该头结点存储一些这个链表的整体信息。比如链表的结点数量。

  这种

创建方法跟第一种方法是一样的思路。

 

1 LinkList LinkListCreate(const int n) 2 { 3 int i = 0;LinkList p; 4 LinkList head = (Node*)malloc(sizeof(Node)); 5 head->next = NULL; 6 7 for(;i<n;i++) 8 { 9 p = (Node*)malloc(sizeof(Node)); 10 scanf("%d",&p->data); 11 p->next = head->next; 12 head->next = p; 13 } 14 15 return head; 16 }

【纯C语言,是要求所有的变量在使用的时候,必须在作用域的开始处定义。】

4、带头结点的尾插入法创建链表。

  

开始创建的时候,rear = head.  rear->next = p; rear = p;最后要使的rear->next = NULL;

LinkList LinkListCreate(const int n) { int i = 0;Node *p,*rear; LinkList head = (Node*)malloc(sizeof(Node)); rear = head; for(;i<n;i++) { p = (Node*)malloc(sizeof(Node)); scanf("%d",&p->data); rear->next = p; //尾指针 指向新建结点 rear = p;//rear指针移动 } rear->next = NULL; return head; }

 

欢迎指正……

 有的吧友给我建议说一下有头结点的好处,下面是我的个人所思:、

头结点:如果在链表的开始结点之前附加一个结点,并称它为头结点,那么会带来以下两个优点:

    a、   由于开始结点的位置被存放在头结点的指针域中,

    所以在链表的第一个位置上的操作就和在表的其它位置上

    的操作一致,无需进行特殊处理;

    b、无论链表是否为空,其头指针是指向头结点在的

     非空指针(空表中头结点的指针域为空),因此空表和

     非空表的处理也就统一了。

转载请注明原文地址: https://www.6miu.com/read-450083.html

最新回复(0)