【C进阶】结构体与链表
目录
前言
这里讲述的是链表与结构体的关系，把两个联系在一起可以很好的把杂乱的数据通过链表联系在一起，这样可以更加便利去修改数据和维护数据
正文
一，回顾结构体与指针
结构的基本形式
struct student {
char name[10];
int age;
int number;
};这个是结构的基本形式（加入建立了一个变量，struct student.s1，里面的实质就是&s1=&s1.name）这个需要记住，跟数组差不多
知识点一：定义结构体指针
student *p1=&s1; p1->name="xiaoli" p1->age="11"(可以不用解引用，直接用->因为后续的操作十分方便)这里不会详细讲结构体，主要讲链表与结构体
二，结构体与链表怎么联系
struct student {
char name[10];
int age;
int number;
student* dizhi;
};我们想哈，假设第一个同学是小李，我们找完小李的资料之后就要紧接着找到他另外一个同学的资料，所以我在后面添加一个指针，这个指针的作用是指向他那个同学的，方便找到他下一个同学，如果不好理解，我们来画一个图
我们看到我们用一个指针指向这个小王，不就是可以找到下一个同学的资料了嘛，这个就是链表，将无顺序的数据通过链条的形式连接起来，这样就可以，不断的连接起来，形成链表
接下来我们用代码来实现一下
#include<stdio.h>
#include<string.h>
struct student {
char name[100];
int age;
int number;
student* dizhi;
};
int main()
{
student s1;
strcpy(s1.name, "xiaoli");
s1.age = 17;
s1.number = 20234567;
s1.dizhi = NULL;
student s2;
strcpy(s2.name, "xiaowang");
s2.age = 18;
s2.number = 21312332;
s2.dizhi = NULL;
s1.dizhi = &s2;
}这里我们创建了一个xiaowang和xiaoli这里两个同学的结构体资料，然后用链表的形式来把他们连接起来，记得s2的地址要设置为NULL要不然会出现野指针的情况，这个就是链表的创建，代码和图结合一起看会更加清楚
三，链表的头插法和尾插法
接下来我们来学习头插法与尾插法
我们再来创建一个链表来训练一下我们第二个所学习的知识
我们利用代码实现一下这个链表
#include<stdio.h>
#include<stdlib.h>
struct ListNode {
int val;
ListNode* next;
};
int main()
{
ListNode* L = (ListNode*)malloc(sizeof(ListNode));
L->val = 0; L->next = NULL; //表头
ListNode* L1 = (ListNode*)malloc(sizeof(ListNode));
L1->val = 20; L1->next = NULL;
ListNode* L2 = (ListNode*)malloc(sizeof(ListNode));
L2->val = 80; L2->next = NULL;
L1->next = L2; L->next = L1;
struct ListNode* current = L->next; // 从L1开始，因为L是表头
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
free(L);
free(L1);
free(L2);
return 0;
}我们来实现了这个链表，记得用free释放掉这个指针所指向的内存，要不然会存在内存泄漏的问题为什么要设置这个表头呢，是因为我们有了这个表头才可以找到这个链表，即使这个L1是第一个，但是后续我们用到虚拟头指针的时候，有了这个L表头
头插法：
接下来我们要实现在链表的头部插入一个数据，在头部插入一个40的数据就像下面这个图一样实现这个操作
把这个表头L的地址改为这个要插入的值的地址，然后这个插入的值的next的地址改为val为20的地址，这样就可以实现插入的功能
#include<stdio.h>
#include<stdlib.h>
struct ListNode {
int val;
ListNode* next;
};
ListNode* Insert(ListNode* L, int v) {
ListNode* insertnum = (ListNode*)malloc(sizeof(ListNode));//创建一个插入的值
if (!insertnum) return NULL; // 检查内存分配是否成功
insertnum->val = v; insertnum->next = L->next;
L->next = insertnum;
return L;
}
int main()
{
ListNode* L = (ListNode*)malloc(sizeof(ListNode));
L->val = 0; L->next = NULL; //表头
ListNode* L1 = (ListNode*)malloc(sizeof(ListNode));
L1->val = 20; L1->next = NULL;
ListNode* L2 = (ListNode*)malloc(sizeof(ListNode));
L2->val = 80; L2->next = NULL;
L1->next = L2; L->next = L1;
L = Insert(L, 40);
struct ListNode* current = L->next; // 从L1开始，因为L是表头
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
// 释放内存,确保被插入的值也被释放掉
while (L != NULL) {
ListNode* temp = L;
L = L->next;
free(temp);
}
return 0;
}这个代码是实现头插法的，我们来分开剖析里面的每一个成分：
1.Insert函数：
这里我们创建了一个insertnum的插入值，然后利用这个if语句来判断这个是否创建成功，如果没有的话则返回为空，如果创建成功，则把这个插入的值赋予个insertnum的里面的成员
里面有两个很重要的代码1.insertnum->next = L->next;这个是把L1个赋予到insertnum里面去，这样就可以使链表连接起来，
2.L->next = insertnum;然后把头指针修改一下，方便下面的操作，接下来返回L然后打印遍历打印就可以了
这个释放我稍微做了一下修改，因为在插入的时候，这个头指针是会变得，然后插入了新的成员，为了方便，后续不用自己修改，我们就用一个新的指针逐个进行释放掉，然后L进行移动就可以了
尾插法：
无非实现了一个这个操作接下来我们用代码实现一下这个操作：（我们假设插入一个100）
#include<stdio.h>
#include<stdlib.h>
struct ListNode {
int val;
ListNode* next;
};
ListNode* headInsert(ListNode* L, int v) {
ListNode* insertnum = (ListNode*)malloc(sizeof(ListNode));//创建一个插入的值
if (!insertnum) return NULL; // 检查内存分配是否成功
insertnum->val = v; insertnum->next = L->next;
L->next = insertnum;
return L;
}
ListNode* tailInsert(ListNode* L, int v) {
ListNode* insertnum = (ListNode*)malloc(sizeof(ListNode));//创建一个插入的值
if (!insertnum) return NULL; // 检查内存分配是否成功
insertnum->val = v; insertnum->next = NULL;
ListNode* cur = L; //创建一个尾节点
while (cur->next != NULL) {
cur = cur->next; //遍历找到尾节点
}
cur->next = insertnum;
return L;
}
int main()
{
ListNode* L = (ListNode*)malloc(sizeof(ListNode));
L->val = 0; L->next = NULL; //表头
ListNode* L1 = (ListNode*)malloc(sizeof(ListNode));
L1->val = 20; L1->next = NULL;
ListNode* L2 = (ListNode*)malloc(sizeof(ListNode));
L2->val = 80; L2->next = NULL;
L1->next = L2; L->next = L1;
L = headInsert(L, 40);
L = tailInsert(L, 100);
struct ListNode* current = L->next; // 从L1开始，因为L是表头
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
// 释放内存,确保被插入的值也被释放掉
while (L != NULL) {
ListNode* temp = L;
L = L->next;
free(temp);
}
return 0;
}我稍微把名字改了一下哈，这个头插入以head开头，尾插入以tail开头，我们来剖析一下这行尾插入函数
同样我们利用了if语句来进行是否创建成功，这个后面还是常规操作，赋予新的数值，然后我们就建立一个尾指针，用与指向尾巴好进行插入，然后让尾指针指向插入的即可，十分的简单
四，删除节点和插入节点（虚拟头结点实现）
删除链表特定的val的值：
我们来建立一个链表，如图所示
方法一：不用虚拟头结点（我们要删除含有20的值）这里就不展示所有代码了，展示部分重要代码提供思路
删除第一个20：
if (L->val == 20) {
listNode* temp = L;
L = L - next;
free(temp); }当头指针指向的值为20，则用一个指针指向他，然后把头指针指向下一个，然后释放这个temp，这样就保护了头指针还是在的，还没有内存泄漏
删除后面的20：
这里就不可以想删除第一个20一样了，如果直接删除的话就会是链表断裂，就是你直接删除，你上一个的节点的next就没得指向了，你链表断掉了
ListNode* cur = L;
while (cur->next != NULL) //要使cur指向前面的一个节点
{
if (cur->next->val == v) //v是为你要删除的值
{
ListNode* temp = cur->next;
cur->next = cur->next->next;//跳过那个你要删除的节点，连接后面的
free(temp);
}
else {
cur = cur->next;//向前
}
}
return L;这里用一个指针先指向那个要删除的，然后让next指向删除的后面那个，这个就可以保证链表没有断裂，然后在释放返回L即可
那么我们这样分两次写的话是十分复杂的，那么我们该怎么更加方便呢，这个时候我们就可以引进我们的虚拟头指针
这样，虚拟头指针本是不会存在的，但是有了这个我们就可以让插入头指针的时候，就可以实现这个了
这一行代码，我们就可以很水灵灵的实现了
ListNode* cur = dummyHead;
while (cur->next != NULL) //要使cur指向前面的一个节点
{
if (cur->next->val == v) //v是为你要删除的值
{
ListNode* temp = cur->next;
cur->next = cur->next->next;//跳过那个你要删除的节点，连接后面的
free(temp);
}
else {
cur = cur->next;//向前
}
return dummyHead->next;代码如下，我们加了一个虚拟头指针，返回一个虚拟头指针的next即可，然后就又可以从L遍历输出了
插入节点：
1.插入空链表：
与头插法相似
ListNode*node= (ListNode*)malloc(sizeof(ListNode));
node->vale = 8; node->next = NULL;
L = node;这个太简单了，就不讲了，自己看看
2.插入普通链表：
ListNode*dummyHead= (ListNode*)malloc(sizeof(ListNode));
ListNode* node= (ListNode*)malloc(sizeof(ListNode));
dummyHead->next = L;
ListNode* cur = dummyhead;
while (cur != NULL) {
if (cur->val == v) {
cur->next = node;
}
else { cur = cur->next; }
}这个就是把一个虚拟头指针执行那个头部，然后就是遍历找这个值进行插入
总结
我们学习了
一，回顾一点结构体与指针
二，结构体怎么与链表联系在一起
三，链表的头插法和尾插法
四，删除特定的节点和插入特定的节点（虚拟头结点实现)
这些东西，然后只写最主要的是将就是思想要知道和方法
更多推荐
35
0- 0
已为社区贡献2条内容
所有评论(0)