备案控制台
开发者社区 人工智能 文章 正文

顺序表的应用

2024-06-20 18
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 顺序表的应用


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指向位置的值不等于val
      nums[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 < 0
  while (l2 >= 0)
  {
    nums1[l3--] = nums2[l2--];
  }
}

3. 顺序表的问题及思考

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

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

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

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


文章标签：
算法
waves浪游
目录
相关文章
Kevin_17
|
1月前
|
存储 测试技术 C语言
顺序表详解（SeqList）
顺序表详解（SeqList）
Kevin_17
49 0
YoungMLet
|
8月前
|
存储
【顺序表】
【顺序表】
YoungMLet
37 0
waves浪游
|
8天前
|
存储 算法
顺序表专题
顺序表专题
waves浪游
18 4
游客rx3o5mumc7bka
|
26天前
|
存储
2.顺序表_链表（附练习)
2.顺序表_链表（附练习)
游客rx3o5mumc7bka
13 1
游客rx3o5mumc7bka
|
26天前
|
存储
25.顺序表专题
25.顺序表专题
游客rx3o5mumc7bka
11 0
Mylvzi
|
1月前
|
存储
顺序表讲解
顺序表讲解
Mylvzi
27 0
醋溜马桶圈
|
1月前
顺序表的实现
顺序表的实现
醋溜马桶圈
31 0
唐唐思
|
7月前
|
测试技术
顺序表（2）
顺序表（2）
唐唐思
532 0
唐唐思
|
7月前
|
存储 C语言
顺序表(1)
顺序表(1)
唐唐思
58 0
阿甘兄
|
7月前
|
存储 NoSQL
03 顺序表
03 顺序表
阿甘兄
18 0