2.1 线性表的定义与基本操作
线性表(linear-list)
2.1.1 线性表的定义
线性表是具有相同数据类型的 n(n≥0)个数据元素的有限序列。
线性表的抽象数据类型定义:
在数据元素的非空有限集中:
- 存在唯一的一个被成做“第一个”的数据元素;
- 存在唯一的一个被称作“最后一个”的数据元素;
- 除第一个之外,集合中的每个数据元素均只有一个前驱;
- 除最后一个之外,集合中每个数据元素均只有一个后继。
线性表是逻辑结构,顺序表和链表是存储结构
特点:
- 元素个数有限
- 元素具有逻辑上的顺序性,在序列中各元素排序有先后顺序
- 元素都是数据,每个元素都是单个元素
- 元素的数据类型都相同,这意味着每个元素占有相同大小的存储空间
- 元素具有抽象性,即仅讨论元素间的逻辑关系,而不考虑元素究竟表示什么内容
2.1.2 线性表的基本操作
- InitList(&L):初始化表。构造一个空的线性表 L,分配内存空间。
- Length(L):求表长。返回线性表 L 的长度,即 L 中数据元素的个数。
- LocateElem(L, e): 按值查找操作。在表 L 中查找具有给定关键字值的元素。
- GetElem(L, i): 按位查找操作。获取表 L 中第 i 个位置的元素的值。
- ListInsert(&L, i, e): 插入操作。在表 L 中第 i 个位置插入指定元素 e。
- ListDelete(&L, i, &e): 删除操作。删除表 L 中第 i 个位置的元素,并用 e 返回删除元素的值。
- PrintList(L): 输出操作。按前后顺序输出线性表 L 的所有元素值。
- Empty(L): 判空操作。若 L 为空表,则返回 true,否则返回 false。
- DestroyList(&L): 销毁操作。销毁线性表,并释放线性表 L 所占用的内存空间。
2.2 线性表的顺序表示
2.2.1 顺序表的定义
特点:逻辑顺序与物理顺序相同。可以随机存取
优点:
- 随机存取时间复杂度 O(1)
- 存储密度高,每个节点只存储数据元素(不包含位置指针)
缺点:
- 插入删除时间复杂度 O(n)
- 需要预分配连续的存储空间
2.2.2 顺序表的基本操作
1. 顺序表的初始化
typedef struct {
ElemType *data;
int length;
int MaxSize;
} SeqList;
静态分配
void InitList(SqList &L)
{
L.length = 0;
}
动态分配
#define MAX_SIZE 10
void InitList(SeqList &L)
{
L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
L.length = 0;
L.MaxSize = MAX_SIZE;
}
2. 插入操作
bool ListInsert(SqList &L, int i, ElemType e)
{
if (i < 1 || i > L.length + 1 || L.length >= L.MaxSize)
return false;
for (int j = L.length; j >= i; j--)
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.length++;
return true;
}
3. 删除操作
bool ListDelete(SqList &L, int i, ElemType &e)
{
if (i < 1 || i > L.length)
return false;
e = L.data[i - 1];
for (int j = i; j < L.length; j++)
{
L.data[j - 1] = L.data[j];
}
L.length--;
return true;
}
4. 按值查找
int LocateElem(SqList L, ElemType e)
{
for (int i = 0; i < L.length; i++)
{
if (L.data[i] == e)
return i + 1;
}
return 0;
}
2.3 线性表的链式表示
线性链表
节点(Node):数据元素的存储映像。由存放数据元素的数据域和存放后继结点地址的指针域组成
- 数据域:存储数据元素信息的域
- 指针域:存储直接后继位置的指针
特点:
- 用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)
- 链表中结点的逻辑顺序和物理顺序不一定相同
2.3.1 单链表的定义
优点:
- 插入删除时间复杂度 O(1)
- 不需要分配连续的存储空间
缺点:
- 随机存取时间复杂度 O(n)
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode, *LinkList;
单链表分为带头节点和不带头节点
引入头节点的优点:
- 链表第一个位置上的操作和其他位置一致,无需特殊处理
- 无论链表是否为空,头指针都是指向头节点的非空指针,空表和非空表的处理也就统一了
2.3.2 单链表的基本操作
1. 初始化
带头节点
bool InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
return true;
}
不带头节点
bool InitList(LinkList &L)
{
L= NULL;
return true;
}
2. 求表长操作
带头节点
int Length(LinkList L)
{
int len = 0;
LNode *p = L->next;
while (p != NULL) {
p = p->next;
len++;
}
return len;
}
不带头节点
int Length(LinkList L)
{
int len = 0;
LNode *p = L;
while (p != NULL) {
p = p->next;
len++;
}
return len;
}
3. 按位查找
带头节点
LNode *GetElem(LinkList L, int i)
{
if (i < 1)
return NULL;
LNode *p = L->next;
int j = 1;
while (j != i && p != NULL)
{
p = p->next;
j++;
}
return p;
}
不带头节点
LNode *GetElem(LinkList L, int i)
{
if (i < 1)
return NULL;
LNode *p = L;
int j = 1;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
4. 按值查找
带头节点
LNode *LocateElem(LinkList L, ElemType e)
{
LNode *p = L->next;
while (p->data != e && p!= NULL) {
p = p->next;
}
return p;
}
不带头节点
LNode *LocateElem(LinkList L, ElemType e)
{
LNode *p = L;
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}
5. 插入操作(后插操作)
带头节点
bool ListInsert(LinkList &L, int i, ElemType e)
{
LNode *p = L;
int j = 1;
while (p != NULL && j != i) {
p = p->next;
j++;
}
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
不带头节点
第一位插入时,需要特殊处理
bool ListInsert(LinkList &L, int i, ElemType e)
{
if (i < 1)
return false;
if (i == 1)
{
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L = s;
return true;
}
LNode *p = L;
int j = 2;
while (p != NULL && j != i) {
p = p->next;
j++;
}
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
6. 删除操作
带头节点
bool ListDelete(LinkNode &L, int i, ElemType &e)
{
LNode *p = L;
int j = 0;
while (p->next != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p->next == NULL || j > i - 1)
return false;
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
不带头结点
bool ListDelete(LinkList &L, int i, ElemType &e)
{
if (L == NULL)
return false;
if (i == 1) {
LNode *q = L;
e = q->data;
L = q->next;
free(q);
return true;
}
LNode *p = L;
int j = 1;
while (p->next != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || p->next == NULLF)
return false;
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
7. 采用头插法创建单链表
带头节点
LinkList List_HandleInsert(LinkList &L, ElemType e)
{
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L->next;
L->next = s;
return L;
}
LinkList List_HeadInsert(LinkList &L)
{
LNode *s; int x;
L = (LNode*)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d", &x);
while(x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
不带头结点
LinkList List_HeadInsert(LinkList &L)
{
LNode *s; int x;
L = NULL;
scanf("%d", &x);
while(x != 9999) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L == NULL ? NULL : L->next;
L = s;
scanf("%d", &x);
}
return L;
}