C语言相关简单数据结构：顺序表
目录
1.顺序表的概念及结构
1.1 线性表
如何理解逻辑结构和物理结构？
1.2 顺序表分类
顺序表和数组的区别：
顺序表分类：
静态顺序表
动态顺序表
1.3 动态顺序表的实现
初始化
尾插
头插
尾删
头删
在指定位置之前插入数据
删除指定位置的数据
顺序表的查找
最终代码：
test.c
SeqList.h
SeqList.c
2.顺序表实现通讯录
2.1 基于动态顺序表实现通讯录
2.1.1 功能要求
2.2 代码的实现：
1.建立五个文件
2.将顺序表结构体的类型，int改为通讯录结构体自定义类型
顺序表
通讯录
3.给通讯录结构体改名为typedef SL contact
4.对于SeqList.h和Contact.h头文件包含的处理
5.列出通讯录的功能
6.通讯录的初始化和销毁
7.通讯录的添加数据
8.通讯录删除
9.展示通讯录数据
10.通讯录的修改和查找
11.打印菜单
最终代码
test.c
Contact.h
Contact.c
1.顺序表的概念及结构
1.1 线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。案例：蔬菜分为绿叶类、⽠类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合
如何理解逻辑结构和物理结构？
物理结构：在内存中存储的形式，不一定连续
逻辑结构：肉眼可以看到的，我们想象出来的数据结构，人为想象的，连续的
顺序表是物理结构和逻辑结构都连续的一种线性表
1.2 顺序表分类
顺序表和数组的区别：
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
顺序表分类：
静态顺序表
概念：使⽤定⻓数组存储元素
静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费
动态顺序表
1.3 动态顺序表的实现
初始化
尾插
头插
尾删
头删
在指定位置之前插入数据
删除指定位置的数据
顺序表的查找
最终代码：
test.c
#include"SeqList.h"void SLTest01()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//SLPushFront(&sl, 5);//SLPushFront(&sl, 6);SLPopBack(&sl);SLPrint(sl);//1 2 3 SLPopBack(&sl);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopFront(&sl);SLPrint(sl);//...........SLDestroy(&sl);
}void SLTest02()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);//1 2 3 4//测试指定位置之前插入数据//SLInsert(&sl, 1, 99);//SLInsert(&sl, sl.size, 88);//测试删除指定位置的数据//SLErase(&sl, 1);//SLPrint(sl);//1 3 4//测试顺序表的查找int find = SLFind(&sl, 40);if (find < 0){printf("没有找到！\n");}else {printf("找到了！下标为%d\n",find);}SLDestroy(&sl);
}int main()
{SLTest01();SLTest02();return 0;
}SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构//#define N 100
//
////静态顺序表
//struct SeqList
//{
// int arr[N];
// int size;//有效数据个数
//};typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{SLDataType* arr;int size; //有效数据个数int capacity; //空间大小
}SL;//typedef struct SeqList SL;//顺序表初始化
void SLInit(SL* ps);
//顺序表的销毁
void SLDestroy(SL* ps);
void SLPrint(SL s);//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);//尾插
void SLPushFront(SL* ps, SLDataType x);//头插void SLPopBack(SL* ps);//尾删
void SLPopFront(SL* ps);//头删//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);
SeqList.c
#include"SeqList.h"
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestroy(SL* ps)
{if (ps->arr) //等价于 if(ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLCheckCapacity(SL* ps)
{//插入数据之前先看空间够不够if (ps->capacity == ps->size){//申请空间//malloc calloc realloc int arr[100] --->增容realloc//三目表达式int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//要申请多大的空间if (tmp == NULL){perror("realloc fail!");exit(1);//直接退出程序，不再继续执行}//空间申请成功ps->arr = tmp;ps->capacity = newCapacity;}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{////温柔的解决方式//if (ps == NULL)//{// return;//}assert(ps); //等价与assert(ps != NULL)//ps->arr[ps->size] = x;//++ps->size;SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//先让顺序表中已有的数据整体往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//arr[1] = arr[0]}ps->arr[0] = x;ps->size++;
}void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}printf("\n");
}
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空//ps->arr[ps->size - 1] = -1;--ps->size;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);//数据整体往前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1]; //arr[size-2] = arr[size-1]}ps->size--;
}//在指定位置之前插入数据
// 1 2 size = 2
//pos 0 -1 100000
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);//插入数据：空间够不够SLCheckCapacity(ps);//让pos及之后的数据整体往后挪动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];//arr[pos+1] = arr[pos]}ps->arr[pos] = x;ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到啦return i;}}//没有找到return -1;
}2.顺序表实现通讯录
2.1 基于动态顺序表实现通讯录
C语⾔基础要求：结构体、动态内存管理、顺序表、⽂件操作
2.1.1 功能要求
1）⾄少能够存储100个⼈的通讯信息
2）能够保存⽤⼾信息：名字、性别、年龄、电话、地址等
3）增加联系⼈信息
4）删除指定联系⼈
5）查找制定联系⼈
6）修改指定联系⼈
7）显⽰联系⼈信息
2.2 代码的实现：
1.建立五个文件
分别为SeqList.c和SeqList.h，这两个是通讯录的底层文件；Contact.c和Contact.h，这两个函数是通讯录的实现文件；test.c是测试函数
2.将顺序表结构体的类型，int改为通讯录结构体自定义类型
顺序表
SeqList.h
通讯录
Contact.h
3.给通讯录结构体改名为typedef SL contact
4.对于SeqList.h和Contact.h头文件包含的处理
因为SeqList.h中包含了Contact.h所以可以直接使用重命名peoInfo
因为Contact.h没有包含SeaList.h所以找不到顺序表的结构体，但是SeqList.h已经包含了Contact.h不能相互包含头文件，会报错，所以要在Contact.h前置声明struct SeqList;所以typedef struct SeqList Contact;这样才能找到SL
由以上两步通讯录的实现和顺序表有了连接
5.列出通讯录的功能
6.通讯录的初始化和销毁
在Contact.c包含头文件SeqList.h
通讯录的初始化和销毁就是顺序表的初始化和销毁
测试，通过调试观察
7.通讯录的添加数据
将姓名、性别、年龄、电话号码、地址储存进通讯录的结构体，注意：只要年龄是int类型的，所以要&，其他的都是数组，数组名表示首元素地址；然后调用头插/尾插函数（自定义都能实现）
测试，通过调试观察
8.通讯录删除
通讯录的删除就是顺序表的删除，调用顺序表的删除函数，调用指定删除函数，不是头删也不是尾删
测试，通过调试观察
9.展示通讯录数据
测试，直接打印
10.通讯录的修改和查找
测试，直接打印
11.打印菜单
最终代码
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()
{int op = -1;Contact con;ContactInit(&con);do {menu();printf("请选择您的操作：\n");scanf("%d", &op);//要根据对应的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:printf("输入错误，请重新选择您的操作！\n");break;}} while (op != 0);ContactDesTroy(&con);return 0;
}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; //sl
//通讯录相关的方法//通讯录的初始化
void ContactInit(Contact* con);
//通讯录的销毁
void ContactDesTroy(Contact* con);
//通讯录添加数据
void ContactAdd(Contact* con);
//通讯录删除数据
void ContactDel(Contact* con);
//通讯录的修改
void ContactModify(Contact* con);
//通讯录查找
void ContactFind(Contact* con);
//展示通讯录数据
void ContactShow(Contact* con);Contact.c
#include"Contact.h"
#include"SeqList.h"//通讯录的初始化
void ContactInit(Contact* con)//sl
{//实际上要进行的是顺序表的初始化//顺序表的初始化已经实现好了SLInit(con);
}
//通讯录的销毁
void ContactDesTroy(Contact* con)
{SLDestroy(con);
}
//通讯录添加数据
void ContactAdd(Contact* con)
{//获取用户输入的内容：姓名+性别+年龄+电话+地址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(con, info);
}int FindByName(Contact* con, char name[])
{for (int i = 0; i < con->size; i++){if (0 == strcmp(con->arr[i].name, name)){//找到了return i;}}//没有找到return -1;
}//通讯录删除数据
void ContactDel(Contact* con)
{//要删除的数据必须要存在，才能执行删除操作//查找char name[NAME_MAX];printf("请输入要删除的联系人姓名:\n");scanf("%s", name);int find = FindByName(con, name);if (find < 0){printf("要删除的联系人数据不存在！\n");return;}//要删除的联系人数据存在--->知道了要删除的联系人数据对应的下标SLErase(con, find);printf("删除成功！\n");
}
//展示通讯录数据
void ContactShow(Contact* con)
{//表头：姓名 性别 年龄 电话 地址printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "地址");//遍历通讯录，按照格式打印每个联系人数据for (int i = 0; i < con->size; i++){printf("%3s %3s %3d %3s %3s\n", //手动调整一下格式con->arr[i].name,con->arr[i].gender,con->arr[i].age,con->arr[i].tel,con->arr[i].addr);}
}
//通讯录的修改
void ContactModify(Contact* con)
{//要修改的联系人数据存在char name[NAME_MAX];printf("请输入要修改的用户姓名：\n");scanf("%s", name);int find = FindByName(con, name);if (find < 0){printf("要修改的联系人数据不存在！\n");return;}//直接修改printf("请输入新的姓名：\n");scanf("%s", con->arr[find].name);printf("请输入新的性别：\n");scanf("%s", con->arr[find].gender);printf("请输入新的年龄：\n");scanf("%d", &con->arr[find].age);printf("请输入新的电话：\n");scanf("%s", con->arr[find].tel);printf("请输入新的住址：\n");scanf("%s", con->arr[find].addr);printf("修改成功！\n");
}
//通讯录查找
void ContactFind(Contact* con)
{//11char name[NAME_MAX];printf("请输入要查找的联系人姓名\n");scanf("%s", name);int find = FindByName(con, name);if (find < 0){printf("要查找的联系人数据不存在！\n");return;}// 姓名 性别 年龄 电话 地址// 11 11 11 11 11printf("%s %s %s %s %s\n", "姓名", "性别", "年龄", "电话", "地址");printf("%3s %3s %3d %3s %3s\n", //手动调整一下格式con->arr[find].name,con->arr[find].gender,con->arr[find].age,con->arr[find].tel,con->arr[find].addr);
}