数据结构与算法精解：顺序表

本文介绍了顺序表的实现方法，包括静态和动态两种实现方式。顺序表通过连续内存空间存储数据，支持随机访问（O(1)），但插入删除操作需要移动元素（O(n)）。文章详细说明了顺序表的数据结构设计（包含静态数组和动态指针两种方案），并给出完整的接口函数实现，包括初始化、增删改查等核心操作。其中特别处理了静态与动态顺序表的不同实现细节，如动态扩展数组大小、数据迁移等关键问题。所有函数都包含详尽的代码注释，展现了顺序表这一基础数据结构的具体实现思路。

作者
WildPointer
发布
2024.06.04
专栏
数据结构与算法精解
阅读
约 9 分钟 / 626 次原文浏览

目录

实现思想

        顺序表是一种基本的数据结构，它使用连续的内存空间来存储线性表的数据元素。顺序表的实现通常依赖于数组。以下是顺序表实现的一些核心思想和特点：

        1.连续内存空间：顺序表通过数组实现，数组中的每个元素都紧密排列在内存中，这意味着可以通过索引快速访问任何元素。

        2.动态与静态：顺序表可以是静态的，即其大小在创建时就固定，也可以是动态的，即其大小可以根据需要调整。

        3.随机访问：由于顺序表基于数组，它支持随机访问，即可以在O(1)时间复杂度内访问任何位置的元素。

        4.插入和删除操作：在顺序表中插入或删除元素可能需要移动其他元素以维持元素的连续性，这通常会导致较高的时间开销（O(n)）。

        5.空间局部性：顺序表利用了空间局部性原理，即访问过的元素附近的元素很可能也会被访问，这可以提高缓存利用率。

        6.扩展和收缩：对于动态顺序表，当元素数量达到当前容量时，可能需要扩展数组以容纳更多元素。这通常涉及到创建一个更大的数组，并将旧数组中的元素复制到新数组中。相反，当顺序表中有很多未使用的空间时，可以收缩数组以节省空间。

包含头文件

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

结点设计

cpp
#define Initsize 10typedef int Elemtype;typedef struct {	Elemtype data[Initsize];	//定义数组data大小为Initsize，存储的是静态顺序表的数据	Elemtype* next;				//定义next为Elemtype类型的指针，用于动态扩展顺序表的大小	int Maxsize;				//定义变量Maxsize存储顺序表的大小	int lenth;					//定义变量lenth存储顺序表所存储的数据个数}SqlList;

接口函数定义

cpp
void PrintfList(SqlList& A);					//定义函数PrintfList用于输出顺序表void InputList(SqlList& A);						//定义函数InputList用于输入顺序表中的数据void InitStaticList(SqlList& A);				//定义函数InitStaticList用于初始化静态顺序表void InitMoveList(SqlList& A);					//定义函数InitMoveList用于初始化动态顺序表void AddList(SqlList& A);						//定义函数AddList用于动态增加顺序表长度bool ListInsert(SqlList& A, int len, int X);	//定义函数ListInsert用于在顺序表中插入数据bool ListDelete(SqlList& A, int len, int &X);	//定义函数ListDelete用于在顺序表中删除数据Elemtype GetElem(SqlList& A, int len);			//定义函数GetElem用于在顺序表中按位查找数据Elemtype LocateElem(SqlList& A, int X);			//定义函数LocateElem用于在顺序表中按值查找数据

接口函数实现

cpp
Elemtype LocateElem(SqlList& A, int X){//定义函数LocateElem用于在顺序表中按值查找数据	int i;	if(A.next == NULL){	 //判断传入的是否为静态顺序表		for (i = 0; i < A.lenth; i++){			if (A.data[i] == X){	//遍历静态顺序表，查询是否有数据相同				printf("该数据位于的顺序表中的次序为%d", i + 1);				return i + 1;			}		}		printf("在该顺序表中未能找到此数据");		return 0;	}else{		for (i = 0; i < A.lenth; i++) {			if (A.next[i] == X) {    //遍历动态顺序表，查询是否有数据相同				printf("该数据位于的顺序表中的次序为%d", i + 1);				return i + 1;			}		}		printf("在该顺序表中未能找到此数据");		return 0;			}}Elemtype GetElem(SqlList& A, int len){	//定义函数GetElem用于在顺序表中按位查找数据	if(len<1 || len>A.lenth){    //判断传入的次序是否合理		printf("输入的次序有误");		return 0;	}	if(A.next==NULL){    //判断传入的是否为静态顺序表		printf("您查找的数据为%d", A.data[len - 1]);		return A.data[len-1];	}else {		printf("您查找的数据为%d", A.next[len - 1]);		return A.next[len-1];	}}bool ListDelete(SqlList& A, int len, int &X){//定义函数ListDelete用于在顺序表中删除数据	int i;	if(len<1 || len>A.lenth){						//判断传入的次序是否合理		printf("输入的次序有误");		return false;	}	if(A.next == NULL){							//判断传入的是否为静态顺序表		X = A.data[len - 1];						//将要删除的数据带回		printf("删除的数据为%d", X);		for (i = len - 1; i < A.lenth; i++){			A.data[i] = A.data[i + 1];				//将静态顺序表中的数据依次前移		}		A.lenth -= 1;								//更新静态顺序表中的数据		return true;	}else{		X = A.next[len - 1];						//将要删除的数据带回		printf("删除的数据为%d", X);		for(i = len - 1; i < A.lenth; i++){			A.next[i] = A.next[i + 1];				//将动态顺序表中的数据依次前移		}		A.lenth -= 1;								//更新动态顺序表中的数据		return true;	}}bool ListInsert(SqlList& A, int len, int X){//定义函数ListInsert用于在顺序表中插入数据	int i;	if(A.lenth >= A.Maxsize){					//判断传入顺序表中含有的数据是否以满		printf("该顺序表填充数据已满");		return false;	}	if(len<1 || len>A.lenth + 1){				//判断传入的次序是否合理		printf("输入的次序有误");		return false;	}	if(A.next == NULL){						//判断传入的是否为静态顺序表		for (i = A.lenth; i >= len; i--){					A.data[i] = A.data[i-1];			//将次序后的数据依次后移		}		A.data[len - 1] = X;					//更新静态顺序表中的数据		A.lenth += 1;		return true;	}	else{		for(i = A.lenth; i >= len; i--){			A.next[i + 1] = A.next[i];			//将次序后的数据依次后移		}		A.next[len - 1] = X;					//更新动态顺序表中的数据		A.lenth += 1;		return true;	}}void AddList(SqlList& A){    //定义函数AddList用于动态增加顺序表长度	int i,len;	printf("当前顺序表的大小为%d，请问要在原基础上增加多少存储空间?");	scanf_s("%d", &len);	Elemtype* Q = (Elemtype*)malloc(sizeof(Elemtype) * (A.Maxsize + len));		if(A.next == NULL){						//判断该顺序表是否为静态初始化的顺序表		for (i = 0; i < A.lenth; i++) {		//将静态顺序表中的数据更新到新的地址上			Q[i] = A.data[i];		}	}	A.next = Q;					//更新顺序表中的数据	A.Maxsize += len;}void InputList(SqlList& A){	    //定义函数InputList用于输入顺序表中的数据	int i,X;	if(A.next == NULL){    //判断传入的顺序表是否为静态顺序表		printf("输入静态顺序表要存储的数据个数(最大为10):");		scanf_s("%d", &X);		for(i = 0; i < X; i++){			scanf_s("%d", &A.data[i]);			//循环输入数值，赋值于静态顺序表中的数组里		}		A.lenth = X;	}else{		printf("您所创建的动态顺序表大小为%d，请问您要输入的数据个数:", A.Maxsize);		scanf_s("%d", &X);		for(i = 0; i < X; i++){			scanf_s("%d", &A.next[i]);			//循环输入数值，赋值于动态顺序表中的地址里		}		A.lenth = X;	}}void PrintfList(SqlList& A){    //定义函数PrintfList用于输出顺序表	int i;	if(A.next==NULL){							//判断传入的顺序表是否为静态顺序表		for(i = 0; i < A.lenth; i++){			printf("%d  ", A.data[i]);			//循环输出静态顺序表中的数据				}	}else{		for(i = 0; i < A.lenth; i++){			printf("%d  ", A.next[i]);			//循环输出动态顺序表中的数据		}	}}void InitMoveList(SqlList& A){	//定义函数InitMoveList用于初始化动态顺序表	int len,i;					//定义变量len用于存储动态创建的顺序表大小	printf("请问想要向计算机申请多大的顺序表?");	scanf_s("%d", &len);	A.next= (Elemtype *)malloc(sizeof(Elemtype) * len);		for(i = 0; i < len; i++){					A.next[i] = 0;	}	A.Maxsize = len;					//调用动态顺序表中的Maxsize存储动态顺序表大小	A.lenth = 0;						//调用动态顺序表中的lenth存储动态顺序表中数据的个数，默认为0	printf("初始化动态单链表成功");}void InitStaticList(SqlList& A){		//定义函数InitStaticList用于初始化静态顺序表	int i;	for(i = 0; i < Initsize; i++){	//将传入的静态顺序表的初始值全部赋值为0		A.data[i] = 0;					//调用静态顺序表中的data数组并依次赋值	}	A.Maxsize = Initsize;				//调用静态顺序表中的Maxsize存储静态顺序表大小	A.lenth = 0;	      //调用静态顺序表中的lenth存储静态顺序表中数据的个数，默认为0	A.next = NULL;	printf("初始化静态单链表成功");}
4次原文点赞；这里的喜欢仅保存在本机
WildPointer

专注系统编程、工程实践与底层技术，记录 C++、Qt、OpenCV 与 VTK 的学习和实践。