2.1. 定义与特点
定义
具有相同数据类型的 \(n(n\geq0)\) 个数据元素的有限序列。\(n\) 是表长,当 \(n=0\) 时该线性表是一个空表。若用 \(L\) 表示线性表,一般表示为:
\[L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)
\]
特点
- 元素个数有限
- 元素具有逻辑上的顺序,有先后次序
- 元素都是数据元素,每个元素都是单个元素
- 元素数据类型都相同,每个元素的存储空间都相同
- 元素具有抽象性,仅讨论元素间的逻辑关系,不讨论元素的具体意义
操作
1. 初始化表
2. 求表长
3. 按值查找位
4. 按位查找值
5. 插入元素
6. 删除元素
7. 输出元素
8. 空值判断
9. 销毁操作
2.2. 线性表的顺序表示——顺序表
定义
用一组地址连续的储存单元依次存储线性表中的数据元素,逻辑上相邻的两个元素在物理位置上也相邻。
特点
- 随机访问,通过首地址和元素序号即可在时间 \(O(1)\) 内找到指定元素
- 存储密度高,每个节点值存储数据元素
- 元素逻辑相邻则物理相邻,插入和删除操作需要移动大量元素
基本操作
插入 | 删除 | 按值查找位 | 按位查找值 | |
---|---|---|---|---|
最好情况 | \(O(1)\) | \(O(1)\) | \(O(1)\) | \(O(1)\) |
最差情况 | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(O(1)\) |
平均情况 | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(O(1)\) |
2.3. 线性表达链式表示——链表
意义
由于顺序表的插入删除需要移动大量元素,影响效率,由此引入链表(链式存储)。
定义
通过一组任意的存储单元来存储线性表中的数据元素。每个链表节点一般由【数据 | 指针】这样的结构构成,指针用于记录下一个或上一个链表节点的内存地址,从而达到连接的效果。
特点
- 附加的指针域消耗空间
- 非随机存取,查找某点时需要从表头开始遍历
构造
每一个链表必然有一个 \(头指针\) 来指向链表的第一个节点,该节点如果不用来存储数据(或者存储链表长度),则称为头节点。头节点的指针指向第一个有意义的数据节点。
引入头结点的优点:
- 由于开始节点的地址被放在头节点的指针里,所以在链表的开始节点上的操作和其他位置一样,无需特殊处理。
- 无论链表是否为空,头指针都要指向一个头节点,而非空指针,这样就把空表和非空表的处理统一起来了。
基本操作
操作 | 复杂度 |
---|---|
头插法建立单链表 | \(O(1)\) |
尾插法建立单链表 | \(O(1)\) |
按序号查找值 | \(O(n)\) |
按值查找表节点 | \(O(n)\) |
前插入节点 | \(O(1)\) |
后插入节点 | \(O(1)\) |
删除节点 | \(O(1)\) |
求表长 | \(O(n)\) |
2.4. 顺序表与链表的比较
顺序表 | 链表 | |
---|---|---|
存取方式 | 顺序或随机 | 从表头顺序 |
逻辑结构和物理结构 | 逻辑相邻物理相邻 | 逻辑相邻物理不相邻 |
按值查找 | 无序\(O(n)\),有序\(O(log_2n)\) | \(O(n)\) |
按序号查找 | \(O(1)\) | \(O(n)\) |
插入删除 | \(O(n)\) | \(O(1)\) |
空间分配 | 固定 | 按需(灵活) |
选择
-
存储
长度可预测 顺序表 更合适,长度不可预测 链表 更合适
-
运算
插入删除操作频繁则 链表 更合适,读写操作频繁的 顺序表 更合适
-
环境
顺序表在大多数语言中都可实现,链表基于指针,最好是c和c++。(当然高级语言有那种不限制元素类型和数量的表结构!比如python的list和Java的array)
2.5. 代码实现
实现带头节点的单链表
#include<iostream>
using namespace std;
//带头结点的单链表
typedef int T;
struct LinkedListNode{
T data;//数据
LinkedListNode *pointer;//后向指针
};
LinkedListNode* init()//初始化链表的头结点
{
return NULL;
}
void show(LinkedListNode* P_head_node)//显示链表数据
{
LinkedListNode* P_current_node;
P_current_node=P_head_node->pointer;
cout<<"[";
while(true)
{
if(P_current_node==NULL)
{
break;
}
cout<<P_current_node->data;
P_current_node=P_current_node->pointer;
if(P_current_node!=NULL)
{
cout<<",";
}
}
cout<<"]"<<endl;
}
void showDetail(LinkedListNode* P_head_node)//显示链表详细参数
{
LinkedListNode* P_current_node;
P_current_node=P_head_node->pointer;
cout<<"\n\n===============================\n";
cout<<"|序号\t地址\t数据\t"<<endl;
//cout<<"===============================\n";
cout<<"-------------------------------\n";
cout<<"|头\t"<<P_head_node<<"\tNULL\t"<<endl;
int len=0;
while (true) {
if(P_current_node==NULL)
{
break;
}
cout<<"|"<<len<<"\t"<<P_current_node<<"\t"<<P_current_node->data<<"\t"<<endl;
len=len+1;
P_current_node=P_current_node->pointer;
}
cout<<"===============================\n\n";
}
int length(LinkedListNode* P_head_node)//计算链表长度
{
LinkedListNode* P_current_node;
P_current_node=P_head_node->pointer;
int len=0;
while(true)
{
if(P_current_node==NULL)
{
break;
}
len=len+1;
P_current_node=P_current_node->pointer;
}
return len;
}
void append(T data,LinkedListNode* P_head_node)//在链表最后插入数据
{ //newNode=(LinkedListNode *)malloc(sizeof (LinkedListNode));
LinkedListNode* P_current_node;
P_current_node=P_head_node;
while (true) {
if(P_current_node->pointer==NULL)
{
break;
}
P_current_node=P_current_node->pointer;
}
LinkedListNode* P_new_node;
P_new_node=(LinkedListNode *)malloc(sizeof (LinkedListNode));
P_new_node->data=data;
P_new_node->pointer=NULL;
P_current_node->pointer=P_new_node;
}
void deleteLastest(LinkedListNode* P_head_node)//删除最尾数据
{
if(P_head_node->pointer==NULL)
{
cout<<"链表为空,无法删除最尾数据!"<<endl;
}
else
{
LinkedListNode* P_current_node;
P_current_node=P_head_node;
while(true)
{
if(P_current_node->pointer->pointer==NULL)
{
break;
}
P_current_node=P_current_node->pointer;
}
free(P_current_node->pointer);
P_current_node->pointer=NULL;
}
}
int main()
{
LinkedListNode head_node;
head_node.pointer=init();
deleteLastest(&head_node);
int i;
for(i=0;i<5;i++)
{
append(i,&head_node);
}
show(&head_node);
cout<<length(&head_node)<<endl;
deleteLastest(&head_node);
show(&head_node);
cout<<length(&head_node)<<endl;
showDetail(&head_node);
return 0;
}
结果为:
链表为空,无法删除最尾数据!
[0,1,2,3,4]
5
[0,1,2,3]
4
===============================
|序号 地址 数据
-------------------------------
|头 0x7ffd78a061a0 NULL
|0 0x558797464280 0
|1 0x5587974642a0 1
|2 0x5587974642c0 2
|3 0x5587974642e0 3
===============================
按 <RETURN> 来关闭窗口...