本文共 7719 字，大约阅读时间需要 25 分钟。

github代码下载

github代码：

一、链表的概念及结构

1.1 概念

链表是一种物理结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.2 结构

二、链表的接口实现

2.1 链表的存储定义

typedef int SLTDataType;//单链表的定义typedef struct SListNode{   	SLTDataType data;		struct SListNode * next; //next指向当前节点的下一个节点}SListNode;

2.2 动态申请一个节点

申请一个节点首先使用malloc开辟一块结构内存

然后将数据元素x放入data数据区

将next置空

//2.2 动态申请一个节点SListNode * BuyListNode(SLTDataType x){   		SListNode * plist=(SListNode *)malloc(sizeof(SListNode));	//判断申请是否成功	if (plist==NULL)	{   		printf("申请新节点失败\n");		exit(-1);	}	plist->data = x;	plist->next = NULL;	return plist;}

2.3 单链表打印

//2.3 单链表打印void SListPrint(SListNode * plist){   	//打印链表	while (plist)	{   		printf("%d->", plist->data);		plist = plist->next;	//节点指向下一个	}	printf("NULL\n");}

2.4 单链表尾插

• 首先申请一个新节点

  

• 判断链表是否为空，如果为空则直接将新节点插入

• 不是空的话，遍历链表找到尾节点

  

• 找到后，申请新节点，让原链表尾节点指向新节点

  
  注意：由于尾插可能存在空链表的情况，因此当链表为空时传入一级指针不会改变链表的状态，所以传入二级指针。

//2.4 单链表尾插void SListPushBack(SListNode** pplist, SLTDataType x){   	//申请一个新节点	SListNode* NewNode = BuyListNode(x);	//判断链表是否为空，如果为空则申请节点直接插入，否则找到尾节点插入	if ((*pplist) == NULL)	{   		*pplist = NewNode;	}	else	{   		//定义一个当前节点tail去找链表的尾节点		SListNode* tail = *pplist;		//遍历节点找尾节点		while (tail->next)		{   			tail = tail->next;		}		//尾节点的next指向新节点		tail->next = NewNode;	}}

2.5 单链表头插

• 首先申请新节点
• 判断链表是否为空，若为空直接插入
• 不为空，让NewNode的next指向Plist，然后让Plist指向NewNode
  

//2.5 单链表头插void SListPushFront(SListNode** pplist, SLTDataType x){   	//申请新节点	SListNode * NewNode = BuyListNode(x);	//判断链表是否空	if (*pplist == NULL)	{   		//链表为空直接插入		*pplist = NewNode;	}	else 	{   		NewNode->next = *pplist;	//新节点next指向pplist		*pplist=NewNode;			//更新头结点	}}

2.6 单链表尾删

尾删有三种情况：

• 单链表为空则返回

• 单链表只有一个节点，直接删除

  

• 单链表有一个以上节点，定义两个指针，一个指向尾节点，一个指向尾节点前的一个节点。首先找到尾节点删除，

  
  然后将prev的next置空
  

//2.6 单链表尾删void SListPopBack(SListNode** pplist){   	//1.单链表为空	if (*pplist == NULL)	{   		return;	}	//2.单链表只有一个节点	else if((*pplist)->next==NULL)	{   		free(*pplist);		*pplist = NULL;	}	//3.单链表有一个以上节点	else	{   		//tali指向第1个节点，prev为空		SListNode * prev = NULL;		SListNode * tail = *pplist;				//遍历链表找到尾节点		while (tail->next!=NULL)		{   			//注意先后顺序，prev先走才不会丢失节点			//prev向后走一个节点			prev = tail;			//tail向后走一个节点			tail = tail->next;		}		//删除尾节点		free(tail);		//prev作为新的尾节点		prev->next = NULL;	}}

2.7 单链表头删

链表三种情况同上

//2.7 单链表头删void SListPopFront(SListNode** pplist){   	//1.空单链表	if (*pplist == NULL)	{   		return;	}	//2.一个节点	else if ((*pplist)->next == NULL)	{   		free(*pplist);		*pplist = NULL;	}	//3.一个以上	else	{   		SListNode * phead = *pplist;		//现移动删除后的头结点		*pplist = phead->next;		//再释放原来的头结点		free(phead);	}}

2.8 单链表查找

//2.8 单链表查找SListNode * SListFind(SListNode * plist, SLTDataType x){   	SListNode * cur = plist;	//1.空链表直接返回	//遍历链表	while (cur)	{   		//如果找节点值等于x则返回		if (x == cur->data)		{   			return cur;		}		//没找到继续遍历		cur = cur->next;	}	return NULL;}

2.9 单链表任意位置之后插入

在pos位置之后插入新节点容易实现，首先让新节点指向当前节点cur的下一个节点，然后让cur当前节点指向新节点

//2.9 单链表在任意位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDataType x){   	assert(pos);	SListNode * newNode = BuyListNode(x);	newNode->next = pos->next;	pos->next = newNode;}

2.10 单链表删除任意位置之后的值

//2.10 单链表删除任意位置之后的值void SListEraseAfter(SListNode* pos){   	assert(pos);	if (pos->next)	{   		SListNode * next = pos->next;	//找到pos位置后面的节点保存起来，防止删除后丢失		pos->next = next->next;			//pos位置节点指向next后的节点		free(next);		//释放pos后的节点	}}

三、多文件实现

3.1 ListNode.h

#ifndef _LISTNODE_H#define _LISTNODE_H#include
   
    #include
    
     #include
     
      #include
      
       typedef int SLTDataType;//单链表的定义typedef struct SListNode{   	SLTDataType data;	//data	struct SListNode * next; //next指向当前节点的下一个节点}SListNode;//动态申请一个节点SListNode * BuyListNode(SLTDataType x);//单链表打印void SListPrint(SListNode * plist);//单链表尾插void SListPushBack(SListNode** pplist, SLTDataType x);//单链表头插void SListPushFront(SListNode** pplist, SLTDataType x);//单链表尾删void SListPopBack(SListNode** pplist);//单链表头删void SListPopFront(SListNode** pplist);//单链表查找SListNode * SListFind(SListNode * plist, SLTDataType x);//单链表在任意位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDataType x);//单链表删除任意位置之后的值void SListEraseAfter(SListNode* pos);//单链表的销毁void SListDestory(SListNode* plist);#endif
      
     
    
   

3.2 ListNode.c

#include "ListNode.h"//2.2 动态申请一个节点SListNode * BuyListNode(SLTDataType x){   		SListNode * plist=(SListNode *)malloc(sizeof(SListNode));	//判断申请是否成功	if (plist==NULL)	{   		printf("申请新节点失败\n");		exit(-1);	}	plist->data = x;	plist->next = NULL;	return plist;}//2.3 单链表打印void SListPrint(SListNode * plist){   	//打印链表	while (plist)	{   		printf("%d->", plist->data);		plist = plist->next;	//节点指向下一个	}	printf("NULL\n");}//2.4 单链表尾插void SListPushBack(SListNode** pplist, SLTDataType x){   	//申请一个新节点	SListNode* NewNode = BuyListNode(x);	//判断链表是否为空，如果为空则申请节点直接插入，否则找到尾节点插入	if ((*pplist) == NULL)	{   		*pplist = NewNode;	}	else	{   		//定义一个当前节点tail去找链表的尾节点		SListNode* tail = *pplist;		//遍历节点找尾节点		while (tail->next)		{   			tail = tail->next;		}		//尾节点的next指向新节点		tail->next = NewNode;	}}//2.5 单链表头插void SListPushFront(SListNode** pplist, SLTDataType x){   	//申请新节点	SListNode * NewNode = BuyListNode(x);	//判断链表是否空	if (*pplist == NULL)	{   		//链表为空直接插入		*pplist = NewNode;	}	else 	{   		NewNode->next = *pplist;	//新节点next指向pplist		*pplist=NewNode;			//更新头结点	}}//2.6 单链表尾删void SListPopBack(SListNode** pplist){   	//1.单链表为空	if (*pplist == NULL)	{   		return;	}	//2.单链表只有一个节点	else if((*pplist)->next==NULL)	{   		free(*pplist);		*pplist = NULL;	}	//3.单链表有一个以上节点	else	{   		//tali指向第1个节点，prev为空		SListNode * prev = NULL;		SListNode * tail = *pplist;				//遍历链表找到尾节点		while (tail->next!=NULL)		{   			//注意先后顺序，prev先走才不会丢失节点			//prev向后走一个节点			prev = tail;			//tail向后走一个节点			tail = tail->next;		}		//删除尾节点		free(tail);		//prev作为新的尾节点		prev->next = NULL;	}}//2.7 单链表头删void SListPopFront(SListNode** pplist){   	//1.空单链表	if (*pplist == NULL)	{   		return;	}	//2.一个节点	else if ((*pplist)->next == NULL)	{   		free(*pplist);		*pplist = NULL;	}	//3.一个以上	else	{   		SListNode * phead = *pplist;		//现移动删除后的头结点		*pplist = phead->next;		//再释放原来的头结点		free(phead);	}}//2.8 单链表查找SListNode * SListFind(SListNode * plist, SLTDataType x){   	SListNode * cur = plist;	//1.空链表直接返回	//遍历链表	while (cur)	{   		//如果找节点值等于x则返回		if (x == cur->data)		{   			return cur;		}		//没找到继续遍历		cur = cur->next;	}	return NULL;}//2.9 单链表在任意位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDataType x){   	assert(pos);	SListNode * newNode = BuyListNode(x);	newNode->next = pos->next;	pos->next = newNode;}//2.10 单链表删除任意位置之后的值void SListEraseAfter(SListNode* pos){   	assert(pos);	if (pos->next)	{   		SListNode * next = pos->next;	//找到pos位置后面的节点保存起来，防止删除后丢失		pos->next = next->next;			//pos位置节点指向next后的节点		free(next);		//释放pos后的节点	}}

3.3 test.c

#include "ListNode.h"//测试单链表的头尾删除void TestListNode1(){   	SListNode * Plist=NULL;	//定义一个单链表	//测试申请一个节点	Plist = BuyListNode(1);	//打印链表测试	SListPrint(Plist);	//2.4 单链表尾插测试	SListPushBack(&Plist, 2);	SListPushBack(&Plist, 3);	SListPushBack(&Plist, 4);	SListPushBack(&Plist, 5);	SListPrint(Plist);	//2.5 单链表头插	SListPushFront(&Plist, -1);	SListPrint(Plist);	//单链表尾删	//SListPopBack(&Plist);	//SListPopBack(&Plist);	//SListPopBack(&Plist);	//SListPopBack(&Plist);	//SListPopBack(&Plist);	//SListPopBack(&Plist);	//SListPopBack(&Plist);	//SListPopBack(&Plist);		//SListPopBack(&Plist);		//SListPopBack(&Plist);	//SListPrint(Plist);	//单链表头删	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPopFront(&Plist);	//SListPrint(Plist);	//2.8 单链表查找	SListNode * pos = SListFind(Plist, 3);	SListPrint(pos);	//2.9 单链表在任意位置之后插入x	SListInsertAfter(pos, 30);	SListPrint(Plist);	//2.10 单链表删除任意位置之后的值	SListEraseAfter(pos);	SListPrint(Plist);}int main(){   	TestListNode1();	system("pause");	return 0;}