[数据结构与算法]重新认识顺序表和链表

1.线性表

1.1什么是线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1概念和结构

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

顺序表一般可以分为：

1.静态顺序表：使用一定长度的数组来存储元素。

2.动态顺序表：使用动态开辟的数组来存储元素。

2.2增删查改的实现

静态顺序表一般用于已知元素个数的情况下使用，定长数组的N的值开大了会导致浪费，开小了不够用，所以我们这里使用动态顺序表。

typedef int SqListData;

typedef struct SqList SL;

struct SqList
{
	SqListData *a;
	int size;
	int capacity;
}L;

//顺序表初始化
void SeqListInit(SL *ps);

//顺序表的插入
void SeqListInsert(SL* ps,int pos, SqListData x);

//顺序表的删除
void SeqListPop(SL* ps, int pos);

//顺序表的查找
int SeqListFind(const SL* ps, SqListData x);

//顺序表长度
int SeqListLength(const SL* ps);

//获取指定位置的值
int SeqListGet(const SL* ps, int pos);

//清空并释放内存
void SeqListClear(SL* ps);

//判断表是否为空
void SeqListNULL(const SL* ps);

//顺序表遍历
void SeqListTrough(const SL* ps);


//检查容量够不够,不够就扩容至两倍。
void SeqListCheakCapacity(SL *ps);

//打印
void SeqListPrint(SL* ps);

下面具体用代码实现动态顺序表：

void SeqListInit(SL* ps)//顺序表初始化
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
	printf("初始化成功。\n");
}

void SeqListInsert(SL* ps, int pos, SqListData x)//插入
{
	int i = 0;
	assert(pos - 1 <= ps->size&&pos>0);
	SeqListCheakCapacity(ps);
	if (ps->size == 0)
	{
		ps->a[0] = x;
		ps->size++;//1
	}
	else
	{
		for (i = ps->size; i > pos - 1; i--)
		{
			ps->a[i] = ps->a[i - 1];
		}
		ps->a[pos - 1] = x;
		ps->size++;
	}
	printf("插入成功。\n");
}

void SeqListPop(SL* ps, int pos)//顺序表的删除
{
	assert(pos <= ps->size);
	for (int i = pos - 1; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
	printf("删除成功。\n");
}

int SeqListFind(const SL* ps, SqListData x)//查找
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;
}

int SeqListLength(const SL* ps)//表长
{
	return ps->size;
}

int SeqListGet(const SL* ps, int pos)//获取指定位置的值
{
	assert(pos <= ps->size);
	return ps->a[pos - 1];
}

void SeqListClear(SL* ps)//清空
{
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
	printf("该顺序表已清空。\n");
}

void SeqListNULL(const SL* ps)//判断是否为空
{
	if (ps->a == NULL)
		printf("该顺序表为空\n");
	else
		printf("该顺序表不为空\n");
}

void SeqListTrough(const SL* ps)//遍历
{
	if (ps->a == NULL)
	{
		printf("该顺序表为空表，无法遍历。\n");
		return;
	}
	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->a[i]);
	printf("\n");
}

void SeqListCheakCapacity(SL* ps)//查看容量
{

	if (ps->size == ps->capacity)//满了就要扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SqListData* tmp = (SqListData*)realloc(ps->a, newcapacity * sizeof(SqListData));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

//打印
void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

3.链表

3.1链表的概念及结构

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

3.2链表的分类

实际链表组合一共有单向或者双向，带头或者不带头节点，循环或者非循环两两组合的8种情况。

需要注意的是：

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

3.3链表的实现

typedef int LinkListData;

typedef struct LinkList
{
	LinkListData data;
	struct LinkList *next;
}LinkList,*LNode;

链表初始化
void LinkListInit(LinkList *L);

//链表的插入
void LinkListInsert(LinkList *L, int pos, LinkListData x);

//链表删除
void LinkListDelete(LinkList* L, int pos);

//链表长度
int LinkListLength(LinkList* L);

//链表遍历
void LinkListTrough(LinkList *L);

//获取指定位置
int LinkListGet(LinkList* L, int pos);

//链表清空
void LinkListClear(LinkList* L);

//创建链表
void LinkListCreate(LinkList* L);

下面用代码具体实现下链表结构：

链表初始化
void LinkListInit(LinkList* L)
{
	L->next = NULL;
	printf("初始化成功，当前为空链表。\n");
}

//链表指定位置插入
void LinkListInsert(LinkList * L, int pos, LinkListData x)
{
	LNode p = L, tail = L;
	int i = 0;
	while (tail->next != NULL)
	{
		i++;
		tail = tail->next;
	}
	if (pos<0||pos-1>i)
	{
		printf("非法插入。\n");
		return;
	}
	i = 0;
	while (i < pos-1)
	{
		p = p->next;
		i++; 
	}
	LNode s = (LNode)malloc(sizeof(LinkList));
	s->data = x;
	s->next = p->next;
	p->next = s;
	printf("插入成功。\n");
}

//链表指定位置删除
void LinkListDelete(LinkList* L, int pos)
{
	LNode p = L,s=NULL,tail=L;//1 2 3 4
	int i = 0,a; 
	a=LinkListLength(L);
	if (a == 0)
	{
		printf("空栈无法删除。\n");
		return;
	}
	while (tail->next != NULL)
	{
		i++;
		tail = tail->next;
	}
	if (pos<0 || pos>i)
	{
		printf("删除错误。\n");
		return;
	}
	i = 0;
	while (i < pos - 1)
	{
		p = p->next;
		i++;
	}
	s = p;
	s = s->next;
	p->next = s->next;
	free(s);
	printf("删除成功.\n");
}

//链表长度
int  LinkListLength(LinkList* L)
{
	LNode tail = L;
	int i = 0;
	while (tail->next != NULL)
	{
		i++;
		tail = tail->next;
	}
	return i;
}

//链表遍历
void LinkListTrough(LinkList* L)
{
	LNode p = L;
	if (p->next==NULL)
	{
		printf("该链表为空表，无法遍历。\n");
		return;
	}
	p = p->next;
	while (1)
	{
		printf("%d ", p->data);
		p = p->next;
		if (p== NULL)
			break;
	}
	printf("\n");
}

//获取指定位置
int LinkListGet(LinkList* L, int pos)
{
	LNode p = L;
	int i = 0;
	while (i < pos)
	{
		p = p->next;
		i++;
	}
	if (pos == i)
	{		printf("该位置没有元素。\n");
	return -999;
}
	return p->data;
}

//链表清空
void LinkListClear(LinkList* L)
{
	LNode p = L;
	p = p->next;
	free(p);
	L->next = NULL;
	printf("链表已清空。\n");
}

//创建链表
void LinkListCreate(LinkList* L)
{
	LNode p = L;
	int i = 0, n = 0,x=0;
	printf("请输入您要创建的链表长度：");
	scanf("%d", &n);
	printf("请输入链表数据用空格隔开：");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &x);
		LNode s = (LNode)malloc(sizeof(LinkList));
		s->data = x;
		s->next = p->next;
		p->next = s;
		p = p->next;
	}
	p->next = NULL;
	printf("创建成功。\n");
}

4.顺序表和链表的优缺点