本文共 1999 字，大约阅读时间需要 6 分钟。

顺序表ADT模板及其简单应用算法设计：比较两个顺序表的大小

问题描述

目的：使用STL中的vector模板，设计并实现顺序表应用场合的一些简单算法设计。

应用2：试设计一个算法，实现两个顺序表A、B大小的比较。若 A<B，则返回 -1；若 A=B，则返回 0；若 A>B，则返回 1。

参考函数原型：template

输入说明

第一行：顺序表A的长度

第二行：顺序表A的数据元素（数据元素之间以空格分隔）

第三行：顺序表B的长度

第四行：顺序表B的数据元素（数据元素之间以空格分隔）

输出说明

第一行：比较结果

（输入与输出之间以空行分隔）

输入范例

1013 5 27 9 32 123 76 98 54 87813 5 27 9 32 164 5 8

输出范例

13 5 27 9 32 123 76 98 54 87 13 5 27 9 32 164 5 8 -1

基本思路

• 先求出最长的公共子串
• 然后两个向量分别除去最长公共子串，就剩余的部分开始比较
• 先比较都为空串的情况：防止出现数组越界
• 比较剩余两种的，注意一边为空，一边不为空的特殊的情况

代码实现

#include 
   
    #include 
    
     using namespace std;/*    description:find the longgest common public substring*/template
     
      int commonSubstring(vector
      
        &A,vector
       
         &B){
       int i = 0;    while(i < A.size() && i < B.size())    {
           if(A.at(i) == B.at(i))        {
               i ++;        }        else        {
               return i;        }    }    return i;}/*    description:show all the elements of the vector*/template
        
         void show(vector
         
          & A){ typename std::vector
          
            test = A; typename std::vector
           
            ::iterator iter; for(iter = test.begin();iter != test.end();iter ++) { cout<<*iter<<" "; } cout<
            
              B ,return 1;A
             
              int ListCompare(vector
              
                &A,vector
               
                 &B){ int commonIndex = commonSubstring(A,B); A.erase(A.begin(),A.begin() + commonIndex); B.erase(B.begin(),B.begin() + commonIndex); if(A.size() == 0 && B.size() == 0) { return 0; } if((A.size() == 0 && B.size() != 0) || A.at(0) < B.at(0)) { return -1; } if((A.size() != 0 && B.size() == 0) || A.at(0) > B.at(0)) { return 1; }}int main(){ int Asize; cin>>Asize; vector
                
                  A(Asize); string str; for(int i = 0 ;i < Asize;i ++) { cin>>str; A.at(i) = str; } int Bsize; cin>>Bsize; vector
                 
                   B(Bsize); for(int i = 0 ;i < Bsize;i ++) { cin>>str; B.at(i) = str; } show(A); show(B); cout<
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

问题解决

• RE，输出值不为零，说明两者相等的情况无法通过的。本机如下效果

• 当两个向量，取出最长公共子串的时候，有可能会变为空表，在访问索引为0的字符会出现越界。所以先将这种情况排除，最先判定是否相等

分析与总结

• 注意push_back()是在向量的末尾添加元素，会增加原来的长度，改变长度。如果要赋值的话，只需要进行的根据索引进行修改就可以。

转载地址：http://iwwvb.baihongyu.com/