单链表的创建和基本操作_本题实现单链表的创建、结点删除等基本操作。要求实现listdelete函数和displist函

链表

一、链表是什么样的：

链表是由很多个结点通过指针连接成一条链。

二、链表的创建和相关操作：

定义结构体，存放了两个变量：数据和指针

1、静态链表：

直接在main函数里创建链表中的结点：

struct Node node1={1,NULL};
struct Node node2={2,NULL};

2、动态链表（单链表）：

所谓动态链表，我们只定义一个头结点（表头），之后的结点通过插入操作进行。我们还需要定义

结构体指针指向链表，使用动态内存申请使结构体指针变成结构体变量。

使用模块化设计，将功能分为多个函数来实现。

2.1创建表头的函数：

用结构体指针表示表头

我们定义了一个结构体函数，返回结构体指针，这个指针指向一个结点，headNode->data表示结点的数据域。headNode->next表示结点的下一个结点。初始化头结点的下一个结点为空。

2.2创建结点的函数：

我们同样定义一个结构体指针指向该结点，并给结点的数据赋值为传递来的值。

2.3插入结点的函数：

插入结点的方法：头插法、尾插法、指定位置插入。

头插法：每个结点都从头部插入，如果从头输出，结果为倒序。

我们以头插法为例：

插入的主要实现步骤为：对指针域进行改变

我们以尾插法为例：

每次插入都是从尾部插入，这样顺序打印出来的数据是顺序的。

在某个值后插入结点

定义两个指针去遍历，两个指针初始化指向headNode。

2.4删除的函数：

删除和插入有异曲同工之妙：

首先我们在函数中定义两个结构体指针：posNode、frontNode。这样方便我们更改指向。

2.5打印链表：

打印同样通过指针来进行，我们只输出表头之后的结点，定义一个指针pow，它指向headNode->next。

2.6链表元素查找：

查找同样使用遍历的方法，定义一个结构体指针初始化指向headNode,只有数据不是我们目标数据，指针就向后移动，当指针变为空时说明没找到。

2.7经验：

我们定义的创建链表和创建结点都是结构体函数，在函数中定义了结构体指针变量headNode和newNode，所以我们用这两个函数创建多个表和多个结点，每个表和结点中都有headNode和newNode。

但在插入、删除、打印函数中，我们都是在函数中重新定义了结构体指针指向headNode，如果不这么做会出现问题。例如，我在打印函数中直接使用headNode来实现，最后headNode会指向最后一个结点，接着我们实现删除时，第一条判定语句就是headNode->next!==NULL，这条语句将会执行。

数中直接使用headNode来实现，最后headNode会指向最后一个结点，接着我们实现删除时，第一条判定语句就是headNode->next!==NULL，这条语句将会执行。

所以，我们定义的结构体指针变量不要再其他函数中直接使用，而是应该重新定义指针去间接实现。

代码实现

结构体定义、结构体函数

#include<stdio.h>
#include<stdlib.h>
//1、创建结构体
struct Node{
	int data;            //数据域 
	struct Node* next;   //指针域 
}; 
//创建表头
struct Node* creatList(){ //定义结构体函数，返回结构体指针表示链表 
	//headNode变成了结构体变量 
	struct Node* headNode=(struct Node*)malloc(sizeof(struct Node));
	//变量初始化
	headNode->next=NULL;
	return headNode; 
} 
//创建结点
struct Node* creatNode(int data){
	//定义一个newNode指针，指向结点 
	struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
	 newNode->data=data;
	 newNode->next=NULL;
	 return newNode;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

插入结点（头插、尾插、指定位置插入）

//插入结点（头插法）
void  insertHead(struct Node*headNode,int data){
	//1、创建插入的结点
	struct Node* newNode=creatNode(data);
	newNode->next=headNode->next;
	headNode->next=newNode; 
} 
//插入结点(尾插法）
void insertBH(struct Node* headNode,int data){
	
	//1、创建插入的结点
	struct Node* newNode=creatNode(data);
	if(headNode->next==NULL){     //如果链表只有头结点 
		//newNode->next=NULL;
			headNode->next=newNode;
	}else{
	   struct Node* pre=headNode;
		while(pre->next!=NULL){   //找最后一个结点 
			pre=pre->next;
		}
		 pre->next=newNode;
        
	} 	 
} 

//指定位置插入
void insertZd(struct Node* headNode,int frontdata,int data){
	//再frontdata后插入data结点
	//1、创建结点
	struct Node* newNode=creatNode(data);
	struct Node* temp=headNode;
	struct Node* afterNode=headNode->next;
	//2、先查找有没有目标结点
	while(temp->data!=frontdata){
			temp=afterNode;
			afterNode=temp->next;
		
			if(afterNode==NULL) {
				printf("找不到对应的值%d\n",frontdata);
				return ;
			}
		}
	newNode->next=afterNode;
	temp->next=newNode;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

查找、删除、输出

//查找结点
int findNode(struct Node* headNode,int data){
	//例如查找链表中有没有4，这和删除差不多
	struct Node* posNode=headNode;
	int count=0;
	while(posNode->next!=NULL){
	   count++;
		if(posNode->next->data==data){
			printf("链表中存在这个数，是第%d个数\n",count);
			return 1;
		}
		
		posNode=posNode->next;
	} 
	printf("没有找到\n");
	return 0;
}
//删除函数
void deleteNode(struct Node* headNode,int posdata){
	struct Node* posNode=headNode;
	struct Node* frontNode=headNode;
	//找到对应删除的结点
	if(posNode==NULL){
		printf("找不到，链表为空\n");
	}else{
		while(posNode->data!=posdata){
			frontNode=posNode;
			posNode=frontNode->next;
		
			if(posNode==NULL) {
				printf("找不到对应的值%d\n",posdata);
				return ;
			}
		}
		frontNode->next=posNode->next;
	} 
} 
//输出函数
void printNode(struct Node* headNode){
	struct Node* pow=headNode->next; 
	while(pow){
		printf(" %d->",pow->data);	
		pow=pow->next;
	}
	printf(" null");
	printf("\n");
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

输出调试

int main(){
	/* 静态链表 
	struct Node node1={1,NULL};
	struct Node node2={2,NULL};
	printf("%d",node1.data);
	*/
	//动态链表
	struct Node* list=creatList();//创建了一个list表 
	struct Node* list1=creatList();//创建一个list1表 
	insertHead(list,1);
	insertHead(list,2);
	insertHead(list,3);//
	printf("头插法：\n"); 
	printNode(list);
	deleteNode(list,1);
	printf("删除后：\n");
	printNode(list);
	deleteNode(list,4);
	printNode(list);
	//deleteNode(list1,4);
//	printNode(list1);
	
	insertBH(list1,1);
	insertBH(list1,2);
	insertBH(list1,3);
	printf("尾插法：\n");
	printNode(list1);
	findNode(list,2);
	printf("指定位置插入：\n");
	insertZd(list1,2,4);
	printNode(list1);
	system("pause");
	return 0;
	 
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

输出结果