线性表
线性表是一种逻辑结构,是抽象概念;顺序表、链表是存储结构,两者是不同层次的概念
线性表由数据元素组成,数据元素由数据项组成
线性表的位序从1开始
线性表的基本操作
void InitList(&L); //初始化
int Lenth(L); //获得表长
int LocateElem(L,e); //按值查找操作
ElemType GetElem(L,i); //按位查找操作
bool ListInsert(&L,i,e); //插入操作
bool ListDelete(&L,i,&e); //删除操作
void PrintList(L); //输出操作
bool Empty(L); //判空操作
void DestroyList(&L); //销毁操作
顺序表
顺序表是一种随机存取的存储结构
链表
链表是一种顺序存取的存储结构
链表内的元素值进行互换,一般视为两个节点断链后互换,而不是元素直接赋值。
双链表
双链表每个节点均有两个指针,头节点只有后继节点,前驱节点为NULL;最后节点只有前驱节点,后继节点为NULL。
循环单链表
表尾元素:该节点的NEXT指针是否指向头节点
空表判定:头指针的NEXT指针是否指向头节点自己
循环双链表
在循环单链表基础上,头节点的PRIOR指针指向表尾最后节点
静态链表
静态链表中的元素也包含数据域data以及指针域next,此时的指针与next指向的是下一个元素存放的下标。
0号节点充当头节点,当静态链表已满时指针域next设为-1.表示已到达表尾。
将静态链表作为数组去访问
#define MAXSIZE 10
typedef struct Node{
Element data;
int next;
};
void main{
struct Node S[MAXSIZE];
}
将静态链表作为独立的数据结构去访问
#define MAXSIZE 10
typedef struct Node{
Element data;
int next;
}SLinkList[MAXSIZE];
void main{
SLinkList S;
}
本质上,上下两种等价,但是后者让开发者可以不关注其存储结构,只关注其逻辑结构线性表本身,因此静态链表也不允许随机存取。
顺序表与链表对比
逻辑结构
顺序表和链表均为线性表,均为线性结构,一对一的关系
存储结构
顺序表
- 优点:可以随机存取,存储密度高
- 缺点:连续空间的分配不方便,改变容量不方便
链表:
- 优点:离散空间分配容易,改变容量容易
- 缺点:无法随机存取,存储密度低
基本操作
创建初始化:
顺序表需要预先分配大片连续空间。空间过大会浪费空间,空间过小扩展容量不方便
链表只需要预先分配头节点(或只声明头指针),改变容量随时扩展
销毁
对于静态分配所申请的空间,线性表生命周期结束自动回收。
对于动态分配,使用malloc所申请的空间均存储在栈堆中,需要手动free释放空间,即malloc和free成对出现,顺序表、链表是一样的。
插入、删除
顺序表插入/删除操作需要将后续元素后移/前移产生开销,如果超出容量还需要扩展。
时间复杂度为O(n),开销主要在移动元素上
链表插入/删除操作只需要修改指针域即可。
时间复杂度也为O(n),开销主要在查找元素上,相比移动元素高额的代价,查找所花费的开销一般更小
查找
顺序表按位查找只需要O(1),按值查找最坏需要O(n),如果顺序表内元素有序,可以在O(log2n)内找到
链表不论是按位还是按值(不论是否有序)均需要O(n)
使用场景
链表: 表长不可预估,需要频繁增删元素
顺序表:表长可预估,需要频繁查找元素
标签:02,顺序,线性表,元素,链表,节点,指针 From: https://www.cnblogs.com/GKJerry/p/18264780开放问题答题思路:
1.两种数据结构的逻辑结构差异
2.两种数据结构的存储结构差异
3.两种数据结构的基本操作上实现效率的差异