数据结构：线性结构之顺序表、链表篇

线性表

线性表：线性表是具有逻辑结构是连续，物理结构不一定是连续的一类数据结构的集合。链表和顺序表都是线性表

顺序表 ： 物理结构连续，逻辑结构连续

链表 ： 物理结构不一定连续（动态内存申请的空间可能是连续的，但是一般不会）， 逻辑结构连续

一、顺序表

用物理地址连续的存储单元依次储存数据结构的线性结构，一般采用数组实现。顺序表分为动态顺序表和静态顺序表，为了防止空间过度浪费，空间不足，我们一般采用动态顺序表。

（一）顺序表的结构定义

typedef int SLdataType;typedef struct SeqList {SLdataType* data;int count, size;
}SeqList;

用到typedef, 可以使得我们的顺序表存放数据的类型更加的灵活。

（二）顺序表的功能实现

1、初始化

void initSeqList(SeqList* SL) {SL->data = NULL;SL->count = SL->size = 0;return;
}

2、销毁

void clearSeqList(SeqList* SL) {if (SL == NULL) return;if (SL->data) free(SL->data);SL->data = NULL;SL->count = SL->size = 0;return;
}

3、扩容

采用 realloc 进行扩容，考虑到原来的容量为 0， 不可单纯的进行乘二

void SLCheckCapacity(SeqList* SL) {if (SL->count == SL->size) {int n = SL->count == 0 ? 4 : 2 * SL->size;SLdataType* temp = (SLdataType*)realloc(SL->data, sizeof(SLdataType) * n);if (temp == NULL) {perror("realloc fail\n");exit(1);}SL->data = temp;SL->size *= n;}return;
}

4、插入

插入操作分为头插、尾插，和任意位置插入。
插入操作需要整体后移 ： 从后面像前面遍历，反之会产生数据的覆盖。

//头插
void insertPushFront(SeqList* SL, SLdataType x) {SLCheckCapacity(SL);for (int i = SL->count - 1; i >= 0 ; i--) {SL->data[i + 1] = SL->data[i];}SL->data[0] = x;SL->count += 1;return;
}//尾插
void insertPushBack(SeqList* SL, SLdataType x) {SLCheckCapacity(SL);SL->data[SL->count++] = x;return; 
}//任意位置插入
void insert(SeqList* SL, SLdataType x, int pos) {if (pos < 0 && pos > SL->count) return;SLCheckCapacity(SL);for (int i = SL->count - 1; i >= pos; i--) {SL->data[i + 1] = SL->data[i];}SL->data[pos] = x;SL->count += 1;return;
}

5、删除

删除操作分为头删、尾删，和任意位置删除。
删除操作需要整体前移 ： 从前面向后面遍历，反之会产生数据的覆盖。

//头删
void erasePopFront(SeqList* SL) {for (int i = 1; i < SL->count; i++) {SL->data[i - 1] = SL->data[i];}SL->count -= 1;return;
}//尾删
void erasePopBack(SeqList* SL) {assert(SL);assert(SL->count);SL->count -= 1;return;
}//任意位置删除
void erase(SeqList* SL, int pos) {if (pos < 0 && pos >= SL->count) return;for (int i = pos; i < SL->count - 1; i++) {SL->data[i] = SL->data[i + 1];}SL->count -= 1;return;
}

（三）顺序表例题分析

1、删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;while(src < nums.size()){if(nums[src] == nums[dst]){src += 1;}else{nums[++dst] = nums[src++];}}return dst + 1;}
};

题目中我们用到双指针指针删除重复项，其中while 循环的条件设计十分巧妙

2、合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/

小结 ： 采用两个指针分别指向两个数组的末尾，依次将数据放在数组一。
while 循环可以用 && 也可以用 || 采用两种代码实现

采用 || 的方式实现

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;while (l1 >= 0 || l2 >= 0) {if (l2 < 0 || (l1 >= 0 && nums1[l1] > nums2[l2]))nums1[l3--] = nums1[l1--];elsenums1[l3--] = nums2[l2--];}}
};

或者采用 && 的方式实现

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;while (l1 >= 0 && l2 >= 0) {if (nums1[l1] > nums2[l2])nums1[l3--] = nums1[l1--];elsenums1[l3--] = nums2[l2--];}while (l2 >= 0) {nums1[l3--] = nums2[l2--];}}
};

(四）顺序表的弊端

1、顺序表的插入删除操作的时间复杂度为O（n）
2、顺序表扩容后任然可能造成空间的浪费，并且顺序表扩容带来性能消耗

二、链表

（一）链表的结构定义

这里也用的typedef 可以使得我们的数据类型更加灵活。

typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;

（二）链表的功能实现

1、链表的初始化

同顺序表相同，链表在初始化时也采取泛型的方式，适应多种数据类型。

SLTNode* BuyNode(SLTDataType x) {SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode));p->data = x;p->next = NULL;return p;
}

2、链表的插入

链表的插入分为头插、尾插和任意位置插入。任意位置插入时采用双指针定向移动。

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {SLTNode* node = BuyNode(x);if (*pphead == NULL) {*pphead = node;return;}SLTNode* p = *pphead;while (p->next) p = p->next;p->next = node;return;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* node = BuyNode(x);if (*pphead == NULL) {*pphead = node;return;}node->next = *pphead;*pphead = node;return;
}//任意位置之前插入，采用双指针的方式
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);assert(*pphead);SLTNode* node = BuyNode(x);if (*pphead == pos) {node->next = pos;*pphead = node;return;}SLTNode* fast = (*pphead)->next, * slow = *pphead;while (fast != pos) {fast = fast->next;slow = slow->next;}slow->next = node;node->next = fast;return;
}//任意位置之后插入方式会大大简便
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* node = BuyNode(x);node->next = pos->next;pos->next = node;return;
}

3、链表的删除

链表的插入分为头删、尾删和任意位置删除。任意位置删除时采用双指针定向移动。

//尾删
void SLTPopBack(SLTNode** pphead) {assert(*pphead);if (!(*pphead)->next) {free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;return;
}//头删
void SLTPopFront(SLTNode** pphead) {assert(*pphead);SLTNode* node = (*pphead)->next;free(*pphead);*pphead = node;return;
}//任意位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(*pphead);assert(pos);if (pos == *pphead) {SLTPopFront(pphead);}else {SLTNode* p = *pphead;while (p->next != pos) {p = p->next;}p->next = pos->next;free(pos);pos = NULL;}return;
}

4、链表的销毁

存储链表的下一个结点，然后进行 free

void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

（三）链表的例题分析

1、移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* newhead = NULL, *tail = NULL, *p = head;while(p){if(p->val != val){if(newhead == NULL) {newhead = tail = p;}else{tail->next = p;tail = tail->next;}}p = p->next;}if(tail) tail->next = NULL;return newhead;}
};

小结： 如果 tail 不是NULL， 要将 tail 置空。

2、反转链表

https://leetcode.cn/problems/reverse-linked-list/

题目分析

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == NULL) return NULL;ListNode* pre = NULL, * cur = head, * Next = head->next;while(cur){cur->next = pre;pre = cur;cur = Next;if(!cur) break;Next = Next->next;}return pre;}
};

小结：与另外新建一个链表的方式不同，这种算法可以在原来的链表上进行处理就能达到反转链表的效果。

3、链表的中心结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

题目分析

采用快慢指针进行分析，快指针每次走两步，慢指针每次走一步，当
fast = NULL 或者 fast -> next = NULL 时，slow指针指向的就是中间位置的指针。

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* fast, *slow;fast = slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}
};

小结： 用快慢指针有很多好处，这道题的中间值就是一个

4、合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目分析

这道题的思路并不困难，主要是学一种新的头节点创建方式，通过 malloc 申请内存来获得头节点。

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newhead, * tail;newhead = tail = (ListNode*)malloc(sizeof(ListNode));newhead->next = NULL;while(list1 && list2){if(list1->val < list2->val){tail->next = list1;tail = tail ->next;list1 = list1->next;}else{tail->next = list2;tail = tail->next;list2 = list2->next;}}if(list1) tail->next = list1;if(list2) tail->next = list2;ListNode* ret = newhead->next;free(newhead);newhead = NULL;return ret;}
};

小结：这道题可以有三种方式创建头结点
1、直接开辟变量 Node head， 返回head->next;
2、创建两个指针Node* head, * tail;
3、用 malloc 开辟空间，返回malloc 的下一个结点， 记得要free；

5、链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&qru=/ta/2016test/question-ranking

题目分析

这道题有两个思路：
方法一 ： 采用数组，将链表的结点数据依次放入数组之中，然后创建两个指针向中间移动，依次比较。但是创建数组的时间复杂度为O（n)，不可以通过。
方法二 ： 中间结点后面的结点进行反转，切记反转链表反转的是指针的方向，数据位置没有变。然后同一。

方法一

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {int arr[1000], i = 0;ListNode* p = A;while (p) {arr[i++] = p->val;p = p->next;}int left = 0, right = i - 1;while(left <= right) {if(arr[left++] != arr[right--]) return false;}return true;}
};

方法二

这种在原链表上进行修改的反转操作有妙用

6、相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

题目分析

将长的链表先截成和短的链表的长度，因为是后面部分相交，挨个比较直到两个指针的地址相等为相交结点

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* p = headA;int lenA = 0, lenB = 0;while(p){p = p->next;lenA += 1;}p = headB;while(p){p = p->next;lenB += 1;}int length = abs(lenA - lenB);ListNode* longlist = headA;ListNode* shortlist = headB;if(lenA < lenB){longlist = headB;shortlist = headA;}while(length--){longlist = longlist->next;}while(longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}return shortlist;}
};

7、环形链表

https://leetcode.cn/problems/linked-list-cycle/

题目分析

用快慢指针，如果有环，那么快指针就会追上慢指针。

问题一 ： 快指针为什么一定会追上慢指针
因为每次追逐两个指针的距离都会减一

问题二：快指针每次可以走2， 3， 4 ~步吗
下面我们以快指针每次走三步为例，结果是一定相遇，其他推理结论相同

class Solution {
public:bool hasCycle(ListNode *head) {ListNode* fast ,* slow;fast = slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow) return true;}return false;}
};

小结：上面的文章里面，我们用快慢指针找中间结点，现在又多了一种新的用法，用来判断是否有环。

8、环形链表||

https://leetcode.cn/problems/linked-list-cycle-ii/description/

题目分析

在相遇之后，相遇点和头结点到环的起始点的距离相等，用两个指针从这两个位置同时出发，直到相遇。

9、随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

题目分析

如下图

步骤一 ： 添加复制的结点

步骤二： 给random 赋值
步骤三： 断开原来的链表和拷贝链表

class Solution {
public:Node* BuyNode(int val) {Node* p = (Node*)malloc(sizeof(Node));p->val = val;p->next = p->random = NULL;return p;}void AddNode(Node* head) {Node *pcur = head, *next;while (pcur) {next = pcur->next;Node* node = BuyNode(pcur->val);pcur->next = node;node->next = next;pcur = next;}return;}Node* SetRandom(Node* head) {Node* pcur = head;while (pcur) {Node* temp = pcur->next;if (pcur->random) {temp->random = pcur->random->next;}pcur = pcur->next->next;}return head;}Node* getNewLinkList(Node* head) {Node *newHead, *tail;Node* pcur = head;newHead = tail = head->next;while (pcur) {pcur->next = tail->next;if (tail->next) {tail->next = pcur->next->next;tail = tail->next;}pcur = pcur->next;}// tail->next = NULL; // 确保新链表的尾部正确return newHead;}Node* copyRandomList(Node* head) {if (head == NULL)return NULL;AddNode(head);head = SetRandom(head);head = getNewLinkList(head);return head;}
};

小结：无需多言，值得反复学习

结束语

好了，小编也要睡觉了，下一篇小编会带来双向链表的博文。如果感兴趣的话记得要给博主一个关注哦，不然就再也找不到啦，小伙伴们周末快乐！