C语言单链表基本操作总结

心已赠人 2022-05-27 22:58 252阅读 0赞

# C语言单链表基本操作 #

**    本文是参考他人实现的C语言单链表，对多篇博文整理的结果，仅作为学习笔记。文末有参考出处。**

## 1、单链表定义 ##

链表是通过一组任意的存储单元来存储线性表中的数据元素，这些存储单元可以是连续的也可以是不连续的。为了建立起数据元素之间的关系，对于每个数据元素除了存放数据元素自身的信息外，还必须有包含的指示该元素直接后继元素存储位置的信息，这两部分信息组成一个结点，即每个结点都有至少包括两个域，一个域存储数据元素信息，称为 **数据域**，另一个域存储直接后继的地址,称为 **指针域**。

typedef struct node{
            int data;    //数据域
            struct node *next;    //指针域
        }NODE;

**2、函数声明**

typedef struct node{
    	int data;
    	struct node *next;
    }Node, *pNode;
    
    //初始化一个链表结点
    pNode init_node(Node *pnode, int data);
    //创建链表函数  
    pNode create_list();
    //遍历链表
    void traverse_list(pNode pHead);
    //头插法建立链表，每次在表头插入
    pNode createlink_byhead(Node *phead, Node node, int data);
    //尾插法建立链表
    pNode createlink_bytail(Node *phead, Node node, int data);
    //求链表长度
    int linklen(Node *phead);
    //按值查找操作
    pNode searchnode(Node *phead, int key);
    //前插法
    pNode insertnode_bypre(Node *phead, Node node, int data, int key);
    //后插法
    pNode insertnode_byback(Node *phead, Node node, int data, int key);
    //删除结点
    pNode deletenode(Node *phead, int key);
    //链表倒置
    pNode reverselink(Node *phead);
    //链表排序（冒泡排序）
    pNode linksort(Node *phead);

## 3、具体实现 ##

初始化一个链表结点

//初始化一个链表结点
    pNode init_node(Node *pnode, int data)
    {
    	pnode = (Node *)malloc(sizeof(Node));
    	pnode->data = data;//初始化数字域
    	pnode->next = NULL;//初始化指针域
    
    	return pnode;
    }

//创建链表函数   
pNode create\_list();

//创建链表函数  
    pNode create_list()
    {
    	int i;                                            //    用于下面循环  
    	int len;                                        //    用来存放有效节点的字数  
    	int val;                                        //    用于临时存放用户输入的数据  
    	pNode pHead = (pNode)malloc(sizeof(Node));        //  分配一个不存放有效数据的头结点  
    	pNode pTail = pHead;                            //    链表的最后一个节点  
    	pTail->next = NULL;                            //    最后一个节点的指针置为空  
    	printf("请输入节点个数：");
    	scanf("%d", &len);
    	for (i = 0; i < len; i++)
    	{
    		printf("第 %d 个节点的数值：", i + 1);
    		scanf("%d", &val);
    		pNode pNew = (pNode)malloc(sizeof(Node));    //    为节点分配空间  
    		pNew->data = val;                            //将用户输入的数据赋给节点的成员  
    		pTail->next = pNew;                        //将最后一个节点的指针指向下一个新的节点  
    		pNew->next = NULL;                            //将新节点中的指针置为空  
    		pTail = pNew;                                //将新节点赋给最后的一个节点  
    	}
    	return pHead;                                    //返回头节点  
    
    }

//遍历链表  
void traverse\_list(pNode pHead);

//遍历链表
    void traverse_list(pNode pHead)
    {
    	pNode p = pHead->next;                            //将头节点的指针给予临时节点p  
    	while (NULL != p)                                //节点p不为空，循环      
    	{
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    	return;
    }

//头插法建立链表，每次在表头插入  
pNode createlink\_byhead(Node \*phead, Node node, int data);

//头插法建立链表，每次在表头插入
    pNode createlink_byhead(Node *phead,Node node, int data)
    {
    	Node *pnode = init_node(&node, data);
    	Node *ptmp = phead;
    
    	if (phead == NULL)
    	{
    		return pnode;
    	}
    	else
    	{
    		phead = pnode;
    		pnode->next = ptmp;
    	}
    
    	return phead;
    }

//尾插法建立链表  
pNode createlink\_bytail(Node \*phead, Node node, int data);

//尾插法建立链表
    pNode createlink_bytail(Node *phead,Node node ,int data)
    {
    	Node *pnode = init_node(&node, data);
    	Node *ptmp = phead;
    
    	if (phead == NULL)
    	{
    		return pnode;
    	}
    	else
    	{
    		while (ptmp->next != NULL)
    		{
    			ptmp = ptmp->next;
    		}
    		ptmp->next = pnode;
    	}
    
    	return phead;
    }

//求链表长度  
int linklen(Node \*phead);

//求链表长度
    int linklen(Node *phead)
    {
    	int len = 0;
    	Node *ptmp = phead;
    
    	while (ptmp != NULL)
    	{
    		len++;
    		ptmp = ptmp->next;
    	}
    
    	return len;
    }

//按值查找操作  
pNode searchnode(Node \*phead, int key);

//按值查找操作
    pNode searchnode(Node *phead,int key)
    {
    	Node *ptmp = phead;
    
    	if (ptmp == NULL)
    	{
    		return NULL;
    	}
    
    	while (ptmp->data != key && ptmp->next != NULL)
    	{
    		ptmp = ptmp->next;
    	}
    
    	if (ptmp->data == key)
    	{
    		return ptmp;
    	}
    	if (ptmp->next == NULL)
    	{
    		return NULL;
    	}
    }

//前插法  
pNode insertnode\_bypre(Node \*phead, Node node, int data, int key);

//前插法
    pNode insertnode_bypre(Node *phead, Node node,int data,int key)
    {
    	Node *pnode = init_node(&node, data);//初始化插入的结点
    	Node *ptmp = phead;
    
    	if (phead == NULL)//链表为空，直接返回初始化的值
    	{
    		return pnode;
    	}
    	else if (phead->data == key)//处理的第一个结点是否为目标结点
    	{
    		phead = pnode;
    		pnode->next = ptmp;
    	}
    	else
    	{
    		while((ptmp->next != NULL) && (ptmp->next->data != key))
    		{
    			ptmp = ptmp->next;
    		}
    		if (ptmp->next == NULL)//没有找到的情况
    		{
    			printf("insert key NOT FOUND\n");
    		}
    		else//把新结点插入到目标结点的前面
    		{
    			ptmp->data = key;
    			pnode->next = ptmp->next;
    			ptmp->next = pnode;
    		}
    	}
    
    	return phead;
    }

//后插法  
pNode insertnode\_byback(Node \*phead, Node node, int data, int key);

//后插法
    pNode insertnode_byback(Node *phead,Node node ,int data,int key)
    {
    	Node *pnode = init_node(&node, data);//初始化插入的结点
    	Node *ptmp = searchnode(phead,key);//查找目标结点
    
    	if (ptmp == NULL)//链表为空，或者没有找到
    	{
    		printf("Link is empty or not found key!\n");
    		return phead;
    	}
    	if (ptmp->next == NULL)//如果key为最后一个结点
    	{
    		ptmp->next = pnode;
    	}
    	else//将新结点插入到目标结点的后面
    	{
    		pnode->next = ptmp->next;
    		ptmp->next = pnode;
    	}
    
    	return phead;
    }

//删除结点  
pNode deletenode(Node \*phead, int key);

//删除结点
    pNode deletenode(Node *phead, int key)
    {
    	Node *ptmp = phead;
    	Node *tmp = NULL;
    
    	if (phead == NULL)//处理链表为空的情况
    	{
    		printf("Link is empty,delete fail!\n");
    		return NULL;
    	}
    	else if(phead->data == key)//单独处理第一个结点
    	{
    		phead = phead->next;
    		free(ptmp);
    		ptmp = NULL;
    	}
    	else
    	{
    		while (ptmp->next != NULL && ptmp->next->data != key)//没找&&没有找到
    		{
    			ptmp = ptmp->next;
    		}
    		if (ptmp->next == NULL)//没有找到
    		{
    			printf("delete key is not found!\n");
    			return phead;
    		}
    		if (ptmp->next->data == key)//找到目标结点删除之
    		{
    			tmp = ptmp->next;
    
    			ptmp->next = tmp->next;
    			free(tmp);
    			tmp = NULL;
    		}
    	}
    
    	return phead;
    
    }

//链表倒置  
pNode reverselink(Node \*phead);

//链表倒置
    //链表的倒置算法思路：一次取出原链表中的每一个结点，将
    //其作为第一个结点插入新链表中。
    pNode reverselink(Node *phead)
    {
    	Node *ptmp = NULL;//创建一个新链表
    	Node *tmp = NULL;
    
    	if (phead == NULL)
    	{
    		printf("list is empty!\n");
    		return NULL;
    	}
    	else
    	{
    		while (phead != NULL)//将链上的结点链到新链上
    		{
    			tmp = phead;
    			phead = phead->next;
    			tmp->next = ptmp;
    			ptmp = tmp;
    		}
    	}
    
    	return phead;
    
    }

//链表排序（冒泡排序）  
pNode linksort(Node \*phead);

//链表排序（冒泡排序）
    pNode linksort(Node *phead)
    {
    	Node *p = NULL;//i
    	Node *q = NULL;//j
    	Node *r = NULL;
    	Node tmp;
    
    	for (p = phead; p; p = p->next)
    	{
    		for (q = p->next; q; q = q->next)
    		{
    			if (p->data > q->data)
    			{
    				tmp = *p;
    				*p = *q;
    				*q = tmp;
    
    				r = p->next;
    				p->next = q->next;
    				q->next = r;
    			}
    		}
    	}
    
    	return phead;
    }

##     ##

## 4、测试代码 ##

`主函数`

//主函数
    int main(int argc, int argv[])
    {
    	int opt = 0;
    
    	printf("请创建一个链表：\n");
    	pNode phead = create_list();
    
    	printf("遍历链表：\n");
    	traverse_list(phead);
            /*......TO DO......*/
    	return 0;
    }

参考链接：

1、https://blog.csdn.net/men\_wen/article/details/52877331?locationNum=14&fps=1

2、https://www.cnblogs.com/chenxiaohei/p/6862791.html