【数据结构】线性表，顺序表

一. 线性表

1. 线性表(linear list)是n个具有相同特性的数据元素的有限序列。

2. 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

3. 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二. 顺序表 

1. 静态顺序表与动态顺序表

1. 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

2. 顺序表一般可以分为：

静态顺序表：使用定长数组存储元素。

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType array[N]; //定长数组
	size_t size;         //有效数据个数
}SeqList;

动态顺序表：使用动态开辟的数组存储。

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* array; //指向动态开辟的数组
	size_t size;       //有效数据个数
	size_t capacity;   //空间容量
}SeqList;

2. 动态顺序表的接口实现 

1. 静态顺序表只适用于确定知道需要存多少数据的场景。

2. 静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。

3. 所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

2.1 顺序表初始化 

1. 将结构的每个成员进行初始化

void SeqListInit(SeqList* psl, size_t capacity)
{
	assert(psl);

	psl->array = (SLDataType*)malloc(sizeof(SeqList) * capacity);
	if (psl->array == NULL)
	{
		perror("malloc");
		return;
	}
	psl->size = 0;
	psl->capacity = capacity;
}

2.2 判断是否需要扩容  

1. 判断有效个数是否和容量相等。

2. 使用realloc增容。

void CheckCapacity(SeqList* psl)
{
	assert(psl);

	if (psl->size == psl->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror(realloc);
			return;
		}
		psl->array = tmp;
		psl->capacity *= 2;
	}
}

 2.3 顺序表指定位置插入

1. 对pos进行范围判断。

1. 判断是否需要扩容。

2. 将pos后面的元素往后挪一位。

3. pos位置插入值。

4. 有效个数加一。

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);

	CheckCapacity(psl);

	size_t cur = psl->size;
	while (cur != pos)
	{
		psl->array[cur] = psl->array[cur - 1];
		cur--;
	}

	psl->array[pos] = x;
	psl->size++;
}

 2.4 顺序表头插

1. 判断是否需要扩容。

2. 将所有元素都往后移一位，留出第一个位置插入(如果头插之前没有元素，则直接插入即可)。

3. 有效个数加一。

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	CheckCapacity(psl);

	int tmp = psl->size;
	while (tmp > 0) //当本身为空时，就不走这个循环
	{
		psl->array[tmp] = psl->array[tmp - 1];
		tmp--;
	}

	psl->array[0] = x;
	psl->size++;
}

方法2：复用SeqListInsert

void SeqListPushFront(SeqList* psl, SLDataType x)
{
	SeqListInsert(psl, 0, x);
}

2.5 顺序表尾插

1. 插入前判断是否需要增容。

2. size作为下标正好是最后一个元素的后一位。

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	CheckCapacity(psl);
	psl->array[psl->size++] = x;
}

方法2：复用SeqListInsert

void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	SeqListInsert(psl, psl->size, x);
}

 2.6 顺序表指定位置删除

1. 判断pos是否合法。

2. 将pos后面的元素往前覆盖一位。

3. 有效个数减一。

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	int cur = pos;
	while (cur < psl->size - 1)
	{
		psl->array[cur] = psl->array[cur + 1];
		cur++;
	}
	
	psl->size--;
}

 2.7 顺序表头删

1. 判断有效个数是否为0，为0不用删。

2. 将后面的与元素往前覆盖一位。

3. 有效元素个数减一。

void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size);

	size_t cur = 0;
	while (cur < psl->size - 1)
	{
		psl->array[cur] = psl->array[cur + 1];
		cur++;
	}

	psl->size--;
}

方法2：复用SeqListErase

void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	SeqListErase(psl, 0);
}

 2.8 顺序表尾删

1. 判断size，size如果为0就不能删。

2. 删除尾部元素直接将size减减即可。

void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size);

	psl->size--;
}

方法2：复用SeqListErase

void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	SeqListErase(psl, psl->size - 1);
}

2.9 顺序表查找

1. 遍历一遍进行比较。

2. 找到返回下标，否则返回-1。

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (size_t i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x) return i;
	}

	return -1;
}

2.10 顺序表修改 

1. 对pos进行范围判断。

2. 将pos作为下标进行修改。

void SeqListModify(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	psl->array[pos] = x;
}

2.11 顺序表销毁

1. 销毁时需要释放空间，指针置空。

2. 有效个数和容量置0。

void SeqListDestory(SeqList* psl)
{
	assert(psl);

	free(psl->array);
	psl->array = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

2.12 顺序表打印

1. 遍历数组打印

void SeqListPrint(SeqList* psl)
{
    assert(psl);

	for (int i = 0; i < psl->size; i++) printf("%d ", psl->array[i]);
    printf("\n");
}

3. 顺序表的缺点

1. 中间/头部的插入删除，时间复杂度为O(N)。

2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

4. 顺序表编程练习题 

4.1 移除元素

链接：. - 力扣（LeetCode）

思路： 

1. src遍历判断，等于val就什么也不做，不等于val就把当前值给dst。

2. 等待src给我值，然后加加。

int removeElement(int* nums, int numsSize, int val)
{
    int dst = 0;
    for(int src=0; src<numsSize; src++)
    {
        if(nums[src] != val) nums[dst++] = nums[src];
    }

    return dst;        
}

4.2 删除有序数组中的重复项

链接：. - 力扣（LeetCode）

思路：利用双指针进行比较。

int removeDuplicates(int* nums, int numsSize) 
{
    int dst = 0;
    for(int src=1; src<numsSize; src++)
    {
        if(nums[dst] != nums[src]) nums[++dst] = nums[src];
    }

    return dst+1;
}

4.3 合并两个有序数组

链接：. - 力扣（LeetCode）

思路：

1. 从后面开始比较，谁大谁放在后面。

2. 注意结束条件，这里以tail为标准。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
    int src1 = m-1;
    int src2 = n-1;
    int tail = nums1Size-1;
    while(tail>=0)
    {
        if(src2<0) break;
        if(src1<0) nums1[tail] = nums2[src2--];
        else if(nums2[src2] >= nums1[src1]) nums1[tail] = nums2[src2--];
        else if(nums2[src2] < nums1[src1]) nums1[tail] = nums1[src1--];
        tail--;
    }
}

三. 链表

1. 链表的概念及结构

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

2. 单链表实现

2.1 单链表节点结构

1. 使用typedef重命名数据类型是为了方便类型的更改。

2. 结构包含存放的数据和指向下一个节点的地址。

typedef int SLDataType;
typedef struct SingleListNode
{
	SLDataType data;
	struct SingleListNode* next;
}SLNode;

2.2 动态申请一个节点

1. 使用malloc申请一块节点空间。

2. 将节点内容初始化。 

SLNode* BuySLNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

2.3 单链表打印

1. 通过获取下一个节点地址进行遍历并打印数据。

2. 遇到空节点停下。

void SLPrint(SLNode* plist)
{
	SLNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

2.4 单链表尾插

1. pplist不可能为空，所以加断言。

2. 无节点情况：直接将新节点地址给头指针。

3. 有节点情况：将最后一个节点连接新节点。

void SLPushBack(SLNode** pplist, SLDataType x)
{
	assert(pplist);

	SLNode* newnode = BuySLNode(x);
	if (*pplist == NULL) *pplist = newnode; //无节点
	else                                    //有节点
	{
		SLNode* cur = *pplist;
		while (cur->next != NULL) cur = cur->next;
		cur->next = newnode;
	}
}

2.5 单链表头插

1. 先将新节点连接第一个结点，再将头指针连接新节点。   

void SLPushFront(SLNode** pplist, SLDataType x)
{
	assert(pplist);

	SLNode* newnode = BuySLNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

2.6 单链表尾删

1. 单节点情况：释放节点然后置空。

2. 多节点情况：利用倒数第二个节点，释放倒数第一个节点并置空。

void SLPopBack(SLNode** pplist)
{
	assert(pplist && *pplist);

	SLNode* cur = *pplist;
	if (cur->next == NULL) //单节点
	{
		free(cur);
		*pplist = NULL;
	}
	else                   //多节点
	{
		while (cur->next->next != NULL) cur = cur->next;
		free(cur->next);
		cur->next = NULL;
	}
}

2.7 单链表头删

1. *pplist不能为空，因为空节点不用删。

2. 将头指针指向第二个节点，释放第一个节点。

void SLPopFront(SLNode** pplist)
{
	assert(pplist && *pplist);

	SLNode* del = *pplist;
	*pplist = del->next;
	free(del);
}

2.8 单链表查找 

1. 遍历一遍，比较数据。

SLNode* SLFind(SLNode* plist, SLDataType x)
{
	SLNode* cur = plist;
	while (cur)
	{
		if (cur->data == x) return cur;
		cur = cur->next;
	}

	return NULL;
}

 2.9 单链表在pos后一位插入x

1. 先将新节点连接pos的后一个节点，再将pos连接新节点。

void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);

	SLNode* newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

2.10 单链表删除pos后一位的值

1. 空节点不用删。

2. 将pos和pos后面第二个节点连接，释放pos后面第一个节点。

void SLEraseAfter(SLNode* pos)
{
	assert(pos);

	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

3. 链表的分类 

4. 双向链表的实现

5. 链表编程练习题

5.1 移除链表元素

链接：. - 力扣（LeetCode）

思路：

1. 遍历链表，删除相同值得节点。

2. 使用前后指针，方便节点的释放。

3. 注意特殊情况，当第一个节点就需要删除的时候。

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    while(cur)
    {
        if(cur->val == val)
        {   
            if(prev == NULL) //这里判断的是当前是不是第一个节点，
            {                   //注意，删除完第一个节点后，第二个节点会变成新的第一个节点。
                cur = cur->next;
                free(head);
                head = cur;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }

    return head;
}

5.2 链表的中间结点

链接：. - 力扣（LeetCode）

思路：

1. 快慢指针，slow一次走一步，fast一次走两步。

2. 有奇数节点，偶数节点两种情况，奇数节点时fast走到最后一个节点停下，偶数节点时fast走到空停下。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

5.3 合并两个有序链表

链接：. - 力扣（LeetCode）

思路：

1. 将小于或等于的节点尾插到一个新的指针上，返回这个指针。

2. 注意第一个节点尾插需要特殊处理。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    if(list1 == NULL) return list2;
    if(list2 == NULL) return list1;

    struct ListNode* list3 = NULL;
    struct ListNode* cur = NULL;
    while(list1 && list2)
    {
        if(list1->val <= list2->val)
        {
            if(list3 == NULL) list3 = cur = list1;
            else
            {
                cur->next = list1;
                cur = cur->next;
            }
            list1 = list1->next;
        }
        else
        {
            if(list3 == NULL) list3 = cur = list2;
            else
            {
                cur->next = list2;
                cur = cur->next;
            }

            list2 = list2->next;
        }
    }

    if(list1) cur->next = list1;
    if(list2) cur->next = list2;

    return list3;
}

5.4 反转链表 

链接：. - 力扣（LeetCode）

思路1：用三个指针来实现反转。

struct ListNode* reverseList(struct ListNode* head) 
{
    if(head == NULL) return NULL;

    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;

    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3) n3 = n3->next;
    }

    return n1;
}

思路2：头插法，每次cur节点对rhead进行头插。

struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* rhead = NULL;
    struct ListNode* cur = head;
    
    while(cur)
    {
        struct ListNode* next = cur->next;

        cur->next = rhead;
        rhead = cur;

        cur = next;
    }

    return rhead;
}

5.5  链表分割

链接：链表分割_牛客题霸_牛客网

思路：

1. 分两个链表，将小于x的尾插一个链表，大于等于x的尾插另一个链表，最后连接起来。

2. 建议用带哨兵位的链表。

3. 连接起来后第二个链表最后记得指向NULL。

ListNode* partition(ListNode* pHead, int x) 
    {
        ListNode* h1 = (ListNode*)malloc(sizeof(ListNode));
        ListNode* h2 = (ListNode*)malloc(sizeof(ListNode));
        ListNode* h1tail = h1;
        ListNode* h2tail = h2;

        ListNode* cur = pHead;
        while(cur)
        {
            if(cur->val < x)
            {
                h1tail->next = cur;
                h1tail = h1tail->next;
            }
            else 
            { 
                h2tail->next = cur;
                h2tail = h2tail->next;
            }

            cur = cur->next;
        }

        h1tail->next = h2->next;
        h2tail->next = NULL;
        pHead = h1->next;
        free(h1);
        free(h2);

        return pHead;
    }

5.6 相交链表

链接：. - 力扣（LeetCode）

思路：

1. 先求两个链表的长度。

2. 长的链表头指针先走，走到和短的链表一样长。

3. 两个指针一起走，直到遇到一样的节点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    int lenA = 0;
    int lenB = 0;
    struct ListNode* cur = headA;
    while(cur)
    {
        lenA++;
        cur = cur->next;
    }
    cur = headB;
    while(cur)
    {
        lenB++;
        cur = cur->next;
    }

    int gap = abs(lenA-lenB);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if(lenA < lenB)
    {
        longlist = headB;        
        shortlist = headA;  
    }
    while(gap--) longlist = longlist->next;  

    while(longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
        
    return longlist;
}

5.7 环形链表 

链接：. - 力扣（LeetCode）

思路：

1. 利用快慢指针，如果有环那么会相遇，如果没环就走到链表结束。

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

    return false;
}

面试问题：

1. 快指针走两步，慢指针走一步，快指针和慢指针一定会相遇吗？

答：一定会，当他们进入环后，距离不断减1直到0。

快指针走n步，慢指针走一步，假设快指针追到慢指针的距离为N，那么N必须是n-1的倍数才有能追上。错过之后，N也会发生变化。

6. 顺序表和链表的区别