系列文章目录

第一章 时间复杂度和空间复杂度

第二章 顺序表，列表

第三章 栈和队列

第四章 二叉树

第五章 排序

作者：🎈乐言🎈

简介：🎈大一学生，目前在致力于c/c++/python，高数的学习，有问题尽管问我，关注后私聊！

持续更新专栏：《c进阶》，《数据结构修炼》🚀（优质好文持续更新中）🎈

目录

系列文章目录

文章目录

前言

线性表

各个接口的实现

1.初始化顺序表

2.销毁顺序表

3.检查顺序表容量是否满了

4.顺序表尾插

5.顺序表尾删

6.顺序表头插

7.顺序表头删

8.在顺序表中查找定值

9.在顺序表指定位置插入数据

链表

无头单向循环链表的实现

单链表定义：

 动态申请一个节点

销毁（释放）所有节点

打印单链表

单链表头插

单链表尾删

单链表头部删除

单链表在pos位置之后插入

单链表中删除位置为pos的节点

单链表删除指定pos位置之后的节点

求单链表的长度：

判断但俩表是否为空

总结

前言

在顺序表和链表的学习过程中，相信大家会有一些困惑，因为这里用到了大量结构体和数组的知识，乐言在这里将会对顺序表和单链表进行深刻的讲解，有代码问题，可以后台私信作者！！！！！！！！如果文章有错误，欢迎指正！！！！！！

🚀线性表

#define N 10000
typedef int sldataline;
struct Seqline
{
    sldataline a[N];
    int size;
};

typedef int SLDataType;
typedef struct Seqlist
{
    SLDataTpye *a;
    size_t size;
    size_t capacity
}SeqList;

🚀各个接口的实现

1.初始化顺序表

要防止传进来的指针为空，所以一定要提前加上断言

void SeqListInit(SeqList*psl)
{
    assert(psl!=NULL);
    psl->size=0;
    psl->capacity=0;
}

2.销毁顺序表

依然要记得加上断言，防止传进来的指针是空指针

void SeqListDestory(SeqList*psl)
{
    assert(psl!=NULL);
    free(psl->a);
    psl->size=0;
    psl->capacity=0;
}

首先释放开辟的空间，然后将指针置为空，将数据和空间容量大小都重置为0

3.检查顺序表容量是否满了

如果我们一个个加入数据，这样重复操作对我们来说太过麻烦，所以我们可以一次性扩容两倍，这样能应付大多数情况，两倍是一个折中的方式

void CheckCapacity(SeqList*psl)
{
    assert(psl!=NULL);
    if(psl->size == psl->capacity)
    {
        size_t newcapacity;
        if(psl->capacity == 0)
            newcapacity = psl->capacity = 4;
        else
            newcapacity = 2 * psl->capacity;
    }
    SLDataTpye*p=(SLDataType*)realloc(psl->a,newcapacity*sizeof(SLDataType));//扩容
    if(p == NULL)
          {
               perror("realloc");
                exit(-1);
            }
    psl->p;
    psl->capacity = newcapacity;
}

4.顺序表尾插

void SeqListPushBack(Seqlist*psl,SLDataType x)
{
    assert(psl !=NULL);
    CheckCapacity(psl);
    psl->a[psl->size] =x;
    psl->size++;
}

5.顺序表尾删

void SeqListPopBack(SeqList*psl)
{
    assert(psl->NULL);
    assert(psl->size >0);
    psl->size --;
}

因为我们无法得知SLDataType是什么类型，他随时都可以改，因此我们不能单纯直接将随意赋值为0（psl->a[psl->size-1]=0)

6.顺序表头插

因为顺序表是连续存储的，所以我们在顺序表头部插入的时候，我们要依次挪动数据

void SeqListPushFront(SeqList*psl,SLDType x)
{
    assert(psl);
    CheckCapacity(psl);
    int i = 0;
    for(i=psl->size-1;i>=0;i--)
    {
        psl->a[i+1] = psl->a[i];
    }
    psl->a[0] = x;
    psl->size++;
}

7.顺序表头删

因为顺序表是连续存储的，所以要依次挪动数据

void SeqListPopFront(SeqList* psl)
{
    assert(psl);
    assert(psl->size >0);
    int i =0;
    for(i=1;i<psl->size;i++)
        {
            psl->a[i-1]=psl->a[i];
        }
        psl->size--;
}

依次覆盖即可，然后再把有效数据-1；

8.在顺序表中查找定值

int SeqListFind(const SeqList*psl,SLDataType x)
{
    assert(psl);
    int i = 0;
    for(i=0;i<psl->size;i++)
    {
        if(psl->[i]==x)
        {
            return i;
        }
    }
     return -1;
}

9.在顺序表指定位置插入数据

void SeqListInsert(SeqList*psl,size_t pos,SLDataType x)
{
    assert（psl）；
    assert（pos>=0 && pos <=psl->size);
    CheckCapacity(psl);
    size_t i =0;
    for(i=psl->size;i>pos;i--)
        {
            psl->a[i]=psl->a[i-1];
        }
    psl->a[pos]=x;
    psl->size++;
}

🚀链表

顺序表我们在使用时，虽然下标可以随时访问，但是会出现一系列问题会引起我们的思考

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容       到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空           间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看

🚀无头单向循环链表的实现

第一步我们依然是先新建一个工程：

• SList.h（单链表的类型定义，函数接口声明，引用头文件）
• SList.c（单链表各个接口函数的实现）
• test.c（主函数，测试函数的各个接口功能） 

单链表定义：

单链表类似如图结构

一部分储存结构体的数据，另一部分储存下一块结构体空间的地址

代码如下：

typedef int SLDatatype;//定义单链表数据类型

typedef struct SListNode//定义单链表节点
{
    SLDataType data;//数据空间
    struct SListNode*next；//指针空间
}SListNode;

 动态申请一个节点

代码如下：

SListNode* BuySListNode(SLTDataType x)
{
    SListNode* node=(SListNode*)malloc(sizeof(SListNode));
    if(node == NULL)
    {
        perror("malloc");
        return;
    }
}

销毁（释放）所有节点

我们在这里有一个遍历链表的操作

{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	if (node == NULL)
	{
		perror("malloc");
		return;
	}
	node->data = x;
	node->next = NULL;
}
void SListDestory(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
	}
	*pphead = NULL;
}

最后不能忘了置空指针

打印单链表

void SListPrint(SListNode* phead)
{
	SListNode* ptr = phead;
	while (ptr != NULL)
	{
		printf("%d->", ptr->data);
		ptr = ptr->next;
	}
	printf("NULL\n");
}

单链表尾插

下面是一个明显的错误

 代码看似逻辑清晰，其实问题暴露无遗。此处的指针传参，相当于把plist指针变量的值拷贝给phead给phead赋值newhead，phead的值改变是不会影响plist

这种写法会导致一个问题：         

• 当链表为空时，我们需要改变plist的指向，让他指向第一个节点，然而初始值plist和phead都指向NULL，调用函数后，phead指向了新的节点，但是plist还是指向NULL

• 问题出现，我们又该如何解决？

plist指向的是第一个节点的指针，想要在函数中改变plist的值（指向），必须把plist指针进行指针传参，因为plist原本就是一级指针，我们要想改变他，我们只能取他的地址进行传参

在函数中，我们想要改变int的值，就要传递int*,当我们想要传递int*的时候，我们就要传递int**......

正确写法是通过二级指针传参，改变plist的指向

单链表为空的时候，plist直接指向新节点

单链表不为空，会找到尾部节点，然后将尾部节点的next指向新节点！！！

//单链表尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);
	SListNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
		*pphead = newnode;
	else if (**pphead != NULL)
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

单链表头插

头插具体实现算法如图：

新数据的next指向plist指向的节点

 代码实现：

void SListPushFront(SListNode* pphead, SLTDataType x)
{
	assert(pphead);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	pphead = *newnode;
}

单链表尾删

思想：

1：找到链表尾节点的上一个节点。

2：双指针，分别找到链表尾节点和它上一个节点

如图所示：

•  当单链表只有一个节点时，删除节点，plist指向NULL
• 而当单链表有多个节点时，先找到单链表尾节点的前一个节点，删除，然后将该节点的next指向NULL
• 可能会改变plist的指向，所以我们要用二级指针接受

代码如下：

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* tail = *pphead;
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

如果pphead为空，那么直接释放＋置空

如果pphead不为空，那么直接判断下一个节点是否为空为空则置空，不为空则继续判断

思路2代码实现：

void SListPopBack(SListNode** phead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* tail = *pphead;
	SListNode* prev = *pphead;
	while (tail->next)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	prev->next = NULL;
}

单链表头部删除

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(**pphead);
	SListNode* cur = *pphead;
	*pphead = cur->next;
	free(cur);
	cur = NULL;
}

将*pphead移向第二个节点即可。

在单链表中查找指定点的节点

SListNode* SListFind(SListNode** pphead, SLDataType x)
{
	SListNode* cur = *pphead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

单链表在pos位置之后插入

 我们只需在pos位置的next指向一个新开辟的地址，新地址的next指向原来的下一个地址

代码实现：

void SListInsertAfter(SListNode* pos, SLDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

单链表中删除位置为pos的节点

考虑到pos位置可能为第一个节点，所以我们有必要选择进行语句

代码如下：

void SListDel(SListNode** pphead,SListNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
			prev = prev->next;
	}
	prev->next = pos->prev;
	free(pos);
	pos = NULL;
}

单链表删除指定pos位置之后的节点

图示：

代码实现： 

此处我们要定义一个新的指针，来存放pos的下一个节点的地址

void SListDelAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* posnext = pos->next;
	pos->next = pos->next->next;
	free(posnext);
}

求单链表的长度：

遍历寻找是否为空即可

int SListSize(SListNode* phead)
{
	int size = 0;
	SListNode* cur = phead;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

判断但俩表是否为空

bool SListEmpty(SListNode* phead)
{
	return phead == NULL;
}

🚀总结

本文具体写了顺序表和单链表增删查改的一系列操作，希望各位同志们也要动手操作一下，这样才能融会贯通，熟稔于心