线性结构。每个节点含有数据与指针两个部分,指针指向其他节点。
与线性表的对比
优势:插入删除方便 缺点:查找不方便
基本结构
<template T>
`struct node{
T data;
node* next;
}
注意首尾节点的维护:
基础知识
1.单链表
1.插入
node* current; node* newnode = new node;
newnode->next =current->next; current->next=newnode;
2.删除
node* current; node* temp= new node;
temp=current->next; current->next=temp->next;
`delete temp;
3.时间复杂度
- 按值查找:O(n)
- 按序号查找:O(n)
- 已知前驱结点后插入:O(1)
- 已知前驱结点后删除:O(1)
- 求长度:若没有专门保存长度,则为 O(n) 注:链表中常使用头节点(不储存信息),方便操作
2.循环链表
与单链表基本一致,主要区别是加入了tail->next=head,的循环链。在空表时需要维护head->next=head
3. 链表表示多项式
每个节点中数据结构为
| |
当进行多项式相加时,若已按指数顺序排列好,则两个m项和n项多项式相加,时间复杂度为o(m+n) 解释:若两个多项式,正好没有指数项重复,则需要每一项都做一步。最好情况是全相同,则时间复杂度为min{0(m,n)}
4.双向链表
与单链表类似,但是要加上一个node* prior成员,指向此节点的前一个节点。 代码示例: struct node{ T data; node* next; node* prior; }
1.双向链表的插入
node* current; node* newnode=new node;
newnode->prior=current; newnode->next+current->next;//先连上新节点的两端
current->next->prior=newnode; current->next=newnode;
双向链表的删除
node* current;//删除current的下一个 node* temp=current->next; current->next=temp->next; temp->next->prior=current;`
5.矩阵的正交链表
稀疏矩阵的正交链表
稀疏矩阵中绝大多数元素为 0,只保存非零元素。
每个非零元素结点包含:
| |
right:指向同一行中的下一个非零元素。down:指向同一列中的下一个非零元素。行链表与列链表交叉形成正交链表。
各行、各列通常使用带头结点的循环链表。
若矩阵有 r 行、c 列和 t 个非零元素,主要存储量约为 O(r+c+t),比保存整个 r×c 矩阵更节省空间。
它适合非零元素会频繁增加、删除或移动的场景,但结构复杂,建立和销毁时必须同时维护行链和列链。
``
`