C语音顺序表专题及应用

发布于：2024-12-18 ⋅ 阅读:(8) ⋅ 点赞:(0)
微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

数据结构引进

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倍的步长进行增容；当已使用空间较低时，可以采用更小的增容步长。
    • 使用紧凑存储结构（如动态数组的优化）：在适当的时候对数组进行紧凑操作。例如，当有大量的删除操作后，数组中可能存在很多空闲空间。可以将有效数据重新排列到数组的前部，释放后面的空闲空间。这样在后续的插入操作中，可以利用这些释放的空间，减少增容的需求。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布