数据结构-顺序表和链表

线性表

线性表n个具有相同特性的数据元素的有限序列，它是一种在实际使用中广泛使用的数据结构，常见的线性表有顺序表、链表、栈、队列等。线性表在逻辑上是线性结构，但是在物理上不一定连续（比如链表）。

顺序表

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

1. 静态顺序表（不常用）：使用定长数组存储。

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

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

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

一般来说，更常使用的是动态顺序表，因为它更灵活一些。

顺序表的接口实现

1. 顺序表的增，可分为头插，尾插，任意位置插入。它们的时间复杂度分别为头插：O(n)、尾插：O(1)、任意位置插入：O(n)。代码如下：

void SeqListPushFront(SeqList* ps, SLDateType x)//头插
{
	if (ps->size >= ps->capacity)
	{
		Realoc(ps);//扩容
	}
	size_t end = ps->size;
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPushBack(SeqList* ps, SLDateType x)//尾插
{
	if (ps->size >= ps->capacity)
	{
		Realoc(ps);//扩容
	}
	ps->a[ps->size] = x;
	ps->size++;
}

void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)//pos位置插入
{
	if (ps->size >= ps->capacity)
	{
		Realoc(ps);//扩容
	}
	size_t end = ps->size;
	while (end > (pos - 1))
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos - 1] = x;
	ps->size++;
}

1. 顺序表的删也可以分为头删、尾删以及任意位置删除，它们的时间复杂度分别为，头删：O(n)、尾删：O(1)、任意位置删除：O(n)。代码如下：

void SeqListPopFront(SeqList* ps)//头删
{
	for (size_t i = 0; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

void SeqListPopBack(SeqList* ps)//尾删
{
	ps->size--;
}

void SeqListErase(SeqList* ps, size_t pos)//pos位置删除
{
	size_t erase = pos - 1;
	while (erase < ps->size)
	{
		ps->a[erase] = ps->a[erase + 1];
		erase++;
	}
	ps->size--;
}

1. 顺序表的查找需要遍历整个表，故时间复杂度为O(n)，代码如下：

int SeqListFind(SeqList* ps, SLDateType x)//查找
{
	size_t find = 0;
	while (find < ps->size)
	{
		if (ps->a[find] == x)
		{
			return find + 1;
		}
		find++;
	}
	return -1;//如果没找到，返回一个不可能是数组下标的值
}

1. 由于顺序表可以支持随机访问的特点，所以他的数据的修改比较简单，在这里不多赘述。

链表

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

1. 单向、双向
2. 带头、不带头
3. 循环、非循环

以上的情况组合起来就有23 = 8 种链表结构。实际中最常用的是无头单项非循环链表以及带头双向循环链表

不带头单向非循环链表

1. 链表的实现

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

1. 创建一个节点以及打印数据

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* new = (SListNode*)malloc(sizeof(SListNode));
	new->data = x;
	new->next = NULL;
	return new;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

1. 插入节点，头插：O(1)、尾插O(n)、任意位置之后插入O(1)。

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* new = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = new;
		return;
	}
	new->next = *pplist;
	*pplist = new;
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* new = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = new;
		return;
	}
	SListNode* cur = *pplist;
	while (cur->next)
	{
		cur = cur->next;
	}
	cur->next = new;
}
// 单链表在pos位置之后插入x
//单向的特性导致它只能从头到尾走，所以获得一个位置的同时只能知道它的下一个位置，而不能知道它前一个位置
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	if (pos == NULL)
	{
		printf("不存在！\n");
		return;
	}
	SListNode* new = BuySListNode(x);
	SListNode* next = pos->next;
	pos->next = new;
	new->next = next;
}

1. 删除节点，头删O(1)、尾删O(n)、任意位置删除O(1)

// 单链表头删
void SListPopFront(SListNode** pplist)
{
	SListNode* first = *pplist;
	if (first == NULL || first->next == NULL)
	{
		free(first);
		*pplist = NULL;
		return;
	}
	SListNode* after = first->next;
	free(first);
	*pplist = after;

}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	SListNode* back = *pplist;
	SListNode* before = NULL;
	if (back == NULL || back->next == NULL)
	{
		free(back);
		*pplist = NULL;
		return;
	}

	while (back->next)
	{
		before = back;
		back = back->next;
	}
	free(back);
	back = NULL;
	before->next = NULL;
}
// 单链表删除pos位置之后的值,原因同任意位置插入
void SListEraseAfter(SListNode* pos)
{
	if (pos == NULL)
	{
		printf("不存在！\n");
		return;
	}
	SListNode* del = pos->next;
	SListNode* del_next = del->next;
	free(del);
	pos->next = del_next;
}

1. 查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* find = plist;
	while (find)
	{
		if (find->data == x)
			return find;
		find = find->next;
	}
	return NULL;
}

1. 链表的修改较为简单，只需要找到该位置并修改数值即可，在此不多赘述。

带头双向循环列表

1. 链表的实现

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;
//初始化一个循环结构，也是该链表的头节点
void Init(ListNode* pHead)
{//它的头节点不存储有效数据
	pHead->_data = 0;
	pHead->_next = pHead;
	pHead->_prev = pHead;
}

1. 创建一个节点以及打印

ListNode* ListCreate(LTDataType x)//创建新的节点
{
	ListNode* Newnode = (ListNode*)malloc(sizeof(ListNode));
	Newnode->_data = x;
	Newnode->_prev = NULL;
	Newnode->_next = NULL;

	return Newnode;
}
void ListPrint(ListNode* pHead)//打印
{
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		printf("%d ", cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}

1. 插入数据，头插O(1)、尾插O(1)、任意位置之前插入O(1)

void ListPushFront(ListNode* pHead, LTDataType x)//头插
{
	ListNode* Newnode = ListCreate(x);
	ListNode* Front = pHead->_next;

	Newnode->_next = Front;
	Front->_prev = Newnode;

	pHead->_next = Newnode;
	Newnode->_prev = pHead;
}
void ListPushBack(ListNode* pHead, LTDataType x)//尾插
{
	ListNode* Newnode = ListCreate(x);
	ListNode* last = pHead->_prev;

	last->_next = Newnode;
	Newnode->_prev = last;

	Newnode->_next = pHead;
	pHead->_prev = Newnode;

}
void ListInsert(ListNode* pos, LTDataType x)//pos位置之前插入
{
	ListNode* Newnode = ListCreate(x);
	ListNode* before = pos->_prev;

	Newnode->_prev = before;
	Newnode->_next = pos;

	before->_next = Newnode;
	pos->_prev = Newnode;
}

1. 删除数据，头删O(1)、尾删O(1)、任意位置删除O(1)

void ListPopFront(ListNode* pHead)//头删
{
	ListNode* Front = pHead->_next;
	pHead->_next = Front->_next;
	Front->_next->_prev = pHead;

	free(Front);
}
void ListPopBack(ListNode* pHead)//尾删
{
	ListNode* last = pHead->_prev;
	pHead->_prev = last->_prev;
	last->_prev->_next = pHead;

	free(last);
}
void ListErase(ListNode* pos)//pos位置删除
{
	ListNode* before = pos->_prev;
	ListNode* after = pos->_next;

	before->_next = after;
	after->_prev = before;

	free(pos);
}

1. 查找

ListNode* ListFind(ListNode* pHead, LTDataType x)//查找
{
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		if (cur->_data == x)
			return cur;
		cur = cur->_next;
	}
	return NULL;
}

1. 链表的修改较为简单，只需要找到该位置并修改数值即可，在此不多赘述。

顺序表和链表各自的特点

顺序表：

• 优点：支持随机访问，尾插尾删时间复杂度O(1)，连续的结构，实现简单。
• 缺点：其他位置的插入删除时间复杂度都为O(n)，并且在插入时有增容代价。
• 适用场景：适合频繁访问的场景

链表（指双向链表）：

• 优点：任意位置插入删除时间复杂度都是O(1)。
• 缺点：不支持随机访问，实现比较复杂（但用起来简单），非连续结构。
• 适用场景：频繁插入删除的场景。