数据结构笔记(一):线性表之顺序表的简单实现

发布于 / 程序猿 / 0 条评论

使用C++简单实现顺序表,完成增删查改以及输出与合并功能。若文中存在错误,敬请指出,感谢阅读。

顺序表还是挺好理解的,相对于链表而言,实现起来也比较简单。


基本知识

顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址(连续的存储单元)依次存储数据元素的线性结构。

顺序表的实现一般是连续开辟一段空间,然后进行数据的增删查改(静态顺序表),所以顺序表一般是固定空间大小的。(当然,顺序表也可以在初始化时利用malloc函数开辟一段空间,每当空间不够用时再用realloc来把当前空间扩容,从而也能实现空间的动态变化,(动态顺序表))

顺序表的结构就像数组一样,可以用下标来访问它的元素,所以它的元素是支持随机访问的,访问随机元素的时间复杂度为O(1),在随机位置插入、删除元素的平均时间复杂度为O(n)。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
const int INIT_SIZE = 100; // 初始大小
const int N = 2; // 重新分配内存时增加倍数
using namespace std;

struct ArrayList
{
    int *elem; // 存储元素(数据)
    int length; // 实际长度
    int capacity; // 容量
};

int initArrayList(ArrayList & List) // 初始化线性表
{
    // List.elem = (int *)malloc(INIT_SIZE)*sizeof(int); // -- C
    List.elem = NULL;
    List.elem = new int [INIT_SIZE];
    if (!List.elem) // 内存分配失败返回-1
        return -1;
    List.length = 0;
    List.capacity = INIT_SIZE;
    return 0; // 分配成功则默认返回0
}

int destroyArrayList(ArrayList & List) // 销毁线性表(回收)
{
    // free (List.elem); // -- C
    delete [] List.elem;
    List.elem = NULL;
    return 0; // 回收成功默认返回0
}

int insertArrayList(ArrayList & List, int pos, int newvalue) // 增
{
    int *newbase, *p, *q;
    if (pos < 0 || pos > List.length) // 插入位置不合法返回-1
        return -1;

    if (List.length >= List.capacity) // 当前存储空间已满,重新分配内存
    {
        newbase = new int [List.capacity * N]; // 新内存大小为原来N倍
        if (!newbase) // 重新分配内存失败时返回-1
            return -1;
        for (p = newbase, q = List.elem; q <= List.elem + List.length; p++, q++) // 重要
            *p = *q;
        List.elem = newbase;
        List.capacity *= N;
    }

    for (int i = List.length - 1; i >= pos; --i) // 插入操作
        List.elem[i+1] = List.elem[i];
    List.elem[pos] = newvalue;
    ++List.length;

    return 0; // 插入成功默认返回0
}

int removeArrayList (ArrayList & List, int pos) // 删
{
    if (pos < 0 || pos > List.length) // 删除位置不合法返回-1
        return -1;

    for (int i = pos; i < List.length - 1; ++i)
        List.elem[i] = List.elem[i+1];
    --List.length;
    return 0; // 删除成功默认返回0
}

int atArrayList(ArrayList & List, int pos) // 查
{
    if (pos < 0 || pos > List.length) // 查询位置不合法返回-1
        return -1;
    return List.elem[pos];
    // bug, 若查询位置的值为-1怎么判断查询是否成功
    // 只需再增加一个形式参数做判断即可
}

int modifyArrayList(ArrayList & List, int pos, int newvalue) // 改
{
    if (pos < 0 || pos > List.length) // 修改位置不合法返回-1
        return -1;
    List.elem[pos] = newvalue;
    return 0; // 修改成功默认返回0
}

void printArrayList(ArrayList & List) // 输出
{
    for (int i = 0; i < List.length; ++i)
        cout << List.elem[i] << " ";
    cout << endl;
}

int isemptyArrayList(ArrayList & List) // 判断是否为空
{
    if (List.length == 0)
        return 0; // 为空时返回0
    return 1; // 不为空时返回1
}

int mergeArrayList(ArrayList & a, ArrayList & b, ArrayList & c) // 合并两个顺序表
{
    while (a.length + b.length > c.capacity) // 注意
    {
        c.elem = new int [c.capacity * N];
        c.capacity *= N;
    }

    for (int i = 0; i < a.length; ++i)
        c.elem[i] = a.elem[i];
    for (int i = 0; i < b.length; ++i)
        c.elem[i+a.length] = b.elem[i];
    c.length = a.length + b.length;
    return 0;
}

int main()
{
    ArrayList List;
    initArrayList(List);
    int a[10] = {2, 7, 4, 3, 8, 6, 5};
    for (int i = 0; i < 7; ++i)
        insertArrayList(List, i, a[i]);
    int idx, pos, value;
    while (cin >> idx && idx)
    {
        if (idx == 1) // 增
        {
            cin >> pos >> value;
            insertArrayList(List, pos, value);
        }
        else if (idx == 2) // 删
        {
            cin >> pos;
            removeArrayList(List, pos);
        }
        else if (idx == 3) // 查
        {
            cin >> pos;
            cout << atArrayList(List, pos) << endl;
        }
        else if (idx == 4) // 改
        {
            cin >> pos >> value;
            modifyArrayList(List, pos, value);
        }
        else if (idx == 5) //输出
            printArrayList(List);

    }
    destroyArrayList(List);

    ArrayList A, B, C;
    initArrayList(A);
    initArrayList(B);
    initArrayList(C);

    int b[10] = {2, 7, 4, 3, 8, 6, 5};
    for (int i = 0; i < 7; ++i)
    {
        insertArrayList(A, i, b[i]);
        insertArrayList(B, i, b[i]+1);
    }

    printArrayList(A);
    printArrayList(B);

    mergeArrayList(A, B, C); // 合并
    printArrayList(C);

    destroyArrayList(A);
    destroyArrayList(B);
    destroyArrayList(C);

    return 0;
}

/*
5
2 7 4 3 8 6 5
1 2 9
5
2 7 9 4 3 8 6 5
2 1
5
2 9 4 3 8 6 5
3 4
8
4 5 21
5
2 9 4 3 8 21 5
0
2 7 4 3 8 6 5
3 8 5 4 9 7 6
2 7 4 3 8 6 5 3 8 5 4 9 7 6

Process returned 0 (0x0)   execution time : 1.875 s
Press any key to continue.

*/

时间复杂度

  • 插入:O(n)[头插入/尾插入]
  • 删除:O(n)[头删除/尾删除]
  • 合并:O(n)

注意

  • 当前存储空间已满时重新分配内存的写法。
  • 查询函数怎么知道查询的值是正确的。
  • 初始化定义线性表后记得释放内存回收。

问题

来源:CSDN论坛 | 数据结构顺序表,存储空间已满,增加分配

  • 截取问题部分代码如下:
Status ListInsert(SqList &L,int i,ElemType e)
{
    ElemType *newbase,*q,*p;

    if(i<1||i>L.length+1)
        return Error;
/*判断i值是否合法*/

    if(L.length>=L.listsize)
    {
        newbase= new ElemType[L.listsize+LISTINCREMENT];
            if(!newbase)
                return Error;
            L.elem=newbase;
            L.listsize+=LISTINCREMENT;
    }

/*判断存储空间是否已满,增加储存容量*/

    q=L.elem +i-1;
     for(p=L.elem+L.length-1;p>=q;--p)
     *(p+1)=*p;
   *q=e;               
   ++L.length;        
   return OK;
 //插入算法
}
   if(L.length>=L.listsize)      /* 当前存储空间已满,增加分配 */
   {
     newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
     if(!newbase)
       return Error;;              /* 存储分配失败 */
     L.elem=newbase;              /* 新基址 */
     L.listsize+=LISTINCREMENT;        /* 增加存储容量 */
   }

上面这是正确的,怎么改成下面的就错了??

    if(L.length>=L.listsize)
    {
        newbase= new ElemType[L.listsize+LISTINCREMENT];
            if(!newbase)
                return Error;
            L.elem=newbase;
            L.listsize+=LISTINCREMENT;
    }

/*判断存储空间是否已满,增加储存容量*/
  • 已采纳的回答:
1. 用newbase在内存堆区开辟空间后得到的是一个新地址,newbase的值(地址)与L.elem的值(地址)不相同
2. 当执行L.elem=newbase;语句时,L.elem的地址是newbase的地址,与未执行该语句的L.elem地址是不一样的       
3. 因此新的L.elem地址空间存储  的全是随机值,要先将未执行L.elem=newbase;语句的L.elem地址空间元素分别赋值给newbase
   修改如下:

 if(L.length>=L.listsize)
 {
        newbase= new ElemType[L.listsize+LISTINCREMENT];
        if(!newbase)
            return Error;
        //加入下条语句即可正常执行
        for (p=newbase,q=L.elem;q<=L.elem+L.length;p++,q++)
             *p=*q;
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
}
/*判断存储空间是否已满,增加储存容量*/

优化

// 快速修改存储数据类型
// 以及函数(返回值)类型

typedef int ElemType;
typedef int Status;

struct ArrayList
{
    ElemType *elem; // 存储元素(数据)
    int length; // 实际长度
    int capacity; // 容量
};

Status initArrayList(ArrayList & List);
Status destroyArrayList(ArrayList & List);
Status insertArrayList(ArrayList & List, int pos, int newvalue)
Status atArrayList(ArrayList & List, int pos)
Status modifyArrayList(ArrayList & List, int pos, int newvalue)
Status mergeArrayList(ArrayList & a, ArrayList & b, ArrayList & c) 


推荐

第一篇博客详细解释C语言中的malloc函数,第二篇博客中线性表是按照严老师书上的结构实现的。

本文基础知识与下文基础知识部分均来自于CSDN博客:线性表之顺序表与单链表的区别及优缺点

最后,致敬迅哥


The end.
2017-10-19 星期四

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(一):线性表之顺序表的简单实现
Not Comment Found