大话数据结构-线性表

线性表的定义

  • 零个或多个数据元素的有限序列

分类

  • 顺序储存结构
  • 链式储存结构
    • 单链表
    • 静态链表
    • 循环链表
    • 双向链表

顺序储存结构

  • 宏定义
1
2
3
4
5
6
7
8
9
#define OK 1
#define ERROR 0
#define TRUE 1
#define MAXSIZE 20
//静态链表的最大空间
#define STATIC_MAXSIZE 1000
#define FALSE 0
typedef int status;
typedef int ElemType;
  • 结构体
1
2
3
4
5
6
7
/**
* 顺序储存结构
*/
typedef struct {
ElemType data[MAXSIZE];
int length;
} SqList;

获得元素

1
2
3
4
5
6
7
status getElem(SqList L, int i, ElemType &e) {
if (i < 1 || i > L.length || L.length == 0) {
return ERROR;
}
e = L.data[i - 1];
return OK;
}

插入元素

算法思路:
  • 如果插入位置不合理,抛出异常
  • 如果线性表长度大于等于数组长度,则抛出异常或者动态扩容
  • 从最后一个元素开始向前遍历到第i的位置,分别将他们向后移动一个位置
  • 将要插入的元素填入到位置i处
  • 表长 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
status insert(SqList &L, int i, ElemType e) {
if (L.length == MAXSIZE) {
return ERROR;
}
if (i < 1 || i > L.length) {
return ERROR;
}
if (L.length >= i) {
for (int j = L.length - 1; j >= i - 1; j--) {
L.data[j + 1] = L.data[j];
}
}
L.data[i - 1] = e;
L.length++;
return OK;
}

删除操作

算法思路
  • 如果删除的位置不合理,抛出异常
  • 去出删除的元素
  • 从删除的元素开始遍历到最后一个元素,分别将他们都向前移动一个位置
    *表长 - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
status deleteElem(SqList &L, int i, ElemType &e) {
if (i < 1 || i > L.length + 1) {
return ERROR;
}
if(L.length == 0) {
return ERROR;
}
e = L.data[i - 1];
if(i < L.length) {
for (int j = i - 1; j <= L.length; ++j) {
L.data[j] = L.data[j + 1];
}
}
L.length--;
return OK;
}

时间复杂度

  • 最好情况下,如果插入的元素是最后一个,或者删除的元素是最后一个,意味着元素不用移动,那么时间复杂度为O(1)。
  • 最坏情况,如果插入的元素在第一个,或者删除的元素在第一个,那么意味着全部元素将要向前或者向后移动,时间复杂度为O(n)。
  • 平均情况: 时间复杂度为O(n)

优点

  • 快速存取表中的任一元素

缺点

  • 插入和删除需要大量移动元素
  • 当线性表长度变化较大时,难以确定储存空间

链式储存结构

  • 结构体
1
2
3
4
5
6
7
8
/**
* 链式储存结构
*/
typedef struct Node {
ElemType e;
struct Node *next;
int length;
} Node, *LinkList;

单链表的读取

算法思路
  • 声明一个指针p指向链表第一个结点,初始化j从1开始
  • 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
  • 若到链表末尾p为空,则说明第i个结点不存在
  • 否则查找成功,返回结点p的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
status lGetElem(LinkList L, int i, ElemType &e) {
int j;
LinkList p;
p = L->next;
j = 1;
while(p && j < i) {
p = p->next;
j++;
}
if(!p || j > i) {
return ERROR;
}
e = p->e;
return OK;
}

单链表的插入

算法思路:
  • 声明一指针指向链表头结点,初始化j从1开始
  • 当j<i时,遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
  • 若到链表末尾为空,则说明第i的结点不存在
  • 否则查找成功,在系统中生成一个空的结点s
  • 将数据元素e赋值给s->data
  • 进行单链表插入操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
status lInsertElem(LinkList &L, int i, ElemType e) {
if(i < 1) {
return ERROR;
}
int j = 1;
LinkList p;
p = L->next;
while (p && j < i) {
p = p->next;
j++;
}
//第i个结点不存在
if(!p || j > i) {
return ERROR;
}
LinkList s = (LinkList) malloc(sizeof(Node));
if(s == NULL) {
return ERROR;
}
s->e = e;
s->next = p->next;
p->next = s;
return OK;
}

单链表的删除

算法思路
  • 声明一指针指向链表头结点,初始化j从1开始
  • 当j<i时,遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
  • 若到链表末尾为空,则说明第i的结点不存在
  • 若查找成功,将欲删除的结点p->next赋值给q
  • 删除结点
  • 将q结点中的数据赋值给e并返回
  • 释放q结点
  • 返回成功
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
status lDeleteElem(LinkList &L, int i, ElemType &e) {
int j = 1;
LinkList p, q;
p = L;
while(p->next && j < i) {
p = p->next;
j++;
}
if(!(p->next) || j > i) {
return ERROR;
}
q = p->next;
p->next = q->next;
e = q->e;
free(q);
}

创建单链表

算法思路
  • 声明一指针p和计数器变量i
  • 初始化空链表L
  • 让空链表的头结点指向NULL,即建立头结点
  • 循环创建结点
  • 头插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
status lCreateLinkListHead(LinkList &L, int n) {
LinkList p;
L = (LinkList) malloc(sizeof(Node));
if(NULL == L) {
return ERROR;
}
L->next = NULL;
for (int j = 0; j < n; ++j) {
p = (LinkList) malloc(sizeof(Node));
if(NULL == p) {
return ERROR;
}
p->e = 0;
//插到表头
p->next = L->next;
L->next = p;
}
return OK;
}
  • 尾插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
status lCreateLinkListTail(LinkList &L, int n) {
LinkList p,r;
L = (LinkList) malloc(sizeof(Node));
if(L == NULL) {
return ERROR;
}
L->next;
r = L; //表尾
for (int i = 0; i < n; ++i) {
p = (LinkList) malloc(sizeof(Node));
if(p == NULL) {
return ERROR;
}
r->next = p;
r = p;
}
r->next = NULL;
return OK;
}

单链表的整体删除

算法思路
  • 声明一个结点p和q
  • 将第一个结点赋值给p
  • 循环
    • 将下一个结点赋值给q
    • 释放q
    • 将q赋值给p
1
2
3
4
5
6
7
8
9
10
11
status lClearLinkList(LinkList &L) {
LinkList p, q;
p = L->next;
while(p) {
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}

比较

储存方式

  • 顺序储存结构用一端连续的储存单元储存元素
  • 单链表用链式储存元素

时间性能

查找
  • 顺序结构:O(1)
  • 链式储存结构O(n)
插入和删除
  • 顺序储存结构需要平均移动毕表长的一半,时间为O(n)
  • 单链表在线出某个位置指针后,插入和删除为O(1)
空间性能
  • 顺序结构需要预分配储存空间,分大了浪费,分小了溢出
  • 单链表可以实时分配空间

静态链表

  • 用数组描述的链表,是为了解决一个语言中没有指针的问题
  • 结构体
1
2
3
4
5
6
7
8
/**
* 用数组实现的静态链表
*/
typedef struct {
ElemType data;
int cur; //游标,为0时表示无指向
int length;
} StaticLinkList[STATIC_MAXSIZE];
  • 通常把未被使用的数组称为备用链表
  • 数组的第一个元素的cur存放备用链表的第一个结点下标
  • 数组最后一个元素的cur存放第一个元素的下标,相当与头结点
  • 初始化:
1
2
3
4
5
6
7
8
status initStaticLinkList(StaticLinkList &L) {
for (int i = 0; i < STATIC_MAXSIZE - 1; ++i) {
L[i].cur = i + 1;
}
L[STATIC_MAXSIZE - 1].cur = 0;
L->length = 0;
return OK;
}

删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
status freeIndex(StaticLinkList &L, int k) {
L[k].cur = L[0].cur; //把第一个元素从cur赋值给要删除的cur分量
L[0].cur = k;
}
status staticDelete(StaticLinkList &L, int i, ElemType e) {
if(i < 1 || i > L->length) {
return ERROR;
}
int k = STATIC_MAXSIZE - 1;
for (int j = 1; j < i - 1; ++j) {
k = L[k].cur;
}
int j;
j = L[k].cur;
L[k].cur = L[j].cur;
freeIndex(L, j);
return OK;
}

插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
status staticInsert(StaticLinkList &L, int i, ElemType e) {
int k = STATIC_MAXSIZE - 1;
if(i < 1 || i > L->length + 1) {
return ERROR;
}
int j = mallocFreeIndex(L);
if(j) {
L[j].data = e;
for (int l = 1; l <= i - 1; ++l) {
k = L[k].cur;
}
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
return ERROR;
}
status mallocFreeIndex(StaticLinkList &L) {
int i = L[0].cur; //当前数组第一个元素的cur值,就是返回第一个备用空闲下表
if(L[0].cur) {
L[0].cur = L[i].cur; //设置下一个空闲下表分量
}
return i;
}

优点

  • 在插入和删除元素时,只需移动修改下标,从而改进顺序储存结构中插入和删除元素需要大量移动元素的缺点

缺点

  • 没有解决难以确定表长的缺点
  • 失去了顺序储存结构中随机存取元素的特性

以上笔记来源《大话数据结构》中
源码

分享到