#数据结构顺序表

🕗 发布于 2024-07-07 17:49 数据结构 算法

线性表

顺序表

每种结构都有它存在意义

线性表的顺序存储实现指的是用一组连续的存储单元存储线性表的数据元素。

概念

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

逻辑结构：线性结构

物理结构：顺序存储结构

线性表的特点：一对一，每个节点最多一个前驱和一个后继，首尾节点特殊：首节点无前驱，尾节点无后继

顺序表前言

操作：

1.创建一个空的顺序表

2.向顺序表的指定位置插入数据

3.删除顺序表指定位置的数据

命名法则：

大驼峰：InsertInto

小驼峰: insertinto

加下划线: insert_into

见名知意；

练习1:

int buf[32] = {1,996,520,4,5,6,7,8}; // 8 个最后一个下标 7 n-1

1 996 520 100 4 5 6 7 8

（1）向数组的第几个位置插入数据

int  *p   //保存的数组的首地址
int  n //n代表的是数组中有效的元素个数（非数组的长度size 100）
int  post; //位置代表的是第几个位置（数组元素下标），数组元素下标 位置的编号从0开始 position
int  data;//插入到数组中的数据
int  InsertInto(int *p,int n,int post,int data);

（2）遍历数组中的有效元素

int  *p        //保存的数组的首地址
int  n//n代表的是数组中有效的元素个数（非数组的长度size 100）
void  Show(int *p,int n)

int main()
{
int  buf[32] = {1,996,520,4,5,6,7,8}; // 8 个最后一个下标 7  n-1
InsertInto(buf,8,3, 100); // 1 996 520 100 4 5 6 7 8
Show(buf,9);//1 996 520 100 4 5 6 7 8
return 0;
}

#include <stdio.h>
int InsertInto(int *p,int n,int post,int data);
void Show(int *p,int n);
int main(int argc, const char *argv[])
{

int buf[32] = {1,996,520,4,5,6,7,8};
InsertInto(buf,8,3,100);
Show(buf,9);

return 0;
}
int  InsertInto(int *p,int n,int post,int data)
{
int i;

if(post < 0 || post > n)
{
printf("InsertInto error\n");
return  -1;
}
for(i = n -1; i >= post; i--)
{
p[i+1] = p[i];
}
p[post] = data;

return 0;
}
void Show(int *p,int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ",p[i]);
}
putchar(10);
}

1 996 520 100 4 5 6 7 8

练习2:

修改成last版本后

前提条件：

全局变量：last :始终表示最后一个有效元素的下标

#include <stdio.h>
int  InsertInto(int *p,int post,int data);
void DeletPost(int *p,int post);
void Show(int *p);
//始终表示数组中最后一个有效元素的下标(全局变量)
int last = 7;
int main(int argc, const char *argv[])
{

int buf[32] = {1,996,520,4,5,6,7,8};
InsertInto(buf,3,100);
Show(buf);
DeletPost(buf,3);
Show(buf);
return 0;
}
int  InsertInto(int *p,int post,int data)
{
int i;

if(post < 0 || post > last+1)
{
printf("InsertInto error\n");
return  -1;
}
for(i = last; i >= post; i--)
{
p[i+1] = p[i];
}
p[post] = data;
last++;
return 0;
}

void DeletPost(int *p,int post)
{
if(post < 0 || post > last)
{
printf("DeletPost error\n");

}
int i;
#if 0
for(i = post; i < last; i++)
{
p[i] = p[i+1];

//p[last] = p[last+1]
}
#endif
#if 1
for(i = post +1; i <= last; i++)
{
        p[i-1] = p[i];

    //p[last -1] = p[last]
}
#endif
last--;
}
void Show(int *p)
{
int i;
for(i = 0; i <= last; i++)
{
printf("%d ",p[i]);
}
putchar(10);
}


1 996 520 100 4 5 6 7 8 
1 996 520 4 5 6 7 8

顺序表：SequeueList

顺序表操作函数

#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include <stdio.h>
#include <stdlib.h>
// 1. 定义操作顺序表的结构体
#define N 5      // 定长数组的大小
typedef int DataType;// 顺序表数据类型
typedef  struct  seq
{
DataType data[N];  
int last;//last始终代表数组中最后一个有效元素的下标 
}SL;
//1.创建一个空的顺序表
SL *CreateEpSeqlist();//返回的是申请空间的首地址
//2.向顺序表的指定位置插入数据
int InsertIntoSeqlist(SL *p, int post,DataType data);//post第几个位置，data插入的数据
//3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(SL *p);
//4.判断顺序表是否为满,满返回１ 未满返回０
int IsFullSeqlist(SL *p);
//5.判断顺序表是否为空
int IsEpSeqlist(SL *p);
//6.删除顺序表中指定位置的数据post删除位置
int DeletePostSeqlist(SL *p, int post);
//7.清空顺序表
void ClearSeqList(SL *p)
//8.修改指定位置的数据
int ChangePostSeqList(SL *p,int post,DataType data);//post被修改的位置，data修改成的数据
//9.查找指定数据出现的位置
int SearchDataSeqList(SL *p,DataType data);//data代表被查找的数据
#endif

为了后续方便需改表中数据的数据类型，我们可以typedef一个新的数据类型叫做DataType顺序表数据类型。

为了让在定义结构体变量或结构体指针时使用更方便，我们同样可以将struct SeqList重定义为SL。

此时SL == struct SeqList

创建seqlist.h函数声明头文件
创建seqlist.c函数实现源文件
创建main.c用来测试顺序表接口

定义操作顺序表的结构体

// 1. 定义操作顺序表的结构体
#define N 5     // 定长数组的大小
typedef int DataType;// 顺序表数据类型
typedef  struct  seq
{
DataType data[N];  
int last;//last始终代表数组中最后一个有效元素的下标 
}SL;

all:
    gcc main.c seqlist.c -o seqlist

创建空顺序表

SL *CreateEpList()
{
SL *p = (SL*)malloc(sizeof(SL));
if(NULL == p)//NULL == p; NULL = p;p = NULL;
{
printf("malloc error\n");
return NULL;
}
    //int last = -1;
p->last = -1;
return p;
}

#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include <stdlib.h>
#include <stdio.h>
#define N 5
typedef int datatype;
typedef struct seq
{
datatype data[N];
int last;
//last始终代表数组中最后一个有效元素的下标 
}SL;
//创建一个表（表首地址返回）
SL *CreateEpList();
//2.向顺序表的指定位置插入数据
#endif

#include "seqlist.h"
int main(int argc, const char *argv[])
{
SL *p = CreateEpList();
        return 0;
}

插入

post不能小于0
post不能大于last + 1
表不能溢出last+1不能大于N

//2.向顺序表的指定位置插入数据
int InsertIntoSeqlist(SL *p, int post,datatype data)//post第几个位置，data插入的数据
{
if(IsFullSeqlist(p) || post < 0 || post > p->last+1)
{
printf("InsertIntoSeqlist error\n");
return -1;
}
int i;
for(i = p->last; i >= post; i--)
{
p->data[i+1] = p->data[i];
}
p->data[post] = data;
p->last++;
    return 0;
}
//3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(SL *p)
{     
   int i;
   for(i = 0; i <= p->last; i++)
   {
   printf("%d ",p->data[i]);
   }
   putchar(10);
}
//4.判断顺序表是否为满,满返回１ 未满返回０
int IsFullSeqlist(SL *p)
{
return p->last == N -1;
//真（1） 假（0）
}

99 88 77 
99 66 88 77

打印

//3.遍历顺序表sequence 顺序 list 表
void ShowSeqlist(SL *p)
{     
   int i;
   for(i = 0; i <= p->last; i++)
   {
   printf("%d ",p->data[i]);
   }
   putchar(10);
}

查找

查找指定数据出现的位置下标

思路：自变量为顺序表下标[0, last]，for循环进行遍历访问，如果相等返回下标。

缺陷：无法返回重复出现数据的位置下标

解决办法：不做要求。

//9.查找指定数据出现的位置
int SearchDataSeqList(SL *p,datatype data)//data代表被查找的数据
{

if(IsEpSeqlist(p))
{
printf("SearchDataSeqList error\n");
return -1;
}
int i;
for(i = 0; i <= p->last; i++)
{
if(p->data[i] == data)
return i;
} 
    return -1;
}

修改

修改顺序表指定位置的数据。

参数：

结构体指针P
修改的位置post
期望的数据data

步骤：

容错判断 [0, last]
直接修改 P->data[post] = data

//8.修改指定位置的数据
int ChangePostSeqList(SL *p,int post,datatype data)//post被修改的位置，data修改成的数据
{

   if(IsEpSeqlist(p) || post < 0 || post > p->last)
   {
printf("ChangePostSeqList error\n");
return -1;
   }
   
   p->data[post] = data;
   return 1;
}

删除

删除顺序表中指定位置的数据

参数：

结构体指针P
删除的位置post

步骤：

容错判断同修改接口[0, last]
post+1~last向前移动

5.判断顺序表是否为空
int IsEpSeqlist(SL *p)
{
     return p->last == -1;
}
//6.删除顺序表中指定位置的数据post删除位置
int DeletePostSeqlist(SL *p, int post)
{
if(IsEpSeqlist(p) || post < 0 || post > p->last)
{
printf("DeletePostSeqlist error\n");
return -1;
}
int i;
#if 0
for(i = post; i < p->last; i++)
{
p->data[i] = p->data[i+1];
}
#endif
#if 1
for(i = post+1; i <= p->last; i++)
{
p->data[i-1] = p->data[i];
}
#endif
p->last--;
return 0;
}

#include "seqlist.h"
int main(int argc, const char *argv[])
{
SL *p = CreateEpList();
InsertIntoSeqlist(p,0,99);
InsertIntoSeqlist(p,1,88);
InsertIntoSeqlist(p,2,77);
ShowSeqlist(p);
InsertIntoSeqlist(p,1,66);
ShowSeqlist(p);
DeletePostSeqlist(p,1);
ShowSeqlist(p);
return 0;
}

99 88 77 
99 66 88 77 
99 88 77

原文地址：https://blog.csdn.net/weixin_58298518/article/details/140163746

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：基于深度学习的异常行为检测
下一篇：中心差商法【python，算法】

多模态—图文匹配
在模型训练时我们需要N个图片和N个文本对进行训练，文本通过text encoder形成文本语义向量，text encoder可以采用BERT，GPT，Bart等，图片也需要通过image encode
阅读更多2024-10-05
新160个crackme - 073-abexcrackme3
C++程序分析，ida：call analysis failed无法分析伪代码处理，ida静态分析
阅读更多2024-10-05
【洛谷】AT_abc372_e [ABC372E] K-th Largest Connected Components 的题解
看 @guozhetao 大佬，写了这篇题解，然后发现我刚好也水过这场比赛的 D 题的题解，刚好顺便切一下 E，然后来写一个题解。查询的时候，直接找到这个点在哪个块内，然后查询相应值即可。，实现两个连
阅读更多2024-10-05
[C++][第三方库][Elasticsearch]详细讲解
[C++][第三方库][Elasticsearch]详细讲解
阅读更多2024-10-05
yub‘s Algorithmic Adventures_Day5
我们想实现的是1和2交换，3和 4交换，此时很难不想到借用中间变量实现，不用递归实现【每次单独处理头节点】更优雅.与数组不同，链表没必要定义新的链表进行存储【对内存空间的浪费】判断next.next不
阅读更多2024-10-05
【LeetCode】每日一题 2024_9_30 座位预约管理系统（堆）
【LeetCode】每日一题 2024_9_30 座位预约管理系统（堆）
阅读更多2024-10-05
LLM端侧部署系列 | 手机上运行47B大模型?上交推理框架PowerInfer-2助力AI手机端侧部署
近日，上海交大为大模型能够在智能手机上部署提出PowerInfer-2，该框架是专为智能手机设计且高度优化的推理框架。目前PowerInfer-2支持的最大模型是Mixtral 47B MoE模型，在
阅读更多2024-10-05
关于Generator，async 和 await的介绍
在本篇文章中我们主要围绕下面几个问题来介绍async 和await🍰Generator的作用，async 及 await 的特点，它们的优点和缺点分别是什么？await 原理是什么？📅我的感受是我们先
阅读更多2024-10-05
Python日常搜索_random
Python日常搜索_random
阅读更多2024-10-05
JavaScript模块化-CommonJS规范和ESM规范
CommonJS 是 Node.js 最初采用的模块系统，基于 require 和 module.exports以及exports 实现动态模块加载。尽管ESM才是官方的模块化标准，但是CommonJ
阅读更多2024-10-05

#数据结构 顺序表

线性表

顺序表

概念

顺序表前言

顺序表操作函数

定义操作顺序表的结构体

创建空顺序表

插入

打印

查找

修改

删除

相关文章

#数据结构顺序表