顺序表的应用

文章目录

  • 目录
    • 1. 基于动态顺序表实现通讯录项目
    • 2.顺序表经典算法
      • 2.1 [移除元素](https://leetcode.cn/problems/remove-element/description/)
      • 2.2 [合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/description/)
    • 3. 顺序表的问题及思考

目录

  • 基于动态顺序表实现通讯录项目
  • 顺序表经典算法
  • 顺序表的问题及思考

1. 基于动态顺序表实现通讯录项目

我们先写一个框架：

//Contact.h#include <stdio.h>//暂时加上

//ConTest.c#include "Contact.h"//通讯录菜单
void menu()
{printf("******************通讯录******************\n");printf("*******1. 添加联系人  2.删除联系人********\n");printf("*******3. 修改联系人  4.查找联系人********\n");printf("*******5. 查看通讯录  0.  退 出   ********\n");printf("******************************************\n");
}int main()
{int op = -1;do{menu();printf("请选择您的操作：\n");scanf("%d", &op);switch (op){case 1://添加联系人break;case 2://删除联系人break;case 3://修改联系人break;case 4://查找联系人break;case 5://查看通讯录break;case 0://退出通讯录printf("通讯录退出中...\n");break;default:break;}} while (op != 0);return 0;
}

接着，我们就可以开始添加具体操作了：

先要创建通讯录数据类型：

//Contact.h#define NAME_MAX 100
#define GENDER_MAX 10
#define TEL_MAX 12
#define ADDR_MAX 100//通讯录数据类型
typedef struct PersonInfo
{char name[NAME_MAX];int age;char gender[GENDER_MAX];char tel[TEL_MAX];char addr[ADDR_MAX];
}Info;

我们要把之前写的顺序表中数组的类型进行替换：

//SeqList.h#include "Contact.h"typedef Info SLDataType;

然后我们写接口：

//Contact.h//通讯录提供的操作typedef struct SeqList Contact;//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表

这里我们想把 SL 换成 Contact，这样看上去更好理解，所以就要 typedef struct SeqList Contact; ，但是要使用struct SeqList 就要 #include “SeqList.h” ，但是这样会出现一个问题：
头文件嵌套问题
解决办法：前置声明

//Contact.h//使用顺序表的前置声明
struct SeqList;typedef struct SeqList Contact;//通讯录提供的操作//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表
void ContactDestroy(Contact* pcon);//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon);
void ContactDel(Contact* pcon);
void ContactModify(Contact* pcon);
void ContactFind(Contact* pcon);
void ContactShow(Contact* pcon);

此外，以下代码不再适用，直接注释掉：

//SeqList.c//在顺序表中查找x
//int SLFind(SL* ps, SLDataType x)
//{
//	//加上断言对代码的健壮性更好
//	assert(ps);
//
//	for (int i = 0; i < ps->size; i++)
//	{
//		if (x == ps->arr[i])
//		{
//			return i;
//		}
//	}
//
//	return -1;
//}

因为现在 ps->arr[i] 已经变成一个结构体了，不能直接使用 == 来比较

接下来就是方法的具体实现：

//Contact.c//#include "Contact.h"
#include "SeqList.h"//通讯录的初始化和销毁
//SL* ps
void ContactInit(Contact* pcon)
{SLInit(pcon);
}void ContactDestroy(Contact* pcon)
{SLDestroy(pcon);
}//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon)
{//创建联系人结构体变量Info info;printf("请输入联系人姓名:\n");scanf("%s", info.name);printf("请输入联系人年龄:\n");scanf("%d", &info.age);printf("请输入联系人性别:\n");scanf("%s", info.gender);printf("请输入联系人电话:\n");scanf("%s", info.tel);printf("请输入联系人住址:\n");scanf("%s", info.addr);//保存数据到通讯录（顺序表）SLPushBack(pcon, info);
}void ContactShow(Contact* pcon)
{printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "住址");for (int i = 0; i < pcon->size; i++){printf("%s %s %d %s %s\n",pcon->arr[i].name,pcon->arr[i].gender,pcon->arr[i].age,pcon->arr[i].tel,pcon->arr[i].addr);}
}int FindByName(Contact* pcon, char name[])
{for (int i = 0; i < pcon->size; i++){if (0 == strcmp(pcon->arr[i].name, name)){//找到了return i;}}return -1;
}void ContactDel(Contact* pcon)
{//删除之前一定要先查找//找到了，可以删除//找不到，不能执行删除printf("请输入要删除的联系人姓名:\n");char name[NAME_MAX];scanf("%s", name);int findIndex = FindByName(pcon, name);if (findIndex < 0){printf("要删除的联系人不存在！\n");return;}//执行删除操作SLErase(pcon, findIndex);printf("联系人删除成功！\n");
}void ContactModify(Contact* pcon)
{//修改之前要先查找//找到了，执行修改操作//没有找到，不能执行修改操作char name[NAME_MAX];printf("请输入要修改的联系人姓名\n");scanf("%s", name);int findIndex = FindByName(pcon, name);if (findIndex < 0){printf("要修改的联系人不存在！\n");return;}//找到了，执行修改操作printf("请输入姓名:\n");scanf("%s", pcon->arr[findIndex].name);printf("请输入年龄:\n");scanf("%d", &pcon->arr[findIndex].age);printf("请输入性别:\n");scanf("%s", pcon->arr[findIndex].gender);printf("请输入电话:\n");scanf("%s", pcon->arr[findIndex].tel);printf("请输入地址:\n");scanf("%s", pcon->arr[findIndex].addr);printf("联系人修改成功！\n");
}void ContactFind(Contact* pcon)
{char name[NAME_MAX];printf("请输入要查找的用户姓名:\n");scanf("%s", name);int findIndex = FindByName(pcon, name);if (findIndex < 0){printf("该联系人不存在！\n");return;}//找到了，打印一下查找的联系人信息printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "住址");printf("%s %s %d %s %s\n",pcon->arr[findIndex].name,pcon->arr[findIndex].gender,pcon->arr[findIndex].age,pcon->arr[findIndex].tel,pcon->arr[findIndex].addr);
}

完整代码：

//SeqList.h#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "Contact.h"//动态顺序表typedef Info SLDataType;typedef struct SeqList
{SLDataType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);//顺序表的尾部插入
void SLPushBack(SL* ps, SLDataType x);//删除指定位置数据
void SLErase(SL* ps, int pos);

//SeqList.c#include "SeqList.h"//初始化和销毁
void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (NULL == tmp){perror("realloc fail!");exit(1);}//扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}//顺序表的尾部插入
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//空间不够，扩容SLCheckCapacity(ps);//空间足够，直接插入ps->arr[ps->size++] = x;
}//删除指定位置数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}void SLDestroy(SL* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

//Contact.h#define NAME_MAX 100
#define GENDER_MAX 10
#define TEL_MAX 12
#define ADDR_MAX 100//通讯录数据类型
typedef struct PersonInfo
{char name[NAME_MAX];int age;char gender[GENDER_MAX];char tel[TEL_MAX];char addr[ADDR_MAX];
}Info;//使用顺序表的前置声明
struct SeqList;typedef struct SeqList Contact;//通讯录提供的操作//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表
void ContactDestroy(Contact* pcon);//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon);
void ContactDel(Contact* pcon);
void ContactModify(Contact* pcon);
void ContactFind(Contact* pcon);
void ContactShow(Contact* pcon);

//Contact.c#include "SeqList.h"//通讯录的初始化和销毁
//SL* ps
void ContactInit(Contact* pcon)
{SLInit(pcon);
}void ContactDestroy(Contact* pcon)
{SLDestroy(pcon);
}//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon)
{//创建联系人结构体变量Info info;printf("请输入联系人姓名:\n");scanf("%s", info.name);printf("请输入联系人年龄:\n");scanf("%d", &info.age);printf("请输入联系人性别:\n");scanf("%s", info.gender);printf("请输入联系人电话:\n");scanf("%s", info.tel);printf("请输入联系人住址:\n");scanf("%s", info.addr);//保存数据到通讯录（顺序表）SLPushBack(pcon, info);
}int FindByName(Contact* pcon, char name[])
{for (int i = 0; i < pcon->size; i++){if (0 == strcmp(pcon->arr[i].name, name)){//找到了return i;}}return -1;
}void ContactDel(Contact* pcon)
{//删除之前一定要先查找//找到了，可以删除//找不到，不能执行删除printf("请输入要删除的联系人姓名:\n");char name[NAME_MAX];scanf("%s", name);int findIndex = FindByName(pcon, name);if (findIndex < 0){printf("要删除的联系人不存在！\n");return;}//执行删除操作SLErase(pcon, findIndex);printf("联系人删除成功！\n");
}void ContactModify(Contact* pcon)
{//修改之前要先查找//找到了，执行修改操作//没有找到，不能执行修改操作char name[NAME_MAX];printf("请输入要修改的联系人姓名\n");scanf("%s", name);int findIndex = FindByName(pcon, name);if (findIndex < 0){printf("要修改的联系人不存在！\n");return;}//找到了，执行修改操作printf("请输入姓名:\n");scanf("%s", pcon->arr[findIndex].name);printf("请输入年龄:\n");scanf("%d", &pcon->arr[findIndex].age);printf("请输入性别:\n");scanf("%s", pcon->arr[findIndex].gender);printf("请输入电话:\n");scanf("%s", pcon->arr[findIndex].tel);printf("请输入地址:\n");scanf("%s", pcon->arr[findIndex].addr);printf("联系人修改成功！\n");
}void ContactFind(Contact* pcon)
{char name[NAME_MAX];printf("请输入要查找的用户姓名:\n");scanf("%s", name);int findIndex = FindByName(pcon, name);if (findIndex < 0){printf("该联系人不存在！\n");return;}//找到了，打印一下查找的联系人信息printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "住址");printf("%s %s %d %s %s\n",pcon->arr[findIndex].name,pcon->arr[findIndex].gender,pcon->arr[findIndex].age,pcon->arr[findIndex].tel,pcon->arr[findIndex].addr);
}void ContactShow(Contact* pcon)
{printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "住址");for (int i = 0; i < pcon->size; i++){printf("%s %s %d %s %s\n",pcon->arr[i].name,pcon->arr[i].gender,pcon->arr[i].age,pcon->arr[i].tel,pcon->arr[i].addr);}
}

//ConTest.c#include "SeqList.h"//通讯录菜单
void menu()
{printf("******************通讯录******************\n");printf("*******1. 添加联系人  2.删除联系人********\n");printf("*******3. 修改联系人  4.查找联系人********\n");printf("*******5. 查看通讯录  0.  退 出   ********\n");printf("******************************************\n");
}int main()
{int op = -1;//创建通讯录结构对象Contact con;ContactInit(&con);do{menu();printf("请选择您的操作：\n");scanf("%d", &op);switch (op){case 1://添加联系人ContactAdd(&con);break;case 2://删除联系人ContactDel(&con);break;case 3://修改联系人ContactModify(&con);break;case 4://查找联系人ContactFind(&con);break;case 5://查看通讯录ContactShow(&con);break;case 0://退出通讯录printf("通讯录退出中...\n");break;default:break;}} while (op != 0);//销毁通讯录ContactDestroy(&con);return 0;
}

2.顺序表经典算法

2.1 移除元素

移除元素

int removeElement(int* nums, int numsSize, int val)
{//定义两个变量int src = 0, dst = 0;while (src < numsSize){//nums[src] == val,src++//否则赋值,src和dst都++if (nums[src] == val){src++;}else{//说明src指向位置的值不等于valnums[dst] = nums[src];dst++;src++;}}//此时dst的值刚好是数组的新长度return dst;
}

2.2 合并两个有序数组

合并两个有序数组

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1 = m - 1;int l2 = n - 1;int l3 = m + n - 1;while (l1 >= 0 && l2 >= 0){//从后往前比大小if (nums1[l1] > nums2[l2]){nums1[l3--] = nums1[l1--];}else{nums1[l3--] = nums2[l2--];}}//要么是l1 < 0，要么是l2 < 0while (l2 >= 0){nums1[l3--] = nums2[l2--];}
}

3. 顺序表的问题及思考

  1. 中间/头部的插入删除，时间复杂度为O(N)。
  2. 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
  3. 增容一般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

是否存在一种数据结构，能够解决以上顺序表表现出来的问题：

  1. 中间/头部的插入删除，可以一步到位，不需要挪动数据
  2. 不需要扩容
  3. 不会造成空间浪费

链表这种数据结构就可以解决这些问题，我们在下一篇中就会进行介绍。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/298937.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

VSCode好用插件

VSCode好用插件

由于现在还是使用vue2&#xff0c;所以本文只记录vue2开发中好用的插件。 美化类插件不介绍了&#xff0c;那些貌似对生产力起不到什么大的帮助&#xff0c;纯粹的“唯心主义”罢了&#xff0c;但是如果你有兴趣的话可以查看上一篇博客&#xff1a;VSCode美化 1. vuter 简介&…
阅读更多...
特朗普数字钱包被空投100万MVP，加密资产或将提供更多竞选资金

特朗普数字钱包被空投100万MVP，加密资产或将提供更多竞选资金

唐纳德.特朗普先生对待加密货币的态度正在发生改变&#xff0c;曾经他对加密货币持有负面的态度&#xff0c;曾多次在公开场合批评比特币等数字货币。然而&#xff0c;随着特朗普NFT等加密资产的上链&#xff0c;他对加密货币的态度也发生了巨大的转变。 据相关媒体报道&#x…
阅读更多...
Hadoop-入门

Hadoop-入门

资料来源&#xff1a;尚硅谷-Hadoop 一、Hadoop 概述 1.1 Hadoop 是什么 1&#xff09;Hadoop是一个由Apache基金会所开发的分布式系统基础架构。 2&#xff09;主要解决&#xff1a;海量数据的存储和海量数据的分析计算问题。 3&#xff09;广义上来说&#xff0c;Hadoop…
阅读更多...
政安晨【AIGC实践】（一）：在Kaggle上部署使用Stable Diffusion

政安晨【AIGC实践】（一）：在Kaggle上部署使用Stable Diffusion

目录 简述 开始 配置 执行 安装完毕&#xff0c;一键运行 结果展示 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: 人工智能数字虚拟世界实践 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提…
阅读更多...
GIt 删除某个特定commit

GIt 删除某个特定commit

目的 多次commit&#xff0c;想删掉中间的一个/一些commit 操作方法 一句话说明&#xff1a;利用rebase命令的d表示移除commit的功能&#xff0c;来移除特定的commit # 压缩这3次commit,head~3表示从最近1次commit开始&#xff0c;前3个commit git rebase -i head~3rebase…
阅读更多...
UNIAPP(小程序)每十个文章中间一个广告

UNIAPP(小程序)每十个文章中间一个广告

三十秒刷新一次广告 ad-intervals"30" <template><view style"margin: 30rpx;"><view class"" v-for"(item,index) in 100"><!-- 广告 --><view style"margin-bottom: 20rpx;" v-if"(inde…
阅读更多...
物联网行业中，我们如何选择数据库？

物联网行业中，我们如何选择数据库？

在当今数字化潮流中&#xff0c;我们面对的不仅是海量数据&#xff0c;更是时间的涟漪。从生产线的传感器到金融市场的交易记录&#xff0c;时间序列数据成为了理解事物演变和趋势的关键。在面对这样庞大而动态的数据流时&#xff0c;我们需要深入了解一种强大的工具——时序数…
阅读更多...
03-自媒体文章发布

03-自媒体文章发布

自媒体文章发布 1)自媒体前后端搭建 1.1)后台搭建 ①&#xff1a;资料中找到heima-leadnews-wemedia.zip解压 拷贝到heima-leadnews-service工程下&#xff0c;并指定子模块 执行leadnews-wemedia.sql脚本 添加对应的nacos配置 spring:datasource:driver-class-name: com…
阅读更多...
机器学习知识点全面总结

机器学习知识点全面总结

机器学习按照模型类型分为监督学习模型、无监督学习模型两大类。 1、有监督学习 有监督学习通常是利用带有专家标注的标签的训练数据&#xff0c;学习一个从输入变量X到输入变量Y的函数映射。Y f (X)&#xff0c;训练数据通常是(nx,y)的形式&#xff0c;其中n代表训练样本的大…
阅读更多...
初识二叉树和二叉树的基本操作

初识二叉树和二叉树的基本操作

目录 一、树 1.什么是树 2. 与树相关的概念 二、二叉树 1.什么是二叉树 2.二叉树特点 3.满二叉树与完全二叉树 4.二叉树性质 相关题目&#xff1a; 5.二叉树的存储 6.二叉树的遍历和基本操作 二叉树的遍历 二叉树的基本操作 一、树 1.什么是树 子树是不相交的;…
阅读更多...
了解这些技术：Flutter应用顺利登陆iOS平台的步骤与方法

了解这些技术：Flutter应用顺利登陆iOS平台的步骤与方法

引言 &#x1f680; Flutter作为一种跨平台的移动应用程序开发框架&#xff0c;为开发者提供了便利&#xff0c;使他们能够通过单一的代码库构建出高性能、高保真度的应用程序&#xff0c;同时支持Android和iOS两个平台。然而&#xff0c;完成Flutter应用程序的开发只是第一步…
阅读更多...
HTML转pdf批量高效转换：释放文本潜力，让信息流动更自由！

HTML转pdf批量高效转换：释放文本潜力，让信息流动更自由！

在数字化信息的海洋中&#xff0c;HTML以其灵活性和互动性成为网页内容的标准格式。然而&#xff0c;有时我们需要将网页内容保存为PDF格式&#xff0c;以确保信息的稳定性和易读性。为了满足这一需求&#xff0c;我们推出了一款强大的HTML转PDF批量高效转换工具&#xff0c;让…
阅读更多...
网络安全 | 什么是单点登录SSO？

网络安全 | 什么是单点登录SSO？

关注WX&#xff1a;CodingTechWork SSO-概念 单点登录 (SSO) 是一种身份认证方法&#xff0c;用户一次可通过一组登录凭证登入会话&#xff0c;在该次会话期间无需再次登录&#xff0c;即可安全访问多个相关的应用和服务。SSO 通常用于管理一些环境中的身份验证&#xff0c;包…
阅读更多...
如何在 Mac 上恢复已删除的数据

如何在 Mac 上恢复已删除的数据

如果您丢失了 Mac 上的数据&#xff0c;请不要绝望。恢复数据比您想象的要容易&#xff0c;并且有很多方法可以尝试。 在 Mac 上遭受数据丢失是每个人都认为永远不会发生在他们身上的事情之一......直到它发生。不过&#xff0c;请不要担心&#xff0c;因为您可以通过多种方法…
阅读更多...
笔记-Building Apps with the ABAP RESTful Application Programming Model-Week3

笔记-Building Apps with the ABAP RESTful Application Programming Model-Week3

Week3 Unit 1: The Enhanced Business Scenario 本节介绍了将要练习的demo的业务场景，在前两周成果的基础上，也就是只读列表，也可以说是报表APP基础上启用了事务能力，也就是CURD以及自定义业务功能的能力，从创建基本的behavior definition，然后behavior definition proj…
阅读更多...
OSPF协议详解

OSPF协议详解

静态缺点 1、中大型复杂网络----配置量大 2、不能实时收敛 动态-----可以实时收敛 IGP----内部网关路由协议 RIP OSPF EIGRP ISIS EGP----外部网关路由协议 BGP IGP &#xff08;选路佳 占用资源 收敛快&#xff09;----一个协议好需满足这三个 距离矢量 DV RIP…
阅读更多...
wordpress全站开发指南-面向开发者及深度用户（全中文实操）--初尝php

wordpress全站开发指南-面向开发者及深度用户（全中文实操）--初尝php

初尝php 打开你下载的wordpress文件夹&#xff0c;如果你用的xampp那它就在xampp安装的文件夹–htdocs文件夹–你可以新建一个test文件夹–新建一个test.php文件 <html><head><title>First attempt at PHP</title></head><body><?ph…
阅读更多...
NoSQL概述

NoSQL概述

NoSQL概述 目录 一、为什么用NoSQL 二、什么是NoSQL 三、经典应用分析 四、N o S Q L 数 据 模 型 简 介 五、NoSQL四大分类 六、CAP BASE 一、为什么用NoSQL 1、单机MySQL的美好年代 在90年代&#xff0c;一个网站的访问量一般不大&#xff0c;用单个数据库完全可以轻松应…
阅读更多...
VScode debug python（服务器）

VScode debug python（服务器）

方法一&#xff1a; 创建launch.json文件&#xff1a; launch.json文件地址&#xff1a; launch.json文件内容&#xff1a; {"version": "0.2.0", //指定了配置文件的版本"configurations": [{"name": "Python: Current File&…
阅读更多...
C++:日期类的实现 const修饰 取地址及const取地址操作符重载(类的6个默认成员函数完结篇)

C++:日期类的实现 const修饰 取地址及const取地址操作符重载(类的6个默认成员函数完结篇)

一、日期类的实现 根据之前赋值运算符重载逻辑&#xff0c;我们现在来实现完整的日期类。 1.1 判断小于 上篇博客已经实现: bool operator<(const Date& d) {if (_year < d._year){return true;}else if (_year d._year){if (_month < d._month){return true…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023