顺序表SeqList

  • 开发
  • 52

顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。

一、顺序表的特性

逻辑结构：线性结构

存储结构：顺序存储

特点：内存连续，大小是固定的。

操作:增删改查

二、数组操作

例题：

int a[100]={1,2,3,4,5,6,7,8};

函数命名规则：

下划线法：create_empty_seqlist

小驼峰法：createEmptySeqList

大驼峰法：CreateEmptySeqList

#include <stdio.h>

/*  (1)插入数组元素
    功能：向数组的第几个位置插数据
    函数：void insetIntoA(int *p,int n, int post, int data);
    参数：
    int *p: 保存数组首地址
    int n: 有效数据元素的个数
    int post: 插入元素下标
    int data: 数据
*/
void insertIntoA(int *p, int n, int post, int data)
{
      
    //1. 把从最后一个元素p[n-1]到插入位置元素p[post]向后移动一个单位
    for (int i = n - 1; i >= post; i--)
        p[i + 1] = p[i];
    //2. 插入新元素data到指定位置
    p[post] = data;
}

/*  (2)遍历数组
    功能：遍历数组中的有效元素
    函数：void showA(int *p,int n);
    参数：
    int *p:保存数组收地址
    int n:有效数据元素的个数
*/
void showA(int *p, int n) //p=a,n=8;
{
      
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", p[i]);
    printf("\n");
}

/*  (3)删除数组元素
    功能：删除数组中指定元素 
    函数：void deleteIntoA(int *p,int n, int post);
    参数：
    int *p: 保存数组首地址
    int n: 有效数据元素的个数
    int post: 删除元素下标
*/
void deleteIntoA(int *p, int n, int post) //a的值 9 4
{
      
    int i;
    //从删除位置的后一个元素p[post+1]到最有后一个元素p[n-1]往前移动一个单位
    for (i = post + 1; i < n; i++) //for(i=4+1;i<9;i++)
        p[i - 1] = p[i];
}
int main(int argc, char const *argv[])
{
      
    int a[100] = {
      1, 2, 3, 4, 5, 6, 7, 8};
    showA(a, 8);
    insertIntoA(a, 8, 2, 100);
    showA(a, 9);
    deleteIntoA(a, 9, 4);
    showA(a, 8);
    return 0;
}

插入元素不会增加空间，导致元素丢失

删除元素不会减少遍历。

三、 数组操作优化：通过添加全局变量

添加全局变量last表示最后一个有效元素下标

#include <stdio.h>
int last = 7; //代表最后一个有效元素得下标 last=有效元素个数-1

/*  (1)插入数组元素
    功能：向数组的第几个位置插数据
    函数：void insetIntoA(int *p,int post, int data);
    参数：
    int *p: 保存数组首地址
    int post: 插入元素下标
    int data: 数据
*/
void insertIntoA(int *p, int post, int data)
{
      
    //1. 把从最后一个元素p[last]到插入位置元素p[post]向后移动一个单位
    for (int i = last; i >= post; i--)
        p[i + 1] = p[i];
    //2. 插入新元素data到指定位置
    p[post] = data;
    //3. 最后一个有效元素下标+1
    last++;
}

/*  (2)遍历数组
    功能：遍历数组中的有效元素
    函数：void showA(int *p);
    参数：
    int *p:保存数组收地址
*/
void showA(int *p)
{
      
    int i;
    for (i = 0; i <= last; i++)
        printf("%d ", p[i]);
    printf("\n");
}

/*  (3)删除数组元素
    功能：删除数组中指定元素 
    函数：void deleteIntoA(int *p,int post);
    参数：
    int *p: 保存数组首地址
    int post: 删除元素下标
*/
void deleteIntoA(int *p, int post)
{
      
    int i;
    //1.从删除位置的后一个元素p[post+1]到最有后一个元素p[last]往前移动一个单位
    for (i = post + 1; i <= last; i++)
        p[i - 1] = p[i];
    //2.将最后一个有效元素下标减一
    last--;
}
int main(int argc, char const *argv[])
{
      
    int a[100] = {
      1, 2, 3, 4, 5, 6, 7, 8};
    showA(a);    //1 2 3 4 5 6 7 8
    insertIntoA(a, 2, 100);
    showA(a);    //1 2 100 3 4 5 6 7 8
    deleteIntoA(a, 4);
    showA(a);    //1 2 100 3 5 6 7 8 
    return 0;
}

四、顺序表的实现

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

#define N 10
typedef int datatype; //int a; <==> datatype a;
typedef struct seqlist
{
      
    datatype data[N]; //相当于int data[N];
    int last;         //代表数组中最后一个有效元素得下标
} seqlist_t;
//struct seqlist s; 相当于 seqlist_t s;

//创建空顺序表
seqlist_t *CreateEpSeqlist()
{
      
    //1.动态申请一块空间存放顺序表
    seqlist_t *p = (seqlist_t *)malloc(sizeof(seqlist_t));
    if (NULL == p)
    {
      
        perror("CreateEpSeqlist p malloc err");
        return NULL;
    }
    //2.对last初始化
    p->last = -1;
    return p;
}

//判断顺序表是否为满，满返回1,未满返回0。
int IsFullSeqlist(seqlist_t *p)
{
      
    return p->last + 1 == N;
}

//向顺序表的指定位置插入
int InsertIntoSeqlist(seqlist_t *p, int post, int data)
{
      
    int i;
    //1.容错判断
    if (post < 0 || post > p->last + 1 || IsFullSeqlist(p))
    {
      
        printf("InsertIntoSeqlist post err\n");
        return -1; //错误返回
    }
    //2.从下标为post到last的元素往后移动一个单位
    for (i = p->last; i >= post; i--)
        p->data[i + 1] = p->data[i];
    //3.插入数据
    p->data[post] = data;
    //4.让last加一
    p->last++;
    return 0;
}

//遍历顺序表sequence顺序list表。
void ShowSeqlist(seqlist_t *p)
{
      
    for (int i = 0; i <= p->last; i++)
        printf("%d ", p->data[i]);
    printf("\n");
}

//判断顺序表是否为空，为空返回1，不为空返回0。
int IsEpSeqlist(seqlist_t *p)
{
      
    return p->last == -1;
}

//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_t *p, int post)
{
      
    //1.容错判断
    if (IsEpSeqlist(p) || post < 0 || post > p->last)
    {
      
        printf("DeleteIntoSeqlist err!\n");
        return -1;
    }
    //2.从下标为post+1到最后下标为last的位置的元素向前移动一个单位
    for (int i = post + 1; i <= p->last; i++)
        p->data[i - 1] = p->data[i];
    //3.让有效元素下标p->last减一
    p->last--;
    return 0;
}

//清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_t *p, int post)
{
      
    p->last = -1; //让最后一个有效元素下标last为-1代表顺序表为空
}

//修改指定位置的数据
int ChangePostSeqList(seqlist_t *p, int post, int data)
{
      
    //1.容错判断
    if (post < 0 || post > p->last || IsEpSeqlist(p))
    {
      
        printf("ChangePostSeqList err!\n");
        return -1;
    }
    //2.修改指定位置post上的数据
    p->data[post] = data;
    return 0;
}

//查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_t *p, int data)
{
      
    for(int i=0;i<=p->last;i++)
    {
      
        if(p->data[i] == data)
            return i;
    }
    return -1;
}

int main(int argc, char const *argv[])
{
      
    seqlist_t *p = CreateEpSeqlist();
    printf("is EpSeqlist? %d\n", IsEpSeqlist(p));
    InsertIntoSeqlist(p, 0, 1);
    InsertIntoSeqlist(p, 1, 2);
    InsertIntoSeqlist(p, 2, 3);
    InsertIntoSeqlist(p, 3, 4);
    InsertIntoSeqlist(p, 4, 5);
    ShowSeqlist(p);
    DeleteIntoSeqlist(p, 3);
    ShowSeqlist(p);
    printf("search 5 post: %d\n",SearchDataSeqList(p,5));

    return 0;
}

五、顺序表分文件编程

头文件seqlist.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#define N 10
typedef int datatype;
typedef struct seqlist
{
      
    datatype data[N]; //相当于int data[N];
    int last;         //代表数组中最后一个有效元素得下标
} seqlist_t;

seqlist_t *CreateEpSeqlist();                            //创建空顺序表
int IsFullSeqlist(seqlist_t *p);                         //判断顺序表是否为满，满返回1,未满返回0。
int InsertIntoSeqlist(seqlist_t *p, int post, int data); //向顺序表的指定位置插入
void ShowSeqlist(seqlist_t *p);                          //遍历顺序表sequence顺序list表。
int IsEpSeqlist(seqlist_t *p);                           //判断顺序表是否为空，为空返回1，不为空返回0。
int DeleteIntoSeqlist(seqlist_t *p, int post);           //删除顺序表中指定位置的数据，post为删除位置
void ClearSeqList(seqlist_t *p, int post);               //清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
int ChangePostSeqList(seqlist_t *p, int post, int data); //修改指定位置的数据
int SearchDataSeqList(seqlist_t *p, int data);           //查找指定数据出现的位置,返回下标，未找到返回-1

#endif

放操作顺序表函数文件seqlist.c

#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"

//创建空顺序表
seqlist_t *CreateEpSeqlist()
{
      
    //1.动态申请一块空间存放顺序表
    seqlist_t *p = (seqlist_t *)malloc(sizeof(seqlist_t));
    if (NULL == p)
    {
      
        perror("CreateEpSeqlist p malloc err");
        return NULL;
    }
    //2.对last初始化
    p->last = -1;
    return p;
}

//判断顺序表是否为满，满返回1,未满返回0。
int IsFullSeqlist(seqlist_t *p)
{
      
    return p->last + 1 == N;
}

//向顺序表的指定位置插入
int InsertIntoSeqlist(seqlist_t *p, int post, int data)
{
      
    int i;
    //1.容错判断
    if (post < 0 || post > p->last + 1 || IsFullSeqlist(p))
    {
      
        printf("InsertIntoSeqlist post err\n");
        return -1; //错误返回
    }
    //2.从下标为post到last的元素往后移动一个单位
    for (i = p->last; i >= post; i--)
        p->data[i + 1] = p->data[i];
    //3.插入数据
    p->data[post] = data;
    //4.让last加一
    p->last++;
    return 0;
}

//遍历顺序表sequence顺序list表。
void ShowSeqlist(seqlist_t *p)
{
      
    for (int i = 0; i <= p->last; i++)
        printf("%d ", p->data[i]);
    printf("\n");
}

//判断顺序表是否为空，为空返回1，不为空返回0。
int IsEpSeqlist(seqlist_t *p)
{
      
    return p->last == -1;
}

//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_t *p, int post)
{
      
    //1.容错判断
    if (IsEpSeqlist(p) || post < 0 || post > p->last)
    {
      
        printf("DeleteIntoSeqlist err!\n");
        return -1;
    }
    //2.从下标为post+1到最后下标为last的位置的元素向前移动一个单位
    for (int i = post + 1; i <= p->last; i++)
        p->data[i - 1] = p->data[i];
    //3.让有效元素下标p->last减一
    p->last--;
    return 0;
}

//清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_t *p, int post)
{
      
    p->last = -1; //让最后一个有效元素下标last为-1代表顺序表为空
}

//修改指定位置的数据
int ChangePostSeqList(seqlist_t *p, int post, int data)
{
      
    //1.容错判断
    if (post < 0 || post > p->last || IsEpSeqlist(p))
    {
      
        printf("ChangePostSeqList err!\n");
        return -1;
    }
    //2.修改指定位置post上的数据
    p->data[post] = data;
    return 0;
}

//查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_t *p, int data)
{
      
    for(int i=0;i<=p->last;i++)
    {
      
        if(p->data[i] == data)
            return i;
    }
    return -1;
}

放主函数的文件main.c

#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"

int main(int argc, char const *argv[])
{
      
    seqlist_t *p = CreateEpSeqlist();
    printf("is EpSeqlist? %d\n", IsEpSeqlist(p));
    InsertIntoSeqlist(p, 0, 1);
    InsertIntoSeqlist(p, 1, 2);
    InsertIntoSeqlist(p, 2, 3);
    InsertIntoSeqlist(p, 3, 4);
    InsertIntoSeqlist(p, 4, 5);
    ShowSeqlist(p);
    DeleteIntoSeqlist(p, 3);
    ShowSeqlist(p);
    printf("search 5 post: %d\n", SearchDataSeqList(p, 5));

    return 0;
}

makefile

CC=gcc
GFLAGS=-c -g -Wall
OBJS=seqlist.o main.o

seqlist:$(OBJS)
	$(CC) $^ -o $@
%.o:%.c
	$(CC) $(GFLAGS) $< -o $@
.PHONY:clean
clean:
	$(RM) seqlist *.o

顺序表总结：

  1. 内存连续存储
  2. 长度固定
  3. 查找和修改效率高，删除和插入效率低。

阅读全部

相关推荐

  2. <span style='color:red;'>顺序</span><span style='color:red;'>表</span>

    顺序表

    2023-12-12 12:42:01      82 阅读

  4. 顺序表和链表

    2023-12-12 12:42:01       30 阅读

  7. 顺序表的应用

    2023-12-12 12:42:01       56 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-12 12:42:01       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-12 12:42:01       106 阅读

  9. 在Django里面运行非项目文件

    2023-12-12 12:42:01       87 阅读

  19. Python语言-面向对象

    2023-12-12 12:42:01       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2023-12-12 12:42:01       91 阅读

热门阅读

  1. 【ITK库学习】使用itk库进行图像滤波ImageFilter：模糊降噪

    2023-12-12 12:42:01       68 阅读

  2. 三（四）ts非基础类型（数组）

    2023-12-12 12:42:01       55 阅读

  4. 【力扣100】48.旋转图像

    2023-12-12 12:42:01       58 阅读

  5. HTTP与HTTPS的区别

    2023-12-12 12:42:01       53 阅读

  9. 算法通关村第十八关 | 白银 | 回溯热门问题

    2023-12-12 12:42:01       70 阅读

  10. springboot中使用aop实现方法拦截处理

    2023-12-12 12:42:01       58 阅读
  11. 打包CSS

    打包CSS

    2023-12-12 12:42:01      60 阅读

  13. C语言实现求1000以内的全部亲密数

    2023-12-12 12:42:01       62 阅读

  14. 在 WordPress 循环中排除置顶文章

    2023-12-12 12:42:01       65 阅读

  17. 【Jeecg Boot 3 - 第二天】第2节 前后端docker部署云服务器

    2023-12-12 12:42:01       57 阅读

  24. 力扣70. 爬楼梯

    2023-12-12 12:42:01       63 阅读

  25. this是指向的哪个全局变量,改变this指向的方法有几种？

    2023-12-12 12:42:01       60 阅读

  27. 纯js+css实现手风琴

    2023-12-12 12:42:01       58 阅读

  29. linux常用命令-curl命令详解（超详细）

    2023-12-12 12:42:01       53 阅读

  30. LeetCode160. Intersection of Two Linked Lists

    2023-12-12 12:42:01       45 阅读