4-12 DSA

问题集

  • 顺序表排列
  • 线性表删除结点

问题1

已知顺序表中各结点有正有负 设计算法满足
使负值结点位于顺序表前面
正值位于顺序表后面

解决

采用两端向中间交替扫描的算法 「也适用排序,结点逆置」
本代码段时间复杂度T(n) = O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int x; //中间变量
int i = 0;
int j = L->n-1;
while (i < j) {
while (i < j && L->data[i] < 0) i++;
while (i < j && L->data[j] > 0) j--;
if (i < j) {
x = L->data[i];
L->data[i] = L->data[j];
L->data[j] = x;
i++;
j--;
}
}

问题2

顺序表中含有若干零值结点 设计算法满足
删除零值结点且不改变其他结点的相对位置

解决

采用单向扫描 但不立即删除零元值结点
声明一个累计零元数的变量

当扫描到零元值 变量自增
当扫描到非零元值 当前结点向前移变量值个位置

最后修改表长
本代码段时间复杂度T(n) = O(n)

1
2
3
4
5
6
7
8
9
10
void delZero (sqlist *L)
{
int s = 0; // 累计的零元数
for (int i = 0; i < L->n; i++)
{
if (L->data[i] == 0) s++;
if (s > 0) L->data[i-s] = L->data[i]; //非零元前移
}
L->n = L->n-s; //修改表长
}
# DSA

Comments

Your browser is out-of-date!

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

×