数据结构之二：表

顺序表代码：SData/SqList/SeqList.h · Hera_Yc/bit_C_学习 - 码云 - 开源中国

链表相关代码：SData/ListLink/main.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国

leetcode相关代码leetcode/reverse_Link/main.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国

本文主要讲解的是线性表（逻辑线性），对于非线性表不做补充。

线性表

线性表是n个具有相同类型的数据元素的有限序列。

线性表是在逻辑上是线性结构，但在物理（内存上）不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

静态顺序表：使用定长数组存储元素。
动态顺序表：动态顺序表能够增容，对空间的利用率必静态数组高。

顺序表接口实现：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//顺序表,有效数据中必须是连续存储
// 
//静态数据表(固定大小)
// 把数组简单封装一下
//
// 动态数据表
// malloc开辟内存
//typedef int SLDataType;
#define N 10
#define INC_N  Ntypedef struct SeqList
{SLDataType* arr; int size;		//有效数据的个数int capacity;	//容量
}SL,SeqList;void SeqListInit(SL* s);//尾插
void SeqListPushBack( SeqList* ps, SLDataType x);
//尾删
void SeqListPopBack( SeqList* ps);
//头插
void SeqListPushFront( SeqList* ps, SLDataType x);
//头删
void SeqListPopFront( SeqList* ps);//任意位置的插入删除
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
void SeqListErase(SeqList* ps, int pos);void SeqListPrint(const SL* ps);//查找
int SeqListFind(SL* ps, SLDataType x);//...
/*
1.二分查找
2.排序
诸多操作
*/
//我把实现粘贴在文章末尾

顺序表的特性

可动态增长数组。
数组在数组中存储时必须是连续的。

缺点：

中间或者头部的插入删除很慢，需要挪动数据。时间复杂度是O(N)。
空间不够时，增容会有一定的消耗和空间浪费。（空间碎片化）。

优点：

顺序表支持随机访问。
和链式存储结构相比，缓存命中率比较高。（物理空间连续导致的）。

链表

链式可以说是,所有数据结构的基础：树、图、队列等在使用连续开辟的内存时，需要复杂的逻辑来支撑，而链式动态开辟内存，即开即用，即删即销，保证内存空间的充足，同时不许要复杂的逻辑。

链表是一种物理上非连续、非顺序，逻辑上是连续的存储结构。链表其实就是针对顺序表的缺点来设计的，补足的就是顺序表的缺点。

结点

typedef int SListData;//结点
typedef struct SListNode
{SListData data;struct SListNode* next;
}SL;
//我们用最纯粹的结点来完成链表的实现

链表的头文件

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>/*链表一共有8种结构:这里是最纯粹的结构*/
typedef int SListDataType;//结点
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SListNode;//struct SList
//{
//	struct SList* head;
//	struct SList* tail;
//};
//一些版本采用这种形式//尾增删
void SListPushBack(SListNode** phead, SListDataType x);
void SListPopBack(SListNode** pphead);//头增删
void SListPushFront(SListNode** pphead, SListDataType x);
void SListPopFront(SListNode** pphead);//打印求值
void SListPrint(SListNode* phead);
int SListSize(SListNode* phead);SListNode* SListFind(SListNode* plist, SListDataType x);// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SListDataType x);// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
//我把实现粘贴在文章末尾

Q1：为什么插入或删除pos后的位置来?

A1：因为单链表是单向的，只能从前往后遍历结点，后面的结点不能找到之前的结点，要想删除pos结点，必须有前面的结点，这需要传入链表的首节点。

扩展：对于这种情况，我们会用双向链表来增删。

Q2：单链表的功能并不强大，为什么我们还要学习它呢？

A2：单链表的结构简单，漏洞更大。

对OJ题来说，用单链表出题更加方便。
单链表会作为更复杂的数据结构的子结构出现。如：哈希表的子结构等。

链表的分类

leetcode用编译器调试的技巧

数组和链表练习题

1、移除元素

27. 移除元素 - 力扣（LeetCode）

int removeElement(int* nums, int numsSize, int val)
{int src = 0, dst = 0;//用src替换dstwhile (src < numsSize){if (nums[src] != val){nums[dst] = nums[src];src++;dst++;}else{++src;}}return dst;
}

2、删除排序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

int removeDuplicates(int* nums, int numsSize) 
{int prev = 0;int cur = prev+1;int dst = 0;while (cur < numsSize){if (nums[prev] == nums[cur]){prev++;cur++;}else{nums[dst] = nums[prev];dst++;prev++;cur++;}}nums[dst] = nums[prev];dst++;return dst;}

3、数组形式的加法

989. 数组形式的整数加法 - 力扣（LeetCode）

//数组形式的加法
//大数的加法
int* addToArrayForm(int* num, int numSize, int k,int* returnSize)
{int KSize = 0;//求出K的位数int Num = k;while (Num){Num /= 10;KSize++;}//比较K的位数和数组的长度谁大?最终结果的位数:一定是大的那位+1(或者就是最大的那一位)//保险起见:我们用大一位开辟内存//calloc初始化一下int* retArr = (int*)calloc((KSize > numSize ? KSize + 1 : numSize + 1),sizeof(int));int tmp = 0;int cur = numSize - 1;int flag = 0;//进位//对于retArr可以倒着放,也可以正着放,然后逆置int reti = 0;int len = KSize > numSize ? KSize : numSize;while (len--){int tmpn = 0;if (cur >= 0){tmpn = num[cur];}tmp = k % 10;k = k / 10;retArr[reti] = tmp + tmpn + flag;//完成每一位的计算if (retArr[reti] >= 10){retArr[reti] = retArr[reti] - 10;flag = 1;//如果进位了}else{flag = 0;}cur--;reti++;}//观察进位符号是否为1:if (flag == 1){retArr[reti] = 1;//首位reti++;}//逆置int left = 0;int right = reti - 1;while (left < right){int tmp = retArr[left];retArr[left] = retArr[right];retArr[right] = tmp;left++;right--;}*returnSize = reti;return retArr;
}int main()
{int arr[4] = { 3,4 };int k = 1200;//1334int size = 0;int* p = NULL;p=addToArrayForm(arr, 2, k,&size);int i = 0;for (i = 0; i < 4; i++){printf("%d ", p[i]);}
}

4、反转链表

反转链表（逆置单链表），可以说是链表最关键的操作之一。(两种方法)。

206. 反转链表 - 力扣（LeetCode）

 //三指针逆方向
struct ListNode* reverseList(struct ListNode* head) 
{if(head==NULL||head->next==NULL){return head;}else{struct ListNode* cur=head;struct ListNode* prev=NULL;while(cur!=NULL){struct ListNode* tmp=cur->next;cur->next=prev;prev=cur;cur=tmp;}return prev;}
}//头插法
//头插创建新链表
//取cur头插到以newhead为头的新链表中
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead = NULL; //新链表的头结点struct ListNode* cur = head;struct ListNode* next = NULL;while (cur != NULL){next = cur->next;   //保存cur的下一个结点cur->next = newhead;  //头插:把cur看作待插入的新结点newhead = cur;cur = next;}return newhead;
}//头插更容易理解

5、删除所有给定值的结点

203. 移除链表元素 - 力扣（LeetCode）

struct ListNode* removeElements(struct ListNode* head, int val) 
{struct ListNode* prev=NULL;struct ListNode* cur=head;struct ListNode* next=NULL;while(cur){if(cur->val==val){if(cur==head){head=cur->next;free(cur);cur=head;}else{prev->next=cur->next;free(cur);cur=prev->next;}}else {prev=cur;cur=cur->next;}}return head;
}

6、链表的中间结点

链表中的双指针问题：快慢指针。

对于一个单链表来说：

快指针每次走两步。
慢指针每次走一步。
当快指针走到尾时，慢指针恰好在链表的中间。

这里对结点个数不同的链表，快指针有所差异（所指向的尾的不同）。

876. 链表的中间结点 - 力扣（LeetCode）

struct ListNode* middleNode(struct ListNode* head) {if (head->next == NULL) {return head;} else {struct ListNode* cur = head;int count = 0;while (cur != NULL) {count++;cur = cur->next;}count = count / 2;cur = head;while (count) {cur = cur->next;count--;}return cur;}
}//追加：要求只能遍历链表一次
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;
}

7、输入一个链表，输出该链表中倒数第k个结点（双指针变形）。

struct ListNode* func(struct ListNode* head, int k){struct ListNode* slow = head;struct ListNode* fast = head;while (k--&&fast){    //k有可能大于链表的长度fast = fast->next;}if (fast == NULL) return NULL;while (fast){slow = slow->next;fast = fast->next;}return slow;}

8、合并有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{// 取小节点下来尾插if (list1 == NULL && list2 == NULL)return NULL;if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode* head = NULL;struct ListNode* tail = NULL;if (list1->val < list2->val){head = tail = list1;list1 = list1->next;}else{head = tail = list2;list2 = list2->next;}//取小的尾插 while (list1 && list2){if (list1->val < list2->val){tail->next = list1;list1 = list1->next;}else {tail->next = list2;list2 = list2->next;}tail = tail->next;}if (list1 == NULL){tail->next = list2;}if (list2 == NULL){tail->next = list1;}return head;}//方法二：哨兵位
struct ListNode* mergeTwoLists2(struct ListNode* list1, struct ListNode* list2) {//带头结点的链表（哨兵位）if (list1 == NULL && list2 == NULL)return NULL;if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode* head = NULL;struct ListNode* tail = NULL;//带哨兵位的头结点，不存储有效数据，主要是方便尾插head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//取小的尾插 while (list1 && list2){if (list1->val < list2->val){tail->next = list1;list1 = list1->next;}else {tail->next = list2;list2 = list2->next;}tail = tail->next;}if (list1 == NULL){tail->next = list2;}if (list2 == NULL){tail->next = list1;}struct ListNode* realhead = head->next;free(head);head = NULL;return realhead;
}

哨兵位：head = tail = (struct ListNode*)malloc(sizeof(struct ListNode))，这里的head就是哨兵，不存储任何数据，只是在尾插时不需要对list进行判断。哨兵位对尾插来说更加方便，但在绝大多数的oj题中，链表一般是不带哨兵位的，第一个头结点存储的有数据。

9、链表分割

链表分割_牛客题霸_牛客网（双哨兵位尾插链表）

这里的maxtail不置空会产生环.

struct ListNode* partition(struct ListNode* phead, int x)
{// write code here//把pHead的结点拿出来,分两个尾插://可以尾插,亦可以头插然后反转//小于x插一次,大于x的插一次//最后整合两个链表,释放哨兵//1.空链表//if(phead==NULL)return NULL;//2.只有一个结点//if(phead->next==NULL)return phead;//1和2合并if (phead == NULL || phead->next == NULL)return phead;//3.有1个以上的结点//开辟两个哨兵struct ListNode* minhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* maxhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = phead;struct ListNode* mintail = minhead;struct ListNode* maxtail = maxhead;//初始化:防止内存错误minhead->next = NULL;maxhead->next = NULL;while (cur){/*链表在这里构成环了,导致的死循环*/if (cur->val < x){mintail->next = cur;mintail = mintail->next;}else{maxtail->next = cur;maxtail = maxtail->next;}cur = cur->next;}mintail->next = maxhead->next;maxtail->next = NULL;//防止环的生成struct ListNode* realhead = minhead->next;free(minhead);minhead = NULL;free(maxhead);maxhead = NULL;return realhead;
}

10、回文链表

链表的回文结构_牛客题霸_牛客网（回文链表=链表逆置+链表的中间结点）

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;  //新链表的头结点struct ListNode* cur = head;struct ListNode* next = NULL;while (cur != NULL) {next = cur->next;   //保存cur的下一个结点cur->next = newhead;  //头插:把cur看作待插入的新结点newhead = cur;cur = next;}return newhead;}//头插更容易理解bool chkPalindrome(ListNode* A) {// write code hereListNode* fast = A;ListNode* slow = A;ListNode* prev = NULL;while (fast && fast->next) {prev = slow;slow = slow->next;fast = fast->next->next;}//利用快慢指针找到那个中间结点prev->next = NULL;//分割前后两个链表slow = reverseList(slow);//反转后一半链表//逐一比较while (A) {if (A->val != slow->val) {return false;} else {A = A->next;slow = slow->next;}}return true;
}

11、相交链表的公共节点

160. 相交链表 - 力扣（LeetCode）

#include <math.h>struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {// 用相交结点的地址去比// 不能用结点的值去比,因为不同的结点可以存相同的值struct ListNode* curA = headA;struct ListNode* curB = headB;//这里用第二种思路:用两个链表的差值int la = 0;int lb = 0;while (curA) {la++;curA = curA->next;}//求链表A的长度while (curB) {lb++;curB = curB->next;}//求链表B的长度struct ListNode* longList = headA;struct ListNode* shortList = headB;if (lb > la) {longList = headB;shortList = headA;}int gap = abs(la - lb);//求两链表的长度差while (gap--) {        //让长的链表先走gap步longList = longList->next;}//这步操作的结果使:longList和shortList距离链表的末尾一样近while (longList) {if (longList == shortList)//比较的只能是地址,不能是值,即使两个结点值相同,也有可能不是同一个结点return longList;longList = longList->next;shortList = shortList->next;}return NULL;}

12、环形链表 i

141. 环形链表 - 力扣（LeetCode）（快慢指针）

bool hasCycle(struct ListNode *head) {struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(fast==slow){return true;}}return false;
}

13、环形链表ii

142. 环形链表 II - 力扣（LeetCode）

这里有个很难理解的方法：待补充……

14、复杂链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

struct Node* copyRandomList(struct Node* head)
{if (head == NULL)return NULL;struct Node* cur = head;//1.将拷贝结点链接在原结点的后面while (cur){//构造拷贝结点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->next = NULL;copy->random = NULL;copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}//2.处理拷贝结点的随机指针random/**这里有个较难理解的点：* 1.对于拷贝结copy点来说:它的random指针指向的必须是拷贝结点.* 2.对于原结点cur来说:它的random指针指向的是原结点* 3.cur->random:是cur随机指针指向的原结点* 4.对于任何一个原结点来说:它后面的结点就是自己的拷贝结点* 因此:* 5. copy->random = cur->random->next*/cur = head;while (cur){struct Node* copy = cur->next;if (cur->random != NULL)copy->random = cur->random->next;elsecopy->random = NULL;cur = copy->next;}//3.拆解出拷贝链表cur = head;struct Node* copyHead = head->next;while (cur){struct Node* copy = cur->next;struct Node* next = copy->next;cur->next = next;if (next != NULL)copy->next = next->next;elsecopy->next = NULL;cur = next;}return copyHead;
}
//leetcode这道题的C底层有错误，不能通过，只能用C++来实现