目录
1 顺序表的概念及结构
1.1 线性表
线性表是n个具有相同特性数据元素的有限序列。线性表是一种实际中被广泛应用的数据结构。常见的线性表有：顺序表、链表、栈、队列、字符串等等。
线性表在逻辑上是线性结构，也就是说是连续上的一条直线。但是物理结构不一定是连续的，在实际上存储时还要看具体的存储方式。线性表在物理上存储时，通常以数组和链式结构的形式存储。本文主要介绍线性表的其中一种：顺序表。
1.2 顺序表分类
顺序表的底层结构是数组，对数组进行了封装，并且实现了增删改查等接口。顺序表分为两类：静态顺序表和动态顺序表。
1.2.1 静态顺序表
静态顺序表使用定长数组存储元素，先开辟一个固定大小的空间，然后将数据存放在里面，具体代码实现如下：
#define N 100
//静态顺序表（不推荐）
struct SeqList
{
int arr[N];
int size;//定义有效数据个数
};静态顺序表实现是首先定义一个结构体，结构体内定义一个固定大小的数组，定义一个整型size来表示有效数据个数，这样一个静态顺序表就创建好了。
静态顺序表在实际上不推荐使用，因为在实际应用的过程中，如果数据量较小，那么剩余空间就会造成浪费；数据量庞大时，如果一直向内部存放数据，某一时刻就会导致空间不够用，数据无法存放，这就会造成严重的结果。因此一般都不使用静态顺序表，这时候就有另一个办法：动态顺序表。
1.2.2 动态顺序表
动态顺序表可以根据实际需要来扩大空间，避免空间浪费和空间不足的情况，灵活性高。动态顺序表的定义如下：
typedef int SLDataType;//便于修改数据类型
typedef struct SeqList
{
SLDataType* arr;
int size;//有效数字个数
int capacity;//空间大小
}SL;
2 顺序表的实现
2.1 顺序表的初始化
创建完顺序表后，我们就要将顺序表初始化，将数组指针置为空，有效数字和容量的初始值为0:
//顺序表初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}2.2 顺序表中数据的增加和修改
对顺序表中数据的增加和修改主要有：顺序表的头插，顺序表的尾插，顺序表的头删，顺序表的尾删，指定位置的插入和删除，顺序表的查找，接下来将逐个实现。
2.2.1 顺序表的头插
顺序的头插就是将数据从顺序表的起始位置处插入，已有的每个数据向后挪一位。
因为顺序表是动态顺序表，在插入数据前都要检查空间是否足够，如果不够，则开辟新的空间，这里开辟空间也是有说法的，一次要开辟出合适的空间，一般新的空间都是原来空间的二倍。这就像手机的存储空间的发展一样，由16GB到32GB再到64GB， 逐步发展到现在有1TB，2TB。下面是检查空间的代码实现：
//顺序表空间检查
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp=(SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}顺序表头插代码实现：
//顺序表头部插入
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
//插入前检查空间是否足够
SLCheckCapacity(ps);
//顺序表原有数据向后挪一位,先后再前
int i = 0;
for (i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i-1];
}
ps->arr[0] = x;
ps->size++;
}2.2.2 顺序表的尾插
顺序表的尾插就是将新数据从顺序表尾部插入：
代码实现：
//顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}2.2.3 顺序表的头删
删除顺序表的第一个位置数据，其余数据向前挪动一位。
代码实现：
//顺序表头部删除
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
int i = 0;
for (i = 0; i < ps->size-1 ; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}2.2.4 顺序表的尾删
顺序表的尾删是删除顺序表的最后一个数据
代码实现：
//顺序表尾部删除
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}2.2.5 顺序表指定位置插入数据
顺序表在指定位置上插入数据，指定位置及其之后的数据向后移动一位。
代码实现：
//顺序表指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
int i = 0;
for (i = ps->size-1; i > pos-1; i--)
{
ps->arr[i+1] = ps->arr[i];
}
ps->arr[pos] = x;
ps->size++;
}2.2.6 顺序表指定位置删除数据
顺序表在指定位置删除数据，指定位置以后的数据向前移动一位。
代码实现：
//顺序表删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int i = 0;
for (i = pos; i <ps->size-1 ; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}2.2.7 顺序表的查找
查找顺序表中的数据，返回数据下标。代码实现：
//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
2.3 顺序表完整代码
实现顺序表，建立一个头文件seqlist.h,一个顺序表seqlist.c文件，一个测试文件test.c，test.c用来测试顺序表功能。
2.3.1 seqlist.h文件
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//定义顺序表的结构
//#define N 100
////静态顺序表（不推荐）
//struct SeqList
//{
// int arr[N];
// int size;//定义有效数据个数
//};
//动态顺序表
typedef int SLDataType;//便于修改数据类型
typedef struct SeqList
{
SLDataType* arr;
int size;//有效数字个数
int capacity;//空间大小
}SL;
//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表空间检查
void SLCheckCapacity(SL* ps);
//顺序表头部插入
void SLPushFront(SL* ps, SLDataType x);
//顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x);
//顺序表头部删除
void SLPopFront(SL* ps);
//顺序表尾部删除
void SLPopBack(SL* ps);
//顺序表指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//顺序表删除指定位置的数据
void SLErase(SL* ps, int pos);
//顺序表的查找
int SLFind(SL* ps, SLDataType x);
//顺序表打印
void SLPrint(SL* ps);
2.3.2 seqlist.c
#include "seqlist.h"
//顺序表初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表销毁
void SLDestroy(SL* ps)
{
if (ps->arr != NULL)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表空间检查
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp=(SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
//顺序表头部插入
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
//插入前检查空间是否足够
SLCheckCapacity(ps);
//顺序表原有数据向后挪一位,先后再前
int i = 0;
for (i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i-1];
}
ps->arr[0] = x;
ps->size++;
}
//顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}
//顺序表打印
void SLPrint(SL* ps)
{
int i = 0;
for (i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//顺序表头部删除
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
int i = 0;
for (i = 0; i < ps->size-1 ; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//顺序表尾部删除
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
//顺序表指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
int i = 0;
for (i = ps->size-1; i > pos-1; i--)
{
ps->arr[i+1] = ps->arr[i];
}
ps->arr[pos] = x;
ps->size++;
}
//顺序表删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int i = 0;
for (i = pos; i <ps->size-1 ; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}2.3.3 test.c文件
#include "seqlist.h"
void SLTest1()
{
SL sl;
//顺序表初始化测试
SLInit(&sl);
//顺序表空间检查测试
SLCheckCapacity(&sl);
//顺序表头插测试
SLPushFront(&sl, 4);
SLPushFront(&sl, 3);
SLPushFront(&sl, 2);
SLPushFront(&sl, 1);
//顺序表尾部插入测试
SLCheckCapacity(&sl);
SLPushBack(&sl, 5);
SLPushBack(&sl, 6);
SLPushBack(&sl, 7);
SLPushBack(&sl, 8);
//顺序表头部删除测试
SLPopFront(&sl);
//顺序表尾部删除测试
SLPopBack(&sl);
//顺序表指定位置插入数据测试
SLInsert(&sl, 0, 99);
SLInsert(&sl,7, 99);
//顺序表指定位置删除数据测试
SLErase(&sl, 7);
SLErase(&sl, 0);
//顺序表的查找测试
int ret=SLFind(&sl, 2);
if (ret != -1)
{+
printf("找到了，下标是%d\n", ret);
}
else
{
printf("找不到\n");
}
//顺序表打印测试
SLPrint(&sl);
//顺序表销毁测试
SLDestroy(&sl);
}
int main()
{
SLTest1();
return 0;
}3 基于顺序表实现通讯录
3.1 功能要求
- 至少能够存储100人的通讯信息
- 能够保存用户信息：名字、性别、年龄、电话、地址等
- 增加联系人信息
- 删除指定联系人
- 查找指定联系人
- 修改指定联系人
- 显示联系人信息
3.2 基本原理
通讯录的内容通过结构体来定义，通讯录的本质就是利用顺序表的原理，顺序表中的每一个元素就是一个人的信息。
文件结构：
3.3 通讯录完整代码
3.3.1 Contact.h文件
#pragma once
#define NAME_MAX 20
#define GENDER_MAX 10
#define TEL_MAX 20
#define ADDR_MAX 100
//定义联系人数据结构
//姓名 性别 年龄 电话 地址
typedef struct personInfo
{
char name[NAME_MAX];
char gender[GENDER_MAX];
int age;
char tel[TEL_MAX];
char addr[ADDR_MAX];
}peoInfo;
//通讯录相关的方法 对通讯录的操作实际就是对顺序表进行操作
// 给顺序表改名字
typedef struct SeqList Contact;
//通讯录初始化
void ContactInit(Contact* pc);
//通讯录销毁
void ContactDestroy(Contact* pc);
//通讯录添加数据
void ContactAdd(Contact* pc);
//通讯录删除数据
void ContactDel(Contact* pc);
//通讯录的修改
void ContactModify(Contact* pc);
//通讯录查找
void ContactFind(Contact* pc);
//展示通讯录数据
void ContactShow(Contact* pc);3.3.2 SeqList.h文件
#pragma once
#include "Contact.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
//动态顺序表
typedef peoInfo SLDataType;//便于修改数据类型
typedef struct SeqList
{
SLDataType* arr;
int size;//有效数字个数
int capacity;//空间大小
}SL;
//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
//顺序表空间检查
void SLCheckCapacity(SL* ps);
//顺序表头部插入
void SLPushFront(SL* ps, SLDataType x);
//顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x);
//顺序表头部删除
void SLPopFront(SL* ps);
//顺序表尾部删除
void SLPopBack(SL* ps);
//顺序表指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//顺序表删除指定位置的数据
void SLErase(SL* ps, int pos);
3.3.3 Contact.c文件
#include "Contact.h"
#include "SeqList.h"
//通讯录初始化
void ContactInit(Contact* pc)
{
//实际就是顺序表的初始化
SLInit(pc);
}
//通讯录销毁
void ContactDestroy(Contact* pc)
{
SLDestroy(pc);
}
//通讯录添加数据
void ContactAdd(Contact* pc)
{
//获取用户输入的内容
peoInfo info;
printf("请输入要添加的联系人姓名：>\n");
scanf("%s", info.name);
printf("请输入要添加的联系人性别：>\n");
scanf("%s", info.gender);
printf("请输入要添加的联系人年龄：>\n");
scanf("%d", &info.age);
printf("请输入要添加的联系人电话：>\n");
scanf("%s", info.tel);
printf("请输入要添加的联系人住址：>\n");
scanf("%s", info.addr);
SLPushBack(pc, info);
}
//通讯录删除数据
int FindByName(Contact* pc,char name[])
{
int i = 0;
for (i = 0; i < pc->size; i++)
{
if (strcmp(pc->arr[i].name, name)==0)
{
//找到了
return i;
}
}
//找不到
return -1;
}
void ContactDel(Contact* pc)
{
char name[NAME_MAX];
printf("请输入要删除的联系人姓名：>\n");
scanf("%s", name);
int find = FindByName(pc, name);
if (find < 0)
{
printf("你要删除的联系人不存在\n");
return;
}
SLErase(pc,find);
printf("删除成功\n");
}
//通讯录的修改
void ContactModify(Contact* pc)
{
char name[NAME_MAX];
printf("请输入要修改的用户姓名：>\n");
scanf("%s", name);
int find= FindByName(pc, name);
if (find < 0)
{
printf("你要修改的联系人数据不存在\n");
return;
}
printf("请输入新的姓名：>\n");
scanf("%s", pc->arr[find].name);
printf("请输入新的性别：>\n");
scanf("%s", pc->arr[find].gender);
printf("请输入新的年龄：>\n");
scanf("%d", &pc->arr[find].age);
printf("请输入新的电话：>\n");
scanf("%s", pc->arr[find].tel);
printf("请输入新的住址：>\n");
scanf("%s", pc->arr[find].addr);
printf("修改成功\n");
}
//通讯录查找
void ContactFind(Contact* pc)
{
char name[NAME_MAX];
printf("请输入要查找的用户姓名：>\n");
scanf("%s", name);
int find = FindByName(pc, name);
if (find < 0)
{
printf("你要查找的联系人数据不存在\n");
return;
}
printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "地址");
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("%s %s %d %s %s\n",
pc->arr[find].name,
pc->arr[find].gender,
pc->arr[find].age,
pc->arr[find].tel,
pc->arr[find].addr);
}
}
//展示通讯录数据
void ContactShow(Contact* pc)
{
printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "地址");
int i = 0;
for (i = 0; i < pc->size; i++)
{
printf("%s %s %d %s %s\n",
pc->arr[i].name,
pc->arr[i].gender,
pc->arr[i].age,
pc->arr[i].tel,
pc->arr[i].addr);
}
}3.3.4 SeqList.c
#include "seqlist.h"
//顺序表初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表销毁
void SLDestroy(SL* ps)
{
if (ps->arr != NULL)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
//顺序表空间检查
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
//顺序表头部插入
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
//插入前检查空间是否足够
SLCheckCapacity(ps);
//顺序表原有数据向后挪一位,先后再前
int i = 0;
for (i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
//顺序表尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}
//顺序表头部删除
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
int i = 0;
for (i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
//顺序表尾部删除
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
//顺序表指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
int i = 0;
for (i = ps->size - 1; i > pos - 1; i--)
{
ps->arr[i + 1] = ps->arr[i];
}
ps->arr[pos] = x;
ps->size++;
}
//顺序表删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int i = 0;
for (i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
3.3.5 test.c文件
#include "SeqList.h"
//通讯录测试
void menu()
{
printf("*****************通讯录*************************\n");
printf("******1.增加联系人 2.删除联系人***********\n");
printf("******3.修改联系人 4.查找联系人***********\n");
printf("******5.展示联系人 0.退出 ************\n");
printf("************************************************\n");
}
int main()
{
Contact con;
ContactInit(&con);
int input = 0;
do
{
menu();
printf("请选择：>");
scanf("%d", &input);
switch (input)
{
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:
printf("输入错误，请重新输入\n");
break;
}
} while (input!=0);
ContactDestroy(&con);
return 0;
}以上就是有关顺序表的原理和通讯录实现的全部内容了，如果这篇文章对你有用，可以点点赞哦，你的支持就是我写下去的动力，后续会不断地分享知识。