链表基本操作

骑猪看日落 2022-06-06 08:21 178阅读 0赞

#### 　动态内存的相关知识 ####

*  链表的知识预备：关于动态存储单元的分配，`malloc`函数的使用，`free`函数的使用；
 *  `malloc(字节数)`：用于在对上面的空间分配连续的空间，如果分配成功，返回值是当前字节的首地址，如果分配失败，返回值为`NULL`；
 *  对于首地址的字节返回值类型是`void *`，所以在进行使用时，必须进行强制类型转换，在进行接收时，必须使用指针变量进行接收；
 *  动态内存的使用过程：

int *p=NULL; //定义指针变量；
    p=(int *)malloc(sizeof(int));//申请内存空间，并且进行强制类型转换；
    *p=3;//使用指针变量；

*  所有用`malloc`函数申请的空间必须使用`free`进行内存空间的释放；并且应该指针变量指向`NULL`；
 *  如果申请的空间是连续的，那么释放只需要释放一次，如果申请的空间不是连续的，那么每次在进行申请内存空间时，都需要进行内存空间的释放；
 *  结构体的相关知识：
 *  对于单链表的创建过程：对于每一个节点来说，其实都是一个结构体单元，这个结构体单元里面必须包含对于结构体本身的引用；

typedef struct {
        char data;
        struct list *link;
    }list;

*  对于这种包含包含结构体本身的指针的元素称为自引用结构体；

typedef struct listNode *listPointer;
    
    struct listNode
    {
        int data;
        listPointer next;
    };

*  通过结构体变量引用结构体成员时，必须通过成员运算符来完成，两个同类型的结构体之间可以直接赋值；
 *  对于两个同类型的结构体之间是不可以直接进行比较的；
 *  个人比较推荐上面这种方式；

#### 链表 ####

*  链表是这样一种结构：![这里写图片描述][SouthEast]
 *  链表由节点组成，节点包含用来存放数据元素的数据域`(各种类型的数据结构)`，指针域：用来存放数据元素申请的指针地址，也就是后继元素的地址；
 *  特殊的节点：前驱节点：链表中两个相邻界点的前一个；后继节点：两个相邻节点的后一个．前驱节点的指针域指向后继节点．对于后继节点只能够通过前驱节点进行访问；
 *  头节点：表示链表的第一个节点，头节点是没有前驱节点的，必须通过指向头节点的指针才能够访问整个链表，对于一个线性链表只能够由一个头节点；
 *  尾节点：表示没有后继节点的节点，尾节点的指针域`NULL`，一个线性链表只能够由一个尾节点；
 *  链表的特点：  
    
    
     *  有且只有一个节点无前驱，由且只有一个节点无后继；
     *  除了首尾节点以外，其余节点由且只有一个前驱和后继；
 *  头节点是访问链表的关键，尾节点链表结束的关键；
 *  单链表的创建，首先应该创建的是结构体数据成员和指针域；

#include<stdio.h>
    #include<stdlib.h>
    typedef struct listNode *listPointer;
    //通过进行类型重命名，使用定义指针更加方便；
    struct listNode
    {
        int data;
        listPointer next;
    };

*  对于上面仅仅定义了一个整型值，对于结构体也是可以包含结构体；
 *  对于单链表的创建首先应该创建的是头节点，头节点的指针是访问整个链表的关键；

listPointer Create_list(int value)
    {
        listPointer pnode = NULL;
        pnode = (listPointer)malloc(sizeof(listPointer));
        if (pnode == NULL)
        {
            fprintf(stderr, "malloc error\n");
            exit(EXIT_FAILURE);
        }
        pnode->data = value;
        pnode->next = NULL;
        return pnode;
    }

*  对于链表的创建使用`malloc`进行链表的创建过程中，必须进行返回值的判定，因为可能是失败；
 *  同时对于现在创建的节点的指针域应该指定为`NULL`，防止野指针的出现；
 *  对于链表的创建方式一般来说包括两种
    
     *  头插法：也就是在当前创建的节点的前面创建并且连接新的节点；![这里写图片描述][SouthEast 1]
     *  头插法的创建过程：
        
            void Head_insert(listPointer *phead, int value)
            {
                if (*phead == NULL)
                {
                    fprintf(stderr, "The head is NULL\n");
                    exit(EXIT_FAILURE);
                }
                listPointer newhead = (listPointer)malloc(sizeof(listPointer));
                newhead->next = *phead;
                newhead->data = value;
                *phead = newhead;
            }
     *  对于头插法来说完善新的节点信息，改变头指针为新创建链接的地址；
     *  尾插法：也就是在当前新的节点的后面创建并且连接已经存在的节点；  
        ![这里写图片描述][SouthEast 2]
        
            void tail_insert(listPointer *phead, int value)
            {
                if (*phead == NULL)
                {
                    fprintf(stderr, "The head is NULL\n");
                    exit(EXIT_FAILURE);
                }
                listPointer newtail = (listPointer)malloc(sizeof(listPointer));
                listPointer newnext = *phead;
                while (newnext->next != NULL)
                    newnext = newnext->next;
                newtail->data = value;
                newtail->next = NULL;
                newnext->next = newtail;
            }
     *  对于尾插法来说，首先应该进行进行节点的遍历，找到指针域为`NULL`的节点，然后改变指针域为新创建的节点，相对于头插法，多的是指针遍历的过程；
     *  链表的打印功能，这个是为了方便验证链表头插法和尾插法的差异而写的；
        
            void list_print(listPointer head)
            {
                if (head == NULL)
                {
                    fprintf(stderr, "The head is NULL\n");
                    exit(EXIT_FAILURE);
                }
                printf("phead");
                for (; head != NULL; head = head->next)
                    printf("->%d",  head->data);
                printf("\n");
            }
     *  链表的大小判断函数
        
            int list_size(listPointer phead)
            {
                if (phead == NULL)
                {
                    fprintf(stderr, "The list is NULL\n");
                    exit(EXIT_FAILURE);
                }
                int i = 1;
                while (phead != NULL)
                {
                    phead = phead->next;
                    i++;
                }
                return i - 1;
            }
     *  链表的插入函数(按照位置进行插入)：
        
         *  链表的插入分为三种函数：
         *  头节点插入:这种方式采用头插法就可以完成
         *  尾节点插入:采用尾插法就可以完成；
         *  中间节点插入:首先应该进行的是链的连接过程，然后应该进行链的断开  
            ![k][]
         *  通过对域中间节点和尾节点的插入的分析其实可以为一种情况；  
            
            
                void Insert_position(listPointer *head,  size_t position, int value)
                {
                    if (head == NULL ||  position > (size_t)list_size(*head))
                    {
                        fprintf(stderr, "The head is NULL\n");
                        exit(EXIT_FAILURE);
                    }
                    listPointer temp = (listPointer)malloc(sizeof(listPointer));
                    temp->data = value;
                    //头节点的插入情况处理，位置处理按照从`0`开始，和数组的保持一致；
                    if (position == 0)
                    {
                        temp->next = *head;
                        *head = temp;
                    }
                    else
                    {
                        //对于中间节点的插入，以及尾节点的插入处理；
                        size_t i = 1;
                        listPointer newnext = *head;
                        for (; newnext != NULL; newnext = newnext->next)
                        {
                            if (i == position)
                            {
                                temp->next = newnext->next;
                                newnext->next = temp;
                                break;
                            }
                            else
                                i++;
                        }
                    }
                }
     *  关于删除元素的过程，删除元素的过程需要使用两个指针进行遍历`revious`，`nexttail`，`previous`表示的是要删除节点的前面一个指针，`nexttail`表示的是要删除的节点；
        
            void list_delete_position(listPointer *head, size_t position)
            {
                if (position > (size_t)list_size(*head)) exit(EXIT_FAILURE);
                listPointer delete = *head;
                //对于头节点的删除；
                if (position == 0)
                {
                    (*head) = (*head)->next;
                    free(delete);
                }
                else
                {
                    //对于尾节点以及中间节点的删除；
                    listPointer previous = *head;
                    listPointer newnext = (*head)->next;
                    size_t i = 1;
                    for (; newnext != NULL; previous = previous->next, newnext = newnext->next)
                    {
                        if (i == position)
                        {
                            previous->next = newnext->next;
                            free(newnext);
                            break;
                        }
                        else
                            i++;
                    }
                }
            }
     *  按照元素进行删除的过程，包括删除里面的重复元素；
    
        void list_delete_value(listPointer *head, int value)
        {
            if (*head == NULL)
            {
                fprintf(stderr, "The list is NULL\n");
                exit(EXIT_FAILURE);
            }
            listPointer previous = *head;
            listPointer newnext = (*head)->next;
            for (; newnext != NULL;)
            {
                //如果重复元素是头节点；
                if ((*head)->data == value)
                {
                    printf("dfdghgfds\n");
                    *head = previous->next;
                    free(previous);
                }
                //重复元素是尾节点或者是中间节点，这里的遍历是可以用来处理相同的重复元素的；
                else if (newnext->data == value)
                {
                    previous->next = newnext->next;
                    free(newnext);
                    newnext = newnext->next;
        
                    printf("12345567890\n");
                }
                else
                {
                    previous = previous->next;
                    newnext = newnext->next;
                }
            }
        }
    
     *  因为是使用`malloc`进行的内存空间的分配工作，所以这里可以使用`free`进行链表的销毁操作；
    
        void list_destory(listPointer phead)
        {
            if (phead == NULL)
            {
                fprintf(stderr, "The phead is NULL when list_destory\n");
                exit(EXIT_FAILURE);
            }
            listPointer temp;
            while (phead != NULL)
            {
                temp = phead->next;
                free(phead);
                phead = temp;
            }
        }
 *  整个链表创建使用的完整程序如下;

#include<stdio.h>
        #include<stdlib.h>
        typedef struct listNode *listPointer;
    
        struct listNode
        {
            int data;
            listPointer next;
        };
    
        listPointer Create_list(int value)
        {
            listPointer pnode = NULL;
            pnode = (listPointer)malloc(sizeof(listPointer));
            if (pnode == NULL)
            {
                fprintf(stderr, "malloc error\n");
                exit(EXIT_FAILURE);
            }
            pnode->data = value;
            pnode->next = NULL;
            return pnode;
        }
    
        void Head_insert(listPointer *phead, int value)
        {
            if (*phead == NULL)
            {
                fprintf(stderr, "The head is NULL\n");
                exit(EXIT_FAILURE);
            }
            listPointer newhead = (listPointer)malloc(sizeof(listPointer));
            newhead->next = *phead;
            newhead->data = value;
            *phead = newhead;
        }
    
        void tail_insert(listPointer *phead, int value)
        {
            if (*phead == NULL)
            {
                fprintf(stderr, "The head is NULL\n");
                exit(EXIT_FAILURE);
            }
            listPointer newtail = (listPointer)malloc(sizeof(listPointer));
            listPointer newnext = *phead;
            while (newnext->next != NULL)
                newnext = newnext->next;
            newtail->data = value;
            newtail->next = NULL;
            newnext->next = newtail;
        }
    
        int list_size(listPointer phead)
        {
            if (phead == NULL)
            {
                fprintf(stderr, "The list is NULL\n");
                exit(EXIT_FAILURE);
            }
            int i = 1;
            while (phead != NULL)
            {
                phead = phead->next;
                i++;
            }
            return i - 1;
        }
    
        void Insert_position(listPointer *head,  size_t position, int value)
        {
            if (head == NULL ||  position > (size_t)list_size(*head))
            {
                fprintf(stderr, "The head is NULL\n");
                exit(EXIT_FAILURE);
            }
            listPointer temp = (listPointer)malloc(sizeof(listPointer));
            temp->data = value;
    
            if (position == 0)
            {
                temp->next = *head;
                *head = temp;
            }
            else
            {
                size_t i = 1;
                listPointer newnext = *head;
                for (; newnext != NULL; newnext = newnext->next)
                {
                    if (i == position)
                    {
                        temp->next = newnext->next;
                        newnext->next = temp;
                        break;
                    }
                    else
                        i++;
                }
            }
        }
    
        void list_delete_position(listPointer *head, size_t position)
        {
            if (position > (size_t)list_size(*head)) exit(EXIT_FAILURE);
            listPointer delete = *head;
            if (position == 0)
            {
                (*head) = (*head)->next;
                free(delete);
            }
            else
            {
                listPointer previous = *head;
                listPointer newnext = (*head)->next;
                size_t i = 1;
                for (; newnext != NULL; previous = previous->next, newnext = newnext->next)
                {
                    if (i == position)
                    {
                        previous->next = newnext->next;
                        free(newnext);
                        break;
                    }
                    else
                        i++;
                }
            }
        }
    
        void list_delete_value(listPointer *head, int value)
        {
            if (*head == NULL)
            {
                fprintf(stderr, "The list is NULL\n");
                exit(EXIT_FAILURE);
            }
            listPointer previous = *head;
            listPointer newnext = (*head)->next;
            for (; newnext != NULL;)
            {
                if ((*head)->data == value)
                {
                    printf("dfdghgfds\n");
                    *head = previous->next;
                    free(previous);
                }
                else if (newnext->data == value)
                {
                    previous->next = newnext->next;
                    free(newnext);
                    newnext = newnext->next;
    
                    printf("12345567890\n");
                }
                else
                {
                    previous = previous->next;
                    newnext = newnext->next;
                }
            }
        }
    
        void list_print(listPointer head)
        {
            if (head == NULL)
            {
                fprintf(stderr, "The head is NULL\n");
                exit(EXIT_FAILURE);
            }
            printf("phead");
            for (; head != NULL; head = head->next)
                printf("->%d",  head->data);
            printf("\n");
        }
    
        void list_destory(listPointer phead)
        {
            if (phead == NULL)
            {
                fprintf(stderr, "The phead is NULL when list_destory\n");
                exit(EXIT_FAILURE);
            }
            listPointer temp;
            while (phead != NULL)
            {
                temp = phead->next;
                free(phead);
                phead = temp;
            }
        }
    
    
        int main()
        {
            listPointer phead = Create_list(10);
            Head_insert(&phead, 10);
            Head_insert(&phead, 10);
            Head_insert(&phead, 9);
            Head_insert(&phead, 8);
            Head_insert(&phead, 7);
            Head_insert(&phead, 6);
            Head_insert(&phead, 5);
            Head_insert(&phead, 4);
            Head_insert(&phead, 3);
            Head_insert(&phead, 2);
            Head_insert(&phead, 1);
            list_print(phead);
            Insert_position(&phead, 10, 11);
            printf("The list size is %d\n", list_size(phead));
            list_print(phead);
            listPointer nphead = Create_list(10);
            tail_insert(&nphead, 9);
            tail_insert(&nphead, 8);
            tail_insert(&nphead, 7);
            tail_insert(&nphead, 6);
            tail_insert(&nphead, 6);
            tail_insert(&nphead, 5);
            tail_insert(&nphead, 4);
            tail_insert(&nphead, 3);
            tail_insert(&nphead, 2);
            tail_insert(&nphead, 1);
            tail_insert(&nphead, 1);
            tail_insert(&nphead, 1);
            tail_insert(&nphead, 5);
            tail_insert(&nphead, 1);
            tail_insert(&nphead, 10);
            list_delete_position(&phead, 0);
            list_delete_position(&phead, 11);
            list_delete_value(&nphead, 10);
            printf("The nphead is \n");
            list_print(nphead);
            printf("The list size is %d\n", list_size(nphead));
            list_destory(phead);
            list_destory(nphead);
    
            return 0;
        }

[SouthEast]: /images/20220606/fafa4e58054a43e5bff223feebd054e6.png
[SouthEast 1]: /images/20220606/62b0886ac5514c8abce47984c0e883bb.png
[SouthEast 2]: /images/20220606/254250c4ddda4980a359f05e4173432e.png
[k]: /images/20220606/a1ec254e97e848bcb4bca3e469204c9c.png