本笔记参考王道数据结构考研复习指导2023版，对上面的知识点进行提炼，以及代码和习题的进一步解释，同时还添加了leetcode的一些例题帮助理解。
第一章 绪论 1.1 数据结构的基本概念 什么是数据？ 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并背计算机程序所识别和处理的符号的合集。世界上第一台通用计算机 ENIAC – 数值型问题现代计算机 – 经常处理非数值型问题数据元素、数据项：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由阮淦数据项组成，数据项是构成数据元素的不可分割的最小单位。数据对象是具有相同性质的数据元素的集合，是数据的一个子集。例如：一个微博账号的基本内容为一个数据元素，其中用户名、密码、生日等是一个个数据项，所有微博账号是一个数据对象。
第一节总结： 
数据的运算 – 针对某种逻辑结构，结合实际需求，定义基本运算 例如对于线性结构，基本运算可以有如下：
查找第i个数据元素在第i个位置插入新元素删除第i个位置的元素 等等物理结构（存储结构）-- 如何用计算机表示这些逻辑结构 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里。 优点：可以实现随机存取，每个元素占用最少的存储空间 缺点：每个元素只能使用相邻一整块的存储单元，可能会产生较多的外部碎片链式存储：逻辑上相邻的元素在物理位置上可以不相邻（通过指针） 优点：不会出现碎片现象，充分利用存储单元 缺点：每个元素的指针会占用额外的存储空间，而且只能实现顺序存取索引存储：在存储信息的同时，还建立附加的索引表 优点：检索速度快所以表额外占用空间，在删除修改数据之后索引表的更新也会浪费时间 缺点：索引表额外占用空间，在删除修改数据之后索引表的更新也会浪费时间散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储 优点：检索、增加和删除结点的操作都很快 缺点：若散列函数不好，可能出现元素冲突增加时间和空间的开销
若采用顺序存储，则各个数据元素在物理上必须是连续的 数据的存储结构会影响存储空间分配的方便程度 数据的存储结构会影响对数据运算的速度
运算的定义是针对对逻辑结构设计的，指出运算的功能；运算的实现是针对存储结构设计的
数据类型、抽象数据类型： 数据类型是一个值的集合和定义在此集合上的一组操作的总称
原子类型：其值不可再分的数据类型结构类型：其值可以再分为若干成分的数据类型抽象数据类型（ADT）是抽象数据组织以及与之相关的操作
1.3 算法的基本概念 程序=数据结构+算法
算法是对特定问题求解步骤的一种描述，他是指令的有限序列，其中的每条指令表示一个或多个操作
算法的特性：
有穷性：一个算法必须总在执行有穷步骤之后结束，且每一步都在有穷时间内完成确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。例如对所有人年龄升序排序，第二行和第三行结果不同，所以这个算法有问题
“好”算法的特质
正确性，算法应能正确的解决求解问题可读性：算法应具有良好的可读性，以帮助人理解健壮性：输入非法数据时，算法能适当的做出反应或进行处理高效率与低存储量需求：花的时间少（时间复杂度低），占用存储少（空间复杂度低）
1.1-1.3 习题： 
算法时间复杂度的概念：事先预估算法时间开销T(n)和问题规模n的关系 一个算法的时间复杂度可以只考虑阶数高的部分，用O表示 
时间复杂度排序：常对幂指阶 
小练习： 
在学习中，一般只考虑最坏时间复杂度和平均时间复杂度
算法的空间复杂度是指执行这个算法所需的存储空间的量度。它是计算算法在执行过程中大约需要多少内存空间的一个标准。在算法分析中，我们常常同时考虑时间复杂度和空间复杂度，两者共同决定了算法的效率
空间复杂度的概念
总体空间需求：算法执行过程中总共需要的存储空间。它包括固定部分（如代码空间、简单变量和固定大小的结构变量等）与变化部分（如动态分配的空间、递归栈空间等）的总和辅助空间需求：除了输入数据所占的空间外，算法运行过程中额外需要的存储空间空间复杂度的计算
固定部分：通常包括算法中的变量（包括常量、简单变量和固定大小的结构类型变量等）变化部分：主要包括动态分配的空间大小和递归栈的使用空间。例如，一个递归算法的空间复杂度通常与递归深度成正比常见的空间复杂度
O(1)：如果算法所需要的临时空间不随着某个变量n的大小而变化，即空间复杂度是一个常量，这个算法的空间复杂度就是O(1)O(n)：对于一些算法，需要的临时空间是随着某个变量n的大小而线性增长的，那么这类算法的空间复杂度是O(n)示例 以递归算法为例：如果有一个递归函数，每次递归都需要一个新的变量空间，而且递归深度为n，那么该算法的空间复杂度是O(n)。因为在递归的最深处，会有n个变量同时存在。
第二章 线性表 2.1 线性表的定义线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。线性表L的一般表示为： L=（a1，a2，… ，an）
ai是线性表中第i个元素，是一个位序a1是表头元素，an是表尾元素除表头元素外，每个元素有且仅有一个直接前驱；除表尾元素外，每个元素仅有一个直接后继位序从1开始，但数组下标从0开始
线性表的基本操作
初始化表 – InitList(&L) ：构造一个空的线性表L，分配内存空间销毁表 – DestoryList(&L): 销毁线性表，并释放线性表L所占用的内存空间插入元素 --ListInsert(&L,i,e): 在表中的第i个位置插入元素e删除元素 – ListDelete(&L,i,&e): 删除表L的第i个元素，并用e返回删除元素的值按值查找 – LocateElem(L,e): 在表中查找具有给定关键字值的元素按位查找 – GetElem(L,i): 在表中查找第i个位置的元素求表长 – Length(L): 返回线性表的长度判断表空 – Empty(L): 若表为空，则返回true，否则返回false…（可自行定义）在C++中，使用&符号作为函数参数，意味着参数是通过引用传递的。这允许函数直接修改外部变量的值，而不仅仅是它的副本。这样做可以提高效率，因为不需要复制数据，也允许函数改变实际传入的变量。简单来说，使用 & 可以让函数直接操作原始变量，而不是它的拷贝
2.2 顺序表顺序表的定义 顺序表：是指用顺序存储的方式实现线性表顺序存储 
静态实现顺序表
头插法建立单链表时，读入数据的顺序和生成链表的数据是相反的，时间复杂度为O(n)
尾插法建立单链表
尾插法的思想是增加一个尾指针r，使其始终指向建立链表的尾结点，这样就能将新插入的节点每次都插入到链表的末尾 LinkList List_TailInsert(LinkList &L){int x;// 设置元素类型为整形L=(LinkList)malloc(sizeof(LNode)); // 创建头结点LNode *s,*r = L; // 创建新结点和尾指针scanf("%d",&x); // 输入新结点元素的值while(x!9999){s = (LNode *)malloc(sizeof(LNode)); //创建新节点s->data =x; // 新结点赋值r->next=s; // 尾指针指向新结点r=s; // 更新尾指针为最后一个节点scanf("%d",&x); // 输入下一个结点的元素值}r->next = NULL; // 尾指针指向空return L;} 按序号查找结点值 对于一个单链表，从第一个结点出发，顺着指针的next域逐个往下查，查到第i个结点为止，如果没查到，则返回NULL LNode *GetElem(LinkList L,int i){ // LNode* 表示返回我们找到的结点的指针int j=1;LNode *p = L->next; //L是头结点，L->next是存储信息的第一个结点if(i==0)return 0;if(idata != e && p){ // p不为空且p所指的值不为e时进入循环p=p->next;return p;} 按值查找操作的时间复杂度为O(n)
插入节点操作 插入节点是将一个新结点s插入到单链表L第i个位置上，解决办法为：先利用GetElem函数查找第i-1位置上的结点记为*p，然后将新结点s插入到p的后面，再将x的next域指向原本p的next指向的结点。
void ListInsert(&L,i,x){ // x为要插入的节点if(iL.length+1)return;LNode *p = GetElem(L,i-1);s->next = p->next;p->next = s;} GetElem的时间复杂度为O(n)，插入时间复杂度为O(1)
前插操作： 上面的例子是在节点后进行插入，如果想在第i个结点前插入，两种办法
GetElem操作查找第i-1个结点，而不是第i个结点，再进行后插操作可以正常的先进性后插操作，再将p->data和s->data相交换，这样也相当于在前面插入了删除结点操作 删除单链表的第i个结点，如果删除位置合法，删除后应把后面的结点接到前面的结点上
void DeleteElem(&L,i,q){LNode *p = GetElem(L,i-1); // p指向被删除节点的前驱节点LNode *q = p->next; // q指向要删除的结点p->next = q->next; // 这步是把被删除结点的前驱结点和后继结点连接起来free(p); // 释放要被删除的节点} 求表长的操作 求表长就是将链表从头到尾走下去，直到结点为NULL为止，统计结点的个数 int LinkListLength(L){LNode *p = L->next;int j = 0;while(p!=NULL)j++;return j;} 2.3.2 双链表 双链表就是在单链表的基础上增加头指针，这样每个结点既有next指针指向后继结点，又有prior指针指向前驱结点。 
双链表的结点类型描述：
相比于单链表，双链表可以向前查找任何前驱结点，而单链表只能再从头查找才能访问某个元素的前驱结点了
双链表操作举例：
插入操作 和单链表不同，双链表插入既要考虑next指针的连接，也要考虑prior指针的连接
void ListInsert(&L,i,x){ // x为要插入的节点if(iL.length+1)return;LNode *p = GetElem(L,i-1);s->next = p->next; //确定s的后继p->next = s; // 确定p的后继s->prior = p; // 确定s的前驱s->next->piror = s; // 确定s的后继的前驱} 删除操作 
void DeleteElem(&L,i,q){LNode *p = GetElem(L,i-1); // p指向被删除节点的前驱节点p->next = q->next; //p的后继指向被删除的结点的后继，对应 ①q->next->prior = p; //q的后继的前驱指向p，对应 ②free(p); // 释放要被删除的节点} 2.3.3 循环单链表 循环单链表是在单链表的基础上将最后一个结点指向的结点由NULL改为头结点，形成一个环。其中指针 r 始终指向表尾，r->next 始终指向表头 
相比于单链表，循环链表对表头和表尾元素进行操作都只需要O(1)的时间复杂度。判断循环单链表是否为空是看头指针L和 r->next 是否相等
循环双链表就是双链表和循环链表的结合，当循环双链表为空时，其头结点的prior和next都为L 
静态链表时借助数组实现线性表的存储结构，也分数据域和指针域，不过静态链表的指针是相对地址，也就是数组下标 
结构类型描述：
静态链表以第一个数组元素作为头结点，以next==-1作为结束的标志。
2.4 顺序表和链表的比较顺序表：
存取时间复杂度为 O(1)，因为顺序表是数组结构，可以通过索引直接访问元素插入和删除操作的时间复杂度较高，平均为 O(n)，因为需要移动元素以维持元素的连续性空间上更紧凑，因为元素紧密排列，不会有额外的空间开销可以快速的访问任意数据，但是扩展大小不方便，当数组满了需要进行扩容，这个过程时间复杂度为 O(n)链表：
存取时间复杂度为 O(n)，因为需要从头节点开始遍历直到找到需要的元素插入和删除操作的时间复杂度较低，平均为 O(1)，因为只需要改变指针的指向即可，不需要移动其他元素需要额外的空间来存储指针，因此相对顺序表来说空间使用率低扩展大小非常方便，只需要改变指针的指向即可完成节点的插入和删除，不需要移动其他元素 2.3习题
解答：
题干模板：
思路： 题目要求将链表中的奇数位置节点和偶数位置节点分开，然后首先连接所有奇数节点，其后连接所有偶数节点。例如，链表 1->2->3->4->5 应该被重新排列为 1->3->5->2->4
这个问题的关键是在一次遍历中改变节点的连接。为此，我们可以使用两个指针，一个指向当前的奇数节点，另一个指向当前的偶数节点。同时，我们需要记住偶数节点链的头部，这样在奇数节点链表遍历完成后，我们可以将两个链表连接起来
下面是题解的步骤解析：
首先检查 head 是否为空。如果为空，则直接返回 NULL初始化两个指针 ji 和 ou。ji 指向链表的第一个节点（即头节点 head），ou 指向链表的第二个节点（即 head->next）。同时，保存偶数链的头部到 ouhead 指针，以便后续连接使用 while 循环，条件是 ji->next 和 ou->next 都不为 NULL。在循环内部，我们将 ji->next 指向 ou->next，即跳过一个偶数位置节点到下一个奇数位置节点。然后 ji 指针移动到这个新的奇数位置节点上接下来，我们需要处理 ou 指针。同样，我们将 ou->next 指向 ji->next，即跳过一个奇数位置节点到下一个偶数位置节点。然后 ou 指针移动到这个新的偶数位置节点上当 while 循环完成时，所有的奇数位置节点已经连接在一起，所有的偶数位置节点也连接在一起。此时，ji->next 应该指向 ouhead，也就是偶数链的头部，这样就连接了两个链表最后，返回修改后的链表头节点 head答案：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* oddEvenList(struct ListNode* head) {if(head==NULL)return NULL;struct ListNode *ji = head;struct ListNode *ou = head->next;struct LinkNode *ouhead = ou;while(ji->next!=NULL && ou->next!=NULL){ji->next = ou->next;ji=ji->next;ou->next = ji->next;ou=ou->next;}ji->next = ouhead;return head;}
题目模板：
思路 刚开始看这道题是懵的，要求删除一个结点，不知道头结点。想了半天，哦，原来是前面学到的，删除一个结点，可以把后继结点的值赋给自己，然后删除 后继结点就行了。
答案
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */void deleteNode(struct ListNode* node) {node->val = node->next->val;node->next = node->next->next;}
思路： 我在自己尝试做的时候，大概能知道要去几个指针来指向当前元素，前驱元素和后继元素来实现反转，但自己弄了半天也没想出来，后来看了题解就觉得自己的脑子就总差一点弯转不过来，然后做不出来。。。
首先，要实现链表逆转，原本的表头变成表尾，所以要指向NULL；之后每次处理到第i个结点的时候，将curr指向当前结点，prev指向前驱，next指向后继，将curr的next指向prev就实现了翻转；然后更新prev和curr向后移动一个结点，也就是curr指向next，prev指向curr，然后重复同样的操作直到curr为空 
官方答案：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head) {struct ListNode * prev = NULL;struct ListNode * curr = head;while(curr){struct ListNode * next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}
解析： 逻辑上分为几个主要步骤，下面是每个步骤的简要说明： 计算链表长度：首先，通过遍历链表计算出链表的总长度 j 定位中点：根据链表的长度，将指针 a 移动到链表的中间位置。如果链表长度为偶数，则 a 位于中间两个节点的后一个 反转后半部分链表：从中点开始，反转链表的后半部分。这里用到了三个指针：curr（当前节点）、prior（前一个节点）、next（下一个节点），以实现链表的反转 连接链表：将前半部分的最后一个节点（c 指向的节点）指向反转后的后半部分的起始节点（curr）。这一步在代码中似乎是为了重构原链表，但实际上这样做会破坏原链表的结构，对于回文判断不是必须的 回文判断：最后，同时遍历原链表的前半部分和反转后的后半部分，比较对应节点的值。如果所有对应节点的值都相同，则链表是回文的，返回 true；否则，返回 false