数据结构之算法设计题专攻_数据结构算法设计题怎么练

---

据可靠情报，算法设计题主要集中：

2 ， 3 ， 7 ， 8 章节

---

---

分别是

• 第2章 线性表

• 第3章 栈和队列

• 第7章 查找

• 第8章 排序

---

主要

前插法后插法创建单链表，合并有个有序链表

线性表课后习题算法设计题1，7

链栈的入栈和出栈

链队

折半查找

冒泡排序

快速排序

堆排序

---

前插法后插法创建单链表，合并有个有序链表

代码描述：

void CreateList_H(LinkList& L, int n)
{
	L = new Lnode;
	L->next = NULL;
	for (int i = 0; i < n; ++i) {
		p = new Lnode;
		cin >> p->data;
		p->next = L->next;
		L->next = p;
	}
}

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

---

算法时间复杂度为 O（n）。

void CreateList_R(LinkList& L, int n) {
	L = new Lnode;
	L->next = NULL;
	r = L;
	for (i = 0; i < n; ++i) {
		p = new Lnode;
		cin >> p->data;
		p->next = null;
		r->next = p;
		r = p;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

算法时间复杂度为 O（n）。

---

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc)
{
   
	pa = La->next;  pb = Lb->next;
	
	Lc = pc = La;  //用La的头结点作为Lc的头结点
	while (pa && pb)
	{
   
		if (pa->data < pb->data) {
    pc->next = pa; pc = pa; pa = pa->next; }
		//取较小者La中的元素，将pa链接在pc的后面，pa指针后移
		else if (pa->data > pb->data) {
    pc->next = pb; pc = pb; pb = pb->next; }
		//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
		else //相等时取La中的元素，删除Lb中的元素
		{
   
			pc->next = pa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18