顺序表创建,初始化,赋值,取值,查找,插入与删除(附小例题)

这篇具有很好参考价值的文章主要介绍了顺序表创建,初始化,赋值,取值,查找,插入与删除(附小例题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


title: 数据结构学习笔记 —— 线性表 tags: 数据结构

定义

由n(n≥0)个数据结构相同的元素构成的有限序列。


重要特点

1)除了第一个元素外,结构中的每一个数据元素均只有一个前驱

2)除了最后一个元素外,结构中的每一个数据元素均只有一个后驱


线性表 —— 顺序表

定义

用一组地址连续的存储单元依次存储线性表的数据元素。


特点

优点随机存储

缺点:在做插入和删除操作时,需要移动大量元素。并且当元素多变化大是会造成存储空间浪费。(解决:链式存储)


描述

#define MAXSIZE 100typedef struct{
​		ElemType * elem;  //存储空间的地址int length; // 当前长度}SqList;  // 顺序表的结构类型 Sqlist

例:

 //构造顺序表
#include<stdio.h>
#define MAXSIZE 100
typedef struct
{
	int* elem;		//声明动态数组
	int length;		//记录表的当前长度
	int maxsize;		//记录表的分配容量(最大长度)
}SqList;

顺序表的基本操作

这是下面所使用函数的原型

// 创建顺序表
typedef struct
{
	int* elem;		//声明动态数组
	int length;		//记录表的当前长度
	int size;		//记录表的分配容量(最大长度)
}SqList;

// 初始化顺序表
int Initlist(SqList &L)
{
	L.elem = (int*)malloc(MAXSIZE * sizeof(int));  //构造一个空的顺序表,动态申请存储空间
	if (!L.elem)  //如果申请失败,作出提示并安全退出程序
	{
		printf("初始化失败!");
		exit(0);
	}
	L.length = 0;  //表的初始长度为0
	L.size = MAXSIZE; // 表的存储空间(最大长度)为MAXSIZE

	return L;
}

// 赋值
void get_value(SqList& L)
{
	int i, n;
	//scanf_s("%d",&n);
	for (i = 0; i < L.size; i++)
	{
		L.elem[i] = i + 1;
		L.length++;//长度随赋值情况增加
	}
}

//取值
int GetElem(SqList L, int i, int& e)
{
	if (i < 1 || i > L.length)   //判断i的值是否合理(是否为负数或是否超出表长),不合理返回ERROR
	{
		printf("获取值失败!");
		exit(0);
	}

	e = L.elem[i - 1];  // elem[i - 1]单元存储第i个数据元素

	return e;
} 

//按值查找
int LocateElem(SqList L, int e)
{
    int i ;
    for (i = 0; i < L.length; i++)
	{
	    if (L.elem[i] == e)
        {
			return i + 1;	          //数组下标为i的元素,其序号为i + 1 
        }
	}	      
	return 0;      	//查找失败, 返回0
}

// 插入
void ListInsert(SqList& L, int i, int e)
{	//在顺序表L中第i个位置的新元素e,i值的合法范围是1≤ i ≤L.length + 1
	int j;
	if (i < 0 || i > L.length)
	{
		printf("插入失败!");
		exit(0);
	}
	if (L.length == MAXSIZE)	//当前存储空间已满
	{
		printf("空间已满!");
		exit(0);
	}

	for ( j = L.length; j >= i; j--)
	{
		L.elem[j + 1] = L.elem[j];	// 插入位置及之后的元素后移
	}

	L.elem[j - 1] = e;	// 将新元素e放入第i个位置
	++L.length;		//表长加一
}

void ListDelete(SqList& L, int i)
{
	int j;
	if ((i < 0) || (i > L.length))  //i值不合法
	{
		printf("删除失败!");
		exit(0);
	}

	for ( j = i; j <= L.length - 1; j++)
	{
		L.elem[j - 1] = L.elem[j];	//被删除元素之后的元素前移
	}
	--L.length;	//表长减一
}

初始化

算法描述

Status InitList(SqList &L) // &L 引用参数类型(因为表L会改变)
{
	L.elem = new ElemType[MAXSIZE];
    if(! L.elem)
    {
        exit(OVERFLOW);  //内存分配失败退出
	}
    l.length = 0;   // 空表长度为0
    return OK;
}

例:

#include<stdio.h>
#define MAXSIZE

int main(void)
{
	SqList L;   //声明顺序表
	Initlist(L);  //初始化
	
    return 0;
}


取值(时间复杂度为 O(1) )

算法描述

Status GetElem(Sqlist L, int i, ElemType &e)
{
	if(i < 1 || i > L.length)   //判断i的值是否合理(是否为负数或是否超出表长),不合理返回ERROR
    {
		return ERROR;
    }
    
    e = L.elem[i - 1];  // elem[i - 1]单元存储第i个数据元素
	
    return OK;
}

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

int main(void)
{	
	int i= 64; 	//取值第64个元素
	int e = 0;
	int t = 0;
	SqList L;  // 声明顺序表
	Initlist(L); //初始化
    get_value(L);  //赋值
	t = GetElem(L, i, e); //取值
	
	printf("输出:%d", t);

	free(L.elem); 
	return 0;
}

查找(平均算法复杂度为 O(n) )

算法描述

//按值查找
Status LocateElem(SqList L, ElemType e)
{
    int i;
    for (i = 0; i < L.length; i++)
	{
	    if (L.elem[i] == e)  
        {
             return i + 1;	          //查找成功, 返回序号 i + 1           
        }      
	}	      
	return 0; 					//查找失败, 返回0
} 

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

int main(void)
{	
	int e;  //要查找的元素
	SqList L;  // 声明顺序表
	Initlist(L); //初始化 
	get_value(L); // 赋值

	printf("请输入1-100中任意整数:");
	scanf_s("%d", &e);
	 
	printf("查找结果:%d", LocateElem(L, e));
	
	free(L.elem);
	return 0;
}

插入(平均算法复杂度为 O(n) )

步骤

① 判断插入位置i是否合法(i值的合法范围是1≤i≤n+1),若不合法则返回ERROR(n为原顺序表长度)

②判断顺序表的存储空间是否已满,若满则返回ERROR

③将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i = n + 1时无需移动)

④将要插入的新元素e放入第i个位置

⑤表长加一

算法描述

//插入
Status ListInsert(SqList &L, int i, ElemType e)
{  //在顺序表L中第i个位置的新元素e,i值的合法范围是1≤ i ≤L.length + 1
	if( (i < 1) || (i > L.length + 1) )    //i值不合法
    {
		return ERROR;
	}
    if(L.length == MAXSIZE) //当前存储空间已满
    {
		return ERROR;
	}
    for(j = L.length - 1; j >= i - 1; j--)
    {
		L.elem[j + 1] = L.elem[j];  	// 插入位置及之后的元素后移
    }
    L.elem[i - 1] = e;     // 将新元素e放入第i个位置
    ++L.length;			//表长加一
    return OK;
}

int main(void)
{	
	int n;
	int i; //要插入位置
	int e;  //要插入的元素
	SqList L;  // 声明顺序表
	Initlist(L); //初始化 
	get_value(L); // 需要将get_value中的L.size 改为L.size - 1,否则表满,不能插入

	printf("初始表:");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	printf("\n请输入插入位置(1-10间):");
	scanf_s("%d", &i);
	printf("请输入插入元素(1-10间):");
	scanf_s("%d", &e);

	ListInsert(L, i, e);	//插入

	printf("插入后的表:");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	
	free(L.elem);
	return 0;

}

删除

步骤

① 判断删除位置i是否合法(i值的合法范围是1≤i≤n+1),若不合法则返回ERROR(n为原顺序表长度)

②将第i + 1个至第n个位置的元素依次向前移动一个位置,(i = n时无需移动)

③表长减一

算法描述

//删除
Status ListDelete(SqList &L, int i)
{
	if( (i < 1) || (i > L.length) )    //i值不合法
    {
		return ERROR;
	}
    for(j = i; j < L.length - 1: j++)
    {
		L.elem[j - 1] = L.elem[j];   //被删除元素之后的元素前移
	}
    --L.length;   //表长减一
    return OK;
}

文章来源地址https://www.toymoban.com/news/detail-727908.html

int main(void)
{	
	int n;
	int i; //要删除位置
	SqList L;  // 声明顺序表
	Initlist(L); //初始化 
	get_value(L); // 赋值

	printf("初始表:");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	printf("\n请输入删除位置(1-10间):");
	scanf_s("%d", &i);

	ListDelete(L, i); 	//删除第i个

	printf("删除后的表:");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	
	free(L.elem);
	return 0;
}
									顺序表完

到了这里,关于顺序表创建,初始化,赋值,取值,查找,插入与删除(附小例题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MATLAB中怎样初始化(创建)二维、三维、四维以及多维矩阵,各维度的索引顺序是怎样的?

    在MATLAB中初始化一个二维矩阵是很容易的,我们既可以直接把矩阵的元素值写出,比如下面这样: 也可以直接用函数ones()、zeros()、rand()等函数初始化一个全1或全0或均匀随机分布等的矩阵,然后再对其中的元素进行访问赋值,比如下面这样: 从上面的示例中我们可以看出,

    2024年01月17日
    浏览(45)
  • 数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)

    目录 邻接矩阵 图节点的结构 创建并初始化 插入边 完整的图的建立  邻接表 图节点的结构 创建并初始化 插入边  完整的图的建立  定义结构体GNode,其中包含以下成员变量: Nv:表示图中的顶点数。 Ne:表示图中的边数。 二维数组表示图的邻接矩阵。它的大小是MaxVertexN

    2024年02月06日
    浏览(44)
  • C++二维数组的初始化赋值及示例

    C++二维数组可以看作一个表格,横向为表格的行,纵向为表格的列,数组定义时行号在前,列号在后。二维数组的定义格式为: 数据类型  数组名[常量行表达式][常量列表达式] 。 二维数组的元素是按先行后列的顺序存放的,例如,定义一个int a[3][2]的数组,其形式为: a[

    2024年02月12日
    浏览(55)
  • Java中Map集合初始化并赋值

    Java中Map集合初始化并赋值的几种方式:

    2024年02月11日
    浏览(51)
  • golang变量初始化顺序

    顺序: 1.引用的包 2.全局变量 3.init()函数 4.main()函数 输出 $ go run 1.go pkg init func() main init main()

    2024年04月17日
    浏览(79)
  • java基础:初始化ArrayList时直接赋值的四种方式

    在Java中,初始化ArrayList时直接赋值有以下几种常见方式: 构造器传入集合 : 或者在Java 9及以上版本中使用 List.of() 方法创建不可变列表: 使用匿名内部类 (不常用且可能引起混淆,实际编程中很少这样用): 注意:这种方式利用了匿名内部类的实例初始化块,但不是标准

    2024年04月22日
    浏览(41)
  • Java之初始化顺序实践

    在创建Java对象时,需要将对象中的成员变量进行初始化后,才能调用对象的构造方法创建对象。本文中将会讲解初始化时父类与子类对应的顺序。 场景1:父类、子类的初始化顺序 用例代码 结果输出 结果分析 先初始化静态块:父类的静态块 - 子类的静态块。 再初始化非静

    2024年02月11日
    浏览(39)
  • 【数组】二分查找(减不减一,看初始化!)

    704. 二分查找 - 力扣(LeetCode) 这道题目的前提是数组为有序数组 ,同时题目还强调 数组中无重复元素 ,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的, 这些都是使用二分法的前提条件 ,当大家看到题目描述满足如上条件的时候,可要想一想是不是

    2024年02月07日
    浏览(45)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(39)
  • go语言包、变量、init初始化顺序

    一个完整的 go 语言可运行程序,通常会包含引用的包、变量、init 函数以及 main 函数几个部分。 包、变量、常量、init 函数以及 main 函数初始化顺序如下图所示: 在一个 go 语言程序中,初始化顺序规则如下: 引入的包 当前包中的变量、常量 当前包的 init 函数 main 函数 初始

    2023年04月14日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包