线性表---＞算法总结

1. 逆转顺序表中的所有元素

算法思想 第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，……，依此类推。

void Reverse(int A[], int n)

{
	int i, t;
	for (i=0; i < n/2; i++)
	{
		t = A[i];
		A[i] = A[n-i-1];
		A[n-i-1] = t;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

2. 删除线性链表中数据域为 item 的所有结点。

算法思想 先从链表的第 2 个结点开始，从前往后依次判断链表中的所有结点是否满足条件，若某个结点的数据域为 item，则删除该结点。最后再回过头来判断链表中的第 1 个结点是否满足条件，若满足则将其删除。

void PurgeItem(LinkList &list)
{
	LinkList p, q = list;
	p = list->next;
	while (p != NULL)
	{
		if (p->data == item) {
			q->next = p->next;
			free(p);
			p = q->next;
		} else { 
		q = p;
		p = p->next;
		}
	}
	if (list->data == item)
	{
		q = list;
		list = list->next;
		free(q);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3. 逆转线性链表

void Reverse(LinkList &list)
{
	LinkList p, q, r;
	p = list;
	q = NULL;
	while (p != NULL)
	{
		r = q;
		q = p;
		p = p->next;
		q->next = r;
	}
	list = q;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. 复制线性链表（递归）

LinkList Copy(LinkList lista)
{
	LinkList listb;
	if (lista == NULL)
		return NULL;
	else {
		listb = (LinkList)malloc(sizeof(LNode));
		listb->data = lista->data;
		listb->next = Copy(lista->next);
		return listb;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表

LinkList MergeList(LinkList lista, LinkList listb)
{
	LinkList listc, p = lista, q = listb, r;
	//	listc 指向 lista 和 listb 所指结点中较小者 
	if (lista->data <= listb->data) {
		listc = lista; r = lista;
		p = lista->next; 
	} else {
		listc = listb; r = listb;
		q = listb->next;
	}
	while (p != NULL && q != NULL)
	{
		if (p->data <= q->data) {
			r->next = p;
			r = p;
			p = p->next;
		} else {
			r->next = q;
			r = q;
			q = q->next;
		}
	}
	//	将剩余结点（即未参加比较的且已按升序排列的结点）链接到整个链表后面 
	r->next = (p != NULL) ? p : q;
	return listc;
}
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
26
27