1. Toy模板网首页
  2. > Toy博客

【数据结构与算法】二、线性表的顺序表示【硬核】

9月前 作者：韩飞雨 分类：Toy博客 阅读(45) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】二、线性表的顺序表示【硬核】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二、线性表

2.1 线性表的定义和特点

【数据结构与算法】二、线性表的顺序表示【硬核】

2.2 线性表的顺序表示和实现

图书表的顺序存储结构类型定义：
【数据结构与算法】二、线性表的顺序表示【硬核】

#define OK	1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAXSIZE  10000 //能够存储的最大图书数量

//1、图书表的顺序存储结构类型定义
//1.1、图书的存储结构
typedef struct{
	char isbn[20];//图书的isbn编号
	char name[50];//图书的名称
	double price;//图书的价格
}Book;
typedef Book ElemType;//元素数据的类型
//1.2、图书表的顺序存储结构
typedef struct{
	ElemType* books;//存储图书数组结构的基地址
	int length;//当前有多少本图书
}BookList;

2.3 类C语言有关操作补充

在调用函数的过程中，当形参为引用类型时，实参和形参占用了相同的空间
【数据结构与算法】二、线性表的顺序表示【硬核】

2.4 线性表基本操作的实现

2.4.1 线性表的基本操作：

【数据结构与算法】二、线性表的顺序表示【硬核】

2.4.2 线性表L的初始化

【数据结构与算法】二、线性表的顺序表示【硬核】

// 顺序表的存储结构
typedef struct {
	ElemType* elems;//存储基本元素的数组基地址
	int length;//当前基本元素的个数
}SqList;
typedef int Statu;
//1、顺序表L的初始化
Statu initSqList(SqList &L) {
	L.elems = new ElemType[MAXSIZE];//为存储数据的数组开辟空间
	if (!L.elems) exit(OVERFLOW);//空间开辟失败
	L.length = 0;//空表长度置为0
	return OK;
}

2.4.3 销毁和清空线性表L

【数据结构与算法】二、线性表的顺序表示【硬核】

//2、销毁和清空线性表L
//2.1 销毁顺序表L
void destroySqList(SqList &L) {
	if (L.elems) delete L.elems;
	L.length = 0;
}
//2.2 清空线性表L
void clearSqList(SqList &L) {
	L.length = 0;
}

2.4.4 求线性表L的长度以及判断线性表L是否为空

【数据结构与算法】二、线性表的顺序表示【硬核】

//3、求线性表L的长度以及判断线性表L是否为空
//3.1 求线性表L的长度
int getLength(SqList L) {
	return L.length;
}
//3.2 判断线性表L是否为空
Statu isEmpty(SqList L) {
	if (L.length == 0) return TRUE;
	return FALSE;
}

2.4.5 顺序表的取值（根据位置i获取相应位置数据元素的内容）

【数据结构与算法】二、线性表的顺序表示【硬核】

//4、顺序表的取值（获取第i个位置数据元素的内容）
Statu getElem(int i, SqList L,ElemType &e) {
	if (i<1 || i>L.length) return ERROR;//数组越界
	e=L.elems[i - 1];
	return OK;
}

2.4.6 顺序表的查找(在线性表L中查找与指定值e相同的数据元素的位置)

【数据结构与算法】二、线性表的顺序表示【硬核】

//5、判断两个数据元素是否相等
Statu isEqual(ElemType a, ElemType b) {
	if (strcmp(a.isbn,b.isbn)==0) return TRUE;
	return FALSE;
}
//6、顺序表的查找(在线性表L中查找与指定值e相同的数据元素的位置)
int LocateElem(ElemType e, SqList L) {
	for (int i = 0; i < L.length; i++) {
		if (isEqual(L.elems[i],e)) return i+1;
	}
	return 0;
}

顺序表的查找算法分析

【数据结构与算法】二、线性表的顺序表示【硬核】

2.4.7 顺序表的插入(在第i个位置插入指定的元素)

【数据结构与算法】二、线性表的顺序表示【硬核】

Statu insertSqList(SqList &L, int i,ElemType e) {
	if (i<1 || i>L.length + 1) return ERROR;//插入位置不合法
	if (L.length == MAXSIZE) return ERROR;//元素已满，无法插入
	for (int j = L.length-1; j >=i-1; j--) {
		L.elems[j+1] = L.elems[j];
	}
	L.elems[i - 1] = e;
	L.length++;
	return OK;
}

2.4.8 顺序表的删除(删除第i个位置的元素)

【数据结构与算法】二、线性表的顺序表示【硬核】

Statu deleteSqList(SqList& L, int i) {
	if (i<1 || i>L.length) return ERROR;//删除位置不合法
	for (int j = i; j < L.length; j++) {
		L.elems[j - 1] = L.elems[j];
	}
	L.length--;
	return OK;
}

2.5 顺序表（线性表的顺序存储结构）的特点

  • (1)利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致

  • (2)在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等

  • 这种存储元素的方法被称为随机存取法
    【数据结构与算法】二、线性表的顺序表示【硬核】

2.6 C++实现代码

main.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include"Sqlist.h"


int main() {
	test();
	return 0;
}

Sqlist.h

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK	1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define MAXSIZE  10000 //能够存储的最大图书数量

//1、图书表的顺序存储结构类型定义
//1.1、图书的存储结构
typedef struct{
	char isbn[20];//图书的isbn编号
	char name[50];//图书的名称
	double price;//图书的价格
}Book;
typedef Book ElemType;//元素数据的类型
//1.2、图书表的顺序存储结构
typedef struct{
	ElemType* books;//存储图书数组结构的基地址
	int length;//当前有多少本图书
}BookList;

// 顺序表的存储结构
typedef struct {
	ElemType* elems;//存储基本元素的数组基地址
	int length;//当前基本元素的个数
}SqList;
typedef int Statu;

//函数声明===========================================
//2、顺序表L的初始化
Statu initSqList(SqList &L);
//3、销毁线性表L
void destroySqList(SqList &L);
//4、清空线性表L
void clearSqList(SqList& L);
//5、求线性表L的长度
int getLength(SqList L);
//6、判断线性表L是否为空
Statu isEmpty(SqList L);
//7、顺序表的取值（根据位置i获取相应位置数据元素的内容）
Statu getElem(int i, SqList L, ElemType& e);
//8、顺序表的查找(在线性表L中查找与指定值e相同的数据元素的位置)
//8.1 //判断两本图书是否相等
Statu isEqual(ElemType a, ElemType b);
//8.2 顺序表的查找(在线性表L中查找与指定值e相同的数据元素的位置)
int LocateElem(ElemType e, SqList L);
//9、顺序表的插入(在第i个位置插入指定的元素)
Statu insertSqList(SqList& L, int i, ElemType e);
//10、顺序表的删除(删除第i个位置的元素)
Statu deleteSqList(SqList& L, int i);
//11、打印单个元素
void displayElem(ElemType e);
//12、打印整个线性表
void displaySqList(SqList L);
//13、从txt文件中读取数据元素数据
Statu readDataFromTxt(SqList& L, const char* filename);

//================================================

//2、顺序表L的初始化
Statu initSqList(SqList& L) {
	L.elems = new ElemType[MAXSIZE];//为存储数据的数组开辟空间
	if (!L.elems) exit(OVERFLOW);//空间开辟失败
	L.length = 0;//空表长度置为0
	return OK;
}
//3、销毁线性表L
void destroySqList(SqList& L) {
	if (L.elems) delete L.elems;
	L.length = 0;
}
//4、清空线性表L
void clearSqList(SqList& L) {
	L.length = 0;
}
//5、求线性表L的长度
int getLength(SqList L) {
	return L.length;
}
//6、判断线性表L是否为空
Statu isEmpty(SqList L) {
	if (L.length == 0) return TRUE;
	return FALSE;
}
//7、顺序表的取值（根据位置i获取相应位置数据元素的内容）
Statu getElem(int i, SqList L,ElemType &e) {
	if (i<1 || i>L.length) return ERROR;//数组越界
	e=L.elems[i - 1];
	return OK;
}

//8、顺序表的查找(在线性表L中查找与指定值e相同的数据元素的位置)
//8.1 判断两本图书是否相等
Statu isEqual(ElemType a, ElemType b) {
	if (strcmp(a.isbn,b.isbn)==0) return TRUE;
	return FALSE;
}
//8.2 顺序表的查找(在线性表L中查找与指定值e相同的数据元素的位置)
int LocateElem(ElemType e, SqList L) {
	for (int i = 0; i < L.length; i++) {
		if (isEqual(L.elems[i], e)) return i + 1;
	}
	return 0;
}
//9、顺序表的插入(在第i个位置插入指定的元素)
Statu insertSqList(SqList &L, int i,ElemType e) {
	if (i<1 || i>L.length + 1) return ERROR;//插入位置不合法
	if (L.length == MAXSIZE) return ERROR;//元素已满，无法插入
	for (int j = L.length-1; j >=i-1; j--) {
		L.elems[j+1] = L.elems[j];
	}
	L.elems[i - 1] = e;
	L.length++;
	return OK;
}
//10、顺序表的删除(删除第i个位置的元素)
Statu deleteSqList(SqList& L, int i) {
	if (i<1 || i>L.length) return ERROR;//删除位置不合法
	for (int j = i; j < L.length; j++) {
		L.elems[j - 1] = L.elems[j];
	}
	L.length--;
	return OK;
}
//11、打印单个元素
void displayElem(ElemType e) {
	printf("isbn编号是：%s\n", e.isbn);
	printf("图书的名称是：%s\n", e.name);
	printf("图书的价格是：%lf\n", e.price);
}
//12、打印整个线性表
void displaySqList(SqList L) {
	for (int i = 0; i < L.length; i++) {
		displayElem(L.elems[i]);
	}
}
//13、从txt文件中读取数据元素数据
Statu readDataFromTxt(SqList &L, const char* filename) {
	FILE* file = freopen(filename, "r", stdin);
	if (!file) {
		printf("文件读取失败\n");
		return ERROR;
	}
	ElemType e;
	int i = 0;
	while (scanf("%s%s%lf", e.isbn, e.name, &e.price)!=EOF&&i<MAXSIZE) {
		L.elems[i++] = e;
		L.length++;
	}
	return OK;
}
//14、测试函数
void test() {
	SqList L;//定义一个线性表
	initSqList(L);//初始化线性表
	//判断线性表是否为空
	if (isEmpty(L)) printf("线性表是空的\n");
	else{
		printf("线性表的长度是: %d\n", L.length);
	}
	printf("======1、从文件中读取图书表数据========\n");
	//从文件中读取图书表数据
	readDataFromTxt(L, "data.in.txt");
	displaySqList(L);
	//往线性表中插入元素
	printf("======2、往线性表中插入元素========\n");
	ElemType e1;
	strcpy(e1.isbn, "00X");
	strcpy(e1.name, "安徒生童话");
	e1.price = 88.8;

	insertSqList(L, 3, e1);

	//判断线性表是否为空
	if (isEmpty(L)) printf("线性表是空的\n");
	else {
		printf("线性表的长度是: %d\n", L.length);
	}
	printf("=======3、取第三个元素=======\n");

	//取第三个元素
	ElemType e;
	getElem(3, L, e);
	displayElem(e);
	printf("========4、在第三个位置插入元素e========\n");

	//在第三个位置插入元素e
	insertSqList(L, 3, e);
	//打印线性表
	displaySqList(L);
	printf("=========5、删除第三个位置的元素========\n");

	//删除第三个位置的元素
	deleteSqList(L, 3);
	displaySqList(L);
	printf("=========6、查看元素e在线性表的哪个位置=======\n");

	//查看元素e在线性表的哪个位置
	int index=LocateElem(e, L);
	printf("元素e在线性表中的位置: %d\n", index);

}

data.in.txt文章来源地址https://www.toymoban.com/news/detail-425619.html

001 平凡的世界 22.2
002 活着 66.5
003 天之下 33.2

到了这里，关于【数据结构与算法】二、线性表的顺序表示【硬核】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(六)——线性表的顺序实现

    数据结构(六)——线性表的顺序实现

    🏠个人主页：尘觉主页 🧑个人简介：大家好，我是尘觉，希望我的文章可以帮助到大家，您的满意是我的动力😉 在csdn获奖荣誉: 🏆csdn城市之星2名 ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ 💓csdn2023年后端赛道第第七 ⁣⁣⁣⁣ ⁣⁣⁣⁣

    2024年01月25日
    浏览(56)

  • 【考研复习】24王道数据结构课后习题代码｜2.3线性表的链式表示

    删除结点：1、2、4 就地逆置：5、 合并链表 分解链表：10、11、 去除重复元素：12、 并集：14、15 循环链表：17、18、19、20 头插法、尾插法重点基础必掌握。 判断是否有环：21 用函数递归调用删除结点。 注意删除结点的时候可能断链。 利用函数调用的特性反向输出。 设置保

    2024年02月13日
    浏览(31)
  • 【玩转408数据结构】线性表——双链表、循环链表和静态链表（线性表的链式表示 下）

    【玩转408数据结构】线性表——双链表、循环链表和静态链表（线性表的链式表示 下）

            在前面的学习中，我们已经了解到了链表（线性表的链式存储）的一些基本特点，并且深入的研究探讨了单链表的一些特性，我们知道，单链表在实现插入删除上，是要比顺序表方便的，但是，单链表中每个结点仅存在一个指针指向其后续结点，那么如果我们想要找

    2024年04月10日
    浏览(49)
  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ，其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为： 所以， 只要确定了存储顺序表的起始地址（即基地址），计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(46)
  • 数据结构 线性表的定义和基本操作（以顺序表为例）

    数据结构 线性表的定义和基本操作（以顺序表为例）

    名人说：一花独放不是春，百花齐放花满园。——《增广贤文》 作者：Code_流苏(CSDN) （一个喜欢古诗词和编程的Coder😊） 以下代码个人分享出来，仅供学习交流，且仅在CSDN平台发布，未经授权禁止二次转发。 〇、线性表是什么？ 1、定义 线性表 是具有 相同数据类型 的 n（

    2024年02月12日
    浏览(48)
  • 【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

    【数据结构】线性表（一）线性表的定义及其基本操作（顺序表插入、删除、查找、修改）

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(55)
  • 数据结构（王道）——线性表之静态链表&顺序表和链表的比较

    数据结构（王道）——线性表之静态链表&顺序表和链表的比较

      如何定义一个静态链表     初始化静态链表：   静态链表的查找、插入、删除           创： 销：   增、删：   查：   顺序表、链表该如何选择？  

    2024年02月16日
    浏览(40)
  • 数据结构-线性表的顺序表基本操作代码实现（超级详细清晰 C++实现）

    数据结构-线性表的顺序表基本操作代码实现（超级详细清晰 C++实现）

    顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表： 可动态增长的数组，要求数据是连续存储的 特点： 随机访问 顺序既可以 静态分配 ，也可以 动态分配 。在静态分配时，由于数组

    2024年02月07日
    浏览(49)

  • 数据结构与算法 --顺序表的创建

    1. 顺序表（Sequence List）是一种线性表的实现方式，通过连续的内存空间存储元素，按照顺序排列。 顺序表的特点包括： 元素在内存中的存储是连续的，通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(46)
  • 数据结构：线性表————顺序表的实现、项目和OJ题目(手把手教你写代码)

    数据结构：线性表————顺序表的实现、项目和OJ题目(手把手教你写代码)

    🌈 个人主页： 小新_- 🎈个人座右铭：“成功者不是从不失败的人，而是从不放弃的人！”🎈 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 🏆所属专栏：  话说那些与C++的爱恨情仇   欢迎订阅，持续更新中~~~                                           ✨让小新带着你

    2024年04月16日
    浏览(77)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包