顺序表和链表
顺序表
线性表的顺序表示简称顺序表，逻辑上相邻的两个元素在物理位置上也相邻。
1
2
3
4
5
| #define MAxSzie 50
typedef struct {
ElemType data[MAxSzie];
int len;
}SqList;
|
优点：
- 可以随机存取（根据表头元素地址和元素序号）表中的任意一个元素。
- 存储密度高，每个结点指存储数据元素
缺点：
- 插入和删除操作需要移动大量元素（时间复杂度平均O(n)）
- 线性表变化较大时，难以确定存储空间的容量
- 存储分配需要一整段连续的存储空间，不够灵活
增
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool ListInsert(SqList &L, int i, ElemType element) {
if (i >= 1 && i <= L.length + 1) {
if (L.length == MaxSize)
return false;
for (int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = element;
L.length++;
return true;
}
return false;
}
|
删
1
2
3
4
5
6
7
8
9
10
| bool ListDelete(SqList &L, int i, ElemType &del) {
if (i > L.length || i <= 0)
return false;
del = L.data[i - 1];
for (int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j];
}
L.length--;
return true;
}
|
查
1
2
3
4
5
6
7
8
| int LocateElem(SqList L,ElemType i)
{
for(int j =0;j<L.length;j++){
if(L.data[j] == i)
return j+1;
}
return -1;
}
|
链表
线性表的链式表示简称链表，逻辑上相邻的两个元素在物理位置上不相邻。
1
2
3
4
| typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
|
头指针：链表中的第一个结点的存储位置，用来标识单链表。
头结点：在单链表第一个结点之前附加的一个结点，为了操作上方便。
若链表有头结点，则头指针永远指向头结点，不论链表是否为空，头指针均不为空，头指针是链表的必需元素，它标识一个链表。头结点是为了操作方便而设立的，其数据域一般为空，或者存放链表的长度。有头结点后，对在第一结点前插入和删除第一结点的操作就统一了，不需要频繁重置头指针。但头结点不是必须的。
优点：
- 插入和删除操作不需要移动元素，只需要修改指针。
- 不需要大量的连续空间。
缺点：
- 单链表附加指针域，浪费存储空间。
- 查找操作需要从表头遍历，依次查找，不能随机存取。
头插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
void ListHeadInsert(LinkList &L) {
L = (LNode *) malloc(sizeof(LNode));
L->next = NULL;
ElemType x;
scanf("%d", &x);
LinkList s;
while (x != 9999) {
s = (LNode *) malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
}
int main() {
LinkList L;
ListHeadInsert(L);
return 0;
}
|
尾插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void ListTailInsert(LinkList &L) {
L = (LNode *) malloc(sizeof(LNode));
L->next = NULL;
ElemType x;
scanf("%d", &x);
LinkList s,r=L;
while (x != 9999) {
s = (LNode *) malloc(sizeof(LNode));
s->data = x;
r->next = s;
r=s;
scanf("%d", &x);
}
s->next=NULL;
}
|
按位置查询
1
2
3
4
5
6
7
8
9
10
| LinkList Select(LinkList L, int x) {
int i;
if (x < 0)
return NULL;
while (L && i < x) {
L = L->next;
i++;
}
return L;
}
|
按位置插入
1
2
3
4
5
6
7
8
9
10
11
12
| bool InsertI(LinkList L, int i, int v) {
LinkList p = Select(L, i - 1);
if (NULL == p) {
return false;
}
LinkList q;
q = (LinkList) malloc(sizeof(LNode));
q->data = v;
q->next = p->next;
p->next = q;
return true;
}
|
按位置删除
1
2
3
4
5
6
7
8
9
10
11
| bool ListDelete(LinkList L, ElemType pos) {
LinkList p = Select(L, pos - 1);
if (NULL == p)
return false;
LinkList q = p->next;
if (NULL == q)
return false;
p->next = q->next;
free(q);
return true;
}
|
中间分离链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void FindMiddle(LinkList L, LinkList &L2) {
L2 = (LinkList) malloc(sizeof(LNode));
LinkList pcur, ppre;
ppre = pcur = L->next;
while (pcur) {
pcur = pcur->next;
if (NULL == pcur) {
break;
}
pcur = pcur->next;
if (NULL == pcur) {
break;
}
ppre = ppre->next;
}
L2->next = ppre->next;
ppre->next = NULL;
}
|
翻转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void Reverse(LinkList L2) {
LinkList r, s, t;
r = L2->next;
if (NULL == r) {
return;
}
s = r->next;
if (NULL == s) {
return;
}
t = s->next;
while (t) {
s->next = r;
r = s;
s = t;
t = t->next;
}
s->next = r;
L2->next->next = NULL;
L2->next = s;
}
|
合并链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void Merge(LinkList L, LinkList L2) {
LinkList pcur, p, q;
pcur = L->next;
p = pcur->next;
q = L2->next;
while (p != NULL && q != NULL){
pcur->next = q;
q=q->next;
pcur=pcur->next;
pcur->next=p;
p=p->next;
pcur=pcur->next;
}
if(p!=NULL){
pcur->next=p;
}
if(q!=NULL){
pcur->next=q;
}
}
|
