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

数据结构：第2讲：线性表

news 2026/6/4 3:56:52

目录

1.线性表的定义和特点
2.线性表的顺序表示与实现 （顺序表）
3.线性表的链式表现与实现（链表）
4.线性表的应用
5.单向循环链表
6.判断链表是否有环
7.双向链表

1.线性表的定义和特点

（1）定义：
由 n（n>=0）个数据特性相同的元素构成的有限序列（有限即数量有限，序列理解为集合），称为线性表。

（2）特点：
线性表中元素的个数 n（n>=0）定义为线性表的长度，当 n=0 时称之为空表。对于非空的线性表，其特点是：

  • 存在唯一的一个被称作“第一个”的数据元素。
  • 存在唯一的一个被称作“最后一个”的数据元素。
  • 除第一个元素之外，结构中的每个数据元素均只有一个前驱（前一个元素叫前驱）。
  • 除最后一个元素外，结构中的每个数据元素均只有一个后继（后一个元素）。

2.顺序表

（1）定义：
用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的。

（2）存储结构：

简单来说，该结构体里有一个数组，还有一个 length，length 的值为几，就说明数组中有几个元素。

（3）初始化：

数组不需要去初始化，因为只要写了，就已经在内存中开辟了100个位置的连续空间了，故数组默认已经有了，只用对 length 初始化。

（4）在尾部添加元素

（5）遍历

（6）插入元素

intinsertElem(Seqlist*L,intpos,ElemType e)//pos 是位置，不是数组下标{if(L->length>=MAXSIZE){printf("表已经满了\n");return0;}if(pos<1||pos>L->length){printf("插入位置错误\n");return0;}if(pos<=L->length){for(inti=L->length-1;i>=pos-1;i--){L->data[i+1]=L->data[i];}L->data[pos-1]=e;L->length++;}return1;}

注：
往第一个位置插需要 n 次，往最后一个位置插需要 1 次。所以顺序表插入数据的最好时间复杂度是 O(1)，最坏时间复杂度是 O(n)。

（7）删除元素

本质是覆盖。

ElemType *e 的作用是用来储存被删除的数据，便于后续观察。

（8）查找（在当前顺序表中查找有没有自己想要的元素）

（9）动态分配内存地址初始化

3.链表

（1）链表存储结构的特点：
用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

（2）

（3）存储结构：

注：顺序表是有一个结构体能完整的表示一个顺序表，而链表是用一个结构体来表达一个节点。

（4）单链表（单一方向的链表）

  • 单链表的初始化

单链表的初始化是去创建一个头节点。

注：头节点（不存有效数据的头节点）不算链表的有效节点，真正链表从 head -> next 开始，所以 head ->next 的位置才是1。

  • 头插法

每一次插入新数据的时候，都把新数据放在头节点的后面。所以头插法的插入顺序和 printf 输出的排列顺序是相反的。

L 是头节点，也可以说是一条链表。

  • 遍历

  • 尾插法

要先获得尾节点地址：

再进行尾插法：

  • 在指定位置插入数据

要先把 70 的 next 赋值给 new 的 next，再把 new 的地址赋值给 70 的 next。new 插入后的位置是 2，不是 3。

  • 删除节点

找到要删除节点的前置节点 p，用指针 q 记录要删除的节点，通过改变 p 的后继节点来实现删除，释放被删除节点的空间。

intdeleteNode(Node*L,intpos){Node*p=L;inti=0;while(i<pos-1){p=p->next;i++;if(p==NULL){return0;}}if(p->next==NULL){printf("要删除的位置错误\n");return0;}Node*q=p->next;p->next=q->next;free(q);return1;}
  • 获取链表长度

该长度包括了头节点。

  • 释放链表

除了头节点以外的所有节点，都要给它删除掉。

思路：让指针 p 指向头节点后的第一个节点，判断指针 p 是否指向空节点，如果 p 不为空，用指针 q 记录指针 p 的后继节点，然后释放指针 p 指向的节点，把指针 q 赋值给指针 q ，让指针 p 和指针 q 指向同一节点，循环上面操作，最后再把头节点的 next 置空。

4.线性表的应用

（1）单链表应用1

①思路（快慢指针）：

  • 假设要找倒数第三个节点。

  • 声明两个指针，都指向头节点后的这个节点。

  • 因为要找倒数第三个节点，所以让快指针先走三步。

  • 快慢指针同时走，快指针指向空的时候，慢指针就找到了倒数第三个节点。

②代码实现

intfindNodeFS(Node*L,intk){for(inti=0;i<k;i++){fast=fast->next;}while(fast!=NULL){fast=fast->next;slow=slow->next;}printf("倒数第%d个节点值为：%d\n",k,slow->data);return1;}

（2）单链表应用2

①思路：

  • 先分别求出两条链表的长度 m 和 n。

  • fast 指针指向较长的链表，先走 m-n 或 n-m 步。

  • 同步移动指针，判断它们是否指向同一个节点。

②代码实现

Node*findIntersectionNode(Node*headA,Node*headB){if(headA==NULL||headB==NULL){returnNULL;}Node*p=headA;intlenA=0;intlenB=0;while(p!=NULL){p=p->next;lenA++;}p=headB;while(p!=NULL){p=p->next;lenB++;}Node*m;Node*n;intstep;if(lenA>lenB){step=lenA-lenB;m=headA;n=headB;}else{step=lenB-lenA;m=headB;n=headA;}for(inti=0;i<step;i++){m=m->next;}while(m!=n){m=m->next;n=n->next;}returnm;}

（3）单链表应用3

①思路：

  • 找到链表中绝对值最大的数，假如是21，然后创建一个长度为22的数组（保证数组下标有21），并将数组中每个元素置0。

  • 开始去遍历链表，先拿到了21，然后把21当成下标，将数组下标为21的元素置1。同理，遇到-15，将数组下标为15的元素置1。

  • 又遇到了-15，去找数组下标为15的元素，发现不是0而是1，说明之前已经见过绝对值为15的值了，将此节点删除，并释放内存。

  • 后面同理。

②代码实现

voidremoveNode(Node*L,intn)//L是头节点，n是链表中绝对值最大的数的绝对值{NOde*p=L;intindex;int*q=(int*)malloc(sizeof(int)*(n+1));for(inti=0;i<n+1;i++){*(q+i)=0;}while(p->next!=NULL){index=abs(p->next->data);if(*(q+index)==0){*(q+index)=1;p=p->next;}else{Node*temp=p->next;p->next=temp->next;free(temp);}}free(q);}

（4）单链表应用4

反转链表

①思路：

  • 先准备三个指针

  • 把 first 赋值给 second 的 next

  • 把三个指针往后挪，即把second赋值给first，把third赋值给second，并将third指向second的next。

  • 再将first赋值给second的next。

  • 后面同理，直到second指向NULL，循环结束。

  • 最后再加个头节点。

②代码实现

Node*reverseList(Node*head){Node*first=NULL;Node*second=head->next;Node*third;while(second!=NULL){third=second->next;second->next=first;first=second;second=third;}Node*hd=initList();hd->next=first;returnhd;}

该代码与上面思路略有不同，把 third 往后走一步放到了循环的最前面。

（5）单链表应用5

删除链表中间节点

①思路：

利用快慢指针

  • 让快指针指向1，慢指针指向头节点。

  • 每次让慢指针走一步，快指针走两步。即可找到中间节点的前驱节点，即可删除中间节点。

②代码实现

intdelMiddleNode(Node*head){Node*fast=head->next;Node*slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}Node*q=slow->next;slow->next=q->next;free(q);return1;}

（6）单链表应用6

①思路：

      将456翻转

      • 见缝插针

      q1放p1后面，q2放p2后面，以此类推。

      ②代码实现

      voidreOrderList(Node*head){Node*fast=head->next;Node*slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}Node*first=NULL;Node*second=slow->next;slow->next=NULL;Node*third=NULL;while(second!=NULL){third=second->next;second->next=first;first=second;second=third;}Node*p1=head->next;Node*q1=first;Node*p2,q2;while(p1!=NULL&&q1!=NULL){p2=p1->next;q2=q1->next;p1->next=q1;q1->next=p2;p1=p2;q1=q2;}}

      5.单向循环链表

      （1）特点：

      表中最后一个节点的指针域指向头节点，整个链表形成一个环。

      6.判断链表是否有环

      （1）判断是否有环
      ①题目意思解析：

      比如此链表，写出一个程序判断该链表是否有环（不一定是循环链表，头尾相连）。

      ②思路：

      • 利用快慢指针

      • 快指针每次比慢指针多走一步，如果链表中有环，则二者一定会相遇（生活中的例子：两人在操场跑圈，只要一个人始终比另一个人跑的快，则两人一定会相遇）。

      ③代码实现

      intisCycle(Node*head){Node*fast=head;Node*slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow){return1;}}return0;}

      7.双向链表

      （1）在双向链表的节点中有两个指针域，一个直接指向后继，另一个直接指向前驱。

      （2）组成：

      （3）初始化：

      Node*initList(){Node*head=(Node*)malloc(sizeof(Node));head->data=0;head->prev=NULL;head->next=NULL;returnhead;}

      （4）头插法：

      intinsertHead(Node*L,ElemType e){Node*p=(Node*)malloc(sizeof(Node));p->data=e;p->prev=L;p->next=L->next;if(L->next!=NULL){L->next->prev=p;}L->next=p;return1;}

      （5）尾插法：

      Node*insertTail(Node*tail,ElemType e){Node*p=(Node*)malloc(sizeof(Node));p->data=e;p->prev=tail;tail->next=p;p->next=NULL;returnp;}

      注：使用尾插法要先获得尾部节点：

      Node*get_tail(Node*L){Node*p=L;while(p->next!=NULL){p=p->next;}returnp;}

      （6）指定位置插入：

      intinsertNode(Node*L,intpos,ElemType e){Node*p=L;inti=0;while(i<pos-1){p=p->next;i++;if(p==NULL){return0;}}Node*q=(Node*)malloc(sizeof(Node));q->prev=p;q->next=p->next;p->next->prev=q;p->next=q;return1;}

      （7）删除节点：

      intdeletNode(Node*L,intpos){Node*p=L;inti=0;while(i<pos-1){p=p->next;i++;if(p==NULL){return0;}}if(p->next==NULL){printf("要删除的位置错误\n");return0;}Node*q=p->next;p->next=q->next;q->next->prev=p;free(q);return1;}
      http://www.jsqmd.com/news/946318/

      相关文章：

    • BQ4050电量计I2C通信避坑指南：当芯片手册地址遇上硬件自动左移
    • 计算机毕业设计之基于Python的微博热点新闻舆情分析与可视化
    • Simulink生成DLL时遇到的‘玄学’崩溃？我踩过的坑和终极避坑指南
    • 城市区域火灾概率推演工具：基于贝叶斯网络的Python可运行分析包
    • 从零搭建本地 Hermes Agent，一套整合包搞定自动化智能应用部署
    • 芯片热潮引爆韩国股市跻身全球第六，但泡沫隐忧渐显
    • 2026年10款降AI率平台实测：最高AI率100%直降至0.12%
    • 告别音频接口混乱：用FPGA实现16通道TDM音频传输的保姆级教程（基于48kHz/32bit）
    • 避开Arduino控制好盈电调的三个常见坑：从模拟PWM到定时器中断的优化之路
    • Unity杀戮尖塔风分层地牢生成器：自动布房+智能连通路径Demo
    • 别再乱搜代码了！Arduino Uno控制好盈电调的正确姿势（附寄存器版PWM详解）
    • 告别 Photoshop 插件：纯代码实现 QML 仪表盘的动态变色与交互（附完整工程）
    • STM32F407模拟SMBus读取BQ40Z50电量，我踩过的坑和调试心得（附完整代码）
    • 风电塔架风速与风荷载时程生成MATLAB工具包（含升阻力系数模块）
    • FFT/IFFT性能对决：递归 vs 迭代，谁才是C/C++项目中的效率王者？（附Benchmark测试）
    • 新手避坑指南：告别office破解版，用快马AI制作你的第一个文档工具
    • 超越默认编辑器：用QStyledItemDelegate为你的Qt表格打造专业级数据录入体验
    • [智能体-233]：传统的基于LLMchain langchain与基于LCEL langchain，在已定义的chain基础之上增加记忆功能的方式上的区别？
    • 示波器函数/任意波形发生器直流电源 | SiC/GaN 宽禁带半导体器件动态特性测试
    • 磁盘寻道时间计算与调度算法（FCFS、SSTF、SCAN、C-SCAN）
    • 计算机毕业设计之基于推荐的系统的新闻阅读平台的设计与实现
    • 从传感器延迟到坐标变换：深入拆解Lidar与IMU标定的核心难题
    • 规范与约束：抽象类与接口核心学习笔记
    • WinCC数据备份避坑指南：用VBS脚本搞定OnlineTableControl周期性导出CSV（附解决‘文件已存在’弹窗方法）
    • 别再只会用LM2596降压了！手把手教你搭建一个可调恒压恒流电源（附完整电路图）
    • 避坑指南：Verilog写BMP图片时多出0D字节？详解‘wb+’与‘w+’模式的区别
    • AutoJs Pro 7.0.4-1 保姆级脚本实战：从零写一个快手极速版自动化脚本（附完整源码）
    • 保姆级教程：在ROS1/ROS2中配置AMCL参数，让机器人定位又快又准
    • 大数据量高并发的数据库优化
    • 终极指南：5个简单步骤使用MediaCreationTool.bat轻松安装Windows 11，完整绕过硬件限制