链表

线性结构。每个节点含有数据与指针两个部分,指针指向其他节点。

与线性表的对比

优势:插入删除方便 缺点:查找不方便

基本结构

<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. 链表表示多项式

每个节点中数据结构为

1
[系数 coef | 指数 exp | next]

当进行多项式相加时,若已按指数顺序排列好,则两个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,只保存非零元素。

每个非零元素结点包含:

1
row, col, value, right, down
  • right:指向同一行中的下一个非零元素。

  • down:指向同一列中的下一个非零元素。

  • 行链表与列链表交叉形成正交链表。

  • 各行、各列通常使用带头结点的循环链表。

若矩阵有 r 行、c 列和 t 个非零元素,主要存储量约为 O(r+c+t),比保存整个 r×c 矩阵更节省空间。

它适合非零元素会频繁增加、删除或移动的场景,但结构复杂,建立和销毁时必须同时维护行链和列链。


``

`

使用 Hugo 构建
主题 Stack 由 Jimmy 设计