顺序表：数组

太过爱你忘了你带给我的痛 2022-11-25 10:12 142阅读 0赞

### 数组 ###

实际应用中以表的形式出现，数组中的元素是同一类型的。  
一维数组又称向量，二维数组又称矩阵。  
多维数组通过行优先或列优先描述，可以映射为一维数组。

##### 在数组中第i个位置插入值为x的新元素 #####

template <class T>
    boolean Array<T>::Insert(T&x,int i)
    { 
        //在数组中第i个位置插入值为x的新元素
        //若插入成功，则返回TRUE,否则返回FALSE
        if(ArrayLength==ArraySize)  //数组存储空间已满 
        { 
      	cerr<<"overflow"<<endl;
      	return FALSE;
         } 
        else if(i<0||i>ArrayLength)  //插入位置错 
        { 
      	cerr<<"position error"<<endl;
      	return FALSE;
        } 
        else
        { 
      	for(int j=ArrayLength-1;j>=i;j--)
      	{ 
                array[j+1]=array[j]; //后移 
                array[i]=x;    	 //插入 
                ArrayLength++;   	 //数组长度增1 
                return TRUE;
            }
        } 
    }

##### 删除数组中的第i个元素 #####

template <class T>
    boolean Array<T>::Remove(int i)
    { 
         //删除第i个元素，若删除成功，则返回TRUE,否则返回FALSE
         if(ArrayLength==0)  
         { 
     	 cerr<<"Array is empty"<<endl;
     	 return FALSE;
         }
         //空向量
         else if(i<0||i>ArrayLength-1)
         { 
    	 cerr<<"position error"<<endl;
    	 return FALSE;
         }
         //删除位置错
         else
         { 
     	 for(int j=i;j<ArrayLength-1;j++) //前移 
     	 { 
                   array[j]=array[j+1];
     	 }
     	 ArrayLength--;      		  //数组长度减1 
     	 return TRUE; 
         }
    }

### 数组的应用 ###

##### 集合的并运算（将两个数组合并为一个数组） #####

template <class T>
    void Union(Array<T> &Va,Array<T> &Vb)
    { 
        //把数组Vb合并到Va中，重复元素只留一个
        int n=Va.GetLength();
        int m=Vb.GetLength();
        for(int i=0;i<m;i++)
        { 
            T x=Vb.Getnode(i)	//从Vb中取一元素
            int k=Va.Find(x);	//在Va中查找同值元素
            if(k==-1)		//若找不到同值元素
            { 
                Va.Insert(x,n);	//则插入到Va的最后
                n++;
            }
        }
    }

##### 集合的交运算 #####

template <class T>
    void Intersection(Array<T> &Va,Array<T> &Vb)
    { 
        //求Va和Vb中的相同元素，存入Vb
        int n=Va.GetLength();
        int m=Vb.GetLength();
        int i=0;
        while(i<m)
        { 
            T x=Vb.Getnode(i) //从Vb中取一元素
            int k=Va.Find(x); //在Va中查找同值元素
            if(k==-1)	  //若找不到等值元素
            { 
                Vb.Remove(i); //则从Vb中删去该元素
                m--;
            }
            else		  //否则，在Vb中保留该元素
            { 
                i++;
            }
        }
    }

##### 约瑟夫问题 #####

设n个人围成一个圆圈，按一指定方向，从第s个人开始报数，报数到m为止，报数为m的人出列，然后从下一个人开始重新报数，报数为m的人又出列…，直到所有的人全部出列为止。Josephus问题要对任意给定的n,s和m,求按出列次序得到的人员顺序表。  
**分析**  
依初始位置，顺序地给这n个人每个人一个编号（可以是数字的，也可以是符号的）。Josephus问题就是要按报数出列的方法将人员序编号重新排列。将这n个人存入一个数组P中，，某个人出列即把对应的数组元素从数组中删除。每删去一个数组元素后就将后面的所有元素前移，同时把这个删去的元素插到数组最后的位置上，然后对前n-1个数组元素重复上述过程。  
当数组P中所有的元素都删去一次后，数组P中存放的就是报数出列的人员顺序。

//模拟Josephus问题求解
    void Josephus(Array<int>&P,int n;int s;int m)
    { 
        //将人员编号存入数组P中
        int k=1;
        for(int i=0;i<n;i++)
        { 
      	P.Insert(k,i);
      	k++;
        } 
        int s1=s;
        for(int j=n;j>=1;j--)
        { 
      	s1=(s1+m-1)%j;
      	if(s1==0)
      	{ 
                s1=j;
      	} 
      	int w=P.Getnode(s1-1);
      	P.Remove(s1-1);
      	P.Insert(w,n-1);
        }
    }