数据结构基础：2.顺序表。

news/2024/12/22 14:31:34/

顺序表的介绍和实现

  • 一.线性表
    • 1.基本概念：
  • 二.顺序表：
    • 1.基本概念：
    • 分类：1.静态顺序表：
    • 分类：2.动态顺序表：
    • 2.动态顺序表的功能接口的实现：
      • 0.顺序表打印：
      • 1.初始化和删除：
      • 2.尾插尾删：
      • 3.头插头删
      • 4.任意位置插入删除
      • 5.查找对应数据的下标。
      • 6.对于头插头删尾插尾删的优化：
      • 7.一个问题：
  • 三，整体代码和测试函数。
    • 一.声明：
    • 二，接口：
    • 三，主函数和测试函数。

一.线性表

1.基本概念：

1.线性表是N个相同相同特性的数据元素的有限的序列。线性表在实际中使用非常广泛使用的数据结构，常见的线性表有：顺序表，链表，栈，和队列，字符串。
2.线性表在逻辑上是一条直线，都是在物理结构上不一定是一个连续的，线性表在物理存储的时候，通常是以数组和链式结构的形式存储。

区分：
1.顺序表的物理结构是线性的。
2.链表的物理结构不是线性的。

二.顺序表：

1.基本概念：

顺序表是在物理地址上连续存储的的存储单元依次存储数据元素的线性结构，一般情况采用数组存储，在数组上完成对数据的增删查改。

分类：1.静态顺序表：

使用定长数组存储元素：
问题：我们这个数组的长度应该给多少合适？给多了使用不完浪费空间，给少了不够用。可以看出来这个方法不是一个好的顺序表，应该使用动态开辟的空间去作为我们顺序表存储空间的基础：

请添加图片描述

分类：2.动态顺序表：

使用动态开辟的数组存储元素：
请添加图片描述
请添加图片描述

2.动态顺序表的功能接口的实现：

函数统一的实参是结构体变量的地址，传地址调用才能改变顺序表。

0.顺序表打印：

//打印数据
void seqListPrint(SL* ps) 
{int n = ps->sz;for (int i = 0; i < n; i++){printf("%d ", ps->a[i]);}printf("\n");
}

1.初始化和删除：

（注意)
malloc开辟初始空间大小，有效数据和容量的初始化。
free空间，指针置空，有效数据和容量变成空。

//初始化
void seqListInit(SL* ps)
{//动态开辟所以开始就开辟2个空间SL* pa = (SL*)malloc(sizeof(SL) * 4);if (pa == NULL){perror("malloc fial");exit(-1);}ps->a = pa;ps->sz = 0;ps->capacity = 4;
}//删除
void seqListDestort(SL* ps)
{free(ps->a);ps->capacity = 0;ps->sz = 0;
}

2.尾插尾删：

尾插：
1.容量足够：（加入之后有效数据个数++）
请添加图片描述

2.容量不够是需要增容的：
判断数据个数和当前的容量是否相同，相同需要增容，因为增容在插入的过程中是需要使用的所以我们封装一个函数用来增容：每次增加多少容量？建议每次增加容量的两倍这样可以避免空间的使用多次去扩容。

//增容函数
void seqListAdd(SL* ps)
{SL* pa = (SL*)realloc(ps->a, ps->capacity * 2 * sizeof(SL));if (pa == NULL){perror("realloc file");exit(-1);}ps->a = pa;ps->capacity = ps->capacity * 2;
}

//尾插
void seqListPushBack(SL* ps, SLDataType x)
{if (ps->sz == ps->capacity){//增容函数seqListAdd(ps);}//尾插ps->a[ps->sz] = x;ps->sz = ps->sz + 1;
}

尾删：
1.注意删除的一个问题没有了就不可以删除了。
2.断言函数：assert（ps->capacity>0）
3.关于capacity一但发生了错误就会结束程序，返回错误的行数。
4.比如删除到-1这个时候就直接结束程序：并返回错误的行数。

//尾删
void seqListPopBack(SL* ps)
{assert(ps->sz > 0);ps->sz = ps->sz - 1;
}

3.头插头删

头插
1.头插每一次的位置是固定的。
2，这个位置在插入的之前要空出来，整个数据需要进行移动。
3.最后一个赋值到下一个，以此类推直到把第一个赋值到第二个结束。
4.在插入的过程中需要进行一个数据的移动说明这个效率是非常底。每一次插入之前需要进行时复位N的移动。

//头插
void seqListPushFront(SL* ps, SLDataType x)
{//头插的时间复杂度是非常高的，进行一个数据移动。if (ps->sz == ps->capacity){//增容seqListAdd(ps);}//1.移动int n = ps->sz;for (int i = n; i > 0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->sz == ps->sz++;
}

头删：
1.删除位置固定第一个。
2.第二个赋值到第一个，一直到最后一个赋值到倒数第二个位置。
3…有效数据个数–。
4.使用断言判断是否已经没有内容可以删除了。

//头删
void seqListPopFront(SL* ps)
{//头删的时间复杂度是非常高的，进行一个数据移动。assert(ps->sz > 0);ps->sz = ps->sz - 1;int n = ps->sz;for (int i = 0; i < n-1; i++){ps->a[i] = ps->a[i+1];}
}

4.任意位置插入删除

任意位置pos是通过函数的一个参数确定任意位置的下标
1.从末尾开始最后一个赋值到下一个，直到pos位置的置赋值到下一个的时候。
2.这个数据就可以放到pos位置。
3.增容函数
4.有效数据++

// 顺序表在pos位置插入x
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x)
{if (ps->sz == ps->capacity){seqListAdd(ps);}//在对应位置插入数值。int n = ps->sz;for (int i = n; i >pos ; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x![请添加图片描述](https://img-blog.csdnimg.cn/837991a19f794402be4534f9b324441a.png)
;ps->sz++;
}

1.把这个位置的置覆盖，pos+1覆盖到pos最后一个覆盖到倒数第二个上就结束了。
2.有效数据个数–。

// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos)
{assert(ps->sz > 0);int n = ps->sz;for (int i = pos; i < n-1; i++){ps->a[i] = ps->a[i+1];}ps->sz--;
}

5.查找对应数据的下标。

1.我们想要删除一个确定的数据可以通过查找函数返回对应数据的下标。
2.然后再使用任意位置插入删除的函数去删除这个数据。
3.遍历动态开辟数组去查找数据返回下标。找不到就返回-1数。
4.使用之前判断一下如果返回值为-1说明数据不存在。

// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{//遍历查找int n = ps->sz;for (int i = 0; i < n; i++){if (ps->a[i] == x){return i;}}return -1;
}

6.对于头插头删尾插尾删的优化：

对于他们来说就是插入删除的位置固定，我们使用任意位置的插入删除函数去复用实现头插头删尾插尾删功能。

请添加图片描述

7.一个问题：

函数使用之前断言一下结构体的指针是否为空指针。

三，整体代码和测试函数。

一.声明：

#pragma once#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType; 
//定义的数组，当前数组中元素个数，容量。typedef struct seqlist {SLDataType* a;//指向动态开辟的数组int sz;//数组的有效数据个数int capacity;//容量空间的大小
}SL;//初始化
void seqListInit(SL* ps);//删除
void seqListDestort(SL* ps);//尾插
void seqListPushBack(SL*ps, SLDataType x);//尾删
void seqListPopBack(SL* ps);//头插
void seqListPushFront(SL* ps, SLDataType x);//头删
void seqListPopFront(SL* ps);//打印数据
void seqListPrint(SL* ps);// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);

二，接口：

#include"seqlist.h"// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);//初始化
void seqListInit(SL* ps)
{//动态开辟所以开始就开辟2个空间SL* pa = (SL*)malloc(sizeof(SL) * 4);if (pa == NULL){perror("malloc fial");exit(-1);}ps->a = pa;ps->sz = 0;ps->capacity = 4;
}//删除
void seqListDestort(SL* ps)
{free(ps->a);ps->capacity = 0;ps->sz = 0;
}//打印数据
void seqListPrint(SL* ps)
{int n = ps->sz;for (int i = 0; i < n; i++){printf("%d ", ps->a[i]);}printf("\n");
}//增容函数
void seqListAdd(SL* ps)
{SL* pa = (SL*)realloc(ps->a, ps->capacity * 2 * sizeof(SL));if (pa == NULL){perror("realloc file");exit(-1);}ps->a = pa;ps->capacity = ps->capacity * 2;
}//尾插
void seqListPushBack(SL* ps, SLDataType x)
{if (ps->sz == ps->capacity){//增容函数seqListAdd(ps);}//尾插ps->a[ps->sz] = x;ps->sz = ps->sz + 1;
}//尾删
void seqListPopBack(SL* ps)
{assert(ps->sz > 0);ps->sz = ps->sz - 1;
}//头插
void seqListPushFront(SL* ps, SLDataType x)
{SeqListInsert(ps, 0, x);//头插的时间复杂度是非常高的，进行一个数据移动。//if (ps->sz == ps->capacity)//{//	//增容//	seqListAdd(ps);//}1.移动//int n = ps->sz;//for (int i = n; i > 0; i--)//{//	ps->a[i] = ps->a[i - 1];//}//ps->a[0] = x;//ps->sz == ps->sz++;
}//头删
void seqListPopFront(SL* ps)
{SeqListErase(ps, 0);//头删的时间复杂度是非常高的，进行一个数据移动。/*assert(ps->sz > 0);ps->sz = ps->sz - 1;int n = ps->sz;for (int i = 0; i < n-1; i++){ps->a[i] = ps->a[i+1];}*/
}// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{//遍历查找int n = ps->sz;for (int i = 0; i < n; i++){if (ps->a[i] == x){return i;}}return -1;
}// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x)
{if (ps->sz == ps->capacity){seqListAdd(ps);}//在对应位置插入数值。int n = ps->sz;for (int i = n; i >pos ; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->sz++;
}// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos)
{assert(ps->sz > 0);int n = ps->sz;for (int i = pos; i < n-1; i++){ps->a[i] = ps->a[i+1];}ps->sz--;
}

三，主函数和测试函数。

void test3(SL *ps)
{seqListPushBack(ps, 1);seqListPushBack(ps, 2);seqListPushBack(ps, 3);seqListPushBack(ps, 4);seqListPushBack(ps, 5);seqListPushBack(ps, 6);seqListPrint(ps);seqListPushFront(ps, 7);seqListPushFront(ps, 8);seqListPushFront(ps, 9);seqListPushFront(ps, 10);seqListPrint(ps);int x=SeqListFind(ps, 11);if (x == -1){printf("没有\n");}SeqListInsert(ps, 5, 20);SeqListInsert(ps, 6, 30);SeqListInsert(ps, 7, 50);seqListPrint(ps);SeqListErase(ps, 5);//seqListPrint(ps);SeqListErase(ps, 5);//seqListPrint(ps);SeqListErase(ps, 5);seqListPrint(ps);
}int main()
{SL a;//初始化seqListInit(&a);//测试1//test1(&a);//测试2//test2(&a);//测试3test3(&a);//释放空间seqListDestort(&a);return 0;
}

今天的分享就到这里了谢谢大家的阅读,我也会更加努力给大家带来更加优质的文章的


http://www.ppmy.cn/news/983804.html

相关文章

JSON格式Python，Java,PHP等封装获取淘宝店铺所有商品数据API

JSON格式Python，Java,PHP等封装获取淘宝店铺所有商品数据API

淘宝是一个网上购物平台&#xff0c;售卖各类商品&#xff0c;包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取淘宝天猫店铺商品详情描述数据&#xff0c;您可以通过开放平台的接口或者直接访问淘宝天猫商城的网页来获取店铺所有商品列表详细信息。以下是两种常用方法…
阅读更多...
java-day01

java-day01

一&#xff1a;基础常识 软件&#xff1a;按照特定顺序的计算机数据与指令的集合。可分为系统软件&#xff08;如操作系统&#xff09;和应用软件&#xff08;如QQ&#xff09; 人机交互方式&#xff1a;图形化界面&#xff08;GUI&#xff09;与命令行&#xff08;CLI&#…
阅读更多...
推荐系统-ALS协同过滤算法实现

推荐系统-ALS协同过滤算法实现

从协同过滤的分类来说&#xff0c;ALS&#xff08;Alternating Least Squares&#xff0c;交替最小二乘&#xff09;算法属于User-Item CF&#xff0c;也叫做混合CF&#xff0c;它同时考虑了User和Item两个方面&#xff0c;通过数量相对少的未被观察到的隐藏因子&#xff0c;来…
阅读更多...
运算放大器基础（二）

运算放大器基础（二）

5.4.4基于理想运放的放大倍数分析 集成运放两个工作区&#xff1a; 线性区、非线性区 集成运放的理想化参数&#xff1a; 理想运放在线性区的特点 集成运放工作在线性区的电路特征
阅读更多...
Pytest学习教程_基础知识（一）

Pytest学习教程_基础知识（一）

前言 pytest是一个用于编写和执行Python单元测试的框架。它提供了丰富的功能和灵活性&#xff0c;使得编写和运行测试变得简单而高效。 pytest的一些主要特点和解释如下&#xff1a; 自动发现测试&#xff1a;pytest会自动查找以"test_"开头的文件、类和函数&#x…
阅读更多...
前端html中让两个或者多个div在一行显示，用style给div加上css样式

前端html中让两个或者多个div在一行显示，用style给div加上css样式

文章目录 前言一、怎么让多个div在一行显示 前言 DIV是层叠样式表中的定位技术&#xff0c;全称DIVision&#xff0c;即为划分。有时可以称其为图层。DIV在编程中又叫做整除&#xff0c;即只得商的整数。 DIV元素是用来为HTML&#xff08;标准通用标记语言下的一个应用&#x…
阅读更多...
Day 64：集成学习之 AdaBoosting (2. 树桩分类器)

Day 64：集成学习之 AdaBoosting (2. 树桩分类器)

做了一个超类, 用于支持不同的基础分类器. 这里为了减少代码量, 只实现了树桩分类器.树桩分类器每次只将数据分成两堆, 与决策树相比, 简单至极. 当然, 这里处理的是实型数据, 而 ID3 处理的是符号型数据. 抽象分类器代码&#xff1a; package dl;import java.util.Random;im…
阅读更多...
MySQL 8.0 OCP (1Z0-908) 考点精析-架构考点1：二进制日志文件（Binary log）

MySQL 8.0 OCP (1Z0-908) 考点精析-架构考点1：二进制日志文件（Binary log）

文章目录 MySQL 8.0 OCP (1Z0-908) 考点精析-架构考点1&#xff1a;二进制日志文件&#xff08;Binary log&#xff09;MySQL二进制日志&#xff08;Binary log&#xff09;二进制日志文件的相关配置二进制日志文件的相关参数的说明二进制日志的格式设置二进制日志的格式 二进制…
阅读更多...
最新文章

Copyright @ 2022~2023