链表简介（一）——创建单向动态链表及输出单向链表内容

╰半夏微凉° 2022-10-19 05:31 3阅读 0赞

本系列文章简要介绍链表的相关知识。

本文是系列文章的第一篇，将介绍**创建单向动态链表**和**输出单向链表内容**的方法，并给出代码示例。

# 1 概述 #

链表（linked list）是一个数据的集合，其中每个元素包含下一个元素的地址，即每个元素包含两部分内容：数据（data）和链（link）。数据部分包含可用的信息；链则将数据连在一起，它包含一个指向链表中下一个元素的**指针**（地址）。

说明：链表中的元素习惯上被称为节点。

链表是动态地进行存储分配的一种数据结构，与数组相比，链表可以根据需要动态地开辟内存单元，并且链表中的节点在内存中是非连续的。

# 2 创建单向动态链表 #

下面通过伪代码的形式介绍创建单向动态链表的算法。

算法：CreateLinkedlist()
    目的：创建单向动态链表
    前提：无
    后续：无
    返回：创建的链表
    {
    	head <- null
    	node_num <- 0
    	
    	tail <- new <- malloc(node)		// allocate new space
    	(*new).data <- data
    	
    	while ((*new).data != 0)		// condition of finishing linked list creation
    	{
    		node_num <- node_num + 1
    		
    		if (1 == node_num)
    		{
    			head <- new;
    		}
    		else
    		{
    			(*tail).link <- new		// link tail and new
                tail <- new				// move location of tail to new
    		}
    		
    		new <- malloc(node)
    		(*new).data <- data
    	}
    	
    	(*tail).link <- null
    	
    	return head
    }

# 3 输出单向链表内容 #

下面通过伪代码的形式介绍输出单向链表内容的算法。

算法：PrintLinkedlist(list)
    目的：输出单向链表内容
    前提：链表（头指针）
    后续：无
    返回：无
    {
    	walker <- list
    	
    	while (walker != null)
    	{
    		print (*walker).data
    		walker <- (*walker).link
    	}
    }

# 4 代码示例 #

根据上述内容，可以编写创建单向动态链表及输出单向链表内容的代码示例。

代码示例内容如下：

#include <stdio.h>
    #include <malloc.h>
    
    #define STRUCT_LEN sizeof(struct student)
    
    struct student
    {
        int stu_num;                /* student number */
        float stu_score;            /* student score */
        struct student* next;
    };
    
    int main()
    {
        /* declaration of func */
        struct student* create(void);
        void print(struct student * list);
    
        struct student* list;
        list = create();
        print(list);
    
        return 0;
    }
    
    /*
    *  this is the create linked list function.
    *  when student number is 0, create operation finish.
    */
    struct student* create(void)
    {
        struct student* head;       /* head pointer name(the name of linked list) */
        struct student* tail;       /* tail node */
        struct student* new;        /* new node */
        int node_num = 0;           /* node numbers of linked list */
        head = NULL;
    
        /* allocate a new code space */
        tail = new = (struct student*)malloc(STRUCT_LEN);
        printf("please input student number and score(delimited by SPACE): \n");
        scanf("%d %f", &(*new).stu_num, &(*new).stu_score);
    
        while ((new != NULL) && ((*new).stu_num != 0))
        {
            /* node number add one */
            node_num = node_num + 1;
    
            /* first node */
            if (1 == node_num)
            {
                head = new;
            }
            else
            {
                /* let tail point new node, link tail and new */
                (*tail).next = new;
                /* move location of tail to new node */
                tail = new;
            }
            
            new = (struct student*)malloc(STRUCT_LEN);
            scanf("%d %f", &(*new).stu_num, &(*new).stu_score);
        }
    
        (*tail).next = NULL;
    
        return head;
    }
    
    /*
    *  this is the print linked list content function.
    */
    void print(struct student * list)
    {
        struct student *walker;
        walker = list;
    
        printf("The linked list contents(student number and score) as followed:\n");
        printf("[student number] [student score]\n");
    
        while (walker != NULL)
        {
            printf("%d                %-f\n", (*walker).stu_num, (*walker).stu_score);
            walker = (*walker).next;
        }
        
        return;
    }

上述代码的编译及运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70][]

说明：

*  在上述代码示例中，链表存储单元的动态开辟是通过 malloc 函数实现的。malloc 函数原型为“void\* malloc(unsigned int size);”，其作用是在内存的动态存储区中分配一个长度为 size 的连续空间。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70]: /images/20221005/4ff56dfbc58b4df7af96efa37e8f8f6b.png