数据结构——线性表和顺序表

🕗 发布于 2025-01-16 08:08 数据结构

1、线性表的基本概念

1.1 定义

线性结构是简单且常用的数据结构，而线性表则是一种典型的线性结构

存储数据，最简单，最有效的方法是吧它们存储在一个线性表中

一个线性表是n个元素的有限序列。每个元素在不同的情况下有不同的含义，可以是整数，也可以是字符

线性表：是具有相同数据类型的n个数据元素的有限序列

1.2 特点：围绕一对一关系进行描述

存在唯一的第一个元素

存在唯一的最后一个元素

除第一个元素外，每一个元素只有一个直接前驱

除最后一个元素外，每一个元素均只有一个直接后继

1.3 逻辑结构：线性结构

1.4 线性表的存储结构

顺序存储结构：顺序表

链式存储结构：链表

1.5 操作

表：创建、销毁

数据：增删改查

2、顺序表

2.1 定义

就是把线性表中的所有元素按照其逻辑顺序依次存储到指定位置开始的一块连续的存储区域

线性表中的第1个元素的存储位置就是指定的存储位置，第i个元素的存储位置紧接第i-1个元素的存储位置的后面

2.2 特点

顺序表的元素是按顺序进行存储的，第i项就存在第i个位置

对顺序表中的所有元素，既可以顺序访问，也可以随机访问，比较擅长随机访问和遍历

不擅长插入、删除操作，需要移动大量元素

2.3 操作

表：创建、销毁

数据：增删改查

2.4 顺序表的实现方式：数组、指针

2.4.1 顺序表的数组的实现方式

顺序表和数组进行对比

1、数组是一种特殊的顺序表

2、顺序表是通过数组来实现的，顺序表的元素存储在一块连续的存储空间中

3、数组的长度是不可变的，顺序表的长度是可以改变的

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h> //需要使用memset时引用
//创建顺序表结构体类型
#define MAX_SIZE 100 //宏定义，为了维护简单
typedef int elementType; //重命名，为了维护简单
typedef struct Order_List {
   elementType data[MAX_SIZE]; //数组：存放顺序表元素
   int lenth; //顺序表的元素总个数
}OrderList;

void print_menu();
OrderList* create_list();
void append_List(OrderList* List, elementType val);
void print_List(OrderList* List);
void insert_List(OrderList* List, int index, elementType val);
void delete_List(OrderList* List, int index);
void edit_List(OrderList* List, int index, elementType val);
void destory_List(OrderList* List);

int main() {
   print_menu();
   int order = 0; //存储用户输入的操作指令
   //创建顺序表变量
   //OrderList list; //结构体变量，静态分配
   OrderList* List = NULL; //结构体指针，动态申请，手动释放
   elementType val = 0;
   int index = 0;
   while (1) {
       printf("请输入操作指令：");
       scanf("%d", &order);
       switch (order) {
           case 1: //创建顺序表
               //创建空表
               List = create_list();
               break;
           case 2: //打印顺序表
               print_List(List);
               break;
           case 3: //追加一个节点，尾部插入
               printf("请输入要追加的元素：");
               scanf(" %d", &val);
               append_List(List, val);
               break;
           case 4: //插入一个节点，随机插入，从0开始
               printf("请输入要插入的位置：");
               scanf(" %d", &index);
               printf("请输入要插入的元素：");
               scanf(" %d", &val);
               insert_List(List, index, val);
               break;
           case 5: //删除一个节点，从1开始
               printf("请输入要删除第几个元素：");
               scanf(" %d", &index);
               delete_List(List, index);
               break;
           case 6: //修改顺序表元素，从1开始
               printf("请输入要修改的元素位置：");
               scanf(" %d", &index);
               printf("请输入修改后的新值：");
               scanf(" %d", &val);
               edit_List(List, index, val);
               break;
           case 7: //销毁顺序表

//List存放的是表的地址，需要销毁List的地址，才能销毁顺序表
               destory_List(&List);
               break;
           case 8: //退出
               break;
           default:
               printf("输入错误，请重新输入！");
       }
       if (order == 8) {
           break;
       }
   }
   return 0;
}

//打印菜单
void print_menu() {
   system("cls"); //系统函数，用于屏幕清空
   printf("操作指令：\n");
   printf("1、创建顺序表\n");
   printf("2、打印顺序表\n");
   printf("3、追加一个节点\n");
   printf("4、插入一个节点\n");
   printf("5、删除一个节点\n");
   printf("6、修改顺序表元素\n");
   printf("7、销毁顺序表\n");
   printf("8、退出\n");
}

//创建空表
OrderList* create_list() {
   //申请内存
   //malloc分配的内存空间不确定，一般使用memset初始化
   OrderList* List = (OrderList*)malloc(sizeof(OrderList));
   //申请失败
   if (List == NULL) {
       printf("内存申请失败，创建失败！\n");
       return NULL;
   }
   //申请成功
   //需要导入memory.h或string.h
   memset(List, 0, sizeof(OrderList)); //功能：将指定内存设置为指定内容，一般用来进行数组清零
   List->lenth = 0;
   printf("初始化成功！\n");
   return List;
}

//追加一个节点，末尾增加
void append_List(OrderList* List, elementType val) {
   //判断是否初始化
   if (List == NULL) { //!List
       printf("请先建表\n");
       return;
   }
   //判断表是否已满
   if (List->lenth >= MAX_SIZE) {
       printf("表已满，无法追加！\n");
       return;
   }
   //正常追加
   List->data[List->lenth] = val;
   List->lenth++;
   printf("追加成功！\n");
}

//打印顺序表
void print_List(OrderList* List) {
   //判断是否初始化
   if (List == NULL) { //!List
       printf("请先建表\n");
       return;
   }

   if (List->lenth == 0) {
       printf("空表，无法打印！\n");
       return;
   }
   //正常打印
   for (int i = 0;i < List->lenth;i++) {
       printf("%d ", List->data[i]);
   }
   printf("\n");
}

//插入一个节点，随机插入
void insert_List(OrderList* List, int index, elementType val) {
   //判断是否初始化
   if (List == NULL) { //!List
       printf("请先建表\n");
       return;
   }
   //判断表是否已满
   if (List->lenth == 0) {
       printf("空表，无法打印！\n");
       return;
   }
   //正常插入，倒序遍历，位置后移
   for (int i = List->lenth - 1;i >= index;i--) {
       List->data[i + 1] = List->data[i];
   }
   List->data[index] = val;
   List->lenth++;
   printf("插入成功！\n");
}

//删除
void delete_List(OrderList* List, int index) {
   //判断是否初始化
   if (List == NULL) { //!List
       printf("请先建表\n");
       return;
   }
   //判断索引是否合法
   int ind = index - 1; //要删除的元素的索引
   if (ind<0 || ind>List->lenth - 1) {
       printf("请输入合适的位置！\n");
       return;
   }
   //执行删除，元素前移
   for (int i = ind;i < List->lenth;i++) {
       List->data[i] = List->data[i + 1];
   }
   List->lenth--;
   printf("删除成功！\n");
}

//修改
void edit_List(OrderList* List, int index, elementType val) {
   //判断是否初始化
   if (List == NULL) { //!List
       printf("请先建表\n");
       return;
   }
   //判断索引是否合法
   int ind = index - 1; //要删除的元素的索引
   if (ind<0 || ind>List->lenth - 1) {
       printf("您要修改的元素不存在！\n");
       return;
   }
   //执行修改
   List->data[ind] = val;
   printf("修改成功！\n");
}

//销毁注意：形参是二级指针
void destory_List(OrderList** List) {
   free(*List); //释放内存空间
   *List = NULL; //销毁后要置空
   printf("销毁成功！\n");
}

2.4.2 顺序表的指针的实现方式

2.4.2.1 02.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h>
#define MAX_SIZE 100
typedef int ElementT;
//定义结构体类型
typedef struct OrderListPtr {
ElementT* datap; //元素类型指针，用于申请内存后，存放数组元素
int length; //存放数组元素的总个数
}ODP;
void print_menu();
void create_List(ODP* list);
void append_List(ODP* list, ElementT value);
void print_List(ODP list);
void insert_List(ODP* list, int index, ElementT value);
void delete_List(ODP* list, int index);
void delete_List(ODP* list, int index);
void edit_List(ODP* list, int index, ElementT value);
void destroy_List(ODP* list);

2.4.2.1 02.c

#include "02.h"
//顺序表的指针的实现方式

//如果要改datap或length的值需要传地址，不需要则传值

void fn2() {
   while (1) {
       print_menu();
       int order = 0; //存储用户输入的操作指令
       ODP list = { NULL,0 }; //定义结构体变量
       ElementT value = 0;
       int index = 0;
       while (1) {
           printf("请输入操作指令：");
           scanf("%d", &order);
           switch (order) {
           case 1: //创建顺序表
               //创建空表
               create_List(&list);
               break;
           case 2: //打印顺序表
               print_List(list);
               break;
           case 3: //追加一个节点，尾部插入
               printf("请输入要追加的元素：");
               scanf(" %d", &value);
               append_List(&list, value);
               break;
           case 4: //插入一个节点，随机插入，从0开始
               printf("请输入要插入的元素的位置：");
               scanf(" %d", &index);
               printf("请输入要插入的元素：");
               scanf(" %d", &value);
               insert_List(&list, index, value);
               break;
           case 5: //删除一个节点，从1开始
               printf("请输入要删除的元素的位置：");
               scanf(" %d", &index);
               delete_List(&list, index);
               break;
           case 6: //修改顺序表元素，从1开始
               printf("请输入要修改的元素的位置：");
               scanf(" %d", &index);
               printf("请输入要修改的元素：");
               scanf(" %d", &value);
               edit_List(&list, index, value);
               break;
           case 7: //销毁顺序表
               destroy_List(&list);
               break;
           case 8: //退出
               break;
           default:
               printf("输入错误，请重新输入！");
           }
           if (order == 8) {
               break;
           }
       }
       return 0;
   }
}
//打印菜单
void print_menu() {
   system("cls"); //系统函数，用于屏幕清空
   printf("操作指令：\n");
   printf("1、创建顺序表\n");
   printf("2、打印顺序表\n");
   printf("3、追加一个节点\n");
   printf("4、插入一个节点\n");
   printf("5、删除一个节点\n");
   printf("6、修改顺序表元素\n");
   printf("7、销毁顺序表\n");
   printf("8、退出\n");
}
//创建顺序表
void create_List(ODP* list) {
   //申请内存空间
   list->datap = (ElementT*)malloc(sizeof(ElementT*) * MAX_SIZE);
   if (!list->datap) {
       printf("内存申请失败！\n");
       return;
   }
   //清0
   memset(list->datap, 0, sizeof(ElementT*) * MAX_SIZE);
   list->length = 0;
   printf("初始化成功！\n");
}

//追加一个节点，尾部插入
void append_List(ODP* list, ElementT value) {
   //判断是否建过表
   if (!list->datap) {
       printf("请先建表！\n");
       return;
   }
   //判断表是否满
   if (list->length >= MAX_SIZE) {
       printf("表已满，无法追加！\n");
       return;
   }
   //正常追加
   *(list->datap + list->length) = value; //list->datap首元素的地址
   另一种方法
   //list->datap[list->length] = value;
   list->length++;
   printf("追加成功！\n");
}

//打印顺序表
void print_List(ODP list) {
   if (!list.datap) {
       printf("请先建表！\n");
       return;
   }
   if (list.length == 0) {
       printf("空表，无法打印！\n");
       return;
   }
   for (int i = 0;i < list.length;i++) {
       printf("%d ", list.datap[i]); //当成数组
       另一种方法
       //printf("%d ", *(list.datap + i)); //当成指针
   }
   printf("\n");
}

//插入一个节点，随机插入，从0开始
void insert_List(ODP* list, int index, ElementT value) {
   //判断是否建过表
   if (!list->datap) {
       printf("请先建表！\n");
       return;
   }
   //判断表是否满
   if (list->length >= MAX_SIZE) {
       printf("表已满，无法插入！\n");
       return;
   }
   //正常插入
   //从index位置，倒叙遍历，位置后移
   for (int i = list->length - 1;i >= index;i--) {
       list->datap[i + 1] = list->datap[i];
   }
   //判断插入的位置是否合法
   if (index<0 || index>list->length - 1) {
       printf("插入位置不合法！\n");
       return;
   }
   list->datap[index] = value;
   另一种方法
   //*(list->datap + list->length) = value;
   list->length++;
   printf("插入成功！\n");
}

//删除一个节点，从1开始
void delete_List(ODP* list, int index) {
   //判断是否建过表
   if (!list->datap) {
       printf("请先建表！\n");
       return;
   }
   if (list->length == 0) {
       printf("空表，无法删除！\n");
       return;
   }
   //判断要删除的元素的位置是否合法
   int ind = index - 1;
   if (ind<0 || ind>list->length - 1) {
       printf("您要删除的元素不存在！\n");
       return;
   }
   //正常删除，从index开始，所有元素前移
   for (int i = ind;i < list->length;i++) {
       list->datap[i] = list->datap[i + 1];
   }
   list->length--;
   printf("删除成功！\n");
}

//修改顺序表元素，从1开始
void edit_List(ODP* list, int index, ElementT value) {
   //判断是否建过表
   if (!list->datap) {
       printf("请先建表！\n");
       return;
   }
   if (list->length == 0) {
       printf("空表，无法修改！\n");
       return;
   }
   //判断要修改的元素的位置是否合法
   int ind = index - 1;
   if (ind<0 || ind>list->length - 1) {
       printf("您要修改的元素不存在！\n");
       return;
   }
   //正常修改
   list->datap[ind] = value;
   另一种方法
   //*(list->datap + ind) = value;
   printf("修改成功！\n");
}

//销毁顺序表
void destroy_List(ODP* list) {
   //判断是否建过表
   if (!list->datap) {
       printf("请先建表！\n");
       return;
   }
   free(list->datap); //释放内存
   list->datap = NULL;
   list->length = 0;
   printf("销毁成功！\n");
}

2.4.2.1 02main.c

#include "02.h"
int main() {
fn2();
return 0;
}

原文地址：https://blog.csdn.net/2301_81699298/article/details/145132033

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

上一篇：《leetcode-runner》【图解】如何手搓一个debug调试器——调试程序【JDI开发】【万字详解】
下一篇：【华为路由/交换机的ssh远程设置】

深度学习J9周：Inception v3算法实战与解析
计算机视觉任务中，Inception v3在图像分类、物体检测和图像分割等方面均表现优异。通过学习，对深度学习更了解了，从代码和网络图也可以看出网络结构越来越深和复杂，需要自己多花时间学习，研究。下一
阅读更多2025-01-18
集成方案 | Docusign + Oracle，实现合同签署与管理的高效协同！
本文将详细介绍 Docusign 与 Oracle 的集成步骤及其效果，并通过实际应用场景来展示 Docusign 的强大集成能力，以证明 Docusign 集成功能的高效性和实用性。
阅读更多2025-01-18
【达梦数据库（Oracle模式）】如何将视图中的数据导出
在某些情况下，我们需要将生产环境某个模式下的数据导入到开发电脑中，因为正式环境无法连接外网数据。
阅读更多2025-01-18
Docker详解与部署微服务实战
这跟 Maven的仓库有点类似，如果把 Docker Registry比作 Maven仓库的话，那么 Docker仓库就可理解为某jar包的路径，而镜像标签则可理解为jar包的版本号。使用命令dock
阅读更多2025-01-18
PostgreSQL 中进行数据导入和导出
在 PostgreSQL 中，数据的导入和导出是数据库管理中不可或缺的操作。通过使用COPYCOPYpg_dump和pg_dumpall等工具，您可以高效地管理您的数据。掌握这些命令和技巧，将有助于提
阅读更多2025-01-18
反转字符串II力扣--541
给定一个字符串s和一个整数k，从字符串开头算起，每计数至2k个字符，就反转这2k字符中的前k个字符。
阅读更多2025-01-18
[BrainShadow-V1] VR头戴设备统计报告
#xiaoen #设备统计 #选用分析 #BrainShadow
阅读更多2025-01-18
20250118 Flink中的延迟执行机制和数据处理的逻辑拓扑结构（向圖）
【代码】20250118 Flink中的延迟执行机制和数据处理的逻辑拓扑结构（向圖）
阅读更多2025-01-18
CrossFormer实战：使用CrossFormer实现图像分类任务（二）
训练部分。
阅读更多2025-01-18
开源AI智能名片2+1链动模式S2B2C商城小程序在ABM漏斗中的应用探索
本文旨在深入探讨开源AI智能名片2+1链动模式S2B2C商城小程序在目标客户营销（Account Based Marketing，ABM）漏斗中的应用，旨在揭示其如何通过智能化、数据化和社交化的方式，
阅读更多2025-01-18