链表的相关操作

女爷i 2022-05-12 03:10 206阅读 0赞

*   *   *  定义
         *  定义结构体
         *  初始化
         *  销毁
         *  插入
            
             *   *  头插
                 *  尾插
                 *  随机插入（在结点pos前面插入）
         *  删除
            
             *   *  头删
                 *  尾删
                 *  随机删除（删除pos结点）
         *  查找
         *  删除（第一个数值为data的结点）
         *  删除（所有值为data的结点）

### 定义 ###

#include <stdio.h>
        #include <stdlib.h>
        #include <assert.h>
    
        typedef int DataType;

### 定义结构体 ###

typedef struct Node
        {
            DataType data;
            struct Node *next;
        }Node;

### 初始化 ###

void SListInit(Node **ppfirst)
        {
            assert(ppfirst);
            *ppfirst = NULL;
        }

### 销毁 ###

void SListDestory(Node **ppfirst)
        {
            assert(ppfirst);
            Node *cur, *next;
            for (cur = *ppfirst; cur != NULL; cur = next)
            {
                next = cur->next;
                free(cur);
            }
        }

注：销毁链表时一定要把每一个结点都释放

### 插入 ###

##### 头插 #####

static Node *CreateNewNode(DataType data)
        {
            Node *node = (Node *)malloc(sizeof(Node));
            node->data = data;
            node->next = NULL;
            return node;
        }
    
        void SListPushFront(Node **ppfirst, DataType data)
        {
            assert(ppfirst);
            Node *newNode = CreateNewNode(data);
            newNode->next = *ppfirst;
            *ppfirst = newNode;
        }

##### 尾插 #####

void SListPushBack(Node **ppfirst, DataType data)
        {
            assert(ppfirst);
            Node *newNode = CreateNewNode(data);
            if (*ppfirst == NULL)
            {
                *ppfirst = newNode;
                return;
            }
            Node *cur = *ppfirst;
            while (cur->next != NULL)
            {
                cur = cur->next;
            }
            cur->next = newNode;
        }

##### 随机插入（在结点pos前面插入） #####

void SListInsert(Node **ppfirst, Node *pos, DataType data)
        {
            assert(ppfirst);
            Node *newNode = CreateNewNode(data);
            if (pos == *ppfirst)
            {
                SListPushFront(ppfirst, data);
                return;
            }
            Node *cur = *ppfirst;
            while (cur->next != pos)
            {
                cur = cur->next;
            }
            newNode->next = pos;
            cur->next = newNode;
        }

### 删除 ###

##### 头删 #####

void SListPopFront(Node **ppfirst)
        {
            assert(ppfirst); //断言不是空指针
            assert(*ppfirst); //断言不是空链表
            Node *first = *ppfirst;
            *ppfirst = (*ppfirst)->next;
            free(first);
        }

##### 尾删 #####

void SListPopBack(Node **ppfirst)
        {
            assert(ppfirst); 
            assert(*ppfirst); 
            if ((*ppfirst)->next == NULL)
            {
                free(*ppfirst);
                *ppfirst = NULL;
                return;
            }
            Node *cur = *ppfirst;
            while (cur->next->next != NULL)
            {
                cur = cur->next;
            }
            free(cur->next);
            cur->next = NULL;
        }

##### 随机删除（删除pos结点） #####

void SListRemove(Node **ppfirst, Node *pos)
        {
            assert(ppfirst);
            assert(*ppfirst);
            if (*ppfirst == pos)
            {
                SListPopFront(ppfirst);
                return;
            }
            Node *cur = *ppfirst;
            while (cur->next != pos)
            {
                cur = cur->next;
            }
            cur->next = pos->next;
            free(pos);
        }

### 查找 ###

Node *SListFind(Node **ppfirst, DataType data)
        {
            assert(ppfirst);
            Node *cur = *ppfirst;
            while (cur->data != data || cur->next != NULL)
            {
                cur = cur->next;
            }
            if (cur->data == data)
            {
                return cur;
            }
            return NULL; //找不到返回NULL
        }

### 删除（第一个数值为data的结点） ###

void SListRemoveFirst(Node **ppfirst, DataType data)
        {
            assert(ppfirst);
            assert(*ppfirst);
            Node *cur = *ppfirst;
            Node *node = *ppfirst; //记录cur的前一个
            while (cur->data != data && cur->next !=  NULL)
            {
                cur = cur->next;
            }
            if (cur->next == NULL)
            {
                printf("不存在\n");
                return;
            }
            if (cur == *ppfirst)
            {
                SListPopFront(ppfirst);
                return;
            }
            while (node->next != cur)
            {
                node = node->next;
            }
            node->next = cur->next;
            free(cur);
        }

### 删除（所有值为data的结点） ###

void SListRemoveAll(Node **ppfirst, DataType data)
        {
            assert(ppfirst);
            assert(*ppfirst);
            Node *cur = *ppfirst;
            Node *node = *ppfirst;
            while (cur->next != NULL)
            {
                node = *ppfirst;
                if (cur->data == data)
                {
                    if (cur == *ppfirst)
                    {
                        cur = cur->next;
                        SListPopFront(ppfirst);
                        continue;
                    }
                    while (node->next != cur)
                    {
                        node = node->next;
                    }
                    node->next = cur->next;
                    free(cur);
                    cur = node->next;
                    continue;
                }
                cur = cur->next;
            }
            if (cur == *ppfirst &&  cur->data == data)
            {
                SListPopFront(ppfirst);
            }
        }

注：在链表中，插入元素一定要先申请空间，删除元素一个要记得释放