目录

顺序表和链表的特点：

时间复杂度：

分析：

单链表结构体和数据类型：

开辟一个节点和存储数据：

打印

尾插

         尾删

头插

头删：

查找单链表中的元素

在pos后插入x

在pos前插入x

删除pos后的一个元素:

删除pos位置的元素：

摧毁单链表：

完整代码：

顺序表和链表的特点：

 顺序表使用数组存储线形的元素,其特点是可以随机存取,但是,因为逻辑上相邻的元素物理上也相邻,所以插入删除需要移动元素.

链表使用指针链表示线形表元素的逻辑关系,插入和删除只需修改指针,不能随机存取.

单向链表增加删除节点简单。 遍历时候不会死循环；

时间复杂度：

链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；

而顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动，因此时间复杂度至少为 O(n);

链表存储数据一次只开辟存储一个节点的物理空间，如果后期不够还可以再申请。

分析：

单链表结构体和数据类型：

typedef int SLTDataType;
typedef struct SLlistNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

开辟一个节点和存储数据：

SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

malloc函数开辟一个大小为sizeof(SLTNode)字节即一个结构体大小的空间，原本malloc返回值是void类型的指针，但是代码里面的（SLTNode*）将malloc的返回值强制类型转换为SLTNode类型，这样方便了后面数据的存储；

打印

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

调用SLTPrint()函数使，用*phead接收传进来的参数

尾插

void SLTPushBack(SLTNode** phead,SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*phead == NULL){*phead = newnode;}else{SLTNode* ptail = *phead;while (ptail->next)     //找尾{ptail = ptail->next;}ptail->next = newnode;}
}

图解：

首先用ptail记住链表头部的位置，再ptail=ptail->next寻找最后一个节点 

尾删

void SLTPopBack(SLTNode** phead)
{assert(*phead);//只有一个指针if ((*phead)->next==NULL){free(*phead);*phead = NULL;}else{SLTNode* pre = NULL;                //记录倒数第二个指针，SLTNode* ptail = *phead;while (ptail->next){pre = ptail;ptail = ptail->next;}free(ptail);pre->next = NULL;                     //将被释放的那个指针置空，避免出现野指针}
}

 assert(*phead)实现对*phead判空；这里解释一下为什么传参要用双指针，因为改变的是指针，而不是指针的值；

例如：

//单指针传参交换指针指向的值
void Swap1(int *p1,int *p2)
{int tmp= *p1;   //这里p1解引用之后就是p1指针指向的值*P1 = *p2;*p2= tmp;
}//双指针传参交换指针
void Swap2(int ** pp1,int **pp2)
{int *tmp=*pp1;*pp1 = *pp2;*pp2 = tmp;
}int main()
{int a=0,b=1;Swap1(&a,&b);int *ptr1  = &a,ptr2 = &b;Swap2(&ptr1,&ptr2); 
}

Swap2(&ptr1,&ptr2)通过交换a、b的地址来交换值，而Swap1通过改变指针指向的值来交换值；

总结：1、改变int,传递int *给形参，*形参进行交换改变

           2、改变int*,传递int**给形参，*形参进行交换改变

头插

void SLTPushFront(SLTNode** phead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *phead;                      //*phead = newnode;                           //换头
}

先将newnode->next指向phead(头节点)，再phead=newnode; 

头删：

void SLTPopFront(SLTNode** phead)
{assert(*phead);SLTNode* newnode = NULL;newnode = (*phead)->next;          //存储第二个指针free(*phead);                            //释放第一个指针空间*phead = newnode;                        //换头
}

查找单链表中的元素

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在pos后插入x

void SLTInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* cur = *phead;while (cur != pos){cur = cur->next;}SLTNode* newnode = BuySLTNode(x);newnode->next = cur->next;cur->next = newnode;}

在pos前插入x

void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x)
{assert(pos);if (*phead == pos){SLTPushFront(phead,x);           //头插}else{SLTNode* pre = *phead;while (pre->next != pos){pre = pre->next;}SLTNode* newnode = BuySLTNode(x);pre->next = newnode;newnode->next = pos;}
}

删除pos后的一个元素:

void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next = NULL){return;}else{SLTNode* next = pos->next;pos->next = next->next;free(next);}}

图解： 

删除pos位置的元素：

void SLTErase(SLTNode** phead, SLTNode* pos)
{assert(pos);assert(*phead);if (*phead == pos){SLTPopFront(phead);                   //这里不用*phead,因为传过去的是**phead;解引用的时候改变的是*phead;}else{SLTNode* pre = *phead;while (pre->next != pos){pre = pre->next;}pre->next = pos->next;free(pos);}}

摧毁单链表：

void SLTDestroy(SLTNode** phead)
{SLTNode* cur = *phead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*phead = NULL;
}

完整代码：

我用SList.h存放函数的声明和一些头文件：

#pragma once
#include
#include
#includetypedef int SLTDataType;
typedef struct SLlistNode
{SLTDataType data;struct SListNode* next;
}SLTNode;SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPushFront(SLTNode** phead, SLTDataType x);
void SLTPopFront(SLTNode** phead);SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 查找链表中的元素
void SLTInsertAfter(SLTNode**phead,SLTNode* pos,SLTDataType x);//在pos位置之后插入x
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);//在pos位置前面插入xvoid SLTEraseAfter(SLTNode* pos);//删除pos后面的一个元素void SLTErase(SLTNode** phead, SLTNode* pos);//删除pos位置的元素
void SLTDestroy(SLTNode** phead);

用SList.c定义函数：

#define  _CRT_SECURE_NO_WARNI
#include"SList.h"SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//SLTNode* CreateSList(int n)
//{
//	SLTNode* phead = NULL;
//	SLTNode* ptail = NULL;
//	int x;
//	for (int i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (phead == NULL)
//		{
//			ptail = phead = newnode;
//		}
//		else
//		{
//			ptail->next = newnode;
//			ptail = newnode;
//		}
//	}
//	return phead;
//}void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}void SLTPushBack(SLTNode** phead,SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);if (*phead == NULL){*phead = newnode;}else{SLTNode* ptail = *phead;while (ptail->next)     //找尾{ptail = ptail->next;}ptail->next = newnode;}
}
void SLTPopBack(SLTNode** phead)
{assert(*phead);//只有一个指针if ((*phead)->next==NULL){free(*phead);*phead = NULL;}else{SLTNode* pre = NULL;                //记录倒数第二个指针，SLTNode* ptail = *phead;while (ptail->next){pre = ptail;ptail = ptail->next;}free(ptail);pre->next = NULL;                     //将被释放的那个指针置空，避免出现野指针}
}void SLTPushFront(SLTNode** phead, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);newnode->next = *phead;                      //*phead = newnode;                           //换头
}void SLTPopFront(SLTNode** phead)
{assert(*phead);SLTNode* newnode = NULL;newnode = (*phead)->next;          //存储第二个指针free(*phead);                            //释放第一个指针空间*phead = newnode;                        //换头
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLTInsertAfter(SLTNode** phead, SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* cur = *phead;while (cur != pos){cur = cur->next;}SLTNode* newnode = BuySLTNode(x);newnode->next = cur->next;cur->next = newnode;}void SLTInsert(SLTNode**phead,SLTNode* pos, SLTDataType x)
{assert(pos);if (*phead == pos){SLTPushFront(phead,x);           //头插}else{SLTNode* pre = *phead;while (pre->next != pos){pre = pre->next;}SLTNode* newnode = BuySLTNode(x);pre->next = newnode;newnode->next = pos;}
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next = NULL){return;}else{SLTNode* next = pos->next;pos->next = next->next;free(next);}}void SLTErase(SLTNode** phead, SLTNode* pos)
{assert(pos);assert(*phead);if (*phead == pos){SLTPopFront(phead);                   //这里不用*phead,因为传过去的是**phead;解引用的时候改变的是*phead;}else{SLTNode* pre = *phead;while (pre->next != pos){pre = pre->next;}pre->next = pos->next;free(pos);}}void SLTDestroy(SLTNode** phead)
{SLTNode* cur = *phead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*phead = NULL;
}

用test.c写主函数和函数调用：

#define  _CRT_SECURE_NO_WARNINGS
#include"SList.h"
//void test1()
//{
//	SLTNode* plist = NULL;
//	plist=CreateSList(3);
//	SLTPrint(plist);
//}
//
//void testSLTNode2()
//{
//	SLTNode* plist = NULL;
//	SLTPushBack(&plist, 1);
//	SLTPushBack(&plist, 2);
//	SLTPushBack(&plist, 3);
//	SLTPushBack(&plist, 4);
//	
//	SLTPopBack(&plist);
//	
//	SLTPrint(plist);
//}
//
//void testSTLNode3()
//{
//	SLTNode* plist = NULL;
//	SLTPushFront(&plist,1);
//	SLTPushFront(&plist,2);
//	SLTPushFront(&plist,3);
//	SLTPushFront(&plist,4);
//	SLTPushFront(&plist,5);
//
//	SLTPrint(plist);
//
//	SLTPopFront(&plist);
//	SLTPopFront(&plist);
//
//	printf("\n");
//	SLTPrint(plist);
//}
//void testSLTNode4()
//{
//	SLTNode* plist = NULL;
//	SLTPushFront(&plist, 2);
//	SLTPushFront(&plist, 3);
//	SLTPushFront(&plist, 5);
//
//	SLTNode *p = SLTFind(plist, 5);
//	SLTInsertAfter(p, 99);
//
//	SLTPrint(plist);
//}//void testSLTNode5()
//{
//	SLTNode* plist = NULL;
//	SLTPushBack(&plist, 1);
//	SLTPushBack(&plist, 2);
//	SLTPushBack(&plist, 5);
//
//	SLTNode* p = SLTFind(plist, 1);
//	SLTInsertAfter(&plist,p , 6);
//
//	SLTPrint(plist);
//}void testSLTNode6()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushFront(&plist, 4);SLTPushFront(&plist, 5);SLTPushFront(&plist, 6);SLTNode* p = SLTFind(plist, 4);SLTInsert(&plist,p, 100);SLTPrint(plist);p = SLTFind(plist, 5);SLTInsertAfter(&plist,p, 200);SLTPrint(plist);p = SLTFind(plist, 100);SLTErase(&plist, p);SLTPrint(plist);p = NULL;SLTDestroy(&plist);SLTPrint(plist);
}int main()
{//test1();//testSLTNode2();//testSTLNode3();//testSLTNode4();//testSLTNode5();testSLTNode6();return 0;
}

 运行结果：