4-22 DSA

问题集

  • 线性表连接
  • 判断单链表中是否有环以及计算环的长度
  • 静态链表的空游标不能使用NULL
  • 删除线性表某个范围内的结点

问题1

实现将两个线性表A(a1,a2,…,an)和B(b1,b2,…,bm)连接成一个线性表(a1,…,an,b1,…,bm)的运算?

解决

  • 若在单链表或头指针表示的单循环链表上做这种链接操作 都需要遍历第一个链表 找到结点an 然后将结点b1链到an的后面 其执行时间是O(n)
  • 若在尾指针表示的单循环链表上实现 则只需要修改指针 无须遍历 其执行时间是O(1)

因为单链表和单循环链表的操作只是多了一个遍历过程 连接操作类似
故练习了尾指针表示的单循环链表上实现的例子

图解

WechatIMG1.jpeg

代码实现

1
2
3
4
5
6
7
8
9
// 假设A,B是两个非空循环链表的尾指针
lklist connectList (pointer A, pointer B)
{
pointer c = A->next; // 临时变量 保存A头结点
A->next = B->next->next; // 将B表首结点链接至A表尾结点
free(B->next); // 释放B表头结点
B->next = c; // 将B表尾结点循环链接至A表头结点
return B;
}

问题2

判断单链表中是否有环
「有环的定义:链表的尾结点指向了链表中的某个结点」

解决

  • 比较步数法:p, q两个指针 q总是往前走「继承上一次的位置」 p总是从头开始往后走 对比每个结点 p, q走的结点位置个数是否相同 若不相同 则表示存在环
  • 快慢指针法:p, q两个指针 p每次走一个结点位置 q每次走两个结点位置 若存在p == q 则表示存在环 「推荐」
  • 数组法:定义一个指针数组 初始化为空指针 从链表的头指针开始往后遍历 若当前指针存在于指针数组 则表示存在环 否则添加进指针数组 「不推荐 T(n)和S(n)都不是最优解」
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 比较步数法
int hasLoop (LinkList L)
{
pointer p = L;
int p_step = 0; // 定义p走的步数
while (p)
{
pointer q = L;
int q_step = 0// 定义q走的步数
while (q)
{
if (p == q)
{
if (p_step == q_step) break; // 走过的步数一致 不存在环
else return 1; //存在环
}
q = q->next; // 如果没有发现环 继续下一个结点
q_step++;
}
p = p->next; // p继续下一个结点
p_step++;
}
}

// 利用快慢指针的方法
int HasLoop (LinkList L)
{
pointer p = L;
pointer q = L;
// p!=NULL && q!=NULL 判断链表是否为空
// q比p走得快 因此判断指针是否到链表末尾 只需要判断q->next
// 若q->next为空 则链表不存在环
while(p!=NULL && q!=NULL && q->next!=NULL){
p = p->next; // p每次走一个结点位置
if(q->next != NULL){
q = q->next->next; // q每次走两个结点位置
}
if(p == q){
return 1; // 存在环
}
}
return 0;
}

问题2拓展

求环的长度

解决

  • 求出的环入口 再走一圈就可以求出长度
  • 当快慢指针相遇时 继续移动直到第二次相遇 此时快指针移动的距离正好比慢指针多一圈

问题3

静态链表的空游标「指针」为什么不能使用NULL表示

解决

从 C++ 定义NULL角度解释
https://www.jianshu.com/p/4c8390d2dfdd

C/C++中 NULL指向的地址为0
而静态链表可看作是数组实现的链表
数组中存在0的下标

  • 将数组的0号单元视为空不用 从而继续使用NULL表示空指针
  • 空指针用另一符号 NIL 表示 并将其定义为-1

问题4

设计算法 删除顺序表中值大于x且小于y的结点「若存在这样的结点」

  • 顺序表无序
  • 顺序表递增有序
  • 顺序表改为单链表呢?

解决

  • 顺序表无序
1
2
3
4
5
6
7
8
9
10
void deleteNode (sqlist *L, datatype x, datatype y)
{
int i, s; // i为循环次数元 s为累加计数元
s = 0;
for (i = 0; i < L->n; i++) {
if (L->data[i] > x && L->data[i] < y) s++; // 累计待删结点个数
else if (s > 0) L->data[i-s] = L->data[i]; // 不满足的当前结点向前移s个位置
}
L->n = L->n-s; //调整表长
}
  • 顺序表递增有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void deleteNode (sqlist *L, datatype x, datatype y)
{
int i, s; // i为循环次数元 s为累加计数元
s = 0;
for (i = 0; i < L->n; i++)
if (L->data[i] > x) break;
for (; i < L->n; i++) { // i 继承上面for循环后的次数
if (L->data[i] < y) s++;
else break;
}
if (s == 0) return;
for (; i < L->n; i++)
L->data[i-s] = L->data[i];
L->n = L->n-s;
}
  • 单链表实现
1
2
3
4
void deleteNode (sqlist *L, datatype x, datatype y)
{
// 待补充
}
# DSA

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×