C++线性表

熊135

361人浏览 · 2026-04-02 13:51:33

熊135 · 2026-04-02 13:51:33 发布

线性表List：具有相同数据类型的n(n>=0)个数的有限序列。

一般表示形式：L = （a1，a2，... ，ai，... ，an）
a1是第一个数据元素，称为表头元素，an是最后一个数据元素，称为表尾元素。除第一个元素外，每一个元素有且只有一个前驱。除最后一个元素外，每一个元素有且只有一个后驱。

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指储存结构。

顺序表：线性表的顺序存储又称顺序表。用一组地址连续的存储单元依次存储线性表中的数据元素的线性表。

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

#include<stddef.h>//size_t是无符号整数类型，通常用于表示对象的大小或数组的索引等。它的定义在stddef.h头文件中。
#include<stdio.h>

typedef struct SeqList{
	int arr[100];//静态分配，数组长度固定
	size_t size;//当前顺序表的长度
}SeqList;//给结构体起别名，后续使用时可以直接写 SeqList，不用写 struct SeqList

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

typedef struct SeqList{
	int* a;//顺序表的数组指针，指向存储元素的内存空间
	int size;//当前顺序表中元素的数量
	int capacity;//当前分配的内存空间可以容纳的元素数量
}SeqList;

C语言malloc，free函数；C++new,delete关键字。malloc返回一篇连续的存储空间的指针

(int*)malloc(sizeof(int)*10)

静态顺序表适用于知道存多少数据的场景。所以一般使用动态顺序表。

//初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
 
//销毁
void SLDestory(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 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));
		if (tmp == NULL)
		{
			perror("sealist newcapacity realloc fail");
			exit(-1);
		}
		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);
	
	for (int end = psl->size - 1; end >= 0; end--)
	{
		psl->a[end + 1] = psl->a[end];
	}
	psl->size++;
	psl->capacity++;
}
 
//尾删
void SLPopBack(SL* psl)
{
	assert(psl);
	assert(psl->size > 0);
	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是下标，插入
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--;
}
 
//按值查找
int SLFind(SL* psl, SLDataType x)
{
	assert(psl);
 
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
}
 
//表长
int SLSize(SL* psl)
{
	assert(psl);
 
	return psl->size;
}
 
//判空
bool SLEmpty(SL* psl)
{
	if (psl == NULL)
		return true;
	else
		return false;
}

顺序表的问题及思考

中间/头部的插入删除，时间复杂度为O(N)
增容需要申请新空间，拷贝数据，释放就空间。有不小的消耗。
增容一般呈两倍增长，可能造成空间浪费。

解决以上问题引出链表结构，也是线性表的一种。

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

单链表：线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

typedef struct SlistNode{
	int data;
	struct SlistNode* next;
}SlistNode;
//链表的节点处理存储元素自身的信息外，还需要存放一个后继的指针。

class Node{
public:
	int data;
	Node* next;
	Node(int x):data(x),next(NULL){}//构造函数，初始化data为x，next为NULL
};

为了操作上的方便，在单链表第一个结点前附加一个结点，成为头结点。头结点的指针域指向线性表的第一个元素的结点。

void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
SLNode* CreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
 
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	//assert(pphead);
 
	SLNode* newnode = CreateNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
 
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
 
void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
 
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
 
 
}
 
void SLTPopFront(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
 
	SLNode* tmp = *pphead;
	*pphead = (*pphead)->next;
 
	free(tmp);
	
}
 
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x) return cur;
		else cur = cur->next;
	}
	return NULL;
}
 
void SLTInser(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	//严格限定pos一定是链表中的一个有效节点
	assert(pphead);
	assert(pos);
	assert(*pphead);
 
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
 
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
 
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
 
 
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);
 
	newnode->next = pos->next;
	pos->next = newnode;
}
 
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);
 
	SLNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(tmp);
	tmp = NULL;
}
 
void STLDestory(SLNode** pphead)
{
	assert(pphead);
 
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

双链表:双链表结点中有两个指针，分别指向其前驱结点和后继结点。

typedef struct ListNode
{
	struct ListNode* next;//后继结点指针
	struct ListNode* prev;//前驱结点指针
	int data;
}LTNode;

循环链表：最后一个结点的指针不是NULL，改为指向头结点，从而使链表形成一个环。在循环双链表中，头结点的prve指针还要指向表尾结点。

带头双向循环链表

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		//return NULL;
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
 
	return node;
}
 
LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}
 
void LTDestroy(LTNode* phead);
 
void LTPrint(LTNode* phead)
{
	assert(phead);
 
	printf("<=head=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
bool LTEmpty(LTNode* phead)
{
	assert(phead);
 
	/*if (phead->next == phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/
 
	return phead->next == phead;
}
 
 
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	//LTNode* newnode = BuyListNode(x);
	//LTNode* tail = phead->prev;
 
	//// phead            tail  newnode
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;
 
	LTInsert(phead, x);
}
 
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
 
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
}
 
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	//LTNode* newnode = BuyListNode(x);
	//LTNode* first = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;
 
	//newnode->next = first;
	//first->prev = newnode;
 
	// 㻻˳
	//newnode->next = phead->next;
	//phead->next->prev = newnode;
 
	//phead->next = newnode;
	//newnode->prev = phead;
 
	LTInsert(phead->next, x);
}
 
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	//....
}
 
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// prev newnode pos
 
	prev->next = newnode;
	newnode->prev = prev;
 
	newnode->next = pos;
	pos->prev = newnode;
}

	顺序表	链表
存取 (读写) 方式	顺序表可以顺序存取，也可以随机存取	链表只能从表头顺序存取元素
逻辑结构与物理结构	采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻	而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的
查找、插入和删除操作	对于按值查找，顺序表无序时，两者的时间复杂度均为 O(n)；顺序表有序时，可采用折半查找, 此时的时间复杂度为 O(log ₂n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1) 顺序表的插入、删除操作，平均需要移动半个表长的元素	链表按值查找的平均时间复杂度为O(n) 链表的插入、删除操作，只需修改相关结点的指针域即可
空间分配顺序	存储在静态存储分配情形下，需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败	链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

栈：只允许在一端进行插入和删除操作的线性表

空栈：不含任何数据元素的栈

栈顶：允许插入和删除的一端；插入：入栈、进栈、压栈。删除：出栈、弹栈

栈底：另一端

特性：先进后出。。。

队列：只允许在表的一端插入，另一端删除的线性表；允许插入的一端叫队尾，允许删除的一端叫队头。

字符串：简称串，是由零个或多个字符组成的有限序列

广义表：n ( >=0 )个表元素组成的有限序列

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

AI编程SubAgent模板大全（适配Spec驱动开发场景）

本文提供了一套完整的AI编程SubAgent模板大全，专为Spec驱动开发场景设计。包含12个标准化YAML模板，覆盖从需求评审到上线运维的全流程开发环节。核心特点：严格遵循Spec驱动开发的递进逻辑（原型→产品Spec→开发Spec）包含需求评审、需求转代码、开发设计、设计评审等关键阶段模板每个模板明确分工边界，强化特定能力（如需求评审SubAgent具备原型解析、风险预判等5大核心能力