当前位置： 首页 > news >正文

顺序表和链表

news 2026/8/23 6:19:37

一 顺序表的定义和实现

1.顺序表的定义

顺序表是线性表的一种存储结构，其逻辑结构和物理结构都为线性，采用连续的物理存储单元依次存放物理元素，其底层结构是数组。

2.顺序表的分类

顺序表底层结构为数组，数组是一段连续的地址空间，我们在申请空间时，可以直接申请一个数组，也可以使用内存分配函数，申请一块大小不确定的内存空间，所以顺序表可以分为静态顺序表和动态顺序表。
（1）静态顺序表

structSeqList{intarr[100];intsize;};

（2）动态顺序表

structSeqList{SLDataType*arr;intsize;intcapacity;}SL;

3.顺序表的功能

对顺序表中的数据我们可以进行增删查改等操作，对顺序表也可以进行初始化与销毁。

  1. 顺序表的初始化与销毁
//顺序表初始化与销毁voidSLInit(SL*ps){ps->arr=NULL;ps->size=ps->capacity=0;}voidSLDestory(SL*ps){if(ps->arr){free(ps->arr);}ps->arr=NULL;ps->size=ps->capacity=0;}

2.顺序表的增删查改

//顺序表的增容voidSLCheckCapacity(SL*ps){if(ps->size==ps->capacity){intnewCapacity=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;}}//顺序表的头插，尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);ps->arr[ps->size]=x;ps->size++;}voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;ps->size++;}//顺序表的删除voidSLPopBack(SL*ps){assert(ps);assert(ps->size);ps->size--;}voidSLPopFront(SL*ps){assert(ps);assert(ps->size);for(inti=0;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}ps->size--;}//在指定位置插入voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos>=0&&pos<=ps->size);SLCheckCapacity(ps);for(inti=ps->size;i>pos;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[pos]=x;ps->size++;}//删除指定位置数据voidSLErase(SL*ps,intpos){assert(ps);assert(pos>=0&&pos<ps->size);for(inti=pos;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}ps->size--;}//查找intSLFind(SL*ps,SLDataType x){assert(ps);for(inti=0;i<ps->size;i++){if(ps->arr[i]==x){returni;}}return-1;}//顺序表的打印voidSLPrint(SL s){for(inti=0;i<s.size;i++){printf("%d ",s.arr[i]);}printf("\n");}

二 顺序表的应用

基于顺序表实现通讯录

上边我们实现了顺序表的基本功能，现在可以在顺序表的基础上增加一些功能，实现一个简易的通讯录。

  1. 定义Contact.h 实现通讯录联系人结构体定义，声明通讯录的功能。
#pragmaonce#defineNAME_MAX20#defineGENDER_MAX10#defineTEL_MAX20#defineADDR_MAX100//创建联系人结构体typedefstructpersonInfo{charname[NAME_MAX];chargender[GENDER_MAX];intage;chartel[TEL_MAX];charaddr[ADDR_MAX];}peoInfo;//给顺序表改个名字typedefstructSeqListContact;//通讯录的初始化与销毁voidContactInit(Contact*con);voidContactDestory(Contact*con);//联系人的增加voidContactAdd(Contact*con);//联系人的删除voidContactDel(Contact*con);//联系人的修改voidContactModify(Contact*con);//联系人的查找voidContactFind(Contact*con);//展示通讯录voidContactShow(Contact*con);
  1. 添加Contact.c 实现通讯录各个功能。
#include"Contact.h"#include"SeqList.h"//通讯录的初始化与销毁voidContactInit(Contact*con){SLInit(con);}voidContactDestory(Contact*con){SLDestory(con);}//联系人的增加voidContactAdd(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);}//通过姓名查找intFindbyname(Contact*con,charname[]){for(inti=0;i<con->size;i++){if(0==strcmp(con->arr[i].name,name)){returni;}}return-1;}//联系人的删除voidContactDel(Contact*con){charname[NAME_MAX];printf("请输入你要删除的联系人姓名：\n");scanf("%s",name);intfind=Findbyname(con,name);if(find<0){printf("要删除的联系人不存在\n");}else{SLErase(con,find);}}//联系人的修改voidContactModify(Contact*con){charname[NAME_MAX];printf("请输入你要修改的联系人姓名：\n");scanf("%s",name);intfind=Findbyname(con,name);if(find<0){printf("要修改的联系人不存在\n");}else{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");}}//联系人的查找voidContactFind(Contact*con){charname[NAME_MAX];printf("请输入你要查找的联系人姓名：\n");scanf("%s",name);intfind=Findbyname(con,name);if(find<0){printf("要查找的联系人不存在\n");}else{printf("姓名 性别 年龄 电话 地址\n");printf("%s %s %d %s %s\n",con->arr[find].name,con->arr[find].gender,con->arr[find].age,con->arr[find].tel,con->arr[find].addr);}}//展示通讯录voidContactShow(Contact*con){printf("姓名 性别 年龄 电话 地址\n");for(inti=0;i<con->size;i++){printf("%s %s %d %s %s\n",con->arr[i].name,con->arr[i].gender,con->arr[i].age,con->arr[i].tel,con->arr[i].addr);}}
  1. 添加test.c 文件，测试功能。
#include"SeqList.h"voidmenu(){printf("***************通讯录****************\n");printf("*******1增加数据 2删除数据********\n");printf("*******3修改数据 4查找数据********\n");printf("*******5展示通讯录 0退出 ********\n");printf("*************************************\n");}intmain(){Contact con;ContactInit(&con);intinput;do{menu();printf("请选择你的操作：\n");scanf("%d",&input);switch(input){case1:ContactAdd(&con);break;case2:ContactDel(&con);break;case3:ContactModify(&con);break;case4:ContactFind(&con);break;case5:ContactShow(&con);break;default:break;}}while(input);ContactDestory(&con);return0;}

三 单链表定义

1.单链表的定义

单链表是线性表的一种链式存储结构，其逻辑结构呈线性排列，但物理存储上节点之间并非连续。单链表由多个节点串联而成，每个节点包含数据域和指针域，其中指针域存储着下一个节点的地址信息。如图所示：

2.单链表的实现

我们需要定义单链表，就要定义单链表里的节点，节点分为数据域和指针域。

//创建节点结构体typedefintSLTDataType;typedefstructSListNode{SLTDataType data;structSListNode*next;}SLTNode;

3.单链表的功能

单链表和顺序表一样，可以对其中数据进行增删查改等操作。

#include"SList.h"//单链表的打印voidSLTPrint(SLTNode*phead){SLTNode*pucr;pucr=phead;while(pucr){printf("%d->",pucr->data);pucr=pucr->next;}printf("NULL\n");}//申请新节点SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail!");exit(1);}newnode->data=x;newnode->next=NULL;returnnewnode;}//单链表的头插尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x){//先申请一个新节点assert(pphead);SLTNode*newnode=SLTBuyNode(x);//空链表和非空链表两种情况if(*pphead==NULL){*pphead=newnode;}else{SLTNode*ptail;ptail=*pphead;while(ptail->next!=NULL){ptail=ptail->next;}ptail->next=newnode;}}voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnode=SLTBuyNode(x);newnode->next=*pphead;//先将新节点与原链表连接*pphead=newnode;//再让头指针指向链表第一个节点（newnode）}//单链表的头删尾删voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);//若链表只有一个节点if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{//先找到尾节点，再将其释放SLTNode*ptail=*pphead;SLTNode*prev=*pphead;while(ptail->next!=NULL){prev=ptail;ptail=ptail->next;}free(ptail);ptail=NULL;prev->next=NULL;}}voidSLTPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next;next=(*pphead)->next;free(*pphead);*pphead=next;}//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*pcur=phead;while(pcur){if(pcur->data==x){returnpcur;}pcur=pcur->next;}returnNULL;}//链表在指定位置之前插入voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead&&*pphead);assert(pos);//在第一个节点之前插入if(pos==*pphead){SLTPushFront(pphead,x);}else//在其他位置插入{SLTNode*prev=*pphead;while(prev->next!=pos){prev=prev->next;}SLTNode*newnode=SLTBuyNode(x);prev->next=newnode;newnode->next=pos;}}//链表在指定位置之后插入voidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnode=SLTBuyNode(x);newnode->next=pos->next;pos->next=newnode;}//删除pos位置的数据voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(pphead&&*pphead);assert(pos);if(*pphead==pos){SLTPopFront(pphead);}else{SLTNode*prev=*pphead;while(prev->next!=pos){prev=prev->next;}prev->next=pos->next;free(pos);pos=NULL;}}//删除pos位置之后的数据voidSLTEraseAfter(SLTNode*pos){assert(pos&&pos->next);SLTNode*del=pos->next;pos->next=del->next;free(del);del=NULL;}//销毁链表voidSlistDestory(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*pcur=*pphead;while(pcur){SLTNode*next=pcur->next;free(pcur);pcur=next;}*pphead=NULL;}
http://www.cnnetsun.cn/news/1436153.html

相关文章：

  • 【RS】从8位到64位：遥感影像位深如何影响地物识别与信息提取
  • SMOTE实战：用Python轻松搞定数据不平衡问题（附完整代码）
  • 松灵机器人二次开发实战：从零搭建Ubuntu环境到ROS包部署（避坑指南）
  • Mi-Create：零基础打造个性化小米穿戴表盘的终极指南
  • SecGPT-14B开源模型实战：中小企业低成本构建专属网络安全智能助手
  • 2026 大型企业网盘选型指南：为何说“同步性能”比“存储空间”更决定成败？
  • 高校科研数据总是丢？教育行业选企业网盘必须死磕的 3 个硬指标（含 5 款主流实测）
  • 丹青识画GPU算力调度：K8s Device Plugin管理书法渲染GPU资源
  • SILVACO TCAD实战：从网格划分到掺杂定制的SPAD器件结构构建
  • 用MATLAB手把手教你仿真3发4收毫米波雷达阵列信号（附完整代码）
  • 避免数据丢失！RK3399系统固件备份与恢复的5个关键步骤（含常见问题解答）
  • Linux驱动开发：环境准备与报错处理
  • AI写春联教程：5分钟上手春联生成模型，零基础也能创作吉祥对联
  • 从零开始：手把手教你用ROS Melodic在Ubuntu 18.04上跑通VINS-Mono（避坑指南）
  • 3分钟掌握Open Interpreter：本地代码执行AI助手的终极指南
  • Z-Image Atelier 自动化测试集成：基于软件测试理论的生成结果验证框架
  • GTE-Base-ZH助力AIGC内容审核：语义相似度匹配实战
  • FastAPI 实战进阶：从零构建高性能用户认证与数据交互API
  • STM32U5定时器实战：用CUBEMX配置TIM从模式实现电机同步控制（附避坑指南）
  • Python Tkinter实战：用20行代码打造你的第一个GUI计算器（附完整源码）
  • GME-Qwen2-VL-2B-Instruct应用开发：Node.js后端服务搭建与API封装
  • 留几手辣评：如今程序员拼命做“上吊绳”，卖个好价钱，然后把自己勒死
  • CLIP-GmP-ViT-L-14惊艳案例：X光片→放射科报告关键句/异常部位定位文本
  • 用Vivado仿真玩转数字存储：从移位寄存器到真双口RAM的FPGA原型验证
  • VMware Workstation Pro 17 安装与激活全攻略
  • FPGA硬件实现三线制SPI协议适配方案
  • Kazumi技术解密：自定义规则驱动的跨平台动漫聚合方案
  • Vue3视频播放器实战：如何用vue3-video-play实现学习视频防快进与断点续播
  • 手把手教你用PyTorch实现轴承故障诊断（代码可直接跑）
  • Windows11下MINIO的快速部署与配置指南