结构体以及链表板块

本板块有关结构体以及链表基本知识，以及刷leetcode中遇到问题总结，欢迎留言讨论，内容不断更新，
有关数组板块 请查看： 数组基础与刷题总结

基本知识

一、 结构

知识点：结构，结构成员，结构变量，结构指针，结构数组。

1、介绍为什么要用结构？

因为常见的数据类型都只包含一种类型信息，而实际问题中，我们常常需要将各种数据类型综合在一起考虑。
结构：由用户自定义的新数据类型，可以看成是一种混合数据类型

2、结构的声明

通常情况下，接受声明在所有函数之外，斌且位于main()函数之前。
语法： 关键字struct + 结构名
结构的声明不分配内存，定义结构变量的时候才分配。
如：

struct Employee
{
	// 结构中的定义的变量称为 结构成员
	// 结构成员不能是自身结构变量
	char name[20];
	float salary;
	long code;
}; // 分号一定要有

void main()
{
	Employee person;// 定义一个Employee结构变量,分配变量空间
}

3、访问结构成员

(1) 使用点（.）操作符
通过定义一个结构变量，如上图中的person,使用person即可访问结构成员：

// 访问结构成员 并赋值
person.name = 'Tom';
person.salary = 334.1;
person.id = 5555993;

(2) 使用(->)操作符
通过定义一个结构指针，通过取地址(’&’)操作得到结构变量的地址，这个地址是第一个成员的地址。

Employee pr1;
Employee * prptr;// 定义一个结构指针
prptr = &pr1; // 得到结构变量的地址

// 访问结构成员 并赋值
prptr->name = 'John';
prptrt->salary = 220.5;
prptr->id = 1234567;

4、结构数组

同样的结构体也可以声明一个数组，叫做结构数组。
需要注意的是，结构数组中的每一个元素都是结构变量。

Employee array[2] ={{'Jc',1233345,333.2}, { 'Aomb',3342268,298.9}}

二、 链表

知识点：链表定义，链表的创建于遍历，链表的插入与删除。
目前只讨论单链表。

2.1 什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

2.2 链表的删除

（a）空链表的时候 : 直接返回
（b）删除的点在链首：三步走策略
P指向链首结点 -----head指向链首下一个节点-------删除P（P是为了回收内存）
（c）删除的点非链首
找到待删除节点的前驱：pGuard, 然后三步走策略
p指向待删除的节点(p = pGuard->next)-------pGuard的next成员只想待删除节点的下一个节点 (pGuard->next = p->next)------删除p所指向的节点
找到待删节点的前一个节点pGuard并保存下来地址

解答：leetcode 203. Remove Linked List Elements（删除链表中的元素值） 详细的说明了三种情况的处理方式。

注意：很多算法题的答案都喜欢用 p->next = p->next->next的操作来实现链表节点的删除工作，但是却忽视了内存的及时释放。

2.3 链表的插入

插入操作是将值为x的新节点插入到单链表的第i个位置上。 首先检查插入位置的合法性，然后找到待插入位置的前驱结点。即第i-1个节点，然后根据改变后继节点的操作，插入新节点。可以根据下图加深理解：
注意：插入操作的①②不能互换，否则会丢失后面节点的位置信息，造成链表结构的破坏。

2.4 链表的建立

包括头插法，尾插法，暂时先不介绍。

三、 链表刷题整理

目前遇到的题型或方法：
1.双指针 / 快慢指针（必考）
解答：leetcode 21 Merge Two Sorted Lists （合并两个有序链表）
解答：leetcode141 Linked List Cycle(判断链表是否有环)
解答：leetcode876. Middle of the Linked List(寻找链表的中间元素)

2.链表去重(高频)
解答：leetcode83. Remove Duplicates from Sorted List（删除有序链表中的重复项）
解答：leetcode82. Remove Duplicates from Sorted List Ⅱ（删除有序链表中的重复数字，只保留非重复数字）
解答：leetcode 203. Remove Linked List Elements（删除链表中的元素值）

3.技巧题（骚操作，迭代，递归）
解答：leetcode160. Intersection of Two Linked Lists(寻找两个链表的交叉点)
解答：leetcode 206. Reverse Linked List (翻转一个链表)
解答leetcode 234. Palindrome Linked List （判断链表是否回文）
解答：leetcode 237. Delete Node in a Linked List（删除链表中的特定节点）

（继续更新）

最后

以上就是聪慧棒棒糖为你收集整理的结构体以及链表总结结构体以及链表板块的全部内容，希望文章能够帮你解决结构体以及链表总结结构体以及链表板块所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。