简介

	本文主要介绍链表的头插、头删、尾插、尾删、查找、插入和删除，提供全部的.c和.h文件，确保使用者直接复制粘贴到编译器上即可直接运行程序。

动态顺序表结构体

typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;

1.头插功能

	思路是将节点的首地址赋值到新申请节点的next中。

/*插入数据-头插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = *ppHead;*ppHead = newNode;return;
}

	开辟一个新的节点，并将要插入的值放心节点对应的data中。

/*创建节点*/
SLTNode* CreatListNode(SLTDateType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (NULL == newNode){printf("CreatListNode malloc fail\n");exit(-1);}newNode->data = x;newNode->next = NULL;return newNode;
}

2.头删功能

	思路是将下一个节点的地址赋值到头节点地址上，将当前节点free掉。

/*头删*/
void SListPopFront(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* next = (*ppHead)->next;free(*ppHead);*ppHead = next;return;
}

3.尾插功能

	思路是先检查输入*ppHead是否为空，不为空就找到链表的尾节点进行新节点的插入。

/*插入数据-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);/*新结点申请空间*/SLTNode* newNode = CreatListNode(x);if (*ppHead == NULL){*ppHead = newNode;}else{/*找到尾结点*/SLTNode* tail = *ppHead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}return;
}

4.尾删功能

	思路是释放节点时，要将下一个节点的地址保存好再释放当前节点。

/*尾删*/
void SListPopBack(SLTNode** ppHead)
{assert(ppHead != NULL);/*如果只有一个节点时，直接释放此节点*/if ((*ppHead)->next == NULL){free(*ppHead);*ppHead = NULL;}else/*存在2个及2个以上节点的处理方式*/{SLTNode* tail = *ppHead;SLTNode* pre = NULL;while (tail->next != NULL){pre = tail;tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}return;
}

5.查找功能

	思路是遍历，找到节点后返回当前节点的地址，找不到就返回NULL。

/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{assert(pHead != NULL);SLTNode* cur = pHead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}

6.插入功能

6.1 指定位置之（前）去插入一个节点

	此方法是比较笨的方法，为了节约资源应该将数据往指定位置的后边插入。

/*指定位置插入数据-在pos位置之前去插入一个节点--时间复杂度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{assert(ppHead != NULL);assert(pos != NULL);SLTNode* newNode = CreatListNode(x);if (*ppHead == pos)/*pos的位置在第一个位置时*/{newNode->next = *ppHead;*ppHead = newNode;}else{/*找到pos位置的前一个位置*/SLTNode* posPrev = *ppHead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newNode;newNode->next = pos;}return NULL;
}

6.2 指定位置之（后）去插入一个节点

	此方法是常用的插入方式，时间复杂度是O(1)。

/*指定位置插入数据-在pos位置之后去插入一个节点--时间复杂度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = pos->next;pos->next = newNode;return NULL;
}

7.删除功能

7.1 删除指定位置的数据-时间复杂度O(N)

	此方法需要记住当前节点前一个的节点地址，会多耗费时间资源，时间复杂度O(N)。

SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{assert(ppHead != NULL);assert(pos != NULL);/*如果删除的数据是头*/if (*ppHead == pos){SListPopFront(ppHead);}else{SLTNode* prev = *ppHead;while (prev->next != pos)/*找到pos前一个节点*/{prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}return NULL;
}

7.2 删除指定位置后一个位置的数据-时间复杂度O(1)

	此方法需要记住当前节点前一个的节点地址，会多耗费时间资源，时间复杂度O(1)。

/*删除指定位置后一个位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos)
{assert(pos->next != NULL);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;return NULL;
}

8. 释放链表缓存

	思路将下一个节点的地址先记住，然后释放当前节点。再将保存的地址赋值到当前节点循环释放缓存。

/*释放链表缓存*/
SLTNode* SListDestory(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* cur = *ppHead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*ppHead = NULL;return NULL;
}

9. 打印链表的值

/*打印链表的值*/
void SListTPrint(SLTNode* pHead)
{SLTNode* cur = pHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}return;
}

10.此程序共包含3个文件，2个.c文件和1个.h文件

10.1 SList.h文件

	文件中包含了函数功能的头文件以及对应的结构体。

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SLTNode;void SListTPrint(SLTNode *pHead);							/*打印链表的值*/
void SListPushBack(SLTNode** ppHead, SLTDateType x);		/*插入数据-尾插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x);		/*插入数据-头插*/void SListPopBack(SLTNode** ppHead);						/*尾删*/
void SListPopFront(SLTNode** ppHead);						/*头删*/SLTNode* SListFind(SLTNode* pHead, SLTDateType x);				    /*查找*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x);/*指定位置插入数据-在pos位置之前去插入一个节点*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x);				/*指定位置插入数据-在pos位置之后去插入一个节点*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos);				/*删除指定位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos);								/*删除指定位置后一个位置的数据*/
SLTNode* SListDestory(SLTNode** ppHead);							/*释放链表缓存*/SLTNode* CreatListNode(SLTDateType x);								/*创建一个新的节点*/

10.2 SList.c文件

	文件中包含了功能函数的具体实现方式。

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"/*插入数据-尾插*/
void SListPushBack(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);/*新结点申请空间*/SLTNode* newNode = CreatListNode(x);if (*ppHead == NULL){*ppHead = newNode;}else{/*找到尾结点*/SLTNode* tail = *ppHead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}return;
}/*插入数据-头插*/
void SListPushFront(SLTNode** ppHead, SLTDateType x)
{assert(ppHead != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = *ppHead;*ppHead = newNode;return;
}/*创建节点*/
SLTNode* CreatListNode(SLTDateType x)
{SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));if (NULL == newNode){printf("CreatListNode malloc fail\n");exit(-1);}newNode->data = x;newNode->next = NULL;return newNode;
}/*尾删*/
void SListPopBack(SLTNode** ppHead)
{assert(ppHead != NULL);/*如果只有一个节点时，直接释放此节点*/if ((*ppHead)->next == NULL){free(*ppHead);*ppHead = NULL;}else/*存在2个及2个以上节点的处理方式*/{SLTNode* tail = *ppHead;SLTNode* pre = NULL;while (tail->next != NULL){pre = tail;tail = tail->next;}pre->next = NULL;free(tail);tail = NULL;}return;
}/*头删*/
void SListPopFront(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* next = (*ppHead)->next;free(*ppHead);*ppHead = next;return;
}/*查找*/
SLTNode* SListFind(SLTNode* pHead, SLTDateType x)
{assert(pHead != NULL);SLTNode* cur = pHead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}/*指定位置插入数据-在pos位置之前去插入一个节点--时间复杂度O(N)*/
SLTNode* SListInsert(SLTNode** ppHead, SLTNode* pos, SLTDateType x)
{assert(ppHead != NULL);assert(pos != NULL);SLTNode* newNode = CreatListNode(x);if (*ppHead == pos)/*pos的位置在第一个位置时*/{newNode->next = *ppHead;*ppHead = newNode;}else{/*找到pos位置的前一个位置*/SLTNode* posPrev = *ppHead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newNode;newNode->next = pos;}return NULL;
}/*指定位置插入数据-在pos位置之后去插入一个节点--时间复杂度O(1)*/
SLTNode* SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos != NULL);SLTNode* newNode = CreatListNode(x);newNode->next = pos->next;pos->next = newNode;return NULL;
}/*删除指定位置的数据--时间复杂度O(N)*/
SLTNode* SListErase(SLTNode** ppHead, SLTNode* pos)
{assert(ppHead != NULL);assert(pos != NULL);/*如果删除的数据是头*/if (*ppHead == pos){SListPopFront(ppHead);}else{SLTNode* prev = *ppHead;while (prev->next != pos)/*找到pos前一个节点*/{prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}return NULL;
}/*删除指定位置后一个位置的数据*/
SLTNode* SListEraseAfter(SLTNode* pos)
{assert(pos->next != NULL);SLTNode* next = pos->next;pos->next = next->next;free(next);next = NULL;return NULL;
}/*释放链表缓存*/
SLTNode* SListDestory(SLTNode** ppHead)
{assert(ppHead != NULL);SLTNode* cur = *ppHead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*ppHead = NULL;return NULL;
}/*打印链表的值*/
void SListTPrint(SLTNode* pHead)
{SLTNode* cur = pHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}return;
}

10.3 test.c文件

	用来进行相应功能的测试，分别测试尾插、尾删和头插、头删等功能。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "SList.h"void Test1()
{SLTNode* SList = NULL;/*尾插*/SListPushBack(&SList, 1);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 4);/*尾删*/SListPopBack(&SList);/*打印链表*/SListTPrint(SList);printf("NULL\n");return;
}void Test2()
{SLTNode* SList = NULL;/*头插*/SListPushFront(&SList, 1);SListPushFront(&SList, 2);SListPushFront(&SList, 3);/*头删*/SListPopFront(&SList);/*打印*/SListTPrint(SList);printf("NULL");return;
}void Test3()
{SLTNode* SList = NULL;SLTNode* pos = NULL;int i = 1;/*尾插*/SListPushBack(&SList, 1);SListPushBack(&SList, 5);SListPushBack(&SList, 2);SListPushBack(&SList, 3);SListPushBack(&SList, 2);/*查找数字的位置*/pos = SListFind(SList, 2);while (pos)/*查找到数据为2的节点的地址*/{printf("第%d个pos节点的:%p->%d\n", i++, pos->next, pos->data);if (pos->next){pos = SListFind(pos->next, 2);}else/*为空指针时，直接跳出循环*/{break;}}/*改变对应节点位置的数据,将5位置前边的位置添加个20*/pos = SListFind(SList, 5);if (pos)/*在5的位置之前插入20*/{SListInsert(&SList, pos, 20);}pos = SListFind(SList, 5);if (pos)/*在5的位置之后插入100*/{SListInsertAfter(pos, 100);}/*打印*/SListTPrint(SList);printf("NULL");return;
}int main()
{Test1();/*尾插+尾删*///Test2();/*头插+头删*///Test3(); /*指定位置前插入、后插入、寻找指定数据节点的位置*/return 0;
}

	这里代码大家可以自己拷贝到VS编译器中，Test1()，Test2()，Test3()，分别打开注释看一下效果，本人亲测过，可以直接运行出结果的。