C语言数据结构——顺序表，及通讯录项目的模拟实现
目录
大家好，今天为大家带来C语言初阶数据结构中关于顺序表的相关知识
3.2.7退出程序后自动将信息保存到"test.txt"中（上一期博客有具体讲解）
大家好，今天为大家带来C语言初阶数据结构中关于顺序表的相关知识
1.线性表
线性表（linear list）是若干个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的（就好比我们在日常生活中排队时的场景...），线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。因此我们可以把顺序表就看成数组，但顺序表进行操作简单
我们一般把顺序表分为：静态顺序表和动态顺序表
2.1.1静态顺序表
顾名思义，就是用定长数组来储存元素，大小是不可变的，我们用结构体变量来定义（动态顺序表同理）
//静态
#define N 100//数组总大小
struct SeqList
{
int arr[N];
size_t Size;//已储存元素个数
};
2.1.2动态顺序表
与静态顺序表相反，动态顺序表可以改变数组大小，因此我们就要用到动态内存开辟的相关知识
//动态
typedef int SLtype;
typedef struct SeqList
{
SLtype* arr;
int Size;
int capacity;
}SL;其中 SLtype 类型为我们要储存的数据的类型，指针 arr 就指向我们顺序表的地址，Size 为已储存的数据个数，capacity 为总共能存放数据的个数
很明显动态顺序表比静态顺序表更灵活的
2.2动态顺序表适合场景：
-
待储存数据量未知：在处理大量数据或不确定数据量的情况下，动态顺序表可以开始时分配一个较小的容量，随着数据的增加逐渐扩容，避免一开始就分配过多不必要的内存。
-
频繁插入和删除数据：动态顺序表适合频繁进行插入和删除操作的应用场景。由于它可以在任意节点方便地进行这些操作，不需要像数组那样在每次操作时移动大量元素。
-
性能要求不是首要考虑：虽然动态顺序表的插入和删除操作在大多数情况下速度很快，但在扩容时可能会涉及到较慢的内存重新分配。如果性能要求不是主要考虑因素，或者可以通过其他方式优化性能，那么动态顺序表是一个合适的选择。
-
内存使用不是关键限制：动态顺序表在动态内存开辟时会由于开辟空间太大而导致失败
2.3顺序表的实现（以动态顺序表储存整型数据为例）
我们把顺序表顺序表的可以实现的功能放在头文件" SeqlList.h "里
把顺序表功能的具体实现放在程序" SeqList.c "里
主函数放在程序" test.c "里
2.3.1 "目录"
以下为顺序表的功能：
2.3.2顺序表的初始化
void SeqListInit(SL* ps)//初始化
{
ps->arr = NULL;
ps->Size = 0;
ps->capacity = 0;
}2.3.3检查顺序表空间是否够用
1.当我们在向顺序表里放入数据时，要检查空间是否够用，也就是Size == capacity时空间已满，这时我们就要增大空间（realloc函数），一般是以倍数（2~3倍）的形式增长
2.当然，如果是储存第一个元素时Size ==capacity == 0 ，这时就要先给一个初始空间大小
综上代码实现：
1.用 if 语句检验空间是否足够
2.如果不足，就用三目操作符来判断总空间大小是否为0
a.是0，给一个初始空间大小（这里是5）
b.不是0，乘2重新赋给capacity
3.用 realloc 函数扩增空间大小，防止空间开辟失败（导致数据全部丢失），用同类型指针接收返回地址
4.检查开辟空间是否成功，若开辟失败（realloc 函数返回空指针NULL），则报错退出程序
5.将开辟成功的空间地址赋给指针ps->arr
void CheckCapacity(SL* ps)//检查空间
{
if (ps->Size == ps->capacity)
{
ps->capacity = ps->capacity == 0? 5: 2 * ps->capacity;
SLtype* tmp = (SLtype*)realloc(ps->arr, sizeof(SLtype) * ps->capacity);
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
}
}2.3.4向顺序表尾部添加元素
1.先判断空间是否足够
2.向顺序表最后一个元素(下标为ps->Size)赋值目标值" n "
3.顺序表的有效元素加1（ps->Size++）
里面的assert是用来检查表达式是否为假，如果为假程序会在该处停止运行并报错（下同）
void SeqListPushBack(SL* ps, SLtype n)//尾插
{
assert(ps);
CheckCapacity(ps);
ps->arr[ps->Size++] = n;
}2.3.5向顺序表头部添加元素
1.先判断空间是否足够
2.让顺序表整体向后移一个位置（for循环/memmove函数）
3.顺序表第一个元素赋值
4.顺序表的有效元素加1
void SeqListPushFront(SL* ps, SLtype n)//头插
{
assert(ps);
CheckCapacity(ps);
for (int i = ps->Size; i > 0; i--)
ps->arr[i] = ps->arr[i - 1];
ps->arr[0] = n;
ps->Size++;
}2.3.6删除顺序表最后一个元素
“ 删除 ”一个元素不一定要真的删除，只要让用户没有访问权限就行了（但也不能影响其他操作）
即让顺序表的有效元素减1
void SeqListPopBack(SL* ps)//尾删
{
assert(ps);
ps->Size--;
}2.3.7删除顺序表第一个元素
1.让顺序表其余元素向前移
2.让顺序表的有效元素减1
void SeqListPopFront(SL* ps)//头删
{
assert(ps);
for (int i = 0; i < ps->Size - 1; i++)
ps->arr[i] = ps->arr[i + 1];
ps->Size--;
}2.3.8在下标为pos的位置后面添加一个元素
1.先判断空间是否足够
2.将在下标为pos之后的元素整体向后移
3.给下标为pos + 1的元素赋值
4.让顺序表的有效元素加1
void SeqListInsert(SL* ps, size_t pos, SLtype n)//在下标为pos的位置插入数据(之后)
{
assert(ps);
CheckCapacity(ps);
assert(pos < ps->Size);
for (int i = ps->Size; i > pos; i--)
ps->arr[i] = ps->arr[i - 1];
ps->arr[pos + 1] = n;
ps->Size++;
}2.3.9删除下标为pos的元素
1.将下标为pos之后的元素整体向前移
2.让顺序表的有效元素减1
void SeqListErase(SL* ps, size_t pos)//删除下标为pos处的数据
{
assert(ps);
assert(pos < ps->Size);
for (int i = (int)pos; i < ps->Size - 1; i++)
ps->arr[i] = ps->arr[i + 1];
ps->Size--;
}2.3.10在顺序表中查找元素
1.遍历顺序表，若if条件成立则返回下标
2.遍历完毕都没有找到则返回EOF（-1）（不可能为下标的值）
int SeqListFind(SL* ps, SLtype n)//查找
{
assert(ps);
for (int i = 0; i < ps->Size; i++)
{
if (ps->arr[i] == n)
return i;
}
return EOF;
}
2.3.11打印顺序表中所有数据
void SeqListPrint(SL* ps)//打印
{
assert(ps);
for (int i = 0; i < ps->Size; i++)
printf("%d ", ps->arr[i]);
}2.3.12顺序表的销毁
释放动态开辟的空间
void SeqListDestory(SL* ps)//销毁
{
assert(ps);
free(ps);
ps = NULL;
}2.3.13代码调试
3.顺序表的应用（通讯录）
如果我们把上面的知识点和原理都弄清楚了，那么我们可以试着完成"通讯录"这个项目的书写
我们再新增两个项目，分别是头文件" Peoinfo.h "和项目文件" Peoinfo.c "
3.1思路前引
3.1.1顺序表中带存放数据的元素类型？
在通讯录中，我们不能用仅用某一个数据就清楚的描写一个联系人，所以这个顺序表里的存放的数据应是结构体指针（结构体的自引用）
3.1.2头文件的互相包含？
我们之前在" SeqList.h "头文件中已经实现了顺序表的功能的具体实现，所以在头文件" Peoinfo.h "
中直接调用就行，而我们想要在" Peoinfo.h "中创建的结构体变量struct SLPeoinfo在" SeqList.h "
中使用则又要在" SeqList.h "中包含" Peoinfo.h "（也就是头文件的互相包含）
但是如果头文件的互相包含会导致预处理时无限递归而导致程序崩溃，这时就要使用到"前置声明"
也就是在头文件" SeqList.h "先声明有struct SLPeoinfo这个变量
这样只要" Peoinfo.h "调用" SeqList.h "就行了
3.1.3退出程序后数据丢失？
在程序退出后，数据也接着被销毁，这样我们以后就没法查找联系人信息了，这样我们就要在退出程序之前将信息保存在其他文件中
3.2具体实现
3.2.1通讯录菜单
void menu(void)
{
printf("****************通讯录***************\n");
printf("******1.增加联系人 2.删除联系人******\n");
printf("******3.修改联系人 4.查找联系人******\n");
printf("******5.展示联系人 0.退出通讯录******\n");
printf("*************************************\n");
}
3.2.2增加联系人
1.让用户按顺序输入数据存储到形参 n （结构体）中
2.将存好的数据传给SeqListPushFront函数（头插）（2.2.5）
void PeoinfoPush(Peoinfo* ps, SLtype n)//增加联系人
{
printf("请输入增加联系人的姓名、年龄、性别、号码、住址\n");
scanf("%s%d%s%s%s", n.name, &n.age, n.sex, n.id, n.addr);
SeqListPushFront(ps, n);
printf("增加成功!\n");
}3.2.3查找联系人
1.让用户输入要查找人的信息（姓名）
2.遍历顺序表查找
a.若找到返回下标
b.若查无此人返回EOF
int PeoinfoFind(Peoinfo* ps)//查找联系人
{
printf("请输入要查找人的昵称\n");
char ch[NAME_MAX];
scanf("%s", ch);
for (int i = 0; i < ps->Size; i++)
{
if (strcmp(ps->arr[i].name, ch) == 0)
{
return i;
}
}
return EOF;
}3.2.4删除联系人
1.查找联系人
2.如果没找到就提醒用户
3.如果找到就调用SeqListErase函数（删除指定元素）（2.2.9）
void PeoinfoPop(Peoinfo* ps)//删除联系人
{
int flg = PeoinfoFind(ps);
if (flg == EOF)
{
printf("没有该联系人信息!\n");
return;
}
SeqListErase(ps, flg);
printf("删除成功!\n");
}
3.2.5修改联系人信息
1.查找待修改人的信息
2.重新输入信息
void PeoinfoRev(Peoinfo* ps)//修改联系人
{
int flg = PeoinfoFind(ps);
printf("请按姓名、年龄、性别、号码、住址的顺序输入你需改后的数据\n");
scanf("%s%d%s%s%s", ps->arr[flg].name, &ps->arr[flg].age, ps->arr[flg].sex, ps->arr[flg].id, ps->arr[flg].addr);
printf("修改成功\n");
}3.2.6展示所有联系人
void PeoinfoPrint(Peoinfo* ps)//展示所有联系人
{
for (int i = 0; i < ps->Size; i++)
{
printf("姓名:%s 年龄:%d 性别:%s 号码:%s 住址:%s\n",\
ps->arr[i].name, \
ps->arr[i].age, \
ps->arr[i].sex, \
ps->arr[i].id, \
ps->arr[i].addr \
);
}
}3.2.7退出程序后自动将信息保存到"test.txt"中（上一期博客有具体讲解）
void Income(Peoinfo sl)
{
FILE* pf = fopen("test.txt", "w");
if (pf == NULL)
{
perror("fopen");
return 1;
}
for (int i = 0; i < sl.Size; i++)
{
fprintf(pf, "姓名:%s ", sl.arr[i].name);
fprintf(pf, "年龄:%d ", sl.arr[i].age);
fprintf(pf, "性别:%s ", sl.arr[i].sex);
fprintf(pf, "号码:%s ", sl.arr[i].id);
fprintf(pf, "住址:%s\n", sl.arr[i].addr);
}
fclose(pf);
pf = NULL;
}
C语言中的文件操作-CSDN博客
https://blog.csdn.net/lunar_coder/article/details/157552766?spm=1011.2415.3001.5331
3.3全部代码展示
以上就是全部内容，感谢阅读，希望能够帮到你，也欢迎大家指错及补充
更多推荐
23
0- 0
已为社区贡献1条内容
所有评论(0)