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

线性表

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

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

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

一、顺序表

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

（一）顺序表的结构定义

typedef int SLdataType;

typedef struct SeqList {
	SLdataType* data;
	int count, size;
}SeqList;
1
2
3
4
5
6

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

（二）顺序表的功能实现

1、初始化

void initSeqList(SeqList* SL) {
	SL->data = NULL;
	SL->count = SL->size = 0;
	return;
}
1
2
3
4
5

2、销毁

void clearSeqList(SeqList* SL) {
	if (SL == NULL) return;
	if (SL->data) free(SL->data);
	SL->data = NULL;
	SL->count = SL->size = 0;
	return;
}
1
2
3
4
5
6
7

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

（三）顺序表例题分析

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目中我们用到双指针指针删除重复项，其中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--];
            else
                nums1[l3--] = nums2[l2--];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

或者采用 && 的方式实现

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--];
            else
                nums1[l3--] = nums2[l2--];
        }
        while (l2 >= 0) {
            nums1[l3--] = nums2[l2--];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(四）顺序表的弊端

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

二、链表

（一）链表的结构定义

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

typedef int SLTDataType;

typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
1
2
3
4
5
6

（二）链表的功能实现

1、链表的初始化

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

SLTNode* BuyNode(SLTDataType x) {
	SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode));
	p->data = x;
	p->next = NULL;
	return p;
}
1
2
3
4
5
6

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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
2
3
4
5
6
7
8
9
10
11
12
13

（三）链表的例题分析

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

小结： 如果 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

小结：这道题可以有三种方式创建头结点
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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二

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

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

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

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

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

结束语

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