首页 > 代码库 > C++ 顺序表

C++ 顺序表

C++ 顺序表

/***
1顺序表
1、必做题

  1.  编写程序建立一个数续表,并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。
  2.  编写顺序表定位操作子函数,在顺序表中查找是否存在数据元素x。
      如果存在,返回顺序表中和x值相等的第1个数据元素的序号(序号从0开始编号);
    如果不存在,返回-1。编写主函数测试结果。
  3. 在递增有序的顺序表中插入一个新结点x,保持顺序表的有序性。
    解题思路:首先查找插入的位置,再移位,最后进行插入操作;
    从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置;
    然后将从表尾开始依次将元素后移一个位置直至元素i;最后将新结点x插入到i位置。
  4. 删除顺序表中所有等于X的数据元素。

2、选做题
  已知两个顺序表A和B按元素值递增有序排列,
  要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表
  (允许表中含有值相同的元素)。

***/

//在头文件中"SeqList.h"
/**< writer:FDA_orangebook */
/** \brief: 顺序表
 *
 *  int Length(){return length;}
    //用于获取长度1-N
 *  T Get(int i);
    //用于获取第I个数据
 *  T Locate(T value);
    //用于获取 值为value的位置
 *   void Insert(T value);
    //在递增的顺序中,插入value值
 *   void Insert(int position,T value);
    //在position这个位置,插入value
 *   void Insert(T *_data,int _length);
    //将_data与data以递减的顺序合并
 *   T Delete(int position);
    //将position这个中的元素删除
 *   void PrintList();
    //打印 data 序列
 */

const int MaxSize=100;
#define T int //此处修改 数组的类型
class SeqList
{
public:
    //定义两个构造函数
    SeqList()
    {
        length=0;
    }
    SeqList(T a[],int n);
    ~SeqList() {}
    int Length()
    {
        return length;
    }
    T Get(int i);
    T Locate(T value);
    void Insert(T value);
    void Insert(int position,T value);
    void Insert(T *_data,int _length);
    T Delete(int position);
    void PrintList();
private:
    T data[MaxSize];
    int length;
};
//在SwqList.cpp
#ifndef SEQLIST_H_

#define SEQLIST_H_
#include "SeqList.h"
#include<iostream>
#include<algorithm>
using namespace std;
SeqList::SeqList(T *a,int n)
{
    if(n>MaxSize) cout<<"Parameters of illegal"<<endl;
    for(int i=0; i<n; i++)
        data[i]=a[i];
    length=n;
}

void SeqList::Insert(T value)
{
    int j;
    sort(data,data+length);
    cout<<length<<endl;
    for(j=length; value<=data[j-1]&&j>0; --j)
        data[j]=data[j-1];
    data[j]=value;
    ++length;
    cout<<length<<endl;
}

void SeqList::Insert(int position,int value)
{
    if(length>=MaxSize||position<1||position>length+1)
        cout<<"input error"<<endl;
    for(int j=length; j>=position; --j)
        data[j]=data[j-1];
    data[position-1]=value;
    ++length;
}
bool myfunction (int i,int j)
{
    return (i>j);
}
void SeqList::Insert(T *_data,int _length)
{
    //int j=0;
    sort(data,data+length,myfunction);
    sort(_data,_data+_length,myfunction);
    PrintList();
    int i=0;int j;
    for(; i<_length;++i)
    {
        for( j=0;_data[i]<data[j]&&j<length;++j);
        Insert(j+1,_data[i]);

    }

}


T SeqList::Delete(int position)
{
    if(length==0||position<1||position>length) cout<<"error"<<endl;
    else
    {
        int x=data[position-1];
        for(int j=position; j<length; j++)
            data[j-1]=data[j];
        length--;
        return x;
    }
    return (T)-1;
}

T SeqList::Get(int i)
{
    if(i<1||i>length) cout<<"error"<<endl;;
    return data[i-1];
}

T SeqList::Locate(T value)
{
    for(int i=0; i<length; i++)
        if(data[i]==value) return i+1;
    return -1;
}

void SeqList::PrintList()
{
    cout<<"\n****************************"<<endl;
    for(int i=1; i<=length; i++)
        i%5==0?cout<<data[i-1]<<"\n":cout<<data[i-1]<<"\t";
};
#endif // SwqList_H_
#include"SeqList.h"
#include<iostream>
#include<stdlib.h>

using namespace std;
#define MAX 100

int main()
{
    T a[10]= {0,1,2,13,4,5,6,7,8,9};
    T bb[7]= {11,12,3,10,9,16,14};
    SeqList test(a,9);

    test.PrintList();


    if(test.Locate(a[10])!=-1)
          cout<<test.Locate(a[7])<<endl;
    test.Insert(-25);
    test.PrintList();

    test.Delete(test.Locate(-25));
    test.PrintList();

    test.Insert(bb,7);
    test.PrintList();
}