链表的运用-一个单链表的实现，list，malloc

青旅半醒 2023-10-16 22:20 39阅读 0赞

链表是常用的数据结构。本文实现一个简单的单链表，主要实现三个函数：

1，在末尾添加元素；2，从链表中删除元素；3，统计链表元素的个数。其余函数，读者有兴趣的话，可以自己实现。

**一．题目说明：实现一个单链表，具体要求如下：**

1. 元素可以是任何类型；

2. 实现在链表末尾追加给定元素的功能,如果原链表为空，则把要追加的元素作为链表的第一个结点；

3. 将给定的元素从链表中移除；

4. 实现计算链表结点个数的功能；

5. 对单链表进行测试，数据由开发人员自行定义。

**二．简要分析：**

**1. 数据结构：**

因为数据类型要求是任何类型，根据C语言中void\*与其它指针类型可以互相转换的特点，定义此单链表的数据结构如下：

typedef struct list_t{
    
           void        *data;
    
           struct list_t     *next;
    
    } list_t;

**2. 函数说明：**

根据题目说明，为这个单链表提供以下三个函数：

（1） 函数原型：list\_t \*list\_append(list\_t \*list, void \*data)

函数功能：在链表末尾追加给定元素的功能,如果原链表为空，则把要追加的元素作为链表的第一个结点。

输入参数：list, 链表头指针

data, 要追加的数据

返回：链表头指针

（2） 函数原型list\_t \*list\_remove(list\_t \*list, void \*data)

函数功能：将给定的元素从链表中移除。

输入参数：list, 链表头指针

data, 要移除的数据

返回：链表头指针

（3） 函数原型：int list\_getnumber(list\_t \*list)

函数功能：计算链表结点个数并返回。

输入参数：list, 链表头指针

返回：链表中结点的个数

3. 测试分析：

为了进行测试，定义了stu\_data结构体类型，以及一个数组，用于存放测试数据。另外，写了一个函数void display\_stulist(list\_t \*list)，用于显示列表中的所有数据。具体如下：

（1）数据结构与测试数据：

typedef struct stu_data{
    
            char ID[9];
    
            int age;
    
            char name[14];
    
    } stu_data;

测试数据：

static stu_data stu[15][3] = {
    
           {"69231100", 20, "zhang"},
    
           {"69231101", 22, "wang"},
    
           {"69231102", 21, "li"},
    
           {"69231103", 20, "zhao"},
    
           {"69231104", 23, "qian"},
    
    
    
           {"69231105", 20, "sun"},
    
           {"69231106", 20, "zhou"},
    
           {"69231107", 21, "wu"},
    
           {"69231108", 24, "wang"},
    
           {"69231109", 20, "liu"},
    
          
    
           {"69231110", 21, "liu"},
    
           {"69231111", 22, "wang"},
    
           {"69231112", 20, "liu"},
    
           {"69231113", 20, "li"},
    
           {"69231114", 23, "liu"},
    
    };

（2）显示结果函数：

函数原型：void display\_stulist(list\_t \*list)

函数功能：打印链表list中的所有数据，如果链表为空，则打印" list is null!"。

输入参数：list, 链表头指针

返回：无

**三．源代码：**

#include <stdio.h>
    
    #include <stdlib.h>
    
    
    
    /* list_t */
    
    typedef struct list_t{
    
           void        *data;
    
           struct list_t     *next;
    
    } list_t;
    
    
    /* 追加一个元素 */
    
    list_t *list_append(list_t *list, void *data)
    
    {
    
           list_t       *entry, *prev;
    
    
    
           entry = (list_t*)malloc(sizeof(list_t));  /* 为entry分配存储空间 */
    
           if (!entry)
    
                  return NULL;
    
           entry->data = data;
    
           entry->next = NULL;
    
          
    
           if (!list)                     /* 如果列表为空，则返回刚刚创建的结点 */
    
                  return entry;
    
          
    
           for (prev = list; prev->next; prev = prev->next) ; /* 将prev指针移到列表末尾 */
    
          
    
           prev->next = entry;          /* 将新创建的结点加到列表末尾 */
    
           return list;
    
    }
    
    
    /* 移除一个元素 */
    list_t *list_remove(list_t *list, void *data)
    
    {
    
           list_t       *entry, *prev;
    
    
    
           for (prev = NULL, entry = list; entry; prev = entry, entry = entry->next) {
    
                  if (entry->data == data) {
    
                         if (prev)
    
                                prev->next = entry->next;
    
                         else
    
                                list = entry->next;
    
                         free(entry);      /* 释放由list_append中的malloc分配的存储空间 */
    
                         break;
    
                  }
    
           }
    
           return list;
    
    }
    
    
    /* 统计元素个数 */
    int list_getnumber(list_t *list)
    
    {
    
        list_t *prev;
    
        int i=0;
    
       
    
        if (!list)
    
            return 0;
    
       
    
        for (prev = list;  prev->next;  prev = prev->next, i++) ;
    
        return i;
    
    }
    
    
    
    
    
    /* 测试数据结构体定义  */
    
    typedef struct stu_data{
    
            char ID[9];
    
            int age;
    
            char name[14];
    
    } stu_data;
    
    
    /* 测试数据 */
    static stu_data stu[15][3] = {
    
           {"69231100", 20, "zhang"},
    
           {"69231101", 22, "wang"},
    
           {"69231102", 21, "li"},
    
           {"69231103", 20, "zhao"},
    
           {"69231104", 23, "zhang"},
    
    
    
           {"69231105", 20, "liu"},
    
           {"69231106", 20, "han"},
    
           {"69231107", 21, "zhang"},
    
           {"69231108", 24, "wang"},
    
           {"69231109", 20, "liu"},
    
          
    
           {"69231110", 21, "liu"},
    
           {"69231111", 22, "wang"},
    
           {"69231112", 20, "liu"},
    
           {"69231113", 20, "li"},
    
           {"69231114", 23, "liu"},
    
    };
    
    
    /* 显示列表数据 */
    void display_stulist(list_t *list)
    
    {
    
         list_t *prev;
    
         int i = 0;
    
        
    
         if (!list) {
    
             printf(" list is null!/n");
    
             return;
    
         }
    
            printf("ID         age  name/n");
    
            printf("----------------------------/n");
    
                
    
         for (prev = list; prev->next; prev = prev->next,i++) {
    
             if (i%5 == 0)
    
                 printf("/n");
    
             printf("%s   %d   %s /n", (char*)((stu_data*)prev->data)->ID, ((stu_data*)prev->data)->age, (char*)((stu_data*)prev->data)->name);
    
         }
    
    }
    
    
    /* 测试函数 */
    void test_function(void)
    
    {
    
         list_t *list = NULL;
    
         int i = 0;
    
        
    
            /* test 1: init value of list */
    
         printf("/ntest 1: init value of list. /n");
    
         printf(" number of list is : %d/n",list_getnumber(list));
    
         display_stulist(list);
    
    
    
         /* test 2: append 9 data for list */
    
         printf("/n/ntest 2: append 9 data for list. /n");
    
         for (; i<10; i++) {
    
             list = list_append(list, (void*)stu[i]);
    
         }
    
         printf(" number of list is : %d/n",list_getnumber(list));
    
         display_stulist(list);
    
        
    
          /* test 3: remove stu[5] from list. */
    
         printf("/n/ntest 3: remove stu[5] from list./n");
    
         list_remove(list, (void*)stu[5]);
    
            printf(" number of list is : %d/n",list_getnumber(list));
    
         display_stulist(list);
    
            
    
            return;
    
           
    
    }
    
    
    /* main 函数 */
    int main()
    
    {
    
        test_function();
    
    
    
           return 0;
    
    }

**四．测试结果：**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGlyYW5rZQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**测试结果分析：**

（1） test 1 时，由于list=NULL,所以，会输出

“number of list is : 0”

“list is null!”

（2）总共测试数据有15个, 在test 2 时，向列表中追加了**9**个元素，并将内容打印出来，显示的个数是**9**。

（3）test 3 时，从列表中移除stu\[5\]，所以，再打印列表数据时，就没有“69231105”这条记录了，而且，显示的个数是**8**。

--------------------

链表，必须要过的坎

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGlyYW5rZQ_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/20211009113500467.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAbGlyYW5rZQ==,size_20,color_FFFFFF,t_70,g_se,x_16