《算法笔记》总结No.10——链表
从第10期破例插叙一期单链表的实现，这个东东相当重要！考研的同学也可以看：相较于王道考研的伪码不太相同，专注于可以运行。如果是笔试中的伪码，意思正确即可~
注：博主之前写过一个版本的顺序表和单链表的C++实现，和这篇的写法有所不同，不过内容也较全，大家可以先行阅读~C++数据结构笔记（2）线性表的顺序存储和链式存储_c++线性表的顺序存储和链式存储-CSDN博客文章浏览阅读348次。1.线性表是0个或者多个数据元素的有限序列，其中数据元素类型相同2.线性表可以逐项访问和顺序存储3.有顺序存储和链式存储两种存储方式。接下来，_c++线性表的顺序存储和链式存储
https://jslhyh32.blog.csdn.net/article/details/131440870
一.理论精炼
线性表没什么可说的，比较简单，大家姑且把他理解为数组即可。相较于顺序表的物理结构上也连续存取，链表在内存中的存储位置是离散的。在实现的过程中，多数参考资料愿意以带头节点的链表为例，如下图：
二.分配内存空间
先来看一下链表节点的定义方式：
struct LNode{
int data;
LNode* next;
}; 初学者接触的时候有人会蒙圈——因为这相当于是嵌套定义，即类型里面又直接定义了一个指向自己类型的指针。但这恰恰是链表的“几何意义”：顺序表的定义就很符合人类的思维惯式，对吧，一个表，或者说是一个有顺序的集合一样，物理上就应该是连续的一堆东西连在一起——计算机的内存中实际上也是这么存放的，因此在定义的时候直接定义成和数组“长得一样”的类型。
不过链表就不一样了，和他本身的逻辑意义一致——即各节点之间通过指针串起来，彼此之间是不连续的。因此在声明一个链表的时候，其实是声明了一个头结点——这样后面的元素根据指针就可以存在了！即声明的时候先声明一个，然后再根据指针域的值继续赋值。
1.malloc函数
malloc是用于申请分配动态内存的函数，这篇博客已经介绍过，这里不再赘述：
LNode* head;
head=(LNode*)malloc(5*sizeof(LNode));逻辑非常清晰明了，malloc返回的是地址，因此需要将这部分地址赋予一个指针~
2.new运算符
C++中，可以这样写：
LNode* p=new LNode;没什么难度，这里主要想讲C，就不展开细说了。
3.内存泄漏
C语言的设计者认为，程序员完全右能力自己控制内存的分配与释放，因此把对内存的控制、操作都分配给了程序员。使用完malloc等之后，一定要使用free将其释放：
free(head);三.创建链表
先来直观的感受一下如何创建链表：
LNode* node1=(LNode*)malloc(sizeof(LNode));
LNode* node2=(LNode*)malloc(sizeof(LNode));
LNode* node3=(LNode*)malloc(sizeof(LNode));
node1->data=1;
node1->next=node2;
node2->data=2;
node2->next=node3;
node3->data=3;
node3->next=NULL;显然这样太死板了，没有人机交互，那么不妨我们改善一下，main函数中可以输入链表的长度，如下：
int main(int argc, char *argv[]) {
printf("请输入链表的长度：");
int num=0;
scanf("%d",&num);
LNode* List=createLinkList(num); //根据长度创建链表
List=List->next; //第一个是头结点，因此从第二个开始才能遍历到数据
while(List!=NULL)
{
printf("%d ",List->data);
List=List->next;
}
return 0;
}然后我们来编写createLinkList函数：
LNode* createLinkList(int x)
{
LNode* head;// 声明头结点
LNode* tNode;//当前结点
LNode* pre;//当前结点的前驱节点
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;//初始化指针域为0
pre=head;
int i=1;
for(;i<=x;i++)
{
tNode=(LNode*)malloc(sizeof(LNode));//创建一个新节点
int temp=0;
temp=i;
tNode->data=temp;
tNode->next=NULL;
pre->next=tNode;
pre=tNode;
}
return head;
}（加前驱是为了方便链表的创建，也可以不这样做~）
如上图，没什么bug~
为了让大家直观感受一下所谓的【离散】，我们把链表中的节点地址也打印一下，修改main函数如下：
int main(int argc, char *argv[]) {
printf("请输入链表的长度：");
int num=0;
scanf("%d",&num);
LNode* List=createLinkList(num); //根据长度创建链表
LNode* other=List; //另外单独存放一个头结点
printf("地址依次如下：\n");
while(other!=NULL)
{
printf("%d ",&other);
other=other->next;
}
printf("\n");
printf("数值依次如下：\n");
List=List->next; //第一个是头结点，因此从第二个开始才能遍历到数据
while(List!=NULL)
{
printf("%d ",List->data);
List=List->next;
}
return 0;
}如下图：头结点和其他5个节点之间均不是连续的！
另外，每次执行的地址也不尽相同。相信这样直观感受一下，各位就能理解到链表的物理意义了~
四.查找元素
查找就非常简单了，这里我们直接写一个统计某元素个数的函数，如下：
int SearchByValue(LNode* target,int x)
{
int count=0;
LNode* temp=target->next;
while(temp!=NULL)
{
if(temp->data==x)
count++;
temp=temp->next;
}
return count;
}main函数调用：
继续写别的~
五.插入元素
这个有点意思，因为需要交换两个指针，具体的逻辑这里不多说了，太基础了，这里放个图让大家看看，千万别被逻辑绕晕~
代码如下：
void InsertByPos(LNode* L,int pos,int x)
{
LNode* temp=L;//将头结点的值赋给临时的节点
int i=1;
for(;i<=pos-1;i++) //找到待插入位置的前一个指针
temp=temp->next;
LNode* tNode;
tNode=(LNode*)malloc(sizeof(LNode)); //创建一个新节点
tNode->next=temp->next;
temp->next=tNode;
tNode->data=x;
}main函数测试：
//3.测试 InsertByPos
InsertByPos(List,4,32);
List=List->next;
while(List!=NULL)
{
printf("%d %d\n",List->data,&List->next);
List=List->next;
} 结果如下：
堪称完美~
六.删除元素
1.按值删除
简单，直接按照上面按值查询的代码写就好，只需要改变if条件的逻辑即可：
void DeleteByValue(LNode* L,int x)
{
LNode* temp=L->next;//忽略头结点的第一个
LNode* pre=L;//pre始终用来保存
while(temp!=NULL)
{
if(temp->data==x)
pre->next=temp->next;
pre=temp;
temp=temp->next;
}
}main函数：
//4.测试DeleteByValue
DeleteByValue(List,4);
List=List->next; //第一个是头结点，因此从第二个开始才能遍历到数据
while(List!=NULL)
{
printf("%d %d\n",List->data,&List->next);
List=List->next;
} 测试结果：
4成功被删掉~
2.按位删除
根据插入元素的代码即可修改成功。题外话，其实这里还可以写一个按位查找，大家自己试试~
void DeleteByPos(LNode* L,int pos)
{
LNode* temp=L->next;
LNode* pre=L;
int i=1;
for(;i<=pos-1;i++) //找到待插入位置的前一个指针
{
pre=temp;
temp=temp->next;
}
pre->next=temp->next;
} 老套路：
DeleteByPos(List,4);
List=List->next; //第一个是头结点，因此从第二个开始才能遍历到数据
while(List!=NULL)
{
printf("%d %d\n",List->data,&List->next);
List=List->next;
}
free(List);
return 0;还是删除掉了第4位的元素~
主打一个过五关斩六将~
七.静态链表
静态链表感觉没什么意思，感觉还不如直接用顺序表，大家自己看看就行，比较简单：
写在最后：无论408还是众多985名校的自命题，线性表都是算法题、大题考察的热门，大家一定要熟练掌握代码规范。至于二叉树乃至图论的具体编程实现，怎么说，要是你不是奔着140+去考，其实是可以允许自己不会的，参照二八定律——应该尽可能地从简易的20%里面获取占大头的80%分数。因此这期结束后也不优先更新各种数据结构的实现了，优先更新一些数学的问题，接着就是DFS、BFS、DP这些蓝桥杯等竞赛偏爱的内容。（说句题外话，蓝桥杯之所以被戏称圈钱杯、DP杯，就是因为近年来的考试题目逐渐以暴力和DP为主，在一个不是很发达的省份比如我们这里，即便是A组，如果你的DP异常熟练，拿个省一进国赛是没什么难度的。除了蓝桥杯还有CSP，如果代码基础非常扎实，会处理复杂的字符串，还能熟练掌握DP，考个300+似乎也不是很有难度。。由此可见DP的重要性！）
完整的.c文件源码，有需要的自提：
链接：https://pan.baidu.com/s/1uN0elyL2N25vNhF2bSewoA
提取码：hma8
原文地址：https://blog.csdn.net/jsl123x/article/details/140586417
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！