线性表

// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
 	SLDataType array[N]; // 定长数组
 	size_t size; // 有效数据的个数 
}SeqList;
 
 
// 顺序表的动态存储
typedef struct SeqList
{
 	SLDataType* array; // 指向动态开辟的数组
	size_t size ; // 有效数据个数
	size_t capicity ; // 容量空间的大小
}SeqList;

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array;  // 指向动态开辟的数组
	size_t size ;       // 有效数据个数
	size_t capicity ;   // 容量空间的大小
}SeqList;
 
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl)
{
	assert(pq);
	pq->a = NULL;
	pq->size = pq->capacity = 0;
 
}
 
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{
    if (pq->size == pq->capacity)
	{
		int newcapacity = (pq->capacity == 0) ? 7 : pq->capacity * 2;
		Seqdatatype* newA = (Seqdatatype*)realloc(pq->a, sizeof(Seqdatatype) * newcapacity);
		if (newA == NULL)
		{
			printf("增容失败！\n");
			exit(-1);
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}
 
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
    ////第一种方法，自己实现
	//assert(pq);
	//SeqlistCheckCap(pq);
	//pq->a[pq->size] = x;
	//pq->size++;
 
	//第二种方法就是利用任意位置插入函数来实现特殊情况：pos等于pq->size时候就是尾插
	SeqlistInsert(pq, pq->size, x);
}
 
// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
    ////第一种方法是自己实现
	//assert(pq);
	//assert(pq->size > 0);
	//pq->size--;
 
	//第二种方法就是让任意位置删除的pos等于pq->size-1，就是尾删
	SeqlistErase(pq, pq->size-1);
}
 
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
    ////第一种方法就是自己实现
	//assert(pq);
	//SeqlistCheckCap(pq);
	//int end = pq->size - 1;
	//while (end >= 0)
	//{
	//	pq->a[end + 1] = pq->a[end];
	//	end--;
	//}
	//pq->a[0] = x;
	//pq->size++;
 
	//第二种方法就是利用任意位置插入函数来实现特殊情况：pos等于0时候就是头插
	SeqlistInsert(pq, 0, x);
}
 
// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
    ////第一种方法就是自己实现
	//assert(pq);
	//assert(pq->size > 0);
	//int i = 0;
	//while (i < pq->size - 1)
	//{
	//	pq->a[i] = pq->a[i + 1];
	//	i++;
	//}
	//pq->size--;
 
	//第二种方法就是让任意位置删除的pos等于0，就是头删
	SeqlistErase(pq, 0);
}
 
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
{
    assert(pq);
	for (int i = 0; i < pq->size; i++)
	{
		if (pq->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
    assert(pq);
	assert(pos >= 0 && pos <= pq->size);
	SeqlistCheckCap(pq);
	int end = pq->size - 1;
	while (end >= pos)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[pos] = x;
	pq->size++;
}
 
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
    assert(pq);
	assert(pos >= 0 && pos < pq->size);
	while (pos < pq->size - 1)
	{
		pq->a[pos] = pq->a[pos + 1];
		pos++;
	}
	pq->size--;
}
 
// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
    assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}
 
// 顺序表打印
void SeqListPrint(SeqList* psl)
{
    assert(pq);
	for (int i = 0; i < pq->size; i++)
	{
		printf("%d ", pq->a[i]);
	}
	printf("\n");
}
 
// 顺序表修改
void SeqlistModify(Seqlist* pq, int pos, Seqdatatype x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);
	pq->a[pos] = x;
}

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLTDataType;
//1、单向 + 无头 + 不循环
typedef struct SListNode
{
	int data;
	struct SLTNode* next;
}SLTNode;
 
// 动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode != NULL)
	{
		newnode->data = x;
		newnode->next = NULL;
		return newnode;
	}
	else
	{
		printf("空间不够！\n");
		exit(-1);
	}
}
 
//销毁单链表
void SListDestroy(SLTNode** pplist)
{
	assert(pplist);
 
	SLTNode* cur = *pplist;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pplist = NULL;
}
 
// 单链表打印
void SListPrint(SLTNode* plist)
{
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
// 单链表的头插
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
 
// 单链表尾插
void SListPushBack(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
 
// 单链表尾删
void SListPopBack(SLTNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		(*pplist) = NULL;
	}
	else
	{
		SLTNode* tail = *pplist;
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
 
// 单链表头删
void SListPopFront(SLTNode** pplist)
{
	if (*pplist == NULL)
	{
		return;
	}
	//这种累赘一点，多了个判断，其实可以一步到位
	/*else if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SLTNode* head = *pplist;
		(*pplist) = (*pplist)->next;
		free(head);
		head = NULL;
	}*/
 
	else
	{
		SLTNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
	}
}
 
// 单链表查找
SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* cur = plist;
	while (cur != NULL)
	{
		while (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
// 原因：因为需要知道头节点且有多种情况（如pos就是第一个节点等）
// 附：其实前插可以转化为：先后插一个pos节点，然后将原pos节点的值变为x（在不知道头节点的情况下）
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
 
// 知道头节点的前插
void SListInsertKnowBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	if (*pplist == pos)
	{
		newnode->next = *pplist;
		*pplist = newnode;
	}
	else
	{
		SLTNode* cur = *pplist;
		newnode->next = pos;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
 
// 不知道头节点的前插
void SListInsertUNKnowBefore(SLTNode* pos, SLTDataType x)
{
	SListInsertAfter(pos, x);
	SLTDataType tmp = pos->data;
	SLTNode* next = pos->next;
	pos->data = next->data;
	next->data = tmp;
}
 
// pos节点后删
void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next1 = pos->next;
		pos->next = next1->next;
		free(next1);
	}
}

ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		printf("malloc fail!\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->x = x;
	return newnode;
}
 
// 创建返回链表的头结点.
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);//头结点默认赋值给它0
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
// 双向链表销毁
void ListDestroy(ListNode** phead)
{
	assert(*phead);
	ListNode* cur = (*phead)->next;
	while (cur != *phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(*phead);
	*phead = NULL;//传二级指针才能改变原来的指针
}
 
//打印链表
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->x);
		cur = cur->next;
	}
	printf("\n");
}
 
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	/*assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = phead->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = phead;
	phead->prev = newnode;*/
 
	ListInsert(phead, x);
}
 
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	/*assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;*/
 
	ListInsert(phead->next, x);
}
 
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
	/*assert(phead);
	assert(phead->next != phead);
 
	ListNode* del = phead->prev;
	ListNode* prev = del->prev;
	free(del);
	prev->next = phead;
	phead->prev = prev;*/
 
	ListErase(phead->prev);
}
 
// 双向链表头删
void ListPopFront(ListNode* phead)
{
	/*assert(phead);
	assert(phead->next != phead);
 
	ListNode* del = phead->next;
	ListNode* next = del->next;
	free(del);
	phead->next = next;
	next->prev = phead;*/
 
	ListErase(phead->next);
}
 
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->x == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
 
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	newnode->prev = prev;
	prev->next = newnode;
}
 
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
 
//空返回1，非空返回0
int ListEmpty(ListNode* phead)
{
	assert(phead);
	return phead->next == phead ? 1 : 0;
}
 
//返回链表的个数
int ListSize(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		cur = cur->next;
		count++;
	}
	return count;
}