数据结构-链表的基本操作-题解(C++代码)

1019 阅读 1 评论 0 点赞

前插法初始化链表
```c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int len = 0;
typedef struct Node {
	int data;
	struct Node *next;
}LinkList;
LinkList *IntiList(int n)//若倒置需要前插法初始化
{
	LinkList *phead;//开辟一个头指针(无需开辟头结点)
	phead = NULL;//注意初始化头指针
	for (int i = 0; i < n; i++){
		LinkList *p = (LinkList*)malloc(sizeof(LinkList));//开辟一个新结点
		scanf("%d", &p->data);
		p->next = NULL;
		if (phead == NULL){//如果链表为空,则把新开的第一个结点做头结点
			phead = p;}
		else{//前插法
			p->next = phead;
			phead = p；}
		len++;}
	return phead;
}
```
插入操作的注意事项
1.若链表为空,则当插入位置为1时,插入成功。
2.若插入位置大于长度，则插入失败
3.插入需找到要插入的位置之前的位置
```c
LinkList *insert(LinkList *phead)//一定要返回phead
{
	LinkList *p = phead;
	int n, m;
	scanf("%d %d", &n, &m);
	if(n>len)
	{
		if (len == 0)//特殊判断长度为0的情况
		{
			if (n == 1)
			{
				LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
				pNode->data = m;
				phead = pNode;
				pNode->next = NULL;
				len++;
				printf("insert OK\n");
				return phead;
			}
			else {
				printf("insert fail\n");
				return phead;
			}
		}
	}
	else
	{
		if (n == 1)//如果链表不为空，又想在头部插入
		{
			LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
			pNode->next = phead;
			pNode->data = m;
			phead = pNode;
		}
		else if(n==len)//想在尾部之前插入一个数
		{
			for (int i = 1; i < len-1; i++)
				p = p->next;
			LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
			pNode->data = m;
			pNode->next = p->next;
			p->next = pNode;}
		else {
			for (int i = 1; i < n-1; i++)//在中间任意位置插入，先找到插入位置之前
			p->next = p;
			LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
			pNode->data = m;
			pNode->next = p->next;
			p->next = pNode;}
		len++;
		printf("insert OK\n");
		return phead;
	}
}
```
//获取元素
```c
int get(LinkList *phead)
{
	int n = 0;
	scanf("%d", &n);
	LinkList*p = phead;
	if (n > len)
	{
		printf("get fail");
		return 0;
	}
	else {
		for (int i = 1; i < n; i++)
		{
			p = p->next;
		}
		printf("%d\n", p->data);
	}
}
```
删除操作:与插入操作一样，找到需删除节点位置的前一个
头结点与尾结点需要特殊处理
```c
LinkList* Delete(LinkList *phead)
{
	LinkList *p = phead;
	int n = 0;
	scanf("%d", &n);
	if (n > len)
	{
		printf("delete fail\n");
		return 0;
	}
	else {
		if (n == 1)//n==1时特殊判断
		{
			phead = p->next;
			free(p);
		}
		else if (n == len)//想删除最后一个节点
		{
			for (int i = 1; i < len-1; i++)//循环一定是从1到n-1。
			{
				p = p->next;
			}
			p->next = NULL;
		}
		else
		{
			for (int i = 1; i < n-1; i++)//欲删除n，则从i=1开始移动n-1次到n之前
			//先找到待删除的前一个位置
			p = p->next;//现在p在待删除节点之前
			LinkList *q = p->next;
			p->next = p->next->next;
			free(q);}		
	}
		len--;
		printf("delete OK\n");
		return phead;
}

```
显示链表
```c
void  show(LinkList *phead)
{
	if (len == 0)
	{
		printf("Link list is empty\n");
	}
	else
	{
		LinkList *p = phead;
		while (p!= NULL)
		{
			printf("%d ", p->data);
			p = p->next;
		}
		printf("\n");
	}
}
```
以下是完整代码
```c
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int len = 0;
typedef struct Node {
	int data;
	struct Node *next;
}LinkList;
LinkList *IntiList(int n)//前插法初始化
{
	LinkList *phead;//开辟节点和开辟指针是两个意思！！！！
	phead = NULL;
	for (int i = 0; i < n; i++)
	{
		LinkList *p = (LinkList*)malloc(sizeof(LinkList));
		scanf("%d", &p->data);
		p->next = NULL;
		
		if (phead == NULL)
		{
			phead = p;
		}
		else
		{
			p->next = phead;
			phead = p;
		}
		len++;
	}
	return phead;
	
}
LinkList *insert(LinkList *phead)//一定要返回phead
{
	LinkList *p = phead;
	int n, m;
	scanf("%d %d", &n, &m);
	if(n>len)
	{
		if (len == 0)
		{
			if (n == 1)
			{
				LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
				pNode->data = m;
				phead = pNode;
				pNode->next = NULL;
				//插入
				len++;
				printf("insert OK\n");
				return phead;
			}
			else {
				printf("insert fail\n");
				return phead;
			}
		}
	}
	else
	{
		if (n == 1)
		{
			LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
			pNode->next = phead;
			pNode->data = m;
			phead = pNode;
		}
		else if(n==len)//想在尾部之前插入一个数
		{
		
			for (int i = 1; i < len-1; i++)
			{
				p = p->next;
			}
			LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
			pNode->data = m;
			pNode->next = p->next;
			p->next = pNode;

//找到尾部之前
		}
		else {//在中间插入

for (int i = 1; i < n-1; i++)//在n插入
			{
				p->next = p;
			}
			LinkList *pNode = (LinkList *)malloc(sizeof(LinkList));
			pNode->data = m;
			pNode->next = p->next;
			p->next = pNode;

}
		len++;
		printf("insert OK\n");
		return phead;
	}
	//插入尾巴
	//插入头部
	//插入中间
	
}
int get(LinkList *phead)
{
	int n = 0;
	scanf("%d", &n);
	LinkList*p = phead;
	if (n > len)
	{
		printf("get fail");
		return 0;
	}
	else {
		for (int i = 1; i < n; i++)
		{
			p = p->next;
		}
		printf("%d\n", p->data);
	}
}
LinkList* Delete(LinkList *phead)//这里传入的是指针形参,该指针移动不会影响原来的头指针，但如果释放该指针指向的空间，则原来指针的指向也为空
{
	LinkList *p = phead;
	int n = 0;
	scanf("%d", &n);
	if (n > len)
	{
		printf("delete fail\n");
		return 0;
	}
	else {
		if (n == 1)
		{
			phead = p->next;
			free(p);
		}
		else if (n == len)//想删除最后一个节点
		{
			for (int i = 1; i < len-1; i++)//i=1,一定是n-1！
			{
				p = p->next;
			}
			p->next = NULL;
		}
		else
		{
			for (int i = 1; i < n-1; i++)//欲删除n，则从1开始移动n-1次到n之前
			//先找到待删除的前一个位置
			p = p->next;//现在p在待删除节点之前
			LinkList *q = p->next;
			p->next = p->next->next;
			free(q);
		}
		//头删，尾删，中间删除
		
	}
		len--;
		printf("delete OK\n");
		return phead;
}

void  show(LinkList *phead)
{
	if (len == 0)
	{
		printf("Link list is empty\n");
	}
	else
	{
		LinkList *p = phead;
		while (p!= NULL)
		{
			printf("%d ", p->data);
			p = p->next;
		}
		printf("\n");
	}
}
int main()
{
	int n = 0,m=0;
	scanf("%d", &n);
	LinkList *phead = IntiList(n);
	scanf("%d", &m);
	while (m--)
	{
		
		char str[200];
		scanf("%s", str);
		if (strcmp(str, "show") == 0)
		{
			show(phead);
		}
		else if (strcmp(str, "get") == 0)
		{
			get(phead);
		}
		else if (strcmp(str, "delete") == 0)
		{
			phead=Delete(phead);
		}
		else if (strcmp(str, "insert") == 0)
		{
			phead = insert(phead);
		}
	}
}
```

0.0分

2 人评分

本文分类：题解列表
浏览次数：1019 次浏览
发布日期：2020-03-24 12:26:46
本文链接：https://blog.dotcpp.com/a/68414

上一篇 > 回文数(一)-题解(Python代码)
下一篇 > 蓝桥杯算法训练VIP-阶乘-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数据结构-链表的基本操作-题解(C++代码)

评论列表共有 1 条评论

发表评论取消回复

数据结构-链表的基本操作-题解(C++代码)

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 1 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 1 条评论

发表评论取消回复