[数据结构与算法]线性表的顺序实现

一.顺序表

顺序表的概念为，即把线性表的结点按逻辑次序依次的存放到一组地址连续的存续单元里，用这种方法存储的线性表简称为顺序表。顺序表是一种是一种随机存取机构。顺序表与数组的区别为，数组定义后的大小一般不能在改变，但是线性表的表长是可变的，如可以进行插入、删除等操作。

二、顺序表上的基本运算

1.对C/C++语言，顺序表可定义如下：

typedef int datatype;        //线性表结点的数据结构类型，假设为int
const int maxsize=100;       //线性表可能的最大长度，这里假设为100
typedef struct{
  datatype data[maxsize];    //线性表的存储向量，第一个结点是data[0]
  int n;                     //线性表的当前长度
}sqlist;                     //顺序表类型

注:

(1)数据域data是存放线性表各结点的数据空间,下表范围为0~maxsize-1

(2)数据域n记录线性表当前的长度

(3)datatype是线性结点的类型，它应是某种定义过的类型。例如，若线性表是英文字母表，则datatype就是字符类型char

(4)顺序表类型sqlist是一个结构类型，将其当成整体看待，当要访问顺序表的细节时，需要使用成员选择运算符或指针指向运算符。

2.插入运算

顺序表插入的具体算法如下：

int insert (sqlist *L,datatype x,int i){//将x插入到顺序表L的第i个位置上
  int j；
  if(L->n==maxsize)
   {cout<<"表满，不能插入！（上溢）\n"; 
   return -1;}
  if(i<1 || i>L->n+1)               
   {cout<<"非法插入位置！\n";
    return 0；}
  for(j=L->n;j>=i;j--)
     L->data[j]=L->data[j-1];   //将ai~an倒序向后移动
  L->data[i-1]=x;               //插入x，第i个结点的数组下标是i-1
  L->n++;                       //修改表长
  return 1;                     //插入成功
}

3.删除运算

顺序表删除的具体算法如下：

int delete(sqlist *L,int i){
  int j;
  if(L->n==0){
    cout<<"表空，不能删除！(下溢)\n";  
    return -1;}
  if(i<1 || i>L->n) {
    cout<<"非法删除位置！\n";
    return 0;}
  for(j=i+1;j<L->n;j++)
      L->data[j-2]=L->data[j-1];    //结点前移，第j个结点的数组下标为j-1
   L->n--;                          //修改表长
return 1;                           //删除成功
} 

4.定位运算

定位运算LOCATE(L,x)的功能是求表L中第一个值为x的结点序号，当不存在时则返回结果0；

顺序表地位的具体算法如下：

int locate(sqlist *L ,datatype x){
   int i;
   i=1;
   while(1<=L->n && L->data[i-1]!=x)
     i++;
   if(i<=L->n)
     return i;
   else 
     return 0;
}

5.顺序表基础全部代码

#include<iostream>
using namespace std;

typedef int datatype;
const int maxsize = 100;
typedef struct {
    datatype data[maxsize];
    int n;
}sqlist;
sqlist* L = new sqlist();

int initial(sqlist* L, int m) {
    for (int i = 0; i < m; i++) {
        cin >> L->data[i];
        L->n++;
    }
    return 1;
}

int insert(sqlist* L, int i, datatype x) {
    if (i<1 || i>L->n) cout << "非法插入位置!\n";
    if (L->n > maxsize) cout << "表满，无法插入\n";
    for (int c = L->n; c > i - 1; c--) L->data[c] = L->data[c - 1];
    L->data[i - 1] = x;
    L->n++;
    for (int c = 0; c < L->n; c++) {
        if (c < L->n - 1) cout << L->data[c] << " ";
        else cout << L->data[c];
    }
    cout << endl;
    return 1;
}
int deletelist(sqlist* L, int i) {
    if (i<1 || i>L->n) cout << "非法删除位置!\n";
    if (L->n == 0) cout << "表空，无法删除\n";
    for (int c = i - 1; c < L->n - 1; c++) L->data[c] = L->data[c + 1];
    L->n--;
    for (int c = 0; c < L->n; c++) {
        if (c < L->n - 1) cout << L->data[c] << " ";
        else cout << L->data[c];
    }
    cout << endl;
    return 1;
}

int locate(sqlist* L, datatype x) {
    for (int c = 0; c < L->n; c++) {
        if (L->data[c] == x) cout << c + 1;
    }
    cout << endl;
    return 1;
}

int main() {
    L->n = 0;
    int m, i, x, a, b;
    cin >> m;
    initial(L, m);
    cin >> i >> x >> a >> b;
    for (int c = 0; c < L->n; c++) {
        if (c < L->n - 1) cout << L->data[c] << " ";
        else cout << L->data[c];
    }
    cout << endl;
    insert(L, i, x);
    deletelist(L, a);
    locate(L, b);
    return 0;
}