顺序表的实现

 

 

函数接口定义：

顺序表描述的结构体为
typedef struct {ElemType *elem; //存储空间的基地址int length; //当前长度
} SqList;需要实现函数的接口分别为：int GetElem(SqList L, int i, ElemType &e)  顺序表的取值
判断i值是否合理，若不合理，返回0；[i-1]单元存储第i个数据元素; 返回1int LocateElem_Sq(SqList L, double e) 顺序表的查找
查找成功，返回序号i+1；查找失败，返回0int ListInsert_Sq(SqList &L, int i, ElemType e)顺序表的插入
判断i值，不合法返回0；当前存储空间已满，返回0；插入位置及之后的元素后移；将新元素e放入第i个位置；表长增1；返回1int ListDelete_Sq(SqList &L, int i)顺序表的删除
判断i值，不合法返回0；被删除元素之后的元素前移；表长减1；返回1void ListInput(SqList &L)顺序表数据的输入
输入顺序表长度；依次输入数据；表长赋值void ListOutput(SqList L)顺序表数据的输出

裁判测试程序样例：

 

#include<iostream>
#include<string>
#include<iomanip>
#include <cstdlib>
using namespace std;#define OVERFLOW -2typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型#define MAXSIZE 100            //顺序表可能达到的最大长度typedef struct {ElemType *elem; //存储空间的基地址int length; //当前长度
} SqList;void InitList_Sq(SqList &L) { //算法2.1 顺序表的初始化//构造一个空的顺序表LL.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间if (!L.elem)exit(OVERFLOW); //存储分配失败退出L.length = 0; //空表长度为0

}/* 请在这里填写答案 */int main() {SqList L;int i = 0, temp, a, c;double price;ElemType e;//初始化线性表
      InitList_Sq(L);//输入线性表
ListInput(L);//输出线性表
            ListOutput(L);//顺序表取值cin>>i;temp = GetElem(L, i, e);if (temp != 0) {cout <<"查找位置的数是"<<e<< endl;} elsecout << "查找失败！位置超出范围\n";//顺序表查找
cin >> price;temp = LocateElem_Sq(L, price);if (temp != 0) {cout << "该数位置为" << temp << endl;} elsecout << "查找失败！\n";//顺序表的插入
cin >> a;cin >> e; //输入a和e，a代表插入的位置，e代表插入的数值if (ListInsert_Sq(L, a, e))ListOutput(L);elsecout << "插入失败\n";//顺序表的删除
cin >> c;if (ListDelete_Sq(L, c))ListOutput(L);elsecout << "删除失败\n";return 0;
}

 

void ListInput(SqList &L)
{int i=0;cin>>i;for(int j=0; j<i; j++){cin>>L.elem[j];}L.length=i;
}void ListOutput(SqList L)
{for(int j=0; j<L.length; j++){cout<<L.elem[j]<<" ";}cout<<endl;
}int GetElem(SqList L, int i, ElemType &e)
{if(i<1||i>L.length)return 0;e=L.elem[i-1];return 1;
}int LocateElem_Sq(SqList L, double e) 
{for(int j=0; j<L.length; j++){if(L.elem[j]==e)return j+1;}return 0;
}int ListInsert_Sq(SqList &L, int i, ElemType e)
{if(i<1||i>L.length)return 0;if(L.length==MAXSIZE)return 0;for(int j=L.length-1; j>=i-1; j--){L.elem[j+1]=L.elem[j];}L.elem[i-1]=e;L.length++;return 1;
}int ListDelete_Sq(SqList &L, int i)
{if(i<1||i>L.length)return 0;for(int j=i; j< L.length-1; j++){L.elem[j-1]=L.elem[j];}L.length--;return 1;
}