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

不念不忘少年蓝@ 2023-10-18 13:46 147阅读 0赞

1 /****************************************************/  3 File name：no_head_link.c
      4 Author：SimonKly   Version:0.1    Date: 2017.5.20
      5 Description：不带头节点的单链表
      6 Funcion List: 
      7 *****************************************************/
      8 
      9 #include <stdio.h>
     10 #include <stdlib.h>
     11 
     12 typedef struct node
     13 {
     14     int id;
     15     struct node * next;
     16 }* Link, Node;
     17 
     18 /*创建链表*/
     19 void create_link(Link * head)
     20 {
     21     *head = NULL;//空链表
     22 }
     23 
     24 /*头插*/
     25 void insert_node_head(Link * head, Link new_node)
     26 {
     27     new_node->next = *head;
     28     *head = new_node;
     29 }
     30 
     31 #if 1
     32 /*尾插*/
     33 void insert_node_tail(Link * head, Link new_node)
     34 {
     35     Link p = NULL;
     36 
     37     if (*head == NULL)
     38     {
     39         *head =new_node;
     40         new_node->next = NULL;
     41         return ;
     42     }
     43     else
     44     {
     45         p = *head;
     46         while (p->next != NULL)
     47         {
     48             p = p->next;
     49         }
     50         p->next = new_node;
     51         new_node->next = NULL;
     52     }
     53 }
     54 #endif
     55 
     56 /*输出链表*/
     57 void display_link(Link head)
     58 {
     59     Link p = NULL;
     60 
     61     p = head;
     62 
     63     if(p == NULL)
     64     {
     65         printf("link is empty!\n");
     66         return ;
     67     }
     68 
     69     while (p != NULL)
     70     {
     71         printf("id = %d\n", p->id);
     72         p = p->next;
     73     }
     74 
     75     putchar(10);
     76 }
     77 
     78 /*检查malloc是否分配成功*/
     79 void is_malloc_ok(Link new_node)
     80 {
     81     if (new_node == NULL)
     82     {
     83         printf("malloc error!\n");
     84         exit(-1);
     85     }
     86 }
     87 
     88 /*创建节点*/
     89 void create_node(Link * new_node)
     90 {
     91     *new_node = (Link)malloc(sizeof(Node));
     92 
     93     is_malloc_ok(*new_node);
     94 }
     95 
     96 /*释放节点*/
     97 void realse_node(Link * head)
     98 {
     99     Link p = NULL;
    100 
    101     p = *head;
    102     while (*head != NULL)
    103     {
    104         *head = (*head)->next;//head移动
    105         free(p);//释放head之前的节点
    106         p = *head;
    107     }
    108 }
    109 
    110 
    111 /*中间插入节点*/
    112 void insert_node_mid(Link * head, Link new_node, int loc)
    113 {
    114     int i;
    115     Link p = NULL;
    116 
    117     p = *head;
    118 
    119     for(i = 1; i < loc; i++)
    120     {
    121         p = p->next;
    122     }
    123 
    124     new_node->next = p->next;
    125     p->next = new_node;
    126 }
    127 
    128 /*中间插入，前面*/
    129 void insert_node_mid_front(Link * head, Link new_node)
    130 {
    131     Link p = NULL, q = NULL;
    132 
    133     p = q = *head;
    134 
    135     if (*head == NULL)
    136     {
    137         printf("link is empty\n");
    138         return ;
    139     }
    140 
    141     while (p != NULL && p->id != new_node->id)
    142     {
    143         q = p;
    144         p = p->next;
    145     }
    146     
    147     if (p == NULL)
    148     {
    149         printf("No such node in link!\n");
    150         free(new_node);
    151         return ;
    152     }
    153     if (p->id == (*head)->id)
    154     {
    155         new_node->next = *head;
    156         *head = new_node;
    157     }
    158     else
    159     {
    160         q->next = new_node;
    161         new_node->next = p;
    162     }
    163 }
    164 #if 1
    165 /*删除节点*/
    166 void delete_node(Link * head, int data)
    167 {
    168     Link p = NULL, q = NULL;
    169 
    170     q = p = *head;
    171 
    172     if (p == NULL)//链表为空的时候
    173     {
    174         printf("link is empty!\n");
    175         return ;
    176     }
    177     else//链表不为空的时候
    178     {
    179         while (p != NULL && p->id != data)//寻找节点
    180         {
    181             q = p;
    182             p = p->next;
    183         }
    184 
    185         if ((*head)->id == data)//删除节点为头节点时
    186         {
    187             *head = (*head)->next;
    188             free(p);//free(q);
    189         }
    190         else//删除节点不为头节点，尾节点不用考虑
    191         {
    192             q->next = p->next;
    193             free(p);
    194         }
    195     }
    196 }
    197 #endif
    198 
    199 #if 0
    200 void delete_node(Link * head, int data)
    201 {
    202     Link p = NULL, q = NULL;
    203 
    204     q = p = *head;
    205 
    206     if (p == NULL)//链表为空的时候
    207     {
    208         printf("link is empty!\n");
    209         return ;
    210     }
    211     else//链表不为空的时候
    212     {
    213         while (p != NULL && (p->next)->id != data)//寻找节点
    214         {
    215             p = p->next;
    216         }
    217 
    218         if ((*head)->id == data)//删除节点为头节点时
    219         {
    220             *head = (*head)->next;
    221             free(p);//free(q);
    222         }
    223         else//删除节点不为头节点，尾节点不用考虑
    224         {
    225             q = p->next;
    226             p->next = q->next;
    227             free(q);
    228         }
    229     }
    230 }
    231 #endif
    232 
    233 /*插入之后依旧有序*/
    234 void insert_node_seq(Link * head, Link new_node)
    235 {
    236     Link p = NULL, q = NULL;
    237 
    238     p = q = *head;
    239 
    240     if (p == NULL)//链表为空的时候
    241     {
    242         *head = new_node;
    243         new_node->next = NULL;
    244     }
    245     else
    246     {
    247         while (p != NULL && p->id < new_node->id)//寻找位置
    248         {
    249             q = p;
    250             p = p->next;
    251         }
    252         
    253         if ((*head)->id > new_node->id)//找到的节点为头节点
    254         {
    255             new_node->next = *head;
    256             *head = new_node;
    257         }
    258         else
    259         {
    260             q->next = new_node;
    261             new_node->next = p;
    262         }
    263     }
    264 }
    265 
    266 #if 1
    267 /*插入依旧有序实现方法二*/
    268 void insert_node_seq_1(Link * head, Link new_node)
    269 {
    270     Link p = NULL;
    271     Link q = NULL;
    272 
    273     p = q = *head;
    274 
    275     if (p == NULL)//空链表
    276     {
    277         *head = new_node;
    278         new_node->next =NULL;
    279     }
    280     else
    281     {
    282         while ((p->id < new_node->id) && (p->next != NULL))
    283         {
    284             q = p;
    285             p = p->next;
    286         }
    287         
    288         if ((*head)->next == NULL)//一个节点的时候
    289         {
    290             if (p->id > new_node->id)
    291             {
    292                 new_node->next = *head;
    293                 *head = new_node;
    294             }
    295             else
    296             {
    297                 p->next = new_node;
    298             }
    299         }
    300         else
    301         {
    302             if (p->next == NULL)//尾节点
    303             {
    304                 if (p->id > new_node->id)//插入前
    305                 {
    306                     q->next = new_node;
    307                     new_node->next = p;
    308                 }
    309                 else
    310                 {
    311                     p->next = new_node;
    312                 }
    313             }
    314             else//不是尾节点
    315             {
    316                 if((*head)->id > new_node->id)//头节点
    317                 {
    318                     new_node->next = *head;
    319                     *head = new_node;
    320                 }
    321                 else//中间插入时
    322                 {
    323                     q->next = new_node;
    324                     new_node->next = p;
    325                 }
    326             }
    327         }/*end of if()*/
    328     }/*end of if (p == NULL)*/
    329 }
    330 #endif
    331 
    332 int main()
    333 {
    334     Link head = NULL;//防止出现野指针
    335     Link new_node = NULL;//防止出现野指针
    336     int i;
    337     int data;
    338 
    339     create_link(&head);//创建链表
    340 
    341     for (i = 0; i < 10; i++)//值域赋值，并插入新节点
    342     {
    343     //    new_node = (Link)malloc(sizeof(Node));//创建新节点
    344         create_node(&new_node);
    345     //    new_node->id = i + 1;//赋值
    346     //    insert_node_head(&head, new_node);//插入节点，头插
    347     //    insert_node_tail(&head, new_node);//插入节点，尾插
    348     
    349         printf("please input node value:\n");
    350         scanf("%d", &new_node->id);
    351         insert_node_seq(&head, new_node);
    352 //        insert_node_seq_1(&head, new_node);
    353         display_link(head);//输出节点的值域
    354     }
    355 
    356     display_link(head);//输出节点的值域
    357 
    358 #if 0
    359     create_node(&new_node);
    360     new_node->id = i + 1;
    361     insert_node_mid(&head, new_node, 3);//指定位置插入，中间插入
    362     putchar(10);
    363     display_link(head);//输出节点的值域
    364 
    365 #if 0
    366     create_node(&new_node);
    367     scanf("%d", &new_node->id);
    368     insert_node_mid_front(&head, new_node);
    369     display_link(head);//输出节点的值域
    370 #endif
    371 
    372     scanf("%d", &i);
    373     delete_node(&head, i);//删除指定节点
    374     display_link(head);
    375 
    376 #if 0
    377 
    378     create_node(&new_node);
    379     scanf("%d", &new_node->id);
    380     insert_node_seq(&head, new_node);//有序插入指定元素
    381     display_link(head);
    382 #endif
    383 #endif
    384     realse_node(&head);//释放节点
    385 
    386     display_link(head);//输出节点的值域
    387     return 0;
    388 }

![复制代码][copycode.gif]

由于链式数据结构中有指针的各种指向问题，所以在纸上画图是比较容易理解。

其中在对头指针（注意是头指针，不是头节点，两个不是一个概念，头指针是整个链表的操作的基础，链表存在的象征，头指针是整个“链表公司”的一把手，头头结点是链表中的第一个元素）的操作，除了在插入，删除和销毁中头指针的指向发生改变，需要直接对头指针head操作外，其他方法都不要对头指针进行操作，以免丢失整个链表。

在对链表中的增加时，需要考虑链表中开始存在的元老级的“人物”，所以我们不能随便就对它们变换“岗位”，我得先找到”接班人“之后再对这些元老级的岗位进行调整。

在对链表中的节点进行删除时，也需要首先考虑这些元老级的“人物”，毕竟人家没有功劳也有苦劳，我们得代理好它走后它的”上级“和他的”下级“沟通交流的问题。

代码中的一些条件编译和注释是未完成一些功能的另一种方法。

在销毁整个链表时，相当于整个链表公司破产，作为公司一把手的head，依次需要对手下任劳任怨的员工进行思想工作。当整个公司没有员工时，一把手也什么都没有了即NULL。

代码中的功能函数包括：

1.创建链表

2.创建节点

3.插入节点------------头插，尾插以及插入即有序，指定位置插入的方法，根据需要选择合适的方法

头插：实现链式栈

尾插：实现链式队列

4.删除节点

5.销毁整个链

6.判断malloc函数是否执行成功

7.输出链

来源:[http://www.cnblogs.com/SimonKly/p/6890287.html][http_www.cnblogs.com_SimonKly_p_6890287.html]

[copycode.gif]: http://common.cnblogs.com/images/copycode.gif
[http_www.cnblogs.com_SimonKly_p_6890287.html]: http://www.cnblogs.com/SimonKly/p/6890287.html