前言

hello，大家好，今天我们来分享关于数据结构的第二篇博文《红玫瑰与白玫瑰之争》。还请大家继续支持。看到这篇博文的标题，你也许会感到懵懵的，其实我在这篇博文里主要要介绍的是关于顺序表和链表的知识，那么为什么会有这样一个题目呢？希望你可以耐心读完本文，并且从中找到答案。

一、听说你还不知道啥是线性表？

1.线性表的概念

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

2.线性表的特点

有头有尾。即必存在唯一的一个头元素，也必存在唯一的一个尾元素。
除最后一个元素外，均有唯一后件，除第一个元素外，均有唯一前件。

3.线性表的分类

看完以上介绍，你也许对线性表有了初步的了解，也有了初步的迷茫，哈哈哈。莫慌，我们继续往下了解两个典型的线性表，“红玫瑰”顺序表和“白玫瑰”链表。

二、红玫瑰——顺序表

1.概念及结构

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

静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟数组存储
注意：顺序表的逻辑结构和物理结构是一致的。

2.顺序表的静态存储

我们先来看一个顺序表的静态存储的例子

// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
   
 SLDataType array[N]; // 定长数组
size_t size; // 有效数据的个数 
}SeqList;

根据这个例子我们可以看出来，静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。这显然存在着弊端，不能适应多种多样的灵活场景，于是，我们在实际中，多用动态存储。

3.顺序表的动态存储

1.举例

我们先来看一下动态存储的例子

// 顺序表的动态存储
typedef struct SeqList
{
   
 SLDataType* array; // 指向动态开辟的数组
 size_t size ; // 有效数据个数
 size_t capicity ; // 容量空间的大小
}SeqList;

我们发现，利用指针，指向动态开辟的数组，我们便能根据需求，开辟出合适大小的空间，这更能广泛地运用在我们的实际操作中。
下面，我们来分享一个利用动态表来首先增删查改的程序的代码：

2.利用动态表实现增删查改

首先，上头文件

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

// 静态的顺序表
//#define N 100
//struct SeqList
//{
   
// int a[N];
// int size;
//};

//typedef ContactInfo SeqDataType;
typedef int SeqDataType;

typedef struct SeqList
{
   
	SeqDataType* a;
	int size;      // 有效数据的个数
	int capacity;  // 容量
}SeqList, SEQ;

// 内存中个管理数据的结构增删查改的借口

// 头插尾插，头删尾删
void SeqListInit(SeqList* pq);
void SeqListDestory(SeqList* pq);

void SeqListPrint(SeqList* pq);

//void SeqListPushBack(SEQ seq, SeqDataType x);
void SeqListPushBack(SeqList* pq, SeqDataType x);
void SeqListPushFront(SeqList* pq, SeqDataType x);
void SeqListPopBack(SeqList* pq);
void SeqListPopFront(SeqList* pq);

接下来，上函数实现的文件

#include "SeqList.h"

void SeqListInit(SeqList* pq)
{
   
	//assert(pq != NULL);
	assert(pq);

	pq->a = NULL;
	pq->size = pq->capacity = 0;
}

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

	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}

void SeqListPrint(SeqList* pq)
{
   
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
   
		printf("%d ", pq->a[i]);
	}
	printf("\n");
}

void SeqCheckCapacity(SeqList* pq)
{
   
	// 满了，需要增容
	if (pq->size == pq->capacity)
	{
   
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
		if (newA == NULL)
		{
   
			printf("realloc fail\n");
			exit(-1);
		}

		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
   
	assert(pq);

	SeqCheckCapacity(pq);

	pq->a[pq->size] = x;
	pq->size++;
}

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
   
	assert(pq);

	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= 0)
	{
   
		pq->a[end + 1] = pq->a[end];
		--end;
	}

	pq->a[0] = x;
	pq->size++;
}

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

	--pq->size;
}

void SeqListPopFront(SeqList* pq)
{
   }

最后，上test文件

#include "SeqList.h"

void TestSeqList1()
{
   
	SeqList s;
	SeqListInit(&s);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, 0);
	SeqListPushFront(&s, 0);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);


	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListDestory(&s);
}

int main()
{
   
	TestSeqList1();

	return 0;
}

4.顺序表的问题及思考

我们知道，动态表相对于静态表可以满足我们对于灵活运用空间的要求，那么，动态表就真的十分完美而不存在问题了吗？我们来看看以下思考：

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。并且一次扩容过少，大量插入数据时，需要频繁增容。一次扩容过多，则会造成空间浪费。增容是有代价的。
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

那么怎么解决这些问题呢？
我们来看另一种类型的顺序表——链表。

三、白玫瑰——链表

1、链表的概念：

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

2、链表的分类

链表多种多样，以下是一些分类，并且这些分类还可以组合。

虽然链表类型多种多样，乱花渐欲迷人眼，但是在实际中，我们最常用的是两种链表：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

3、链表的实现

1、无头+单向+非循环链表增删查改实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
   
 SLTDateType data;
 struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);

2、带头+双向+循环链表增删查改实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
   
 LTDataType _data;
 struct ListNode* _next;
 struct ListNode* _prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)

四、红玫瑰白玫瑰之争

张爱玲说“也许每一个男子全都有过这样的两个女人，至少两个。娶了红玫瑰，久而久之，红的变了墙上的一抹蚊子血，白的还是“床前明月光”；娶了白玫瑰，白的便是衣服上的一粒饭粘子，红的却是心口上的一颗朱砂痣。”
我说：“也许每个程序员都曾面对过这样两种线性表，至少两个。用了顺序表，支持随机访问，久而久之，发现它中间或前面部分的插入删除时间复杂度O(N) 增容的代价比较大；用了链表，任意位置插入删除时间复杂度为O(1) 没有增容问题，插入开辟的空间，却发现它不支持随机访问。

顺序表和链表的区别和联系

1、顺序表

2、链表

一个人可能无法同时拥有红玫瑰和白玫瑰，但是一个程序员却可以同时拥有线性表和链表，人生中有很多猝不及防的错过，但程序中，代码却可以让你有拥有一切的可能！！！

五、总结

好了，以上就是今天的分享了，希望对大家有所帮助，如有错漏，也欢迎大家批评指正。

数据结构——红玫瑰与白玫瑰之争

文章目录

前言