数据结构 线性表 顺序存储结构

数据结构

本文主要讲解线性表顺序存储结构的实现

顺序表概念：

线性表的顺序存储结构指的是用一组地址连续的存储单元依次存储数据元素。

线性表的顺序存储结构示意

假设线性表的每个元素需要占l个存储单元。

存在以下关系

LOC(a_i+1) = LOC(a_i)

LOC(a_i) = LOC(a₁) + (i-1) * l

存储地址	内存状态	线性表中位置
b	a1	1
b+l	a2	2
......	......	......
b+(i-1)l	ai	i
......	......	......
b+(n-1)l	an	n
b+nl
......
b+(maxsize-1)

顺序表的主要运算(以图书信息为例)

1. 初始化顺序表(时间复杂度O(1))

   Status InitList(SqList &L)
   {
     L.book = new Book[maxsize]; //动态分配内存空间
     if(L.book == NULL)
         return OVERFLOW;       //溢出
     L.length = 0;              //元素个数为0  
         return OK; 
   }
   

2. 插入元素(平均时间复杂度O(n))

Status ListInsert(SqList &L,int pos,Book e)
{
    if(pos < 1 || pos > L.length+1)  //插入数据范围1 <= i <= L.length
        return ERROR;
    if(L.length == maxsize)  //数据存满了
        return ERROR;

    for(int j = L.length-1; j >= pos-1; j--)
            L.book[j+1] = L.book[j];  //每个元素等于前一个元素

    L.book[pos-1] = e;
    ++L.length;  //长度+1
    return OK;
}

3. 删除元素(时间复杂度和插入算法一致O(n))

Status ListDelete(SqList &L,int pos)
{
    if(pos < 1 || pos > L.length)  //1<= i <= L.length
        return ERROR;
    
    for(int j = pos; j <= L.length-1; j++)
        L.book[j-1] = L.book[j];
    
    --L.length;  //元素个数-1
    return OK;
}

4. 查找元素(时间复杂度(O(n)))

Status LocateElem(SqList &L,Book e)
{
    for(i = 0; i < L.length; i++)  //遍历所有元素
        if(strcmp(L.book[i].isbn,e.isbn) == 0 && strcmp(L.book[i].book,e.book) == 0 && L.book[i].price == e.price)  //如果找到目标数据元素
            return i+1; //返回元素所在顺序表位置
    return ERROR;
}

5. 取值

Status GetElem(SqList &L,int pos)
{
    if(pos >= 1 && pos <= L.length)  //判断位置是否在范围内
    {
        e = L.book[pos-1];  //赋值
            return OK;
    }
    return ERROR;
}

6. 遍历顺序表

Status TravelElem(SqList &L)
{
    if(!EmptyList(L))
    {
        for(i = 0; i < L.length; i++)  //遍历所有元素
            printf("%s %s %lf\n",L.book[i].isbn,L.book[i].book,L.book[i].price);  //打印输出
        return OK;
    }
    else
        return ERROR;
}

7. 顺序表是否为空

Status EmptyList(SqList &L)
{
    if(L.book == NULL)  //判断是否为空
        return OK;  //为空返回OK
    return ERROR;  //否则返回ERROR
}

8. 清空顺序表

Status ClearList(SqList &L)
{
    L.length = 0;  //把顺序表L长度设为0
    return OK;
}

9. 销毁顺序表

Status DestroyList(SqList &L)
{
    free(L.book);  //释放内存
    L.book = NULL;
    L.length = 0;
    return OK;
}

---

|插入前|a₁|a₂|a₃|......|a_i|a_i+1|......|a_n|
|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|
|插入后|a₁|a₂|a₃|......|a_i+1|a_i+1|......|a_n+1|

|删除前|a₁|a₂|a₃|......|a_i|a_i+1|......|a_n|
|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|
|删除后|a₁|a₂|a₃|......|a_i+1|a_i+2|......|a_n|

---

查找算法分析：查找每个数据元素的概率均等为1/n，在查找到目标数据元素时已经和i个元素进行比较，则平均查找长度如下，得出时间复杂度为O(n)

平均查找长度

插入算法分析：在一个长度为n的线性表里面插入数据元素，插入概率均等为1/(n+1)，插入算法时间主要花费在插入数据元素后的移动(n-i+1)个数据元素上，则时间复杂度为O(n)

插入算法平均时间复杂度

删除算法分析：在一个长度为n的线性表里面删除数据元素，删除概率均等为1/n，删除算法时间主要花费在插入数据元素后的移动n - i个数据元素上，则时间复杂度为O(n)

删除算法平均时间复杂度

---

C++ 完整代码代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define maxsize 10010
#define OK 1
#define OVERFLOW -1
#define ERROR 0
typedef int Status;

int n;
int S;
int i;



typedef struct Book  //定义结构体Book
{
    char isbn[20];  //isbn号
    char book[20];  //书的名字
    double price;  //书的价格
}Book;

typedef struct SqList  //定义顺序表结构体SqList
{
    Book *book;   //Book类型成员
    int length;  //顺序表当前长度
}SqList;

Book e;

SqList L;

Status InitList(SqList &L)  //初始化顺序表L
{
    L.book = new Book[maxsize];  //动态分配空间
    if(L.book == NULL)
        return OVERFLOW;  //溢出
    L.length = 0;
        return OK; 
}

void IniteListInsert(SqList &L)  //用于初始化顺序表内数据
{
    for(i = 0; i < L.length; i++)
        scanf("%s %s %lf",L.book[i].isbn,L.book[i].book,&L.book[i].price);
}

Status ListInsert(SqList &L,int pos,Book e)  //顺序表插入数据
{
    if(pos < 1 || pos > L.length+1)  //1 <= i <= L.length
        return ERROR;        
    if(L.length == maxsize)  //L.length达到最大长度
        return ERROR;

    for(int j = L.length-1; j >= pos-1; j--)
            L.book[j+1] = L.book[j];

    L.book[pos-1] = e;
    ++L.length;  //自增
    return OK;
}

Status ListDelete(SqList &L,int pos)  //删除顺序表元素
{
    if(pos < 1 || pos > L.length)  //1 <= i <= L.length
        return ERROR;
    
    for(int j = pos; j <= L.length-1; j++)
        L.book[j-1] = L.book[j];
    
    --L.length;  //自减
    return OK;
}

Status LocateElem(SqList &L,Book e)  //返回元素所在顺序表中的位置
{
    for(i = 0; i < L.length; i++)
        if(strcmp(L.book[i].isbn,e.isbn) == 0 && strcmp(L.book[i].book,e.book) == 0 && L.book[i].price == e.price)  //如果找到
            return i+1;  //返回元素所在顺序表的位置
    return ERROR;
}

Status GetElem(SqList &L,int pos)  //顺序表取值
{
    if(pos >= 1 && pos <= L.length)  //判断位置是否在范围内
    {
        e = L.book[pos-1];  //赋值
            return OK;
    }
    return ERROR;
}


Status DestroyList(SqList &L)  //销毁顺序表
{
    free(L.book);  //释放内存
    L.book = NULL;
    L.length = 0;  //长度设置为0
    return OK;
}

Status ClearList(SqList &L)  //清空顺序表  
{
    L.length = 0;
    return OK;
}

Status EmptyList(SqList &L)  //判断顺序表是否为空
{
    if(L.book == NULL)  //如果为空则返回OK
        return OK;
    return ERROR;  //反之返回ERROR
}

Status TravelElem(SqList &L)  //遍历顺序表所有元素
{
    if(!EmptyList(L))  //先判断是否为空
    {
        for(i = 0; i < L.length; i++)
            printf("%s %s %lf\n",L.book[i].isbn,L.book[i].book,L.book[i].price);
        return OK;
    }
    else
        return ERROR;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        S = InitList(L);
        L.length = n;
        IniteListInsert(L);
        
        scanf("%d",&i);
        scanf("%s %s %lf",e.isbn,e.book,&e.price);
        S = ListInsert(L,i,e);
        S = TravelElem(L);

        scanf("%d",&i);
        S = ListDelete(L,i);
        S = TravelElem(L);

        S = EmptyList(L);
        printf("%d\n",S);

        scanf("%s %s %lf",e.isbn,e.book,&e.price);
        S = LocateElem(L,e);
        printf("%d\n",S);

        scanf("%d",&i);
        S = GetElem(L,i);
        printf("%s %s %1.lf\n",e.isbn,e.book,e.price);

        S = DestroyList(L);
        printf("%d\n",S);

        S = ClearList(L);
        printf("%d\n",S);

        //S = TravelElem(L);
       
    }
    return 0;
}

END