【数据结构】顺序表与通讯录的实现（C）

• 高效存储数据
• 方便快速查找
• 支持灵活的增删改查操作

最基础的数据结构是数组，但它的局限性很大。比如当数组已满时，插入新数据需要手动扩容；频繁计算有效元素个数还会降低效率。这就是我们需要学习更高级结构的原因——顺序表就是数组的升级版。

一、顺序表的概念与结构

1. 线性表的基础

顺序表属于线性表的一种。线性表是由n个相同特性的数据元素组成的有限序列，常见的还有链表、栈、队列等。它的逻辑结构是一条连续的直线，但物理存储方式可以是数组或链式结构。

• 线性表物理结构不一定连续，逻辑结构是连续的。
• 顺序表物理结构和逻辑结构都是连续的

2. 顺序表与数组的区别

顺序表的底层基于数组实现，但它对数组进行了封装，提供了更完善的操作接口。简单说：数组是原料，顺序表是加工后的成品。

比如数组只能通过下标访问，而顺序表会额外记录有效元素个数和容量，让数据管理更可控。

二、顺序表的分类

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，通常采用数组存储。根据存储空间的分配方式，可分为两类：

• 静态顺序表：使用固定大小的数组存储数据，空间一旦确定无法更改
• 动态顺序表：使用动态开辟的数组存储数据，可根据需要动态扩容，更灵活实用

本文重点实现动态顺序表，因为它能更好地适应数据量变化的场景。

三、顺序表的结构设计

首先我们需要定义顺序表的结构体，动态顺序表需要包含三个核心要素：

typedefintSLDataType;// 数据类型别名，方便后续修改存储类型structSeqList{SLDataType*arr;// 指向动态开辟的数组intsize;// 有效数据个数intcapacity;// 容量大小（能存储的最大数据个数）};typedefstructSeqListSL;// 重命名，简化代码

这样的设计有几个好处：

• 使用SLDataType统一数据类型，后续要存储char或float只需修改这里
• 分离size和capacity，清晰区分当前数据量和总容量
• 用指针指向动态数组，实现存储空间的动态管理

四、核心功能实现

1. 初始化与销毁

初始化函数：将顺序表初始化为空状态

voidSLInit(SL*p)// 传地址而不是传值，因为要修改结构体内容{p->arr=NULL;p->size=p->capacity=0;// 初始状态：无数据，容量为0}

销毁函数：释放动态开辟的空间，避免内存泄漏

voidSLDes(SL*p){if(p->arr)// 如果数组存在，则释放{free(p->arr);}p->arr=NULL;// 置空指针，避免野指针p->size=p->capacity=0;// 重置状态}

2. 空间检查与扩容

动态顺序表的关键在于自动扩容，我们实现一个专门的函数来处理：

voidcheckCapacity(SL*p){assert(p);// 确保指针有效// 当有效数据个数等于容量时，需要扩容if(p->size==p->capacity){// 初始容量为4，之后每次翻倍intnewCapacity=p->capacity==0?4:2*p->capacity;// 使用realloc进行扩容（首次调用时相当于malloc）SLDataType*tmp=(SLDataType*)realloc(p->arr,newCapacity*sizeof(SLDataType));if(tmp==NULL)// 检查扩容是否成功{perror("realloc fail!!");exit(1);// 扩容失败则退出程序}// 扩容成功，更新指针和容量p->arr=tmp;p->capacity=newCapacity;}}

为什么选择2倍扩容？这是一种时间和空间效率平衡的策略，既能减少频繁扩容的开销，又不会过度浪费空间。

3. 插入操作

尾插

voidSLPushBack(SL*p,SLDataType x){assert(p);checkCapacity(p);// 先检查空间p->arr[p->size]=x;// 直接在末尾赋值++p->size;// 有效数据个数加 1}

头插

voidSLPushFront(SL*p,SLDataType x){assert(p);checkCapacity(p);// 从最后一个元素开始，依次向后移动一位for(inti=p->size;i>=1;i--){p->arr[i]=p->arr[i-1];}p->arr[0]=x;// 头部位置赋值p->size++;// 更新数据个数}

指定位置之前插入

voidSLInsert(SL*p,intpos,SLDataType x){assert(p);assert(pos>=0&&pos<=p->size);// 确保位置有效checkCapacity(p);// 从最后一个元素到pos位置，依次后移for(inti=p->size;i>pos;i--){p->arr[i]=p->arr[i-1];}p->arr[pos]=x;// 在pos位置插入新元素p->size++;}

4. 删除操作

尾删

voidSLPopBack(SL*p){assert(p);assert(p->size);// 确保顺序表不为空p->size--;// 只需将有效数据个数减1（逻辑删除）}

头删

voidSLPopFront(SL*p){assert(p);assert(p->size);// 确保顺序表不为空// 从第二个元素开始，依次向前移动一位for(inti=0;i<p->size-1;i++){p->arr[i]=p->arr[i+1];}p->size--;// 更新数据个数}

指定位置删除

voidSLErase(SL*p,intpos){assert(p);assert(p->size);// 确保顺序表不为空assert(pos>=0&&pos<p->size);// 确保位置有效// 从pos位置开始，依次用后一个元素覆盖前一个for(inti=pos;i<p->size-1;i++){p->arr[i]=p->arr[i+1];}p->size--;}

5. 查找与打印

查找元素：返回元素所在位置，未找到返回-1

intSLFind(SL*p,SLDataType x){assert(p);for(inti=0;i<p->size;i++){if(p->arr[i]==x)returni;}return-1;// 未找到}

打印顺序表：遍历输出所有元素

voidSLPrint(SL s){for(inti=0;i<s.size;i++){printf("%d ",s.arr[i]);}printf("\n");}

五、测试代码与运行结果

我们编写测试函数来验证各个功能：

voidSLtest01(){SL s1;SLInit(&s1);// 初始化// 尾插测试SLPushBack(&s1,1);SLPushBack(&s1,2);SLPushBack(&s1,3);SLPushBack(&s1,4);SLPushBack(&s1,5);SLPrint(s1);// 输出：1 2 3 4 5// 指定位置插入测试SLInsert(&s1,0,9);// 头部插入SLPrint(s1);// 输出：9 1 2 3 4 5SLInsert(&s1,s1.size,6);// 尾部插入（等价于尾插）SLPrint(s1);// 输出：9 1 2 3 4 5 6// 指定位置删除测试SLErase(&s1,1);// 删除索引1的元素SLPrint(s1);// 输出：9 2 3 4 5 6SLErase(&s1,2);// 删除索引2的元素SLPrint(s1);// 输出：9 2 4 5 6SLErase(&s1,s1.size-1);// 删除最后一个元素SLPrint(s1);// 输出：9 2 4 5// 查找测试intfind=SLFind(&s1,4);printf("%d\n",find);// 输出：2（元素4在索引2位置）SLDes(&s1);// 销毁}

六、顺序表的应用：通讯录

1. 项目需求

实现一个具有以下功能的通讯录：

1. 存储至少100个人的通讯信息
2. 保存信息包括：名字、性别、年龄、电话、地址等
3. 支持增加、删除、查找、修改、显示联系人等操作
4. 程序结束后，通讯录信息不丢失

2. 核心设计思路

（1）数据结构设计

首先定义联系人信息结构体：

#defineNAME_MAX100#defineSEX_MAX4#defineTEL_MAX11#defineADDR_MAX100typedefstructPersonInfo{charname[NAME_MAX];// 姓名charsex[SEX_MAX];// 性别intage;// 年龄chartel[TEL_MAX];// 电话charaddr[ADDR_MAX];// 地址}PeoInfo;

然后基于动态顺序表实现通讯录：

// 数据类型为PersonInfotypedefstructPersonInfoSQDataType;// 动态顺序表typedefstructSeqList{SQDataType*a;// 存储联系人数据intsize;// 有效联系人个数intcapacity;// 容量}SLT;// 通讯录类型定义typedefstructSeqListcontact;

（2）核心功能实现

1. 初始化通讯录

voidInitContact(contact*con){SeqListInit(con);// 初始化顺序表LoadContact(con);// 加载历史数据}

2. 添加联系人

voidAddContact(contact*con){PeoInfo info;printf("请输入姓名:\n");scanf("%s",info.name);printf("请输入性别:\n");scanf("%s",info.sex);printf("请输入年龄:\n");scanf("%d",&info.age);printf("请输入联系电话:\n");scanf("%s",info.tel);printf("请输入地址:\n");scanf("%s",info.addr);SeqListPushBack(con,info);// 尾插printf("插入成功!\n");}

3. 删除联系人

voidDelContact(contact*con){charname[NAME_MAX];printf("请输入要删除的用户姓名:\n");scanf("%s",name);intpos=FindByName(con,name);// 查找位置if(pos<0){printf("要删除的用户不存在,删除失败!\n");return;}SeqListErase(con,pos);// 删除指定位置元素printf("删除成功!\n");}

4. 数据持久化
   为了保证程序结束后数据不丢失，需要将数据保存到文件：

voidSaveContact(contact*con){FILE*pf=fopen("contact.txt","wb");if(pf==NULL){perror("fopen error!\n");return;}// 将通讯录数据写入文件for(inti=0;i<con->size;i++){fwrite(con->a+i,sizeof(PeoInfo),1,pf);}printf("通讯录数据保存成功!\n");fclose(pf);}

程序启动时加载数据：

voidLoadContact(contact*con){FILE*pf=fopen("contact.txt","rb");if(pf==NULL){printf("fopen error!\n");return;}// 循环读取文件数据PeoInfo info;while(fread(&info,sizeof(PeoInfo),1,pf)){SeqListPushBack(con,info);}printf("历史数据导入通讯录成功!\n");fclose(pf);}

5. 菜单交互

voidmenu(){contact con;InitContact(&con);intop=-1;do{printf("********************************\n");printf("*****1、添加用户 2、删除用户*****\n");printf("*****3、查找用户 4、修改用户*****\n");printf("*****5、展示用户 0、退出 *****\n");printf("********************************\n");printf("请选择您的操作:\n");scanf("%d",&op);switch(op){case1:AddContact(&con);break;case2:DelContact(&con);break;case3:FindContact(&con);break;case4:ModifyContact(&con);break;case5:ShowContact(&con);break;case0:printf("退出程序\n");break;default:printf("输入有误,请重新输入\n");break;}}while(op!=0);// 销毁通讯录,同时保存数据DestroyContact(&con);}

七、顺序表的问题与思考

优点

1. 随机访问：可以通过下标直接访问任意元素，时间复杂度O(1)
2. 缓存友好：数据存储连续，充分利用CPU缓存，访问效率高
3. 实现简单：相比链表，结构和操作更简单

缺点

1. 插入删除效率问题：中间或头部的插入删除操作需要移动大量元素，时间复杂度为O(N)
2. 增容消耗：增容时需要申请新空间、拷贝数据、释放旧空间，会产生额外消耗
3. 空间浪费：增容通常是2倍增长，可能导致部分空间闲置（例如容量从100增到200，却只再插入5个数据，就浪费了95个空间）

这些问题也引出了另一种重要的数据结构——链表，它在解决上述问题上有独特优势。在实际开发中，我们需要根据具体场景选择合适的数据结构。