C/C++实现线性顺序表：核心原理与完整示例代码

线性顺序表简介

线性顺序表（Sequential List）是一种基于数组实现的线性数据结构。其核心特征在于逻辑上相邻的元素在物理存储位置上也必然相邻。这种设计使得顺序表能够通过下标实现 $O(1)$ 复杂度地直接访问和修改任意位置的元素，极大地提高了读取效率。

然而，顺序表的局限性同样明显。由于其物理空间的连续性，当需要在中部或头部插入/删除元素时，必须移动后续所有元素以保持紧凑性，这使得插入和删除操作的平均时间复杂度退化为 $O(n)$。此外，若初始分配空间不足，还需要重新分配更大的内存块并迁移数据，这进一步增加了开销。

C语言实现代码

在C语言中，通常使用 struct 来封装顺序表的结构，利用 malloc 和 realloc 函数进行堆内存的动态管理。以下是完整的顺序表操作实现代码：

#include<stdio.h>
#include<stdlib.h>

typedef struct 
{
	int* Array;
	int Length;
} Sequential_List;

// 创建空顺序表
Sequential_List Sequential_List_Create(void) 
{
	return (Sequential_List){0}; // 初始化Length为0，Array为NULL
}

// 销毁顺序表
void Sequential_List_Destroy(Sequential_List* sequential_list)
{
	free(sequential_list->Array);
	sequential_list->Array = NULL;
	sequential_list->Length = 0;
}

// 插入元素
void Sequential_List_Insert(Sequential_List* sequential_list, int Insert_Index, int Insert_Element)
{
	if(Insert_Index < 0 || Insert_Index > sequential_list->Length) return;
	
	// 重新分配空间，长度加1
	sequential_list->Array = realloc(sequential_list->Array, (++sequential_list->Length) * sizeof(int));
	
	// 将插入点之后的元素向后移动一位
	for(int Index = sequential_list->Length - 1; Index > Insert_Index; --Index)
		sequential_list->Array[Index] = sequential_list->Array[Index-1];
	
	// 填入新元素
	sequential_list->Array[Insert_Index] = Insert_Element;
}

// 删除元素
void Sequential_List_Delete(Sequential_List* sequential_list, int Delete_Index)
{
	if(Delete_Index < 0 || Delete_Index >= sequential_list->Length) return;
	
	--sequential_list->Length;
	// 将删除点之后的元素向前移动一位
	for(int Index = Delete_Index; Index < sequential_list->Length; ++Index)
		sequential_list->Array[Index] = sequential_list->Array[Index+1];
}

// 获取指定索引的元素
int Sequential_List_Obtain(Sequential_List sequential_list, int Obtain_Index)
{
	if(Obtain_Index < 0 || Obtain_Index >= sequential_list.Length) return 0;
	return sequential_list.Array[Obtain_Index];
}

// 获取当前长度
int Sequential_List_Obtain_Length(Sequential_List sequential_list)
{
	return sequential_list.Length;
}

int main(void)
{
	Sequential_List sequential_list = Sequential_List_Create();
	int Select, Element, Index;
	
	// 简化演示，实际应用中应加入输入合法性检查
	do {
		printf("1: 插入 | 2: 删除 | 3: 查询 | 4: 长度\n请输入操作编号:");
		scanf("%i", &Select);
		
		if(Select == 1) {
			printf("请输入插入位置和元素:");
			scanf("%i%i", &Index, &Element);
			Sequential_List_Insert(&sequential_list, Index, Element);
		} else if(Select == 2) {
			printf("请输入要删除的位置:");
			scanf("%i", &Index);
			Sequential_List_Delete(&sequential_list, Index);
		} else if(Select == 3) {
			printf("请输入要查询的位置:");
			scanf("%i", &Index);
			printf("%i\n", Sequential_List_Obtain(sequential_list, Index));
		} else if(Select == 4) {
			printf("%i\n", Sequential_List_Obtain_Length(sequential_list));
		}
	} while(Select != 0);
	
	Sequential_List_Destroy(&sequential_list);
	return 0;
}

C++语言实现代码

C++提供了更高级的特性如模板和RAII（资源获取即初始化），可以更优雅地实现泛型顺序表。以下代码展示了使用类封装和动态内存分配的C++版本实现：

#include<iostream>

template<typename Type>
struct Sequential_List 
{
	Type* Array = nullptr;
	int Length = 0;

	~Sequential_List() // 析构函数自动释放内存
	{
		delete[] Array;
	}

	// 插入元素
	void Insert(int Insert_Index, Type Insert_Element) 
	{
		if(Insert_Index < 0 || Insert_Index > Length) return;
		
		Type* temporary_Array = new Type[++Length];
		// 复制旧数据
		for(int Index = 0; Index < Length - 1; ++Index)
			temporary_Array[Index] = Array[Index];
		
		delete[] Array;
		Array = temporary_Array;
		
		// 移动新元素后的数据
		for(int Index = Length - 1; Index > Insert_Index; --Index)
			Array[Index] = Array[Index-1];
		
		// 放入新元素
		Array[Insert_Index] = Insert_Element;
	}

	// 删除元素
	void Delete(int Delete_Index) 
	{
		if(Delete_Index < 0 || Delete_Index >= Length) return;
		
		--Length;
		for(int Index = Delete_Index; Index < Length; ++Index)
			Array[Index] = Array[Index+1];
	}

	// 获取元素
	Type Obtain(int Obtain_Index) 
	{
		if(Obtain_Index < 0 || Obtain_Index >= Length) throw std::out_of_range("Index out of range");
		return Array[Obtain_Index];
	}

	// 获取长度
	int Obtain_Length() 
	{
		return Length;
	}
};

int main(void)
{
	Sequential_List<int> sequential_list;
	int Select, Element, Index;
	
	// 交互逻辑类似C版，此处省略以节省篇幅，核心逻辑相同
	std::cout<<"C++ Template Sequential List Ready."<<std::endl;
	return 0;
}

以上就是C/C++实现线性顺序表的详细内容，更多关于C/C++顺序表结构与优化的资料请关注本站其它相关文章！