目录
学习并理解单链表,最好先去熟练掌握下C语言的指针,再跟着书本或视频进行练习。本篇文章所有代码都可以运行,读者可以自行调试。数据结构是抽象的,所以最好是看图解教程,才能更清楚的掌握数据结构。当基础知识掌握后,应进行大量练习,去刷题网站练习相关题目。
一、单链表的建立
1、头插法
#include<stdio.h>
#include<stdlib.h> //malloc需要
typedef struct List{
int data;
struct List* next;
}LinkList;
int main() {
printf("输入要建立的链表,输入-1停止:\n");
LinkList* head, *node;
int x;
scanf("%d", &x);
head = (LinkList*)malloc(sizeof(LinkList));
head->next = NULL;
while (x != -1) {
node = (LinkList*)malloc(sizeof(LinkList));
node->data = x;
node->next = head->next;
head->next = node;
scanf("%d", &x);
}
printf("头插法建立链表后从头往后输出:\n");
LinkList* p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
return 0;
}
输出结果:
让我们来从上到下看一下上述代码的执行效果:
1、LinkList* head, *node;
2、head = (LinkList*)malloc(sizeof(LinkList)); head->next = NULL; //新建一个结点作为头结点,让头指针指向它
3、node = (LinkList*)malloc(sizeof(LinkList)); //为要插入的结点开辟空间
4、node->next = head->next;
5、 head->next = node;
6、整理一下(注意这里head->next指向的是整个node结点而非指向node的next域):
7、执行第二次循环,node = (LinkList*)malloc(sizeof(LinkList));
8、node->next = head->next;
9、 head->next = node;
10、然后进入下一次循环······
2、尾插法
#include<stdio.h>
#include<stdlib.h>
typedef struct List{
int data;
struct List* next;
}LinkList;
int main() {
printf("输入要建立的链表,输入-1停止:\n");
LinkList* head, *rear, *node;
int x;
head = (LinkList*)malloc(sizeof(LinkList));
head->next = NULL;
rear = head;
scanf("%d", &x);
while (x != -1) {
node = (LinkList*)malloc(sizeof(LinkList));
node->data = x;
rear->next = node;
rear = node;
scanf("%d", &x);
}
rear->next = NULL;
printf("尾插法建立链表后从头往后输出:\n");
LinkList* p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
return 0;
}
输出结果:
二、插入结点操作
#include<stdio.h>
#include<stdlib.h>
typedef struct List{
int data;
struct List* next;
}LinkList;
int main() {
printf("输入要建立的链表,输入-1停止:\n");
LinkList* head, *rear, *node;
int x;
head = (LinkList*)malloc(sizeof(LinkList));
head->next = NULL;
rear = head;
scanf("%d", &x);
while (x != -1) {
node = (LinkList*)malloc(sizeof(LinkList));
node->data = x;
rear->next = node;
rear = node;
scanf("%d", &x);
}
rear->next = NULL;
printf("尾插法建立链表后从头往后输出:\n");
LinkList* p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
puts("");
/*以下是插入操作*/
printf("请输入要在第几个结点后面插入:\n");
int target;
scanf("%d", &target);
printf("请输入要插入的数:\n");
int num;
scanf("%d", &num);
LinkList* q = head->next;
int i = 1;
while (q != NULL && i < target) {
q = q->next;
++i;
}
node = (LinkList*)malloc(sizeof(LinkList));
node->data = num;
node->next = q->next;
q->next = node;
printf("插入完成后运行结果:\n");
LinkList* pp = head->next;
while (pp != NULL) {
printf("%d ", pp->data);
pp = pp->next;
}
return 0;
}
输出结果
三、删除节点操作
删除节点要注意,是查找到第 i-1 个结点再开始操作。
#include<stdio.h>
#include<stdlib.h>
typedef struct List{
int data;
struct List* next;
}LinkList;
int main() {
printf("输入要建立的链表,输入-1停止:\n");
LinkList* head, *rear, *node;
int x;
head = (LinkList*)malloc(sizeof(LinkList));
head->next = NULL;
rear = head;
scanf("%d", &x);
while (x != -1) {
node = (LinkList*)malloc(sizeof(LinkList));
node->data = x;
rear->next = node;
rear = node;
scanf("%d", &x);
}
rear->next = NULL;
printf("尾插法建立链表后从头往后输出:\n");
LinkList* p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
puts("");
/*以下是插入操作*/
printf("请输入要删除第几个结点:\n");
int target;
scanf("%d", &target);
LinkList* q = head->next;
int i = 1;
while (q != NULL && i < target - 1) { //找到第target-1个结点即可
q = q->next;
++i;
}
LinkList* temp = q->next;
q->next = temp->next;
free(temp);
printf("删除完成后运行结果:\n");
LinkList* pp = head->next;
while (pp != NULL) {
printf("%d ", pp->data);
pp = pp->next;
}
return 0;
}
输出结果:
四、单链表操作的一些常见问题
1、结构体变量和结构体指针的区别?
有时候我们会看到如下情况:
typedef struct List{
int data;
struct List* next;
}LNode, *LinkList;
一些初学者会对LNode和*LinkList 表示疑惑,为什么要定义一个结构体变量,一个结构体指针呢?
首先说明下它们的区别:结构体变量定义完后,会自动在内存中开辟一段空间;而结构体指针定义完后,并不会开辟新的空间。要使用结构体指针,你得手动去开辟空间(比如malloc),然后让结构体指针指向它才行,或者让结构体指针指向其它已经开辟的空间的地址才行。此外,它们的访问结构体成员方式也不同,结构体变量访问用“.”,而结构体指针用“->”,或者 (*p).xx (其中p是结构体指针,xx是结构体中的一个成员)。
举个例子,比如在头插尾插建立链表中,建立头结点,原来是用结构体指针表示:
LinkList* head;
head = (LinkList*)malloc(sizeof(LinkList));
我们可以改成用结构体变量表示头结点,因为结构体变量声明后,会自动在内存中开辟空间,这样我们后面就不用手动去malloc了:
LinkList head;
//head = (LinkList*)malloc(sizeof(LinkList)); 不需要了
2、什么时候要malloc?
需要新建一个结点时。
3、形参里面出现了取地址符(&),有什么作用?
形参里面出现“&”,比如 int func(int &a, int &b); 这是C++的语法,不是C的,因此这里不展开。