首页 > 代码库 > 带头节点的单链表-------C语言实现

带头节点的单链表-------C语言实现

  1 /*****************************************************
  2 Author:Simon_Kly    Version:0.1    Date:20170520 
  3 Description:带头接点的单链表
  4 Mail:degaullekong@gmail.com
  5 Funcion List: 
  6 *****************************************************/
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 
 11 typedef struct node
 12 {
 13     int data;
 14     struct node *next;
 15 }Node, *Link;
 16 
 17 /*判断malloc是否正确执行*/
 18 void is_malloc_ok(Link head)
 19 {
 20     if (head == NULL)
 21     {
 22         printf("malloc error!\n");
 23         exit(-1);
 24     }
 25 }
 26 
 27 /*建立链表*/
 28 void create_link(Link * head)
 29 {
 30     *head = (Link)malloc(sizeof(Node));
 31     is_malloc_ok(*head);
 32     (*head)->next = NULL;
 33 }
 34 
 35 /*创建节点*/
 36 void create_node(Link * new_node)
 37 {
 38     *new_node = (Link)malloc(sizeof(Node));
 39     is_malloc_ok(*new_node);
 40 }
 41 
 42 /*插入节点尾插*/
 43 void insert_node_tail(Link head, Link new_node)
 44 {
 45     Link p = NULL;
 46     
 47     p = head;
 48 
 49     while (p->next != NULL)
 50     {
 51         p = p->next;
 52     }
 53     p->next = new_node;
 54     new_node->next = NULL;
 55 }
 56 
 57 /*插入节点头插*/
 58 void insert_node_head(Link head, Link new_node)
 59 {
 60     Link p = NULL;
 61 
 62     p = head;
 63 
 64     new_node->next = head->next;
 65     head->next = new_node;
 66 }
 67 
 68 /*打印节点*/
 69 void output_link(Link head)
 70 {
 71     Link p = NULL;
 72 
 73 
 74     if (head == NULL)
 75     {//空链
 76         printf("link is empty!\n");
 77         return ;
 78     }
 79 
 80     p = head->next;
 81     while (p != NULL)
 82     {
 83         printf("%d\n", p->data);
 84         p = p->next;
 85     }
 86 }
 87 
 88 /*置空链*/
 89 void make_empty_link(Link *head)
 90 {
 91     Link p = NULL;
 92 
 93     p = (*head)->next;
 94 
 95     while ((*head)->next != NULL)
 96     {
 97         (*head)->next = (*head)->next->next;
 98         free(p);
 99         p = (*head)->next;
100     }
101 }
102 
103 /*释放链表*/
104 void release_link(Link * head)
105 {
106     make_empty_link(head);
107     free(*head);
108     *head = NULL;
109 }
110 
111 int main()
112 {
113     int i;
114 
115     Link head = NULL;
116     Link new_node = NULL;
117 
118     create_link(&head);
119     
120     /*尾插*/
121     for (i = 0; i < 10; i++)
122     {
123         create_node(&new_node);
124         new_node->data = http://www.mamicode.com/i + 1;
125         insert_node_tail(head, new_node);
126     }
127     output_link(head);
128 
129     /*头插*/
130     create_node(&new_node);
131     new_node->data = http://www.mamicode.com/20;
132     insert_node_head(head, new_node);
133     output_link(head);
134 
135     /*释放链表阶段*/
136     release_link(&head);
137     output_link(head);
138     return 0;
139 }

不带头结点代码传送门:http://www.cnblogs.com/SimonKly/p/6890287.html

可以从代码中看出,不带头结点的代码中插入节点的函数insert*中的参数是二级指针,因为头指针的指向可能会发生变化,需要用二级指针带回一级指针的地址。

而在带头结点的代码中在相同的插入节点的函数insert*中的参数是一级指针并没有使用二级指针,因为带头结点的链表中头结点是真真实实存在,在create*中分配空间于它,只是它的值域没有值,改变的是它的指针域的指向,其指针域的地址可以由它自己带回。

带头结点的链表比不带头结点的链表处理起来更加的简单,不要考虑头指针的指向是否发生变化的问题。

带头节点的单链表-------C语言实现