数据结构与算法之美1_数组&链表

本系列文章，算是《极客时间》的《数据结构与算法之美》专栏的读书笔记。

只是一些个人心得与练习，想要得到更详细更好更系统的学习，请去极客时间APP订阅专栏。

跟着专栏学了好久，也该有点成果不是；

正好趁着最后的几篇练习章节，把之前学到的，做个笔记总结一下。

笔记列表：

回顾

数组

定义

数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性表 & 非线性表
- 线性表：数组、链表、队列、栈等
- 非线性表：二叉树、堆、图等
连续的内存空间
相同的数据类型

特性

快速的随机访问与低效的插入删除。

快速的随机访问：根据下标随机访问
- 1
  a[i](地址) = base(首地址) + i(下标) * data_type_size(数组每个元素大小)
- 随机访问复杂度为O(1)，查找的复杂度大于等于O(logn) (在排好序情况下，用二分查找的复杂度)
低效的插入与删除
- 插入：数组大小为n，将一个数据插入到第k个位置，需要将k~n位置数据均向后移动一位，平均时间复杂度为O(n)。
  - 对于无序数组，可以将第k位置数据放到最后，然后将数据放到第k位置，来避免大规模的数据搬移
- 删除：数组大小为n，将第k个位置数据删除，需要将k~n位置数据均向前移动一位，平均时间复杂度为O(n)。
  - 对于数据连续性要求低的情况，可以将多个删除操作集中到一次进行，被删除的数据标记删除，新数据从数组尾部扩展，直到数组没有空间，将标记删除的数据一次性清除，其余数据一次性前移相应位数

注意

数组越界问题

访问数组其实就是访问连续的内存，只要所访问的内存地址是可用的，那么这个访问就成立。因此，对于没有规定数组越界时编译器应该如何处理的语言中，会出现难以排查的BUG。但是，也有很多语言，自己会做一些越界检查，并抛出错误或异常。

容器与数组的选择

一些容器
- 对于Java的ArrayList，它的优势是将很多数组操作细节进行了封装，并且支持了动态扩容（动态扩容：在超出给数组分配的空间上限时，会重新申请1.5倍数组空间，并将数据迁移过去）。但是，由于扩容比较耗时，最好还是在创建ArrayList时指定数据大小。
- 对于C++ STL的 vector，可以获取长度，可以在末尾增加元素，可以确定长度节省空间，支持了动态扩容（扩容倍数与编译器相关，为1.5倍或2倍，具体为什么是成倍扩容而非固定步长扩容，为什么是1.5倍/2倍，而不是其他倍数，可参考资料[https://blog.csdn.net/yangshiziping/article/details/52550291]]）
- 对于C++11新增的 std::array，它介于内置的array与vector之间。对于内置array，它提供更好的数据访问机制，可以自动释放内存，更安全，提供更好的遍历机制，提供判空、初始化所有成员方法、swap机制等，更容易使用；对于vector而言，它使用了静态存储区，效率高，但不支持改变容器大小操作即不支持动态扩容；使用std:array必须指定元素类型，指定容器大小。
如何选择
- 对于业务开发，直接使用容器，省时省力。
- 对于底层开发，需要将性能优化到极致，此时使用数组优于容器。

链表

定义

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

链表由一系列结点组成，结点可以在运行时动态生成
每个结点包含两部分：
- 存储数据元素的数据域
- 存储下一个结点地址的指针域

特性

与数组相反，高效的插入删除、低效的随机访问。

但是在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。
数组简单易用，在实现上使用的是连续的内存空间，借助于CPU的缓存机制，预读数组数据，可以使得访问效率更高。
链表在内存中并不是连续存储，无法充分利用CPU的缓存机制，无法做到有效的预读数据。
数组的缺点是大小固定。一旦声明，就需要占用整块连续内存空间，声明数组过大，容易导致内存不足；但是声明数组过小，当需要拷贝迁移数据，又很耗时。链表相对于此的优势就显现出来了。
链表的缺点还有：相对于数据，还需要额外存储指针域，多耗费一些存储空间；如果进行频繁的插入、删除操作，将会导致频繁内存申请、释放，容易造成内存碎片。

技巧

理解指针、引用的含义

将某个变量赋值给指针，实际上是将该变量的地址赋值给指针，反过来说，指针中存储了这个变量的内存地址，该地址指向这个变量，通过指针可以找到这个变量。

警惕指针丢失和内存泄漏

插入结点时，一定要注意操作顺序
- 链表结构为 a->b->c->d，将z插入到b与c之间
  1. 将z的后继指针指向c
  2. 将b的后继指针指向z
删除链表结点时，记得手动释放内存空间
- 对于自动管理内存的语言就无需顾虑了

利用哨兵简化实现难度

针对链表的插入第一个结点和删除最后一个结点情况特殊处理，会使得代码繁琐、易出错。

可以引入一个不带数据的哨兵结点，在头部，指向链表的第一个结点。

重点留意边界条件处理

注意下列情况，代码能否正常工作

链表为空
链表只含一个结点
链表只包含两个结点
处理头结点和尾结点

举例&画图

好记性不如烂笔头，多举例、多画图，加深印象，充分理解。

多写多练，没有捷径

常见链表操作

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点

练习

数组

必知必会

实现一个支持动态扩容的数组

class MyArray
{
public:

	void insert(int index, int value)
	{
		
		if (size < total) {
			for (int i = size; i > index; i--) {
				data[i] = data[i - 1];
			}
			data[index] = value;
			++size;
		}
		else  {
			// 扩容
			int *temp = new int[total * 2 + 1];
			for (int i = 1; i < index; i++) {
				temp[i] = data[i];
			}
			temp[index] = value;
			for (int i = index + 1; i <= total + 1; i++) {
				temp[i] = data[i - 1];
			}
			delete[] data;
			data = temp;
			total *= 2;
		}
	}

	void print()
	{
		for (int i = 0; i < size; i++) {
			cout << data[i] << " ";
		}
		cout << endl;
	}

	int *getData()
	{
		return data;
	}

	int getSize()
	{
		return size;
	}

private:
	int total = 5;
	int *data = new int[total + 1];
	int size = 0;
};

实现一个大小固定的有序数组

class SortArray
{
public:
	bool insert(int value)
	{
		if (size >= total)
			return false;

		++size;
		int i = size;
		for ( ; i > 0; i--) {
			if (data[i-1] <= value)
				break;
			data[i] = data[i - 1];
		}
		data[i] = value;
	}

	void print()
	{
		for (int i = 0; i < size; i++) {
			cout << data[i] << " ";
		}
		cout << endl;
	}

	int *getData()
	{
		return data;
	}

	int getSize()
	{
		return size;
	}

private:
	int total = 5;
	int *data = new int[total + 1];
	int size = 0;
};

实现两个有序数组合并为一个有序数组

void mergeArray(int a[], int aLen, int b[], int bLen)
{
    int totalLen = aLen + bLen;
    --aLen;
    --bLen;
    --totalLen;
    while(aLen >= 0 && bLen >= 0)	{
        if(a[aLen] >= b[bLen])	{
            a[totalLen--] = a[aLen--];
        }
        else	{
            a[totalLen--] = b[bLen--];
        }
    }
    
    while(bLen >= 0)	{
        a[totalLen--] = b[bLen--];
    }
}

LeetCode

链表

必知必会

结构体

单链表结点

struct ListNode
{
	int data;
	ListNode* next;
}

双向链表结点

struct DoubleSideListNode
{
    int data;
    ListNode* pre;
    ListNode* next;
}

单链表的反转

三个哨兵

ListNode* reverseSingleList(ListNode* list)	
{
    ListNode* head = list;
    ListNode* temp1 = list;
    ListNode* temp2;
    
	while(temp1 != nullptr && temp1->next != nullptr)	{
    	temp2 = temp1->next;
    	temp1->next = temp2->next;
    	temp2->next = head;
    	head = temp2;
	}
	
	return head;
}

链表中环的检测

快慢指针

bool haveLoop(ListNode* list)
{
    ListNode* slow = list;
    ListNode* fast = list;
    
    while(fast != nullptr && fast->next != nullptr)	{
        slow = slow->next;
        fast = fast->next->next;
        
        if(slow == fast)
            return true;
    }
    return false;
}

两个有序的链表合并

ListNode* mergeSortedLists(ListNode* list1, ListNode* list2)
{
	ListNode* list = new ListNode();
	ListNode* head = list;

	while (list1 != nullptr or list2 != nullptr) {
		if (list1 == nullptr) {
			list->next = list2;
			break;
		}
		else if (list2 == nullptr) {
			list->next = list1;
			break;
		}
		else
		{
			if (list1->data < list2->data) {
				list->next = list1;
				list1 = list1->next;
			}
			else  {
				list->next = list2;
				list2 = list2->next;
			}
			list = list->next;
		}
	}
	
	return head->next;
}

删除链表中倒数第n个结点

和快慢指针差不多，相聚n个结点距离，快指针到尾部就代表慢指针是第n个节点

ListNode* deleteReciprocalNode(ListNode* list, int n)
{
	if (n == 0)
		return list;

	ListNode* aimNode = list;
	ListNode* afterNode = list;
	
	while(afterNode->next != nullptr)	{
		if (n > 0) {
			afterNode = afterNode->next;
			--n;
		}
		else
		{
			aimNode = aimNode->next;
			afterNode = afterNode->next;
		}
	}

	if (n == 0) {
		ListNode* deleteNode = aimNode->next;
		aimNode->next = deleteNode->next;
		delete(deleteNode);
	}

	return list;
}

求链表的中间结点

依旧是快慢指针，慢指针一次移1，快指针一次移2

ListNode* middleNode(ListNode* list)
{
	ListNode* slow = list;
	ListNode* fast = list;

	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;
	}

	return slow;
}

单链表、循环链表、双向链表的增删操作

单链表
循环链表
双向链表

数据结构与算法之美1_数组&链表

回顾

数组

定义

特性

注意

数组越界问题

容器与数组的选择

链表

定义

分类

单链表

双向链表

循环链表

特性

技巧

理解指针、引用的含义

警惕指针丢失和内存泄漏

利用哨兵简化实现难度

重点留意边界条件处理

举例&画图

多写多练，没有捷径

练习

数组

必知必会

LeetCode

链表

必知必会

结构体

单链表的反转

链表中环的检测

两个有序的链表合并

删除链表中倒数第n个结点

求链表的中间结点

单链表、循环链表、双向链表的增删操作

LeetCode练习题