前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >顺序表的应用

顺序表的应用

作者头像
waves浪游
发布于 2024-04-14 09:07:11
480
发布于 2024-04-14 09:07:11
举报
文章被收录于专栏：C语言讲解C语言讲解

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

我们先写一个框架：

代码语言：javascript
复制
//Contact.h

#include <stdio.h>//暂时加上
代码语言：javascript
复制
//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;
}

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

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

代码语言：javascript
复制
//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;

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

代码语言：javascript
复制
//SeqList.h

#include "Contact.h"

typedef Info SLDataType;

然后我们写接口：

代码语言：javascript
复制
//Contact.h

//通讯录提供的操作

typedef struct SeqList Contact;

//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表

这里我们想把 SL 换成 Contact，这样看上去更好理解，所以就要 typedef struct SeqList Contact; ，但是要使用struct SeqList 就要 #include “SeqList.h” ，但是这样会出现一个问题：

头文件嵌套问题
头文件嵌套问题

解决办法：前置声明

代码语言：javascript
复制
//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);

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

代码语言：javascript
复制
//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] 已经变成一个结构体了，不能直接使用 == 来比较

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

代码语言：javascript
复制
//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
	);
}

完整代码：

代码语言：javascript
复制
//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);
代码语言：javascript
复制
//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;
}
代码语言：javascript
复制
//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);
代码语言：javascript
复制
//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
			);
	}
}
代码语言：javascript
复制
//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 移除元素
移除元素
移除元素
代码语言：javascript
复制
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指向位置的值不等于val
			nums[dst] = nums[src];
			dst++;
			src++;
		}
	}

	//此时dst的值刚好是数组的新长度
	return dst;
}
2.2 合并两个有序数组
合并两个有序数组
合并两个有序数组
代码语言：javascript
复制
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 < 0
	while (l2 >= 0)
	{
		nums1[l3--] = nums2[l2--];
	}
}

3. 顺序表的问题及思考

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

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

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

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

本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-04-06，如有侵权请联系 cloudcommunity@tencent.com 删除
ps
scanf
void
数据
int

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ，欢迎热爱写作的你一起参与！

ps
scanf
void
数据
int
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 1. 基于动态顺序表实现通讯录项目
  • 2.顺序表经典算法
    • 2.1 移除元素
      • 2.2 合并两个有序数组
      • 3. 顺序表的问题及思考
      领券

      腾讯云开发者

      扫码关注腾讯云开发者

      扫码关注腾讯云开发者

      领取腾讯云代金券

      热门产品

      热门推荐

      更多推荐

      Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

      深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

      腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

      Copyright © 2013 - 2024 Tencent Cloud.

      All Rights Reserved. 腾讯云 版权所有

      登录 后参与评论