顺序存储的线性表

ゝ一纸荒年。 2023-07-22 09:08 81阅读 0赞

### 线性表 ###

*   *  简介
     *  存储结构：
     *  操作
     *  \*\*成员函数的实现\*\*

## 简介 ##

**线性表**：n(n>=0)个相同特性的数据元素的有限序列，数据元素之间具有线性关系。  
**线性关系**：除第一个元素外，每个元素有且仅有一个前驱；除最后一个元素外，每个元素有且仅有一个后继。  
**特点**：数据元素之间的关系是它们在数据集合中的相对位置。

## 存储结构： ##

**静态顺序存储：**

#define maxSize 100;
    typedef 数据元素类型 ElemType;
    typedef struct
    {
        
        ElemType data[maxSize];
        int last;
    }SeqList;

**动态顺序存储**

typedef 数据元素类型 ElemType;
    typedef struct{
        
        ElemType *data;
        int maxSize;
        int last;
    }pSeqList;

这种顺序存储结构，无论是静态分配还是动态分配，**存储空间都是一次性得到的、地址连续的**，因此空间的大小是有限制的：maxSize。  
所以空间不够的时候只能申请更大的空间，把原来的数组中的元素复制过来，然后释放原数组。

申请空间的C语言函数：

void *malloc(size_t size)
    void *callo(size_t num,size_t size)
    void *realloc(void *ptr,size_t size)

## 操作 ##

**创建空表**  
静态的

//静态的
    void create(SeqList &l)
    {
        
        l.last = -1;
    }

动态的

void Create(pSeqList &l){
        
        l.last = -1;
        l.data = new ElemType[maxSize];
        if(l.data == NULL){
        
            cerr<<"存储分配错误!"<<Endl;
            exit(1);
        }
    }

**求长度**

int Length(SeqList l)
    {
        
        return (l.last + 1);
    }

**查找**

int Search(SeqList l, ElemType x)
    {
        
        int i=0;
        if(l.last == -1)
        	cout<<"所查询的表为空";
        while(i<=l.last && l.data[i] != x)
            i++;
        if(i>l.last)
            return -1;
        else 
            return i+1;
    }

**顺序存储的线性表的类定义：**

typedef ElemType T;
    class SeqList
    {
        
        T *data;
        int MaxSize;
        int last;
    public:
        SeqList(int sz);
        ~SeqList(){
        
            delete []data;
        }
        int Length() const{
          //返回元素的个数
            return (last + 1); 
        }
        int Search(T &x) const;  //返回元素x在表中的位置
        void Delete(int i, T &x);  //删除值为x的元素
        int IsEmpty(){
          //表空否
            return last == -1;
        }
        int IsFull(){
          //判断是否满
            return last == MaxSize-1;
        }
        T GetData(int i){
          //获得第i个元素
            return data[i-1];
        }
        T GetPrior(T &x);  //取x前驱元素
        T GetNext(T &x);  //取x的后继元素
        void PrintList();  //输出线性表
    };

## **成员函数的实现** ##

**构造函数**

//构造函数,指定sz定义数组的长度
    SeqList::SeqList(int sz)
    {
        
        if(sz>0)
        {
        
            data = new T[sz];  //分配连续空间
            if(data != NULL)
            {
        
                MaxSize = sz;
                last = -1;
            }else{
        
                cerr<<"存储分配错误!"<<endl;
                exit(1);
            }
        }
    }

**查找函数：**  
返回的是从左往右第一个元素值等于x的元素下标

//顺序查找x
    int SeqList::Search(T &x)const
    {
        
        int i = 0;
        if(l.last == -1)
            cout<<"所查询的表为空"<<endl;
        while(i <= last && data[i]!=x)
            i++;
        if(i>last)
            return -1;
        else
            return i+1;
    }

**插入元素**

//插入元素到第i个位置
    void SeqList::Insert(int i, const T &x)
    {
        
        if(last == MaxSize-1)
        {
        
            cerr<<"顺序表已满，无法插入!"<<endl;
            exit(0);
        }
        if(i<0||i>last+1)
        {
        
            cerr<<"参数i越界出错!"<<endl;
            exit(1);
        }
        for(int j=last; j>i; j++){
        
            data[j+1] = data[j];
        }
        data[i] = x;
        last++;
    }

**删除元素**

//删除第i个元素
    void SeqList::Delete(int i){
        
        if(i>=0){
        
            for(int j=i; j<last;j++){
        
                data[j] = data[j+1];
            }
            last--;
            cout<<"成功删除!"<<endl;
        }else
            cerr<<"下标越界!"<<endl;
    }