[数据结构]——顺序表和链表

小李很执着

发布于 2024-06-15 08:27:24

9700

代码可运行

文章被收录于专栏：学习笔记学习笔记

运行总次数：0

代码可运行

💗1.线性表💗：只能从头开始连续存储

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

💗2.顺序表💗

💙1.概念及结构❤️

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为： 1. 静态顺序表: 使用定长数组存储元素。（不是很实用，了解就行）

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

❤️ 2. 接口实现💙

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

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

void SLInit(SL* psl);
void SLDestroy(SL* psl);

void SLPrint(SL* psl);
void SLCheckCapacity(SL* psl);
// 头尾插入删除
void SLPushBack(SL* psl, SLDataType x);
void SLPushFront(SL* psl, SLDataType x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);
// 任意下标位置的插入删除
void SLInsert(SL* psl, int pos, SLDataType x);
void SLErase(SL* psl, int pos);

void SLInit(SL* psl)//顺序表初始化
{
	assert(psl);//断言，传入的指针不能为空，报错:显示错误行号，规避错误

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

void SLDestroy(SL* psl)//销毁
{
	assert(psl);

	if (psl->a != NULL)
	{
		free(psl->a);
		//free崩溃的两种可能性：
		//1.传入的指针释放的位置不对
		//2.空间访问有越界
		psl->a = NULL;
		psl->size = 0;
		psl->capacity = 0;
	}
}

void SLPrint(SL* psl)//打印
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

void SLCheckCapacity(SL* psl)//检查空间是否足够，不够就扩容
{
	assert(psl);

	if (psl->size == psl->capacity)
	{
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//扩容
		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);//sizeof(SLDataType):整型4个字节
		//使用tmp是为了防止因为扩容失败使得原有空间被覆盖
		if (tmp == NULL)
		{
			perror("realloc fail");//若开辟空间失败就打印错误（内存不足或者申请空间过大）
			return;
		}

		psl->a = tmp;
		psl->capacity = newCapacity;
	}
}

void SLPushBack(SL* psl, SLDataType x)//尾插
{
	assert(psl);

	SLCheckCapacity(psl);

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

void SLPushFront(SL* psl, SLDataType x)//头插
{
	assert(psl);

	SLCheckCapacity(psl);

	// 挪动数据
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}

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

void SLPopBack(SL* psl)//尾删
{
	assert(psl);

	// 空
	// 温柔的检查
	/*if (psl->size == 0)
	{
		return;
	}*/

	// 暴力检查
	assert(psl->size > 0);//防止因为操作，顺序表为空了还在删

	//psl->a[psl->size - 1] = -1;
	psl->size--;
}

void SLPopFront(SL* psl)//头删
{
	assert(psl);

	// 暴力检查
	assert(psl->size > 0);

	int begin = 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}

// 注意pos是下标
// size是数据个数，看做下标的话，他是最后一个数据的下一个位置
void SLInsert(SL* psl, int pos, SLDataType x)//任意位置的插入
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);

	SLCheckCapacity(psl);

	// 挪动数据
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}

void SLErase(SL* psl, int pos)//任意位置的删除
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);

	// 挪动覆盖
	int begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}

3.顺序表的问题

1、尾部插入效率还不错,头部或者中间插入删除,需要挪动数据,效率低下 2、满了以后只能扩容。扩容是有一定的消耗的;扩容一般是存在一定的空间浪费(假设空间是100满了,扩容到200,只需要插入120个数据,有80个就浪费了) 一次扩得越多,可能浪费越多一次扩的少了,那么可能会频繁扩容

💗3.链表💗

❤️1.链表的概念及结构💙

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

现实中数据结构中

❤️2. 链表的分类💙

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

💕1. 单向或者双向💕

💕2. 带头或者不带头💕

💕3. 循环或者非循环💕

💕4.常用还是两种结构💕

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

❤️3. 链表的实现💙

// 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);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

#include"slist.h"
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    if (newnode == NULL)
    {
        printf("内存分配失败\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
    assert(plist);
    SListNode* cur = plist;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL   \n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
    SListNode* newnode = BuySListNode(x);
    if (*pplist == NULL)
    {
        *pplist = newnode;
    }
    else
    {
        SListNode* current = *pplist;
        while (current->next != NULL)
        {
            current = current->next;
        }
        current->next = newnode;
    }

}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pplist;
    *pplist = newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
    assert(*pplist);
    if ((*pplist)->next == NULL)//一个
    {
        free(*pplist);
        *pplist = NULL;
    }
    else//多个
    {
        SListNode* cur = NULL;
        SListNode* cut = *pplist;
        while (cut->next != NULL)
        {
            cur = cut;
            cut = cut->next;
        }
        free(cut);
        cut = NULL;
        cur->next = NULL;
    }
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
    assert(*pplist);
    SListNode* temp = (*pplist)->next;
    free(*pplist);
    *pplist = temp;
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
    SListNode* cur = plist;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
//在单链表中，每个节点只能指向下一个节点，无法直接访问前一个节点。
void SListInsertAfter(SListNode* pos, SLTDateType x)//在pos位置之后插入x
{
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
//在单链表中，删除一个节点需要找到要删除节点的前一个节点，
//然后将前一个节点的next指针指向要删除节点的下一个节点，跳过要删除节点。
//而要找到要删除节点的前一个节点，需要遍历单链表，时间复杂度为O(n)，
//其中n是链表的长度。 如果要删除pos位置的节点，就需要先找到pos位置的前一个节点，
//然后将前一个节点的next指针指向pos位置的节点的下一个节点，即删除pos位置的节点。
//这个操作同样需要遍历单链表，时间复杂度为O(n)。 
//而如果要删除pos位置之后的节点，只需要将pos位置的节点的next指针指向pos位置的下下个节点，
//跳过pos位置之后的节点。这个操作只需要访问pos位置的节点和pos位置的下一个节点，时间复杂度为O(1)。
//因此，为了减少时间复杂度，在单链表中通常选择删除pos位置之后的节点，而不是删除pos位置的节点。
///这样可以在常数时间内完成删除操作。
void SListEraseAfter(SListNode* pos)//删除pos位置之后的值
{
    assert(pos);
    assert(pos->next);
    SListNode* temp = pos->next;
    pos->next = pos->next->next;
    free(temp);
    temp = NULL;
}

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
    assert(pos);
    assert(*pphead);
    assert(pphead);
    if (*pphead == pos)
    {
        SListPushFront(pphead,x);
    }
    else
    {
        SListNode* temp = *pphead;
        while (temp->next != pos)
        {
            temp = temp->next;
        }
        SListNode* newnode = BuySListNode(x);
        temp->next = newnode;
        newnode->next = pos;
    }
}
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{
    assert(pos);
    assert(*pphead);
    assert(pphead);
    if (*pphead == pos)
    {
        SListPopFront(&pphead);
    }
    else
    {
        SListNode* temp = *pphead;
        while (temp->next != pos)
        {
            temp = temp->next;
        }
        temp->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SLTDestroy(SListNode** pphead)//清空
{
    assert(pphead);
    SListNode* current = *pphead;
    while (current)
    {
        SListNode* next = current->next;
        free(current);
        current = next;
    }
    *pphead = NULL;
}

❤️4.双向链表的实现💙

// 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 ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);

#include"List.h"
// 创建返回链表新的结点.
ListNode* ListCreate(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode ->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//创建双向链表头结点
ListNode* Headnode()
{
	ListNode* phead = ListCreate(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d <-> ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* tail = pHead->prev;
	ListNode* newnode = ListCreate(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pHead;
	pHead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);
	ListNode* cur = pHead->prev;
	ListNode* tail = cur->prev;
	tail->next = pHead;
	pHead->prev = tail;
	free(cur);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = ListCreate(x);
	ListNode* tail = pHead->next;
	tail->prev = newnode;
	pHead->next = newnode;
	newnode->prev = pHead;
	newnode->next = tail;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	ListNode* tail = pHead->next;
	ListNode* tailnext = tail->next;
	free(tail);
	pHead->next = tailnext;
	tailnext->prev = pHead;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode*cur= pHead->next;
	while (cur!=pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;

}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = ListCreate(x);
	ListNode* tail = pos->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pos;
	pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posnext = pos->next;
	ListNode* posprev = pos->prev;
	free(pos);
	posprev->next = posnext;
	posnext->prev = posprev;
}

💗4.顺序表和链表的区别和联系

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低