笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

数据结构：单链表头插入法&尾插入法及几种常用操作_1.设计一个算法,在单链表中的第三个位置插入100,并输出。请输入整数序列 list i

作者：笔触狂放9 | 2024-04-18 05:05:29

踩

1.设计一个算法,在单链表中的第三个位置插入100,并输出。请输入整数序列 list i

头插入法

在初始化之后，就可以着手开始创建单链表了，单链表的创建分为头插入法和尾插入法两种，两者并无本质上的不同，都是利用指针指向下一个结点元素的方式进行逐个创建，只不过使用头插入法最终得到的结果是逆序的。
如图，为头插法的创建过程：
在这里插入图片描述
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。

//初始化单链表，使用头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node)); //申请头结点空间
    L->next = NULL; //初始化一个空链表
    }
    int x;  //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));  //申请新的结点
        p->data = x;  //结点数据域赋值
        p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 链表的创建和遍历
link * initLink(){
    link * p=(link*)malloc(sizeof(link));//创建一个头结点
    link * temp=p;//声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i=1; i<5; i++) {
        link *a=(link*)malloc(sizeof(link));
        a->elem=i;
        a->next=NULL;
        temp->next=a;
        temp=temp->next;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

尾插入法

在这里插入图片描述
头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，可采用尾插法。

该方法是将新结点逐个插入到当前链表的表尾上，为此必须增加一个尾指针 r, 使其始终指向当前链表的尾结点，否则就无法正确的表达链表。

//初始化单链表，尾插法建立单链表
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;            //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

链表（增删改查/遍历/元素个数）

链表结构体声明：

首先，在创建一个链表之前，我们要先创建一个链表单个节点的结构体，分别包含数据域和指针域，具体实现如下：

typedef struct node{
	int data;               //数据域
	struct node *next;      //指针域（结构体类型指针）
}Node,*Link; //取别名 Node 和 结构体指针类型 Link
1
2
3
4

单链表的创建：

创建一个带有头结点的链表，虽然不是必须的，但是很方便。

Link create()
{
	Link head = NULL; //初始化Link指针指向null
	head = (Link)malloc(sizeof(Node));//申请新节点
	if(head == NULL)
	{
		printf("动态内存分配失败");
		return NULL; 
	}
	head->data = 0;            //数据域赋初始值
	head->next = NULL;         //指针域赋初始值
	
	return head;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

单链表的插入：

头插法增加节点：（插入顺序为反向）

void head(Link head,int num)
{
	Link p,pr;
	p = head->next;				//p为头结点的下一个 
	pr = NULL;					//pr为新插入的结点 插在head后p前 
	pr = (Link)malloc(sizeof(Node));
	
	if(pr == NULL)
	{
		printf("动态内存分配失败");
		return ;
	}
	
	pr->data = num;		//给pr数据域赋值 
	
	pr->next = p;		//头插！
	head->next = pr;
	
	return ; 
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

尾插法增加节点：（插入顺序为正向）

void rear(Link head,int num)
{
	Link p = head;
	Link pr = NULL;		//pr为新增节点
	
	pr = (Link)malloc(sizeof(Node));
	if(pr == NULL)
	{
		printf("动态内存分配失败");
		return ; 
	}
	
	pr->data = num;				//数据域赋值 
	if(head->next == NULL)		//如果头结点下一个为空，就可以直接插入 
	{
		head->next = pr;		//插在头结点后一个 
		pr->next = NULL;		//插完后就指向空结束了 
	} 
	else
	{
		while(p->next != NULL)	//头节点不指向空，就先循环遍历链表找到最后一个再插进去 
		{
			p = p->next;
		}
		p->next = pr;			//尾插！ 
		pr->next = NULL;
	} 
	return； 
}
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

单链表的删除：

void deletenode(Link head,int n)	//传入链表和要删除的数
{
	Link p = NULL,pr = NULL;	//定义一前一后两个节点
	p = head;
	pr = head->next;
	
	if(head == NULL)
	{
		printf("链表为空，没有可删除的值");
		return ; 
	}
	
	while(pr->data != n && pr->next != NULL)	//没遍历到要删除的值，并且不指空，就接着遍历
	{
		p = pr;		//删除操作，前保存后
		pr = pr->next; 
	}
	
	 //出循环有两种情况：
	 //1.找到要删除的值了
	 //2.整个链表遍历到最后也没找到，
	 //  也就是说这个传入的要删除的值根本不存在链表当中 
	 
	 if(pr->data == n)
	 {
	 	if(pr == head)			//优先考虑，pr为头节点，直接给head保存，最后一起释放pr 
	 	{
	 		head->next = pr->next;
		}
		else
		{
			p->next = pr->next 	//前面p保存后面pr，最后一起释放pr 
		}
		free(pr);
		printf("删除成功！"); 
	 } 
	 else
	 {
	 	printf("未找到要删除的值"); 
	 }
	 
	 return ;
	 
 } 

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

单链表的修改：

void fix(Link head,int m)		//传入链表和要改动的值
{
	Link pr;
	pr = head->next;
	
	int fixnum;
	if(head == NULL)
	{
		printf("链表为空，无可删除的数据");
		return ;
	}
	
	while(pr->next != NULL)		//遍历整个链表
	{
		if(pr->data == m)
		{
			printf("请输入新值：");
			scanf("%d",&fixnum);
			pr->data = fixnum;		//给pr数据域赋新的值
			
			return;					//修改完毕直接结束执行此函数 
		}
		pr = pr->next;			//没找到则一直遍历 
	}
	
	printf("未找到可以修改的值");	//出循环还没找到就是这个值不存在
	
	return; 
	 
 } 
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

单链表的查询：

void search(Link head,int x)	//传入整个链表和要查询的值
{
	Link p;
	p = head;
	if(head == NULL)
	{
		printf("链表为空，无可查询的数据");
		return ; 
	}
	
	p->data = x;
	int searchnode;
	printf("输入带查询的数：");
	scanf("%d",&searchnode);
	
	while(p->data != searchnode && p->next != NULL)	//如果不是查询的值并且指向不为空，就进入循环遍历 
	{
		p = p->next;
	}
	
	//出循环就是两种情况（和删除修改一样）
	if(p->data == searchnode)
	{
		printf("查询结果：%d",searchnode);
		return ;					//找到直接退出函数执行 
	}
	else
	{
		printf("未找到要查询的值");
	}
	
	return ; 
} 
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

链表的陈列（遍历）：

void display(Link head)
{
	Link pr = head->next;
	while(pr != NULL)			//注意陈列打印的条件 
	{
		printf("%d\t",pr->data);
		pr = pr->next; 
	}
	return ;
}
1
2
3
4
5
6
7
8
9
10

链表的元素个数：

void displaynode(Link head)
{
	Link pr = head->next;
	int count = 0;
	
	while(pr != NULL)
	{
		pr = pr->data;
		cnt++; 
	}
	printf("%d",count);
	
	return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

其他类似操作

遍历单链表（打印，修改）

便利的概念想必大家都不会陌生，即就是从链表的头开始，逐步向后进行每一个元素的访问，这就是遍历，对于遍历操作，我们可以衍生出很多常用的数据操作，比如说查询元素，修改元素，获取元素个数，打印整个链表数据等等。

进行遍历的思路极其简单，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可。

对于遍历操作，以下是代码实现：

//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}
1
2
3
4
5
6
7
8
9

对于元素修改操作，以下是代码实现：

//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12

简单的遍历设计的函数只需要void无参即可，而当我们需要进行元素修等涉及到元素操作时，我们可以设计一个LinkedList类型的函数，使其返回一个修改后的新链表。

以上的操作均用到了遍历的思维，针对于遍历还有非常多的用法供自主设计，请参考后文配套的习题进行练习。

链表插入操作

链表的增加结点操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。

如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：

从原来的链表状态
在这里插入图片描述

到新的链表状态：
在这里插入图片描述

//单链表的插入，在链表的第i个位置插入x的元素
  
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;          //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
  
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

链表删除操作

删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。
在这里插入图片描述

//单链表的删除，在链表中删除值为x的元素
  
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整实现代码

#include <stdio.h>
#include <stdlib.h>
 
//定义结点类型
typedef struct Node {
    int data;           //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;
 
//单链表的初始化
LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L==NULL){    //判断申请空间是否失败
        exit(0);    //如果失败则退出程序
    }
    L->next = NULL;          //将next设置为NULL,初始长度为0的单链表
    return L;
}
 
 
//单链表的建立1，头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
 
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}
 
 
//单链表的建立2，尾插法建立单链表
 
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
 
    return L;
}
 
 
//单链表的插入，在链表的第i个位置插入x的元素
 
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
 
    return L;
}
 
 
//单链表的删除，在链表中删除值为x的元素
 
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}
 
//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
 
 
//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
} 
 
int main() {
    //创建 
    LinkedList list;
    printf("请输入单链表的数据：以EOF结尾\n");
    list = LinkedListCreatT();
    //list=LinkedListCreatT();
    printList(list);
     
    //插入 
    int i;
    int x;
    printf("请输入插入数据的位置：");
    scanf("%d",&i);
    printf("请输入插入数据的值：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    printList(list);
     
    //修改
    printf("请输入修改的数据：");
    scanf("%d",&i);
    printf("请输入修改后的值：");
    scanf("%d",&x);
    LinkedListReplace(list,i,x);
    printList(list);
     
    //删除 
    printf("请输入要删除的元素的值：");
    scanf("%d",&x);
    LinkedListDelete(list,x);
    printList(list);
 
    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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/444133

数据结构 ： 单链表 头插入法&尾插入法 及几种常用操作_1.设计一个算法,在单链表中的第三个位置插入100,并输出。 请输入整数序列 list i