数据结构（2.1）线性表之单链表的表示和实现

谁借莪１个温暖的怀抱￠ 2024-04-17 20:53 65阅读 0赞

### 数据结构（2.1）线性表之单链表的表示和实现 ###

*   *   *  前言
         *  顺序表与单链表
         *  头结点与头指针
         *  单链表的初始化
         *  单链表的插入
         *   *  头部插入
             *  尾部插入
         *  全部代码
         *   *  无头结点
             *  有头结点

### 前言 ###

有急事回了家一趟，进度被拖了很久。回来接着看数据结构，发现顺序表和单链表差别还是很大的，由于单链表涉及到较多指针的操作，光靠注释比较难说清楚，不能直接上代码了，所以花了不少时间来画图。单链表的一些特性，鲍老师讲得很细，我也是跟着他的思路走，把单链表分成两个部分来讲，第一个部分主要是讲单链表最基础的创建和原理，第二个部分则是增加了单链表的管理结构，便于更好地管理单链表。

### 顺序表与单链表 ###

数据结构分为逻辑结构、物理(存储)结构、数据运算三个部分，逻辑结构指的是数据之间的关系，可分为线性结构和非线性结构两类；物理结构指的是数据的逻辑结构在计算机存储空间内的存放方式，包括顺序结构、链式结构、索引结构和散列结构。一种逻辑结构在计算机里可以用不同的存储结构实现。

线性表是一种常见的逻辑结构，多用顺序存储(称为顺序表)或链式存储(称为单链表)来实现。

顺序存储结构中，存储单元的地址必须是连续的，所以逻辑上相邻的元素在物理上也必然相邻。因此在初始化顺序表时，需要开辟好一整块连续的内存空间以供使用；当预先设置的内存空间不足时，需要去申请另外一整块内存来使用，以达到动态分配内存的效果。

![顺序存储][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70]

而链式存储结构不要求物理地址是否连续，使用指针来实现元素之间的逻辑关系，所以链式结构除了设计一个数据域来存储数据本身外，还需要一个指针域来存储其后继元素的地址。链式存储不需要一整块的内存空间，可以有效利用碎片化的内存，在每次需要时去才去申请空间，达到真正的动态分配内存的效果。

![链式存储][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70 1]

由于顺序存储和链式存储的特性，它们各有着一些优缺点，比如顺序存储可以按元素序号直接访问，因此在读取数据时效率很快；而链式存储则在做插入或删除操作时很方便。

### 头结点与头指针 ###

*  **首元结点：链表中存储的第一个数据元素的结点**。
 *  **头结点：为了处理方便，在首元结点之前附设的一个结点**。有了头结点，对首元结点进行插入或者删除的操作就跟对其他结点的操作是一致的了，有利于操作的统一。
 *  头结点的数据域可以不存储任何信息，也可以存储于数据元素类型相同的附加信息。
 *  **头指针：指向链表中第一个节点的指针**。如果链表有头结点，那么头指针所指向的结点就是链表的头结点；如果链表不设头结点，那么头指针所指向的结点就是链表的首元结点。

![头结点与头指针][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70 2]

### 单链表的初始化 ###

无头结点：

![单链表的初始化1][1]

注：

![单链表的初始化2][2]

有头结点：

![单链表的初始化3][3]

### 单链表的插入 ###

在有无头结点这两种情况下，对链表进行头部插入、尾部插入的操作是有区别的

#### 头部插入 ####

无头结点：生成一个新结点，将新结点的next指向首元结点，再将头指针指向新结点即可  
![头部插入1][1 1]  
![头部插入2][2 1]

有头结点：生成一个新结点，将新结点的next指向首元结点，再将头结点的next指向新结点即可  
![头部插入3][3 1]  
![头部插入4][4]

#### 尾部插入 ####

思路是一致的：生成一个新结点，遍历整个链表到尾部，在尾部插入新结点即可

![尾部插入1][1 2]

![尾部插入2][2 2]

![尾部插入3][3 2]

![尾部插入4][4 1]

因此，设置头结点有利于链表操作的统一，并且头结点的数据域可以储存链表的相关信息，方便对链表进行处理。

### 全部代码 ###

#### 无头结点 ####

#include<stdio.h>
    
    #include <assert.h>
    #include <stdlib.h>
    
    //保存的数据类型
    #define ElemType int
    
    typedef struct ListNode{ 
        //数据域
        ElemType data;
        //指针域，指向下一个结构体的地址
        struct ListNode *next;
    }ListNode;
    typedef ListNode* List;
    
    //初始化单链表
    void InitList(List *head);
    
    //尾部插入
    void push_back(List *head,ElemType x);
    //头部插入
    void push_fount(List *head,ElemType x);
    
    //展示单链表
    void ShowList(List head);
    
    
    int main(void){ 
    
        List myList;
        InitList(&myList);
        
        int select = 1;
    	int input;
        while (select) { 
            printf("***************************************************\n");
            printf("* [1] push_back [2] push_front * \n");
            printf("* [3] show *\n");
            printf("***************************************************\n");
            printf("请选择：\n");
            scanf("%d",&select);
            
            if(select == 0){ 
                break;
            }
            
            switch (select) { 
                case 1:
    				printf("请输入:\n");
    				scanf("%d",&input);
                    push_back(&myList, input);
                    break;
                case 2:
    				printf("请输入:\n");
    				scanf("%d",&input);
                    push_fount(&myList, input);
                    break;
                case 3:
                    ShowList(myList);
                    break;
                default:
                    break;
            }
        }
    	
    	return 0;
    }
    
    //初始化单链表
    void InitList(List *head){ 
        *head = NULL;
    }
    
    //尾部插入 无头结点
    void push_back(List *head,ElemType x){ 
    
        //判断是否已经有第一个结点
        if (*head == NULL) { 
            //没有,创建第一个结点并存值
            *head = (ListNode *)malloc(sizeof(ListNode));
            assert(*head != NULL);
    
            (*head)->data = x;
            (*head)->next = NULL;
        }else{ 
    
            //已经有第一个结点了,创建一个结点并存值
            List s = (ListNode *)malloc(sizeof(ListNode));
            assert(s != NULL);
            s->data = x;
            s->next = NULL;
    
            List p = (*head);
            while (p->next != NULL) { 
                p = p->next;
            }
            p->next= s;
        }
    }
    
    //头部插入 无头结点
    void push_fount(List *head,ElemType x){ 
        List s = (ListNode *)malloc(sizeof(ListNode));
        assert(s != NULL);
        s->data = x;
    
        s->next = (*head);
    
        (*head) = s;
    }
    //展示单链表
    void ShowList(List head){ 
        ListNode *p = head;
        while (p != NULL) { 
            printf("%4d",p->data);
            p = p->next;
        }
        printf("\n");
    }

#### 有头结点 ####

#include<stdio.h>
    #include <assert.h>
    #include <malloc.h>
    
    //保存的数据类型
    #define ElemType int
    
    typedef struct ListNode{ 
        //数据域
        ElemType data;
        //指针域，指向下一个结构体的地址
        struct ListNode *next;
    }ListNode;
    typedef ListNode* List;
    
    //初始化单链表
    void InitList(List *head);
    
    //尾部插入
    void push_back(List *head,ElemType x);
    //头部插入
    void push_fount(List *head,ElemType x);
    
    //展示单链表
    void ShowList(List head);
    
    
    int main(void){ 
    
        List myList;
        InitList(&myList);
        
        int select = 1;
    	int input;
        while (select) { 
            printf("***************************************************\n");
            printf("* [1] push_back [2] push_front * \n");
            printf("* [3] show *\n");
            printf("***************************************************\n");
            printf("请选择：\n");
            scanf("%d",&select);
            
            if(select == 0){ 
                break;
            }
            
            switch (select) { 
                case 1:
    				printf("请输入:\n");
    				scanf("%d",&input);
                    push_back(&myList, input);
                    break;
                case 2:
    				printf("请输入:\n");
    				scanf("%d",&input);
                    push_fount(&myList, input);
                    break;
                case 3:
                    ShowList(myList);
                    break;
                default:
                    break;
            }
        }
    	
    	return 0;
    }
    
    //初始化单链表
    void InitList(List *head){ 
        *head = (ListNode *)malloc(sizeof(ListNode));
        assert(*head != NULL);
    
        (*head)->next = NULL;
    }
    
    //尾部插入 有头结点
    void push_back(List *head,ElemType x){ 
        //创建一个结点并存值
        List s = (ListNode *)malloc(sizeof(ListNode));
        assert(s != NULL);
        s->data = x;
        s->next = NULL;
    
        List p = (*head);
        while (p->next != NULL) { 
            p = p->next;
            //printf("here\n");
        }
        p->next = s;
    }
    
    //头部插入 有头结点
    void push_fount(List *head,ElemType x){ 
        List s = (ListNode *)malloc(sizeof(ListNode));
        assert(s != NULL);
    
        s->data = x;
        s->next = (*head)->next;
        (*head)->next = s;
    }
    
    //展示单链表
    void ShowList(List head){ 
        ListNode *p = head->next;
        while (p != NULL) { 
            printf("%4d",p->data);
            p = p->next;
        }
        printf("\n");
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/a7baf496ff844547add353bb9d102f82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/0eeace6b36c54892859f34c3f5912756.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e16405db77e14137a817d1dd7fc8914d.png
[1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/37a92fbc20a14a5da653163e0be09134.png
[2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/7ec6479e70bc46ec91cf5934ec4a6ee2.png
[3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/8c1f506943354d8f837a64756ac8cc7e.png
[1 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/65c28ab1bfd54810b97980e07d27a03d.png
[2 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b69a6ce9a1754a9f930619e0e08e8b2b.png
[3 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/bb46fe4331bc4654ad5969de4f38d78a.png
[4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/4bffcceed18f45b49c324bc811c97355.png
[1 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/01cb20d58f644b42b2d757bb5e7f0549.png
[2 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f1107d7593b54d399078d57eed4fb8ec.png
[3 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/511de07c28fc42e2b49b10c35599bc56.png
[4 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/6f1342909b934d038fd799dd12858ce7.png