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

2674 阅读 4 评论 0 点赞

首先先把题目要求分明确了。然后利用函数一步一步实现。
题目要求的字符串有四个，分别是
“insert”	`L *insert (L *insHead);`、
“delete”	`L *del (L *delHead);`、
“get”		`void get (L *getHead);`、
“show”		`void show (L *showHead);`。
由于一开始会有一个对链表初始化的操作，我这里就增加了一个函数名为“inti”的函数。

创建链表
```
typedef struct Note{
	int data;
	struct Note *Next;
}L;
```

初始化函数`L *inti (L *intiHead)`:
初始化数据案例中输入时3 2 1，输出是 1 2 3.所以这里要一直往前面插入数据
用上的灵魂画手，emmmmmmmmm
![](/image_editor_upload/20191001075245_74590.png)
```
L *inti (L *intiHead){
	int i = len;
	while (i--){
		L *intiP;
		intiP = (L*)malloc(sizeof(L));//分配内存空间 
		scanf("%d", &intiP->data);//写入数据 
		intiP->Next = NULL;
		if (intiHead){
			intiP->Next = intiHead;//头链表有数据时，让intiP的下一个目标地址指向头链表地址 
			intiHead = intiP;//然后让intiP链表地址成为头链表的地址 
		} else {
			intiHead = intiP;//头链表为空时，让intiP链表的地址成为头链表的地址 
		}
	}
	return intiHead;
}```

插入链表函数`L *insert (L *insHead);`
第一步就是判断链表长度是否为空链表
第二步是判断插入位置是否大于链表长度
第三部是寻找链表位置并且插入新的数据
![](/image_editor_upload/20191001084352_85648.png)
最后插入成功后别忘记了要把长度加1
```
L *insert (L *insHead){
	L *o, *tmp;
	o = insHead;//需要改变地址值，也要返回头地址，先创建一个临时链表 
	tmp = (L*)malloc(sizeof(L));//创建一个接受数据的临时链表，分配空间 
	int i, n;
	scanf("%d%d", &n, &tmp->data);//获取在第几个链表插入数据 
	tmp->Next = NULL; 
	if (insHead){//判断头链表，由于计数为0时判断体内是插入不了数据的 
			if (n > len ){//判断项数有没有大于现有的项数 
			printf("insert fail\n"); 
			return insHead;
		} else {
			if (n == 1){//n = 1时插入的数据链表地址当作链表的头链表地址 
				tmp->Next = insHead; 
				insHead = tmp;
			} else {
				i = 1;
				while (i < n - 1){//查找插入数据是第几项，找到他前面的那项就退出循环 
					o = o->Next;
					i++;
				}
				tmp->Next = o->Next;//插入数据链表的下一个链表地址指向要插入第几项的链表地址 
				o->Next = tmp;//插入数据链表的前面那项的下一个链表地址指向新的临时链表地址 
			}
		}
	} else {//头链表不存在 
		if (n != 1){//头链表不存在说明项数为0，插入项数不为1则插入失败 
			printf("insert fail\n"); 
			return insHead;
		} else {
			insHead = tmp;//临时数据链表地址当成头链表地址 
		}
	}
	printf("insert OK\n");
	len++;//插入一个数据那么计数就增加1 
	return insHead;
}
```
删除链表函数`L *del (L *delHead)；`
PS：删除这个是不需要判断头链表的
第一步先判断删除的位置是否大于链表长度
第二步记录删除位置的前一项
第三步把删除链表的前一项链表的next指向删除链表的后一项的地址即可
![](/image_editor_upload/20191001081517_85692.png)
最后不能别忘了长度减一
```
L *del (L *delHead){
	int i, x;
	L *temp, *q;
	q = delHead;
	scanf("%d", &x);
	if (x > len){
		printf("delete fail\n");
		return delHead;
	} else {
		if (len == 1){
			delHead = NULL;//剩下一个链表的时候直接就把头链表清空就可以了 
		} else if (x == 1){
			delHead = delHead->Next;//如果不是只有一个链表，删除第一个链表就是直接让他指向他的下一个链表地址就可以了 
		} else {
			i = 1;
			while (q && i < x - 1){
				q = q->Next;
				i++;
			}
			if (x == len){
				q->Next = NULL;
			} else {
				temp = q->Next;
				q->Next = temp->Next;
			}
		}
	}
	printf("delete OK\n");
	len--;//删除一个链表计数就要减去1 
	return delHead;
}
```

显示全部数据函数`void show (L *showHead)；`
这个就比较简单了
首先判断是否为空链表
然后循环遍历显示数据
```
void show (L *showHead){
	if (showHead){
		for (; showHead; showHead = showHead->Next){
			if (showHead->Next){
				printf("%d ", showHead->data);//不是最后一个数据则输出数据加空格
			} else {
				printf("%d\n", showHead->data);//最后一个数据输出数据后换行
			}
		}
	} else {
		printf("Link list is empty\n");
	}
}
```

显示某个数据`void get (L *getHead);`
这个也比较简单了
首先判断输出显示的位置是否大于链表长度
然后输出显示这个项的数据
```
void get (L *getHead){
	int i, x;
	scanf("%d", &x);
	if (x > len){
		printf("get fail\n");
	} else {
		for (i = 1; i < x; i++)
			getHead = getHead->Next;
		printf("%d\n", getHead->data);
	}
}
```

下面的完整的代码：
```
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int len, count;//长度、计数

typedef struct Note{
	int data;			//数据 
	struct Note *Next;	//指向下一个链表 
}L;

L *inti (L *intiHead);//初始化 
L *insert (L *insHead);//插入 
L *del (L *delHead);//删除 
void show (L *showHead);//显示全部 
void get (L *getHead);//显示某个

int main(){
	L *Head;//创建头链表 
	Head = NULL;
	scanf("%d", &len);// 获取长度 
	Head = inti (Head);//对链表初始化 
	
	scanf("%d", &count);//获取计数次数 
	while (count--){
		char str[7];//创建大小为7的操作指令就够用了 
		scanf("%s", str);//获取操作指令
		/*
			strcmp(str1, str2)
			str1 > str2 返回 1
			str1 == str2 返回 0
			str1 < str2 返回-1 
		*/ 
		if (!strcmp(str, "insert")) //插入 
			Head = insert (Head); 
		else if (!strcmp(str, "delete"))//删除 
			Head = del (Head);
		else if (!strcmp(str, "get"))//显示某个 
			get (Head);
		else if (!strcmp(str, "show"))//显示全部 
			show(Head); 
	}
	return 0;
}

L *inti (L *intiHead){
	int i = len;
	while (i--){
		L *intiP;
		intiP = (L*)malloc(sizeof(L));//分配内存空间 
		scanf("%d", &intiP->data);//写入数据 
		intiP->Next = NULL;
		if (intiHead){
			intiP->Next = intiHead;//头链表有数据时，让intiP的下一个目标地址指向头链表地址 
			intiHead = intiP;//然后让intiP链表地址成为头链表的地址 
		} else {
			intiHead = intiP;//头链表为空时，让intiP链表的地址成为头链表的地址 
		}
	}
	return intiHead;
}
L *insert (L *insHead){
	L *o, *tmp;
	o = insHead;//需要改变地址值，也要返回头地址，先创建一个临时链表 
	tmp = (L*)malloc(sizeof(L));//创建一个接受数据的临时链表，分配空间 
	int i, n;
	scanf("%d%d", &n, &tmp->data);//获取在第几个链表插入数据 
	tmp->Next = NULL; 
	if (insHead){//判断头链表，由于计数为0时判断体内是插入不了数据的 
			if (n > len ){//判断项数有没有大于现有的项数 
			printf("insert fail\n"); 
			return insHead;
		} else {
			if (n == 1){//n = 1时插入的数据链表地址当作链表的头链表地址 
				tmp->Next = insHead; 
				insHead = tmp;
			} else {
				i = 1;
				while (i < n - 1){//查找插入数据是第几项，找到他前面的那项就退出循环 
					o = o->Next;
					i++;
				}
				tmp->Next = o->Next;//插入数据链表的下一个链表地址指向要插入第几项的链表地址 
				o->Next = tmp;//插入数据链表的前面那项的下一个链表地址指向新的临时链表地址 
			}
		}
	} else {//头链表不存在 
		if (n != 1){//头链表不存在说明项数为0，插入项数不为1则插入失败 
			printf("insert fail\n"); 
			return insHead;
		} else {
			insHead = tmp;//临时数据链表地址当成头链表地址 
		}
	}
	printf("insert OK\n");
	len++;//插入一个数据那么计数就增加1 
	return insHead;
}
L *del (L *delHead){
	int i, x;
	L *temp, *q;
	q = delHead;
	scanf("%d", &x);
	if (x > len){
		printf("delete fail\n");
		return delHead;
	} else {
		if (len == 1){
			delHead = NULL;//剩下一个链表的时候直接就把头链表清空就可以了 
		} else if (x == 1){
			delHead = delHead->Next;//如果不是只有一个链表，删除第一个链表就是直接让他指向他的下一个链表地址就可以了 
		} else {
			i = 1;
			while (q && i < x - 1){
				q = q->Next;
				i++;
			}
			if (x == len){
				q->Next = NULL;
			} else {
				temp = q->Next;
				q->Next = temp->Next;
			}
		}
	}
	printf("delete OK\n");
	len--;//删除一个链表计数就要减去1 
	return delHead;
}
void show (L *showHead){
	if (showHead){
		for (; showHead; showHead = showHead->Next){
			if (showHead->Next){
				printf("%d ", showHead->data);
			} else {
				printf("%d\n", showHead->data);
			}
		}
	} else {
		printf("Link list is empty\n");
	}
}
void get (L *getHead){
	int i, x;
	scanf("%d", &x);
	if (x > len){
		printf("get fail\n");
	} else {
		for (i = 1; i < x; i++)
			getHead = getHead->Next;
		printf("%d\n", getHead->data);
	}
}
```
有什么问题给我留言吧！看到会一一回复。

0.0分

6 人评分

本文分类：题解列表
浏览次数：2674 次浏览
发布日期：2019-10-01 20:44:34
本文链接：https://blog.dotcpp.com/a/61941

上一篇 > 回文数(一)-题解(C++代码)
下一篇 > C语言考试练习题_排列-题解(C语言代码)

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

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

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

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

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

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

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

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

评论列表共有 4 条评论

LikeWater 1年前回复TA

#include<iostream>
#include<string>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

Status InitList_L(LinkList &L) { //算法2.6 单链表的初始化
	//构造一个空的单链表L
	L = new LNode; //生成新结点作为头结点，用头指针L指向头结点
    int length=0;//头结点不计入长度
    L->data = length;
	L->next = NULL; //头结点的指针域置空
	return OK;
}//InitList_L

void CreateList_H(LinkList &L , int n){//创建新结点，连接

LikeWater 1年前回复TA

为啥你的运行这么快，我的运行速度就有问题

Monet 3年前回复TA

初始化是init啊

我是最烂的 3年前回复TA

负数可以！不对吧

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

评论列表共有 4 条评论

发表评论取消回复