时间戳

首页 > 技术文章 > 线性表学习之顺序表示

线性表学习之顺序表示

tracylining 2013-10-29 19:28 原文

原创博文，转载请注明出处

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。接下来我们学习：

第一部分：线性表的顺序表示

顺序表最主要的特点是可以进行随机存取，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。顺序表的存储密度高，每个节点只存储数据元素，但是插入和删除需要移动大量元素。

插入、删除、查找的时间复杂度为O(n)

综合应用 ： 

           1、设计一个高效算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1).

           算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i](0<=i<=L.length/2),将其余后半部分对应元素L.data[L.length-i-1]进行交换。

1  void Reverse(Sqlist &L){
2         Elemtype temp;
3         for(i=0;i<L.length/2;i++){
4              temp=L.data[i];
5              L.data[i]=L.data[L.length-i-1];
6               L.data[L.length-i-1]=temp;
7         }
8  }
View Code

 

           2、长度为n的顺序表L，编写一个时间复杂度为O(n),空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

           解法一：用K记录顺序表L中不等于x的元素个数（即需要保存的元素个数），边扫描L边统计k，并将不等于x的元素向前放置k位置上，最后修改L的长度。

1 void del_x(Sqlist &L,Elemtype x){
2        int k=0;
3        for(i=0;i<L.length;i++)
4             if(L.data[i]!=x){
5                L.data[k]=L.data[i];
6                k++;
7            }      
8       L.length=k;
9 }
View Code

          解法二： 用K记录顺序表中等于x的元素个数，边扫描L边统计k，并将不等于x的元素前移k个位置，最后修改L的长度。

          3、从有序 顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，如果s或t不合理或者顺序表为空则显示出错信息并推出运行.

          算法思想：先寻找值大于等于s的第一个元素（第一个删除的元素），然后寻找值>t的第一个元素（最后一个删除的元素的下一个元素），要将这段元素删除，则只需要直接将后面的元素前移即可。实现如下： 

 1 bool Del_s_t(sqList &L,ElemType s,ElemType t){
 2         int i,j;
 3         if(s<=t)||L.length==0
 4             return false;
 5         for(i=0;i<L.length&&L.data[i]<s;i++);
 6         if(i>L.length)
 7              return false;
 8         for(j=0;j<L.length&&L.data[j]<=t;j++);
 9         for(;j<L.length;i++,j++)
10             L.data[i]=L.data[j];
11         L.length=i;
12         return true;
13 }
View Code

            那如果不是有序的怎么办呢？很简单，我们从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置，替代原值，否则执行k++。由于这样每个不在s到t之间的元素仅移动一次，所以算法效率高。

          4、从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

             算法思想：由于是有序表，所以值相同的元素一定在连续的位置上，判断后面的元素是否与前面的非重复有序表最后一个元素相同，如果相同则继续向后判断，如果不同则插入到前面的非重复有序表的最后 ，直到判断整个表尾为止。实现如下：

1 bool Delete_Same(SeqList L){
2         if (L.length==0)
3               return false;
4         int i,j;
5         for(i=0,j=1;j<L.length;j++)
6             if(L.data[i]<L.data[j])
7                  L.data[++i]=L,data[j]
8         L.length=i+1;
9 }
View Code

         5、将两个有序顺序表合并成一个新的有序顺序表，并有函数返回结果顺序表

             算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

 1 bool Merge(SeqList A, SeqList B ,SeqList &C){
 2         if(A.length+B.length>C.maxSize)
 3                return false;
 4         int i=0,j=0,k=0;
 5         while(i<A.length&&j<B.length){
 6                 if(A.data[i]<=B.data[j])
 7                       C.data[k++]=A.data[i];
 8                 else
 9                       C.data[k++]=B.data[j];
10         }
11         while(i<A.length)
12               C.data[k++]=A.data[i++];
13         while(j<B.length)
14               C.data[k++]=B.data[j++];
15         C.length=k;
16         return true;
17 }
View Code

         6、线性表(a1,a2,a3,...,an)中元素递增有序且按顺序存储在计算机内。要求设计一算法完成用最少时间在表中查找数值为x的元素，若找到将其与后继元素位置交换，若找不到将其插入表中并使表中元素仍递增有序。

         算法思想：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求用最少时间，应用折半查找法。

 1 void Search(ElemType A[],ElemType x){
 2         int low=0,high=n-1;
 3         while(low<high){
 4                 mid=(low+high)/2;
 5                 if(A[mid]==x)break;
 6                 else if (A[mid]<x)low=mid+1;
 7                 else high=mid-1;
 8      }
 9      if(A[mid]==x&&mid!=n-1){
10           t=A[mid];A[mid]=A[mid+1];A[mid+1]=t;
11      }
12     if(low>high){
13             for(i=n-1;i>high;i--)A[i+1]=A[i];
14             A[i+1]=x;
15     }
16 }
View Code

       7、设将n(n>1)个整数存放到一堆数组R中。试设计一个在时间和空间两方面都尽可能高校的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(X0,X1,...,Xn-1)变换为(Xp,Xp+1,...,Xn-1,X0,X1,...,Xp-1)。

           算法思想：可以将这个问题看作是吧数组ab转换成ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a-1b，再将b逆置得到a-1b-1，最后将整个逆置得到

（a-1b-1）-1=ba。设Reverse函数执行将数组元素逆置的操作。两个参数分别表示数组中待转换元素的始末位置。实现如下：

 1 void Reverse(int R[ ], int from, int to){
 2        int i,temp;
 3        for(i=0;i<(to-from+1)/2;i++){
 4             temp=R[from+i];R[from+i]=R[to-i];R[to-i]=temp;
 5        }
 6 }
 7 
 8 void main(int R[ ], int n,int p){
 9         Reverse(R,0,p);
10         Reverse(R,p,n-1);
11         Reverse(0,n-1);
12 }
View Code

         上述算法中，三个Reverse函数的时间复杂度分别为O(p/2),O((n-p)/2),O(n/2),故所设计的算法时间复杂度为O(n),空间复杂度为O(1)。

     8、一个长度为L的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=（11，13，15，17，19），则S1 的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2，4，6，8，20），则S1和S2的中位数是11.现在有两个等长的升序序列A和B，设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

         算法思想：一开始我用了快速排序将两个序列进行合并排序（与第5题类似）。后来看了答案，才知道另一种更高效的算法。

                      分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下： 

                      1. 若a=b，则a或b即为所求中位数，算法结束

                      2. 若a<b,则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。

                      2. 若a>b,则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。

                     在保留的两个升序序列中，重复过程1，2，3，直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。

       实现如下： 算法的时间复杂度为O(log2n),空间复杂度为O(1).

 1 int M_Search(int A[ ],int B[ ],int n){
 2     int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
 3     while(s1!=d1&&s2!=d2){
 4          m1=(s1+d1)/2;
 5          m2=(s2+d2)/2;
 6          if(A[m1]=B[m2])
 7             return A[m1]
 8          if(A[m1]<B[m2]){
 9               if ((s1+d1)/2==0){
10                     s1=m1;
11                     d2=m2;
12                }
13               else{
14                     s1=m1+1;
15                     d2=m2;
16               }
17          }
18        else{
19             if((s1+d1)/2==0){
20                          d1=m1; 
21                          s2=m2;
22            }
23            else{
24                          d1=m1;
25                          s2=m2+1; 
26             }
27        }
28    }
29   return A[s1]<B[s2]?A[s1]:B[s2];
30 }
View Code

 

推荐阅读