目录

1.线性表

​编辑 2.顺序表

 2.2接口实现

2.3 顺序表的问题和思考

3.链表

3.1 链表的概念和结构

3.2 链表的分类

3.3 不带头单向非循环链表的实现

3.4 带头双向循环链表的实现

 3.5   链表和顺序表的区别

1.线性表

线性表(linear list)是有n个相同特性的元素组成的有限序列，在逻辑上是线性结构，也就是连续的一条直线；但是在物理结构上，不一定是连续的。

常见的线性表有：

顺序表、链表、栈、队列、字符串....

 2.顺序表

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

顺序表一般分为：

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

define N 6
typedef int SeqListDataType;

typedef struct SeqList
{
	SeqListDataType arr[N];//创建数组
	int size;//有效元素个数
}SL;

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

typedef int SeqListDataType;

typedef struct SeqList
{
	SeqListDataType* ps;//创建指向动态开辟数组的指针
	int size;//有效元素个数
	int capicity;//数组的容量大小
}SL;

 2.2接口实现

        由于静态数据表只适用与确定需要存储多少数据的情况，实际中一般使用动态数据表，根据数据的多寡来扩容空间，所以下面实现动态顺序表。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SeqListDataType;

typedef struct SeqList
{
	SeqListDataType* ps;
	int size;
	int capicity;
}SL;

void SeqLIstInst(SL* ps);               //初始化

void CheckCapacity(SL* ps);	            //判断容量是否足够

void SeqLIstPushBack(SL* ps, int size);//尾插

void SeqListPrint(SL* ps);				//打印顺序表

void SeqListPopBack(SL* ps);			//顺序表尾删

void SeqListPushFront(SL* ps, int size);//顺序表头插

void SeqListPopFront(SL* ps);	        //顺序表头删

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

void SeqListInsert(SL* ps, int pos,int x);		//指定位置插入

void SeqListErase(SL* ps, int pos);				//指定位置pos删除

void SeqListDestory(SL* ps);					//销毁数据表


//-------------------------------------------------------------------------------------

void SeqLIstInst(SL* ps)						//初始化
{
	ps->ps = (SeqListDataType*)malloc(sizeof(SeqListDataType) * 4);
	if (ps->ps == NULL)
	{
		printf("申请空间失败\n");
			exit(-1);
	}
	ps->size = 0;
	ps->capicity = 4;
}

void CheckCapacity(SL* ps)				//检查顺序表满了没
{
	assert(ps);
	if (ps->capicity == ps->size)
	{
		ps->capicity *= 2;
		ps->ps=(SeqListDataType*)realloc(ps->ps	, ps->capicity*sizeof(SeqListDataType));
		if (ps->ps == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
	}

}
void SeqLIstPushBack(SL* ps, int size)			//尾插
{
	assert(ps);
	CheckCapacity(ps);	//检查顺序表满了没
	ps->ps[ps->size] = size;
	ps->size++;
}

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

void SeqListPopBack(SL* ps)			//顺序表尾删
{
	assert(ps);
	ps->size--;
}

void SeqListPushFront(SL* ps, int size)	//顺序表头插
{
	assert(ps);
	CheckCapacity(ps);	//检查顺序表满了没
	int tmp = ps->size-1;
	while (tmp>=0)
	{
		ps->ps[tmp+1] = ps->ps[tmp];
		tmp--;
	}
	ps->ps[0] = size;
	ps->size++;
}
void SeqListPopFront(SL* ps)				//头删
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		ps->ps[i] = ps->ps[i + 1];
	}
	ps->size--;
}

void SeqListFind(SL* ps, int x)				//顺序表查找
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->ps[i] == x)
		{
			printf("找到了\n");
			break;
		}
	}
	if (i == ps->size)
	{
		printf("顺序表没有这个数\n");
	}
}

void SeqListInsert(SL* ps, int pos,int x)//指定位置插入
{
	assert(ps);
	CheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos-1)
	{
		ps->ps[end + 1] = ps->ps[end];
		end--;
	}
	ps->ps[pos - 1] = x;
	ps->size++;
}

void SeqListErase(SL* ps, int pos)//指定位置删除
{
	assert(ps);
	int end = pos - 1;
	while (end < ps->size)
	{
		ps->ps[end] = ps->ps[end + 1];
		end++;
	}
	ps->size--;

}

void SeqListDestory(SL* ps)					//销毁数据表
{
	assert(ps);
	free(ps->ps);
	ps->ps = NULL;
	ps->capicity = 0;
	ps->size = 0;
}

2.3 顺序表的问题和思考

实现了一个顺序表，发现了什么？

问题：

1.头部的插入删除时间复杂度是O(N)，因为要挪动数据。

2.可能会扩容失败，继而重新开辟新的空间，将原有空间数据挪到新空间中

3.增容一般是增容二倍，那么势必会有空间上的浪费

思考：

那么怎么解决上述问题？

下面用链表的结构来解决

3.链表

3.1 链表的概念和结构

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

 1.从上图中可以看到，链式结构在逻辑上是连续的，但是在物理上并不一定连续

2.现实中的结点一般都是在堆上申请出来的

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

3.2 链表的分类

实际中的链表有多种结构，以下结构组合起来就有8种链表结构。

1.单向或双向

2.带头或不带头

3.循环或非循环

 虽然吧，有这么多的链表结构，但实际中最常用的也就是两种结构：

无头单向非循环链表：

 1.无头单向循环链表，结构简单，一般不会用来单独存储数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等

   

带头双向循环带头：

 2.带头双向循环链表：结构最复杂，一般用来单独存储数据。实际中使用的数据结构，都是带头双向循环链表。

3.3 不带头单向非循环链表的实现

//不带头+单向+非循环链表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SListTypeData;
typedef struct SListNode			//定义一个单链表结构
{
	struct SListNode* next;
	SListTypeData x;
}SListNode;
//函数声明
void SListPustBack(SListNode** pphand, SListTypeData x);	//尾插


void SListPopBack(SListNode** pphand);						//尾删

void SListPrint(SListNode* phand);							//打印

void SListPushFront(SListNode** pphand, SListTypeData x);	//头插

void SListPopFront(SListNode** pphand);						//头删

SListNode* SListFind(SListNode* phand, SListTypeData x);			//查找链表中值为x的链表

void SListInsertafter(SListNode* pos, SListTypeData x);//在pos后面的位置插入x

void SListEraseafter(SListNode* pos);//在pos后面的位置删除

-----------------------------------------------------------------------------------

SListNode* BuyPListNode(SListTypeData x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		exit(-1);
	}
	newnode->x = x;
	newnode->next = NULL;
	return newnode;
}
void SListPustBack(SListNode** pphand, SListTypeData x)	//尾插
{
	SListNode* newnode= BuyPListNode(x);
	if (*pphand == NULL)
	{
		*pphand = newnode;
		return;
	}
	SListNode* pcur = *pphand;
	while (pcur->next != NULL)
	{
		pcur = pcur->next;
	}
	pcur->next = newnode;
}

void SListPrint(SListNode* phand)							//打印
{
	if (phand == NULL)
	{
		return;
	}
	SListNode* p = phand;
	while (p != NULL)
	{
		printf("%d -> ", p->x);
		p = p->next;
	}
	printf("NULL\n");
}

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

void SListPushFront(SListNode** pphand, SListTypeData x)	//头插
{
	SListNode* newnode= BuyPListNode(x);
	if (*pphand == NULL)
	{
		*pphand = newnode;
		return;
	}
	else
	{
		newnode->next = *pphand;
		*pphand = newnode;
	}
}

void SListPopFront(SListNode** pphand)						//头删
{
	assert(*pphand != NULL);
	if ((*pphand)->next == NULL)
	{
		free(*pphand);
		*pphand = NULL;
	}
	else
	{
		SListNode* p = *pphand;
		*pphand = (*pphand)->next;
		free(p);
	}
}

SListNode* SListFind(SListNode* phand, SListTypeData x)			//查找链表中值为x的链表
{
	if (phand == NULL)
	{
		printf("链表为空，找不到\n");
		return NULL;
	}
	else
	{
		while (phand != NULL)
		{
			if (phand->x == x)
			{
				printf("值为%d的地址为:%p\n", x, phand);
				return phand;
			}
			phand = phand->next;
		}
		printf("链表没有该数\n");
		return NULL;
	}
}

void SListInsertafter(SListNode* pos, SListTypeData x)//在pos的位置插入x
{
	if (pos == NULL)
	{
		return;
	}
	SListNode* newnode = BuyPListNode(x);
	newnode->next= pos->next;
	pos->next = newnode;

}

void SListEraseafter(SListNode* pos)//在pos后面的位置删除
{
	assert(pos != NULL);
	SListNode* p = pos->next;
	pos->next = pos->next->next;
	free(p);
}

3.4 带头双向循环链表的实现

//带头+双向+循环链表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int ListNodeTypeDate;

typedef struct ListNode//带头双向循环链表结构体 
{
	ListNodeTypeDate date;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* ListInit();//初始化

void ListPushBack(ListNode* phead,ListNodeTypeDate x);//尾插

void ListPopBack(ListNode* phead);//尾删

void ListPushFront(ListNode* phead, ListNodeTypeDate x);//头插

void ListPopFront(ListNode* phead);//头删

ListNode* ListFind(ListNode* phead, ListNodeTypeDate x);//查找

void ListInsert(ListNode* pos, ListNodeTypeDate x);//在pos的前面进行插入

void ListErace(ListNode* pos);//删除pos位置的结点

void ListPrint(ListNode* phead);//打印
-----------------------------------------------------------------------------------------
ListNode* ListInit()//初始化
{
	ListNode* phead=(ListNode*)malloc(sizeof(ListNode));
	assert(phead);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}


void ListPushBack(ListNode* phead, ListNodeTypeDate x)//尾插
{
	assert(phead);
	ListNode* cur = phead->prev;//将链表最后一个记录
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	assert(tmp);
	tmp->date = x;
	cur->next = tmp;//将新结点连接到最后一个结点后面
	tmp->prev = cur;//新节点的前一个结点是原来链表的最后一个结点
	tmp->next = phead;//新节点的后一个是头结点
	phead->prev = tmp;//头结点的前一个改变为新的尾结点

}


void ListPopBack(ListNode* phead)//尾删
{
	assert(phead);
	ListNode* cur = phead->prev;
	phead->prev = phead->prev->prev;
	phead->prev->next = phead;
	free(cur);
}



void ListPushFront(ListNode* phead, ListNodeTypeDate x)//头插
{
	assert(phead);
	ListNode* cur = phead->next;//将原来的头结点存储好
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	assert(tmp);
	tmp->date = x;
	phead->next = tmp;//头结点变为新节点
	tmp->prev = phead;//新结点指向的前一个变为最后一个结点
	tmp->next = cur;//新节点指向的下一个结点是原来的头结点
	cur->prev = tmp;//原来结点的头结点的前一个指向新的头结点
}

void ListPopFront(ListNode* phead)//头删
{
	assert(phead);
	ListNode* cur = phead->next;
	phead->next = phead->next->next;
	phead->next->prev = phead;
	free(cur);
}

ListNode* ListFind(ListNode* phead, ListNodeTypeDate x)//查找
{
	assert(phead);
	ListNode* cur = phead;
	while (cur->date != x)
	{
		cur = cur->next;
	}
	if (cur->date == x)
	{
		printf("找到了，地址是%p\n", cur);
		return cur;
	}
	else
	{
		printf("没找到\n");
		return NULL;
	}
}


void ListInsert(ListNode* pos, ListNodeTypeDate x)//在pos的前面进行插入
{
	assert(pos);
	ListNode* cur = pos->prev;//将pos位置的前一个结点记录
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	assert(tmp);
	tmp->date = x;
	pos->prev = tmp;
	cur->next = tmp;
	tmp->next = pos;
	tmp->prev = cur;
}

void ListErace(ListNode* pos)//删除pos位置的结点
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}


void ListPrint(ListNode* phead)//打印
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}

 3.5   链表和顺序表的区别

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

# 链表 # 数据结构 # 散列表
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区