C语音顺序表专题及应用

数据结构引进

0数据结构相关概念

0.1什么是数据结构

数据结构是由“数据”和“结构”两词组合而来。
什么是数据?常见的数值1、2、3、4…、教务系统⾥保存的用户信息(姓名、性别、年龄、学历等等)、网页肉眼可以看到的信息(⽂字、图⽚、视频等等),这些都是数据

什么是结构?
当我们想要使用⼤量使用同⼀类型的数据时,通过手动定义⼤量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将大量的数据组织在⼀起,结构也可以理解为组织数据的方式。

想要找到草原上名叫“咩咩”的羊很难,但是从羊圈里找到1号羊就很简单,羊圈这样的结构有效将羊群组织起来。

概念:**数据结构是计算机存储、组织数据的方式。**数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据元素之间呈现的结构。

总结:
(1).能够存储数据(如顺序表,链表等结构)
(2).存储的数据能够方便查找

0.2.为什么需要数据结构

程序如果不对数据进行管理,可能导致数据丢失,操作数据困难期,野指针等情况
通过数据结构,能够有效将数据组织和管理在一起,按照我们的方式任意对数据进行增删改查等操作
最基础的数据结构:数组
在这里插入图片描述

假定数组有10个空间,已经使用了5个,向数组中插入数据步骤:
求数组的长度,求数组的有效数据个数,向下标为数据有效个数的位置插入数据(注意:这里是否要判断数组是否满了,满了还能继续插入吗)…
假设数据量非常庞⼤,频繁的获取数组有效数据个数会影响程序执行效率。
结论:最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。

顺序表

1.顺序表的概念及结构

1.1线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表,链表,栈,队列,字符串…
线性表在逻辑上是线性结构,也就是连续的一条直线,但是物理结构上并不一定是连续的
线性表在物理上存储时,通常以数组和链式结构形式存储
线性表指的是具有部分相同特性的一类数据结构的集合

2.顺序表分类

顺序表和数组的区别

  • 顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口
    顺序表分类
  • 静态顺序表
    • 概念:使用定长数组存储元素
      在这里插入图片描述
      +静态顺序表缺陷:空间给少了不够用,给多了造成空间浪费

动态顺序表
在这里插入图片描述

3 .动态顺序表的实习现

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
 	SLDataType* a;
	 int size; // 有效数据个数
	 int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插⼊/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

顺序表的应用

4.基于动态顺序表实现通讯录

  • C语言基础要求:结构体、动态内存管理、顺序表、文件操作

4.1功能要求

(1)至少能够存储100个人的通讯信息
(2)能够保存用户信息:名字,性别,年两千,电话,地址等
(3)增加联系人信息
(4)删除指定联系人
(5)查找指定联系人
(6)修改指定联系人
(7)显示联系人信息

4.2代码实现

【思考1】⽤静态顺序表和动态顺序表分别如何实现
【思考2】如何保证程序结束后,历史通讯录信息不会丢失

//SeqList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h> 
#include"contact.h"
//数据类型为PersonInfo
typedef struct PersonInfo SQDataType;
//typedef int SQDataType;
//动态顺序表
typedef struct SeqList {
	 SQDataType* a;
	 int size;//保存有效数据个数
	 int capacity;//空间的⼤⼩
}SLT;
//初始化与销毁
void SeqListInit(SLT* psl);
void SeqListDesTroy(SLT* psl);
void SeqListPrint(SLT sl);
void CheckCapacity(SLT* psl);
// 头部插⼊删除 / 尾部插⼊删除
void SeqListPushBack(SLT* psl, SQDataType x);
void SeqListPushFront(SLT* psl, SQDataType x);
void SeqListPopBack(SLT* psl);
void SeqListPopFront(SLT* psl);
//查找
int SeqListFind(SLT* psl, SQDataType x);
// 在指定位置之前插⼊/删除
//void SeqListInsert(SLT* psl, int pos, SQDataType x);
void SeqListInsert(SLT* psl, size_t pos, SQDataType x);
void SeqListErase(SLT* psl, size_t pos);
size_t SeqListSize(SLT* psl);
//修改指定位置的值
void SeqListAt(SLT* psl, size_t pos, SQDataType x);
#include<stdlib.h> 
#include"contact.h"
//数据类型为PersonInfo
typedef struct PersonInfo SQDataType;
//typedef int SQDataType;
//动态顺序表
typedef struct SeqList {
	 SQDataType* a;
 	int size;//保存有效数据个数
	 int capacity;//空间的⼤⼩
}SLT;
//初始化与销毁
void SeqListInit(SLT* psl);
void SeqListDesTroy(SLT* psl);
void SeqListPrint(SLT sl);
void CheckCapacity(SLT* psl);
// 头部插⼊删除 / 尾部插⼊删除
void SeqListPushBack(SLT* psl, SQDataType x);
void SeqListPushFront(SLT* psl, SQDataType x);
void SeqListPopBack(SLT* psl);
void SeqListPopFront(SLT* psl);
//查找
int SeqListFind(SLT* psl, SQDataType x);
// 在指定位置之前插⼊/删除
//void SeqListInsert(SLT* psl, int pos, SQDataType x);
void SeqListInsert(SLT* psl, size_t pos, SQDataType x);
void SeqListErase(SLT* psl, size_t pos);
size_t SeqListSize(SLT* psl);
//修改指定位置的值
void SeqListAt(SLT* psl, size_t pos, SQDataType x);
typedef struct SeqList contact;
//⽤⼾数据
typedef struct PersonInfo
{
 	 char name[NAME_MAX];
	 char sex[SEX_MAX];
	 int age;
	 char tel[TEL_MAX];
	 char addr[ADDR_MAX];
}PeoInfo;
//初始化通讯录
void InitContact(contact* con);
//添加通讯录数据
void AddContact(contact* con);
//删除通讯录数据
void DelContact(contact* con);
//展⽰通讯录数据
void ShowContact(contact* con);
//查找通讯录数据
void FindContact(contact* con);
//修改通讯录数据
void ModifyContact(contact* con);
//销毁通讯录数据
void DestroyContact(contact* con);
//contact.c
#define _CRT_SECURE_NO_WARNINGS
#include"contact.h"
#include"SeqList.h"
void LoadContact(contact* con) {
	 FILE* pf = fopen("contact.txt", "rb");
	 if (pf == NULL) {
		 perror("fopen error!\n");
		 return;
	 }
	 //循环读取⽂件数据
	 PeoInfo info;
	 while (fread(&info,sizeof(PeoInfo),1,pf))
	 {
		 SeqListPushBack(con, info);
	 }
	 printf("历史数据导⼊通讯录成功!\n");
}
void InitContact(contact* con) {
 	SeqListInit(con);
	 LoadContact(con);
}
void AddContact(contact* con) {
 	 PeoInfo info;
	 printf("请输⼊姓名:\n");
	 scanf("%s", &info.name);
	 printf("请输⼊性别:\n");
	 scanf("%s", &info.sex);
	 printf("请输⼊年龄:\n");
	 scanf("%d", &info.age);
	 printf("请输⼊联系电话:\n");
	 scanf("%s", &info.tel);
  	 printf("请输⼊地址:\n");
 	 scanf("%s", &info.addr);
 	 SeqListPushBack(con, info);
	 printf("插⼊成功!\n");
}
int FindByName(contact* con, char name[]) {
	 for (int i = 0; i < con->size; i++)
	 {
		 if (0 == strcmp(con->a[i].name, name)) {
		 return i;
		 }
	 }
	 return -1;
}
void DelContact(contact* con){
	 char name[NAME_MAX];
	 printf("请输⼊要删除的⽤⼾姓名:\n");
	 scanf("%s", name);
	 int pos = FindByName(con, name);
	 if (pos < 0) {
		 printf("要删除的⽤⼾不存在,删除失败!\n");
		 return;
	 }
	 SeqListErase(con, pos);
	 printf("删除成功!\n");
}
void ShowContact(contact* con){
	 printf("%-10s %-4s %-4s %15s %-20s\n", "姓名", "性别", "年龄", "联系电话", 
	 for (int i = 0; i < con->size; i++)
	 {
 		printf("%-10s %-4s %-4d %15s %-20s\n",
		con->a[i].name,
 		con->a[i].sex,
 		con->a[i].age,
 		con->a[i].tel,
 		con->a[i].addr);
	 }
}
void FindContact(contact* con){
 	char name[NAME_MAX];
	 printf("请输⼊要查找的⽤⼾姓名:\n");
	 scanf("%s", name);
	 int pos = FindByName(con, name);
	 if (pos < 0) {
		 printf("要查找的⽤⼾不存在,查找失败!\n");
		 return;
	 }
	 printf("查找成功!\n");
	 printf("%-10s %-4s %-4d %15s %-20s\n", 
 		con->a[pos].name,
 		con->a[pos].sex,
	    con->a[pos].age,
 		con->a[pos].tel,
 		con->a[pos].addr);
}
void ModifyContact(contact* con) {
	 char name[NAME_MAX];
	 printf("请输⼊要修改的⽤⼾名称:\n");
	 scanf("%s", name);
 	int pos = FindByName(con, name);
 	if (pos < 0) {
 		printf("要查找的⽤⼾不存在,修改失败!\n");
 		return;
 	}
 	PeoInfo info;
 	printf("请输⼊要修改的姓名:\n");
 	scanf("%s", &con->a[pos].name);
 	printf("请输⼊要修改的性别:\n");
 	scanf("%s", &con->a[pos].sex);
 	printf("请输⼊要修改的年龄:\n");
 	scanf("%d", &con->a[pos].age);
 	printf("请输⼊要修改的联系电话:\n");
 	scanf("%s", &con->a[pos].tel);
 	printf("请输⼊要修改的地址:\n");
 	scanf("%s", &con->a[pos].addr);
 	printf("修改成功!\n");
}
void SaveContact(contact* con) {
	 FILE* pf = fopen("contact.txt", "wb");
 	if (pf == NULL) {
 		perror("fopen error!\n");
 		return;
	 }
 	//将通讯录数据写⼊⽂件
	 for (int i = 0; i < con->size; i++)
	 {
		 fwrite(con->a + i, sizeof(PeoInfo), 1, pf);
	 }
 	printf("通讯录数据保存成功!\n");
}
void DestroyContact(contact* con) {
 	SaveContact(con);
 	SeqListDesTroy(con);
}
//test.c
#include"SeqList.h"
#include"contact.h"
void menu() {
 	//通讯录初始化
 	contact con;
 	InitContact(&con);
 	int op = -1;
 	do {
 		printf("********************************\n");
 		printf("*****1、添加⽤⼾ 2、删除⽤⼾*****\n");
 		printf("*****3、查找⽤⼾ 4、修改⽤⼾*****\n");
 		printf("*****5、展⽰⽤⼾ 0、退出 *****\n");
 		printf("********************************\n");
 		printf("请选择您的操作:\n");
 		scanf("%d", &op);
 		switch (op)
 		{
 		case 1:
 			AddContact(&con);
 			break;
 		case 2:
 			DelContact(&con);
 			break;
 		case 3:
 			FindContact(&con);
 			break;
 		case 4:
 			ModifyContact(&con);
 			break;
 		case 5:
 			ShowContact(&con);
 			break;
 		default:
 			printf("输⼊有误,请重新输⼊\n");
 			break;
 		}
	 } while (op!=0);
 	//销毁通讯录
 	DestroyContact(&con);
}

5.顺序表经典算法

经典算法OJ题1:移除元素
经典算法OJ题2:合并两个有序数组

6.顺序表的问题及思考

  • 1.中间/头部的插入删除,时间复杂度为O(n)

    • 解决:
    • 使用链表结构:对于单链表,在头部插入节点只需要重新调整指针,时间复杂度为O(1)。插入操作只需创建一个新节点,将新节点的指针指向原头部节点,然后更新头部指针指向新节点。在中间插入节点时,先找到要插入位置的前驱节点,然后调整指针将新节点插入,时间复杂度取决于查找前驱节点的时间,平均为O(n),但在已知位置插入时不需要移动大量数据,相比于顺序表性能有提升。
    • 使用跳表(Skip List)结构(适用于有序数据):跳表是在链表基础上改进的数据结构。它通过增加多层索引来提高查找、插入和删除的效率。在跳表中,每个节点有多个指针,除了指向后继节点的指针外,还有指向更高层索引节点的指针。查找一个元素时,可以通过高层索引快速定位到目标元素附近,然后在底层链表进行精确查找。插入和删除操作也能利用索引快速定位到相应位置,虽然插入和删除操作需要更新索引,但时间复杂度平均为O(log n),远低于顺序表在中间/头部操作的O(n)。
  • 2.增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗

    • 解决:
    • 预分配策略:根据数据的增长规律,采用更合理的预分配策略。例如,如果能预估数据量的大致范围,可以一次性分配足够的空间,避免频繁的增容操作。如果数据增长较为缓慢,可以按照较小的固定步长进行预分配,而不是简单的2倍增长。
    • 内存池技术:建立一个内存池,预先申请一块较大的内存空间。当需要为顺序表分配空间时,从内存池中获取内存块,而不是直接向操作系统申请。当顺序表释放空间时,将内存块归还到内存池而不是直接释放给操作系统。这样可以减少频繁的系统调用(申请和释放内存都涉及系统调用),提高效率。
  • 3.增容一般是2倍增长,势必有一定的空间浪费例如当前容量为100,满了以后增容到
    200,我们再继续插⼊了5个数据,后⾯没有数据插⼊了,那么就浪费了95个数据空间。

    • 解决:
    • 动态调整增容步长:不再固定按照2倍增长的方式进行增容。可以根据已使用空间和总空间的比例来动态调整增容步长。例如,当已使用空间达到总空间的80%时,可以按照1.5倍的步长进行增容;当已使用空间较低时,可以采用更小的增容步长。
    • 使用紧凑存储结构(如动态数组的优化):在适当的时候对数组进行紧凑操作。例如,当有大量的删除操作后,数组中可能存在很多空闲空间。可以将有效数据重新排列到数组的前部,释放后面的空闲空间。这样在后续的插入操作中,可以利用这些释放的空间,减少增容的需求。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

单元测试总结

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 Hello&#xff01;大家好&#xff0c;我是一个专注于分享软件测试干货的测试开发。 对于软件测试&#xff0c;我们先按照开发阶段来进行划分&#xff0c;将软件测…

immaculate C# DragDrop 注册失败 解决 C#窗口程序如何看控制台打印的日志

C# DragDrop 注册失败 System.InvalidOperationExceptionHResult0x80131509MessageDragDrop 注册失败。SourceSystem.Windows.FormsStackTrace:在 System.Windows.Forms.Control.SetAcceptDrops(Boolean accept)在 System.Windows.Forms.Control.OnHandleCreated(EventArgs e)…

怎样衡量电阻负载的好坏

电阻负载的好坏通常通过以下几种方法来衡量&#xff1a; 1. 测量电阻值&#xff1a;最直接的方法是使用万用表来测量电阻负载的电阻值。将万用表设置在适当的电阻档位&#xff0c;然后将测试笔连接到电阻负载的两个引脚上。如果电阻负载是好的&#xff0c;那么万用表应该显示一…

酒蒙子骰子小程序系统

酒蒙子流量变现小程序小游戏 后端tp8 前端uniapp 会员变现 分销推广 流量主 …

Spring Boot 3.x:自动配置类加载机制的变化

随着 Spring Boot 3.x 版本的发布&#xff0c;Spring Boot 引入了一些关键的变更。其中最重要的一项变更是 自动配置类的加载机制。在之前的版本中&#xff0c;Spring Boot 使用 spring.factories 文件来管理自动配置类的加载。然而&#xff0c;在 Spring Boot 3.x 中&#xff…

网络安全学习路线

《网络安全自学教程》 网络安全这几年改成了网络空间安全&#xff0c;因为网络空间也是国家主权之一&#xff0c;网络空间不安全&#xff0c;你就要在别人眼皮子底下裸奔&#xff0c;当然&#xff0c;非洲的小伙伴就不用担心受到威胁&#xff0c;毕竟他们连网都没有。 网络安全…

【Linux网络编程】第十一弹---HTTP协议全解析:从请求响应到方法与Header的详尽指南

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【Linux网络编程】 目录 1、HTTP 协议 1.1、认识 URL ​1.2、urlencode 和 urldecode 1.3、HTTP 协议请求与响应格式 1.3.1、代码…

从 Router 到 Navigation:HarmonyOS 路由框架的全面升级与迁移指南

在本教程中&#xff0c;我们深入探讨了 Router 和 Navigation 在 HarmonyOS 中的用法差异及如何从 Router 切换到 Navigation 的方法。重点涵盖了页面跳转、转场动画、生命周期管理以及跨包路由的实现。 页面结构对比 Router 页面结构 每个页面需要使用 Entry 注解。 页面需要…

账号下的用户列表表格分析

好的&#xff0c;这是您提供的 el-table 组件中所有列的字段信息&#xff0c;以表格形式展示&#xff1a; 列标题 (label)字段属性 (prop)对齐方式 (align)宽度 (width)是否可排序 (sortable)说明IDidcenter100否管理员的唯一标识符头像avatarcenter90否管理员的头像 URL 或路…

luckysheet与superslide冲突解决

[现象]控制台报错、界面无法操作 $是jquery。查看源码&#xff0c;发现mousewheel方法来自插件mousewheel&#xff0c;luckysheet初始应该会将mousewheel挂载在jquery上。 在控制台打印jquery取dom及其方法&#xff0c;结果如下&#xff1a; 不存在mousewheel方法&#xff0c…

windows使用python写的YOLO来实现目标识别

使用labelImg标注&#xff0c;YOLO进行目标训练 一、labelImg工具下载及使用1、下载labelImg&#xff08;目标标注工具[【点我下载】](https://github.com/HumanSignal/labelImg)&#xff09;2、使用labelImg 二、下载及使用YOLO1、下载及使用ultralytics&#xff08;volo[点击…

Java——多线程(上)

一 (线程的介绍) 1 多线程的基本概念 (每个进程由三部分构成——>CPU&#xff0c;Data&#xff0c;Code&#xff0c;进程之间完全独立&#xff0c;内存隔离) (运行在进程内的&#xff0c;一个进程可以包含多个线程&#xff0c;线程之间是可以并行的&#xff0c;并且共享相…

SpringBoot3+graalvm:整合并打包为可执行文件

原文网址&#xff1a;SpringBoot3graalvm&#xff1a;整合并打包为可执行文件-CSDN博客 简介 本文介绍SpringBoot3如何整合graalvm&#xff0c;并打包为可执行文件。Windows和Linux都打包。 版本 springboot3.3.6 graalvm21&#xff08;包含JDK21&#xff08;21是最新的LT…

【Bolt.new + PromptCoder】三分钟还原油管主页

【Bolt.new PromptCoder】三分钟还原油管主页 PromptCoder官网&#xff1a;PromptCoder Bolt官网&#xff1a;https://bolt.new/ Bolt 是什么&#xff1f; Bolt.new 是一个提供创建全栈网络应用服务的平台。它允许用户通过提示&#xff08;Prompt&#xff09;、运行&#x…

ubuntu下anconda装pytorch

1、禁用nouveau sudo vim /etc/modprobe.d/blacklist.conf 在文件最后部分插入以下两行内容 blacklist nouveau options nouveau modeset0 更新系统 sudo update-initramfs -u 重启系统 2、装nvidia驱动 卸载原来驱动 sudo apt-get remove nvidia-* &#xff08;若安装…

QT数据库(四):QSqlRelationalTableModel 类

关系数据库概念 例如下列departments、majors、studInfo 这 3 个数据表之间存在关系。 主键与外键 标记“**”的是主键字段&#xff0c;标记“*”的是外键字段。主键字段是一个数据表中表示记录唯一性的字段&#xff0c;例如 studInfo 数据表中的 studID 字段。外键字段是与其…

【Linux】-学习笔记10

第八章、Linux下的火墙管理及优化 1.什么是防火墙 从功能角度来讲 防火墙是位于内部网和外部网之间的屏障&#xff0c;它按照系统管理员预先定义好的规则来控制数据包的进出 从功能实现角度来讲 火墙是系统内核上的一个模块netfilter(数据包过滤机制) …

SpringBoot 手动实现动态切换数据源 DynamicSource (中)

大家好&#xff0c;我是此林。 SpringBoot 手动实现动态切换数据源 DynamicSource &#xff08;上&#xff09;-CSDN博客 在上一篇博客中&#xff0c;我带大家手动实现了一个简易版的数据源切换实现&#xff0c;方便大家理解数据源切换的原理。今天我们来介绍一个开源的数据源…

Crawl4AI:一个为大型语言模型(LLM)和AI应用设计的网页爬虫和数据提取工具实战

这里写目录标题 一、crawl4AI功能及简介1、简介2、特性 二、项目地址三、环境安装四、大模型申请五、代码示例1.生成markdown2.结构化数据 一、crawl4AI功能及简介 1、简介 Crawl4AI 是一个开源的网页爬虫和数据抓取工具&#xff0c;一个python项目&#xff0c;主要为大型语言…

【银河麒麟高级服务器操作系统】有关dd及cp测试差异的现象分析详解

了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer.kylinos.cn 文档中心&#xff1a;https://documentkylinos.cn dd现象 使用银河麒麟高级服务器操作系统执行两次…