首页 > 编程语言 > 详细

顺序表算法设计笔记

时间:2017-06-24 23:24:59      阅读:386      评论:0      收藏:0      [点我收藏+]

1、已知长度为 n 的线性表 A 采用顺序存储结构。设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为 x 的元素数据元素。

以下两种方法都不满足要求:

  • 如果删除一个值为 x 的元素都进行移动, 其时间复杂度为O(n^2),时间复杂度为O(1).
  • 如果借助一个新的顺序表, 存放将A中所有不为x的元素,其时间复杂度O(n), 空间复杂度为O(n)。

解法一:设删除 A 中所有值等于 x 元素后的顺序表为A1, 显然A1包含在 A 中, 为此A1重用 A 的空间。

思路:扫描顺序表 A,重建 A 只包含不等于 x 的元素, 代码如下:

 1 #include <stdio.h>
 2 
 3 // 线性表
 4 typedef struct {
 5     int arr[10];
 6     int length;
 7 } seq_list;
 8 
 9 void delnodel(seq_list* list, int x)
10 {
11     int k = 0;
12     int i;
13     for (i=0; i<list->length; i++){
14         if (list->arr[i] != x){
15             list->arr[k] = list->arr[i];
16             k++;
17         }
18     }
19 }

解法二: 用 k 记录顺序表 A 中遍历过元素中等于 x 的元素个数。

思路:将不为 x 的元素前移 k 个位置, 最后修改 A 的长度, 代码如下:

 1 #include <stdio.h>
 2 
 3 // 线性表
 4 typedef struct {
 5     int arr[10];
 6     int length;
 7 } seq_list;
 8 
 9 void delnode2(seq_list* list, int x)
10 {
11     // 记录以遍历的 x 的个数
12     int k = 0;
13     int i = 0;
14     while (i < list->length){
15         if (list->arr[i] == x){
16             k++;
17         } else {
18             list->arr[i-k] = list->arr[i];  // 移动 k 个位置
19         }
20         i++;
21     }
22     list->length -= k;      // 更新长度
23 }

 

上面的两个解法本质上是干的事情是一样的, 将元素移动 n 个位置覆盖掉不等于x的元素,两个算法中 n 是相等的,一个通过记录不等于x的元素个数知道n;一个通过记录等于x的元素个数知道n;等于x的 + 不等于x的 = 长度;

 

顺序表算法设计笔记

原文:http://www.cnblogs.com/tingshuo123/p/7074767.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!