数据结构与算法③(第二章上)顺序表的实现(动态顺序表+菜单)-阿里云开发者社区

1.线性表的概念

【百度百科】线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

概念：线性表（Linear list）是n个具有相同特性的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串等……

线性表在逻辑上是线性结构，他们在逻辑上是挨着挨着的。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表的概念

【百度百科】顺序表是在计算机内存中以 数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组 地址连续的存储单元中。

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。顺序表一般可以分为静态顺序表和动态顺序表：

静态顺序表：使用定长数组存储元素

动态顺序表：使用动态开辟的数组存储

顺序表的本质是什么？

顺序表的本质就是数组，但是在数组的基础上它还要求数组是从头开始存，并且是连续存储的，

不能跳跃间隔。换言之，顺序表既然叫顺序表，那么数据一定必须是挨着挨着存的。

2.1静态顺序表

使用定长数组存储元素：

 
#define N 8
typedef int SLDataType
 
typedef struct SeqList 
{
    SLDataType array[N];  //定长数组
    size_t size;          //有效数据的个数
} SeqList;

静态顺序表的特点：如果满了就不让插入。

静态顺序表的缺点：数组大小是给多少合适呢？这个往往难以斟酌，N给小了不够用，N给大了又浪费空间。

2.2 动态顺序表

使用动态开辟的数组存储元素：

 
typedef int SLDataType
 
typedef struct SeqList
{
    SLDataType* arr;
    int size; //有效数据个数
    int capacity;//数组实际能存数据的空间容量是多大
}SL;

（空间不够则增容）

3. 动态顺序表的模拟实现

为什么使用动态顺序表？

静态顺序表只适用于确定知道需要存多少数据的场景，如果静态顺序表的定长数组导致N定大了，就会造成空间浪费，如果N定小了又不够用。所以现实中基本都是使用动态顺序表，可以根据需要动态地分配空间大小。

什么是接口函数？

接口函数是在数据进行操作时进行调用的函数，通过调用数据结构的接口帮助你完成一系列操作

基本增删查改接口：

 
//接口函数   命名风格安装STL库的来命名
void SeqListInit(SL* psl);                               //初始化
void SeqListDestory(SL* psl);                           //销毁
void SeqListCheckCapacity(SL* psl);                       //检查是否需要增容
void SeqListPushBack(SL* psl, SLDataType x);           //尾插
void SeqListPrint(SL* psl);                               //打印
void SeqListPushFront(SL* psl, SLDataType x);           //头插
void SeqListPopBack(SL* psl);                           //尾删
void SeqListPopFront(SL* psl);                           //头删
int SeqListFind(SL* psl, SLDataType x);                   //查找
int SeqListInsert(SL* psl, int pos, SLDataType x);     //指定位置插入
int SeqListEarse(SL* psl, int pos);                       //指定位置删除

完整代码实现：

第一部分代码实现

SeqList.h

 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLDataType;
 
typedef struct SeqList
{
    SLDataType* arr;
    int size; //有效数据个数
    int capacity;//数组实际能存数据的空间容量是多大
}SL;
 
void SeqListInit(SL* psl);
void SeqListPushBack(SL* psl, SLDataType x);
void SeqListPrint(SL* psl);
void SeqListDestroy(SL* psl);
void SeqListPopBack(SL* psl);
void SeqListPushFront(SL* psl, SLDataType x);
void SeqListCheckCpacity(SL* psl);
void SeqListPopFront(SL* psl);
int SeqListFind(SL* psl, SLDataType x);

SeqList.c

 
#include"SeqList.h"
 
void SeqListInit(SL* psl)
{
    psl->arr = NULL;
    psl->size = 0;
    psl->capacity = 0;
}
 
void SeqListPrint(SL* psl)
{
    for (int i = 0;i < psl->size;i++)
    {
        printf("%d ", psl->arr[i]);
    }
    printf("\n");
}
 
void SeqListPushBack(SL* psl, SLDataType x)
{
    SeqListCheckCpacity(psl);
    psl->arr[psl->size] = x;
    psl->size++;
}
 
void SeqListDestroy(SL* psl)
{
    free(psl->arr);
    psl->arr = NULL;
    psl->size = psl->capacity = 0;
}
 
void SeqListPopBack(SL* psl)
{
    assert(psl->size > 0);
    psl->size--;
}
 
void SeqListPushFront(SL* psl, SLDataType x)
{
    SeqListCheckCpacity(psl);
    int end = psl->size - 1;
    while (end >= 0)
    {
        psl->arr[end + 1] = psl->arr[end];
        end--;
    }
    psl->arr[0] = x;
    psl->size++;
}
 
void SeqListCheckCpacity(SL* psl)
{
    if (psl->size == psl->capacity)
    {
        int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(psl->arr, newcapacity * sizeof(SLDataType));
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        psl->arr = tmp;
        psl->capacity = newcapacity;
    }
}
 
void SeqListPopFront(SL* psl)
{
    assert(psl->size > 0);
    int begin = 0;
    while (begin < psl->size - 1)
    {
        psl->arr[begin] = psl->arr[begin + 1];
        begin++;
    }
    psl->size--;
}
 
int SeqListFind(SL* psl, SLDataType x)
{
    for (int i = 0;i < psl->size;i++)
    {
        if (psl->arr[i] == x)
        {
            return i;
        }
    }
    return -1;
}

Test.c

 
#include"SeqList.h"
 
void TestSeqList1()//测试初始化函数，打印函数，尾插尾删
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
 
    SeqListPrint(&sl);
 
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPrint(&sl);
 
    SeqListDestroy(&sl);
}
 
void TestSeqList2()//测试头插头删
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPrint(&sl);
 
    SeqListPushFront(&sl, 10);
    SeqListPushFront(&sl, 20);
    SeqListPushFront(&sl, 30);
    SeqListPrint(&sl);
 
    SeqListPopFront(&sl);
    SeqListPopFront(&sl);
    SeqListPrint(&sl);
 
    SeqListDestroy(&sl);
}
 
void TestSeqList3()//测试查找函数
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
    SeqListPrint(&sl);
 
    int ret = SeqListFind(&sl, 3);
    if (ret != -1)
    {
        printf("找到了,下标是：%d\n", ret);
    }
    else
    {
        printf("没找到\n");
    }    
    ret = SeqListFind(&sl, 60);
    if (ret != -1)
    {
        printf("找到了,下标是：%d\n", ret);
    }
    else
    {
        printf("没找到\n");
    }
    SeqListDestroy(&sl);
}
 
int main()
{
    //TestSeqList1();
    //TestSeqList2();
    TestSeqList3();
    return 0;
}

完整代码实现（包含菜单）

加了指定位置删除增加，把头删头插，尾插尾删替换了（增加了菜单的实现）

SeqList.h

 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLDataType;
 
typedef struct SeqList
{
    SLDataType* arr;
    int size; //有效数据个数
    int capacity;//数组实际能存数据的空间容量是多大
}SL;
 
void SeqListInit(SL* psl);
void SeqListPushBack(SL* psl, SLDataType x);
void SeqListPrint(SL* psl);
void SeqListDestroy(SL* psl);
void SeqListPopBack(SL* psl);
void SeqListPushFront(SL* psl, SLDataType x);
void SeqListCheckCpacity(SL* psl);
void SeqListPopFront(SL* psl);
int  SeqListFind(SL* psl, SLDataType x);
void SeqListInsert(SL* psl,int pos, SLDataType x);//position 位置
void SeqListErase(SL* psl, int pos);

SeqList.c

 
#include"SeqList.h"
 
void SeqListInit(SL* psl)
{
    psl->arr = NULL;
    psl->size = 0;
    psl->capacity = 0;
}
 
void SeqListPrint(SL* psl)
{
    for (int i = 0;i < psl->size;i++)
    {
        printf("%d ", psl->arr[i]);
    }
    printf("\n");
}
 
void SeqListPushBack(SL* psl, SLDataType x)
{
    //SeqListCheckCpacity(psl);
    //psl->arr[psl->size] = x;
    //psl->size++;
    SeqListInsert(psl, psl->size, x);
}
 
void SeqListDestroy(SL* psl)
{
    free(psl->arr);
    psl->arr = NULL;
    psl->size = psl->capacity = 0;
}
 
void SeqListPopBack(SL* psl)
{
    //assert(psl->size > 0);
    //psl->size--;
    SeqListErase(psl, psl->size-1);
}
 
void SeqListPushFront(SL* psl, SLDataType x)
{
    //SeqListCheckCpacity(psl);
    //int end = psl->size - 1;
    //while (end >= 0)
    //{
    //    psl->arr[end + 1] = psl->arr[end];
    //    end--;
    //}
    //psl->arr[0] = x;
    //psl->size++;
    SeqListInsert(psl, 0, x);
}
 
void SeqListCheckCpacity(SL* psl)
{
    if (psl->size == psl->capacity)
    {
        int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(psl->arr, newcapacity * sizeof(SLDataType));
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        psl->arr = tmp;
        psl->capacity = newcapacity;
    }
}
 
void SeqListPopFront(SL* psl)
{
    //assert(psl->size > 0);
    //int begin = 0;
    //while (begin < psl->size - 1)
    //{
    //    psl->arr[begin] = psl->arr[begin + 1];
    //    begin++;
    //}
    //psl->size--;
    SeqListErase(psl, 0);
}
 
int SeqListFind(SL* psl, SLDataType x)
{
    for (int i = 0;i < psl->size;i++)
    {
        if (psl->arr[i] == x)
        {
            return i;
        }
    }
    return -1;
}
 
void SeqListInsert(SL* psl, int pos, SLDataType x)//position 位置
{
    assert(pos >= 0 && pos <= psl->size);
    SeqListCheckCpacity(psl);
 
    int end = psl->size - 1;
    while (pos <= end)
    {
        psl->arr[end + 1] = psl->arr[end];
        end--;
    }
 
    psl->arr[pos] = x;
    psl->size++;
}
 
void SeqListErase(SL* psl, int pos)
{
    assert(pos >= 0 && pos <= psl->size - 1);
 
    int begin = pos;
    while (begin < psl->size - 1)
    {
        psl->arr[begin] = psl->arr[begin + 1];
        begin++;
    }
 
    psl->size--;
}

Test.c

 
#include"SeqList.h"
 
void TestSeqList1()//测试初始化函数，打印函数，尾插尾删
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
 
    SeqListPrint(&sl);
 
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPrint(&sl);
 
    SeqListDestroy(&sl);
}
 
void TestSeqList2()//测试头插头删
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPrint(&sl);
 
    SeqListPushFront(&sl, 10);
    SeqListPushFront(&sl, 20);
    SeqListPushFront(&sl, 30);
    SeqListPrint(&sl);
 
    SeqListPopFront(&sl);
    SeqListPopFront(&sl);
    SeqListPrint(&sl);
 
    SeqListDestroy(&sl);
}
 
void TestSeqList3()//测试查找函数
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
    SeqListPrint(&sl);
 
    int ret = SeqListFind(&sl, 3);
    if (ret != -1)
    {
        printf("找到了,下标是：%d\n", ret);
    }
    else
    {
        printf("没找到\n");
    }    
    ret = SeqListFind(&sl, 60);
    if (ret != -1)
    {
        printf("找到了,下标是：%d\n", ret);
    }
    else
    {
        printf("没找到\n");
    }
    SeqListDestroy(&sl);
}
 
void TestSeqList4()//测试指定位置插入删除
{
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
    SeqListPrint(&sl);
 
    //SeqListInsert(&sl, 3, 10);
    //SeqListInsert(&sl, 0, 20);//相当于头插
    //SeqListInsert(&sl, 6, 30);
    //SeqListInsert(&sl, 8, 40);//相当于尾插
    //SeqListPrint(&sl);
 
    SeqListErase(&sl, 3);
    SeqListErase(&sl, 0);//相当于头删
    SeqListPrint(&sl);
 
    SeqListErase(&sl, 2);//相当于尾删
    SeqListPrint(&sl);
 
    SeqListDestroy(&sl);
}
 
void TestSeqList5()//测试新的尾插尾删，头插头删
{
    //SL sl;
    //SeqListInit(&sl);
    //SeqListPushBack(&sl, 1);
    //SeqListPushBack(&sl, 2);
    //SeqListPushBack(&sl, 3);
    //SeqListPushBack(&sl, 4);
    //SeqListPushBack(&sl, 5);
    //SeqListPrint(&sl);
 
    //SeqListPopBack(&sl);
    //SeqListPopBack(&sl);
    //SeqListPopBack(&sl);
    //SeqListPrint(&sl);
 
    SL sl;
    SeqListInit(&sl);
    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPrint(&sl);
 
    SeqListPushFront(&sl, 10);
    SeqListPushFront(&sl, 20);
    SeqListPushFront(&sl, 30);
    SeqListPrint(&sl);
 
    SeqListPopFront(&sl);
    SeqListPopFront(&sl);
    SeqListPrint(&sl);
 
    SeqListDestroy(&sl);
}
 
void menu() 
{
    printf("\n");
    printf("########################\n");
    printf("#  1. 头插    2. 头删  #\n");
    printf("#  3. 尾插    4. 尾删  #\n");
    printf("#  5. 打印    6. 查找  #\n");
    printf("#  7. 指定位置插入     #\n");
    printf("#  8. 指定位置删除     #\n");
    printf("#  0. 退出程序         #\n");
    printf("########################\n");
}
 
enum SQ 
{
    CLOSE,      //0  把CLOSE放在第一个，正好顺势推下去
    PUSH_FRONT, //1
    POP_FRONT,  //2
    PUSH_BACK,  //3
    POP_BACK,   //4
    PRINT,      //5
    SEARCH,     //6
    INSERT,     //7
    EARSE,      //8
};
 
void TestMenu()
{
    SL sl;
    SeqListInit(&sl);
    int input = 0, x = 0, pos = 0;
    do 
    {
        menu();
        printf("请选择操作: ");
        scanf("%d", &input);
        switch (input) 
        {
        case CLOSE: //退出（0）
            printf("已退出\n");
            break;
        case PUSH_FRONT: //头插（1）
            printf("请输入你要头插的数据，以-1结束: ");
            scanf("%d", &x);
            while (x != -1) 
            {
                SeqListPushFront(&sl, x);
                scanf("%d", &x);
            }
            break;
        case POP_FRONT: //头删（2）
            SeqListPopFront(&sl);
            printf("已删除\n");
            break;
 
        case PUSH_BACK: //尾插（3）
            printf("请输入你要尾插的数据，以-1结束: ");
            scanf("%d", &x);
            while (x != -1) 
            {
                SeqListPushBack(&sl, x);
                scanf("%d", &x);
            }
            break;
        case POP_BACK: //尾删（4）
            SeqListPopBack(&sl);
            printf("已删除\n");
            break;
        case PRINT: //打印（5）
            printf("顺序表：");
            SeqListPrint(&sl);
            break;
        case SEARCH: //查找（6）
            printf("请输入查找的数据: ");
            scanf("%d", &x);
            int ret = SeqListFind(&sl, x);
            if (ret != -1) {
                printf("找到了，下标为 %d\n", ret);
            }
            else {
                printf("找不到\n");
            }
            break;
        case INSERT: //指定位置插入 (7)
            printf("请输入你要插入的位置的下标: ");
            scanf("%d", &pos);
            printf("请输入你要插入的数据，以-1结束: ");
            scanf("%d", &x);
            while (x != -1) 
            {
                SeqListInsert(&sl, pos, x);
                scanf("%d", &x);
            }
            break;
        case EARSE: //指定位置删除 (8)
            printf("请输入你要删除的位置的下标: ");
            scanf("%d", &pos);
            SeqListErase(&sl, pos);
            printf("已删除\n");
            break;
        default:
            printf("输入错误，请重新输入！\n");
            break;
        }
    } while (input);
    SeqListDestroy(&sl); //销毁
}
 
 
int main()
{
    //TestSeqList1();//测试初始化函数，打印函数，尾插尾删
    //TestSeqList2();//测试头插头删
    //TestSeqList3();//测试查找函数
    //TestSeqList4();//测试指定位置插入删除
    //TestSeqList5();//测试新的尾插尾删，头插头删
    TestMenu();//测试菜单和整个程序
    return 0;
}

4.选择笔试题练习

练习1

下列数据结构中，不属于线性表的是（）

A.循环队列

B.链表

C.动态顺序表

D.二叉树

练习2

在长度为 n 的顺序表下标为 i 的位置前插入一个元素（1 ≤ i ≤ n+1），元素的移动次数为（）

A.n - i + 1

B.n - i

C.i

D.i - 1

练习3

动态顺序表中，（）操作需要检查是否需要扩容

A.删除

B.插入

C.初始化

D.清空

练习4

自己完成下面的接口函数并测试

 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int SLDataType;
 
typedef struct SeqList
{
    SLDataType* arr;
    int size; //有效数据个数
    int capacity;//数组实际能存数据的空间容量是多大
}SL;
 
void SeqListInit(SL* psl);
void SeqListPushBack(SL* psl, SLDataType x);
void SeqListPrint(SL* psl);
void SeqListDestroy(SL* psl);
void SeqListPopBack(SL* psl);
void SeqListPushFront(SL* psl, SLDataType x);
void SeqListCheckCpacity(SL* psl);
void SeqListPopFront(SL* psl);
int SeqListFind(SL* psl, SLDataType x);

答案

练习1 答案：D

解析：二叉树属于树形结构，不是线性的，队列，链表，顺序表都属于线性表

练习2答案：B

解析：顺序表插入元素，需要移动元素，这里需要把[i, n - 1]区间的元素全部向后移动一次，故移动的次数为n - 1 - i + 1

练习3答案：B

解析：插入操作需要考虑空间是否足够，如果不够需要先增容，再进行插入。

练习4答案参考上面代码

5. 顺序表的优缺点

顺序表的优点：

① 支持随机访问，有些算法需要结构随机访问，比如二分查找和优化的快排等。

② 数据是按顺序存放的，空间利用率高。

③ 通过下标直接访问，存取速度高效。

顺序表的缺点及思考：

① 中间/头部的插入删除，需要挪动，挪动数据时也是存在消耗的，时间复杂度为O(N)

② 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

③ 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：

如何解决以上问题呢？下篇给出了链表的结构。

数据结构与算法③(第二章上)顺序表的实现(动态顺序表+菜单)

1.线性表的概念

2.顺序表的概念

2.1静态顺序表

2.2 动态顺序表

3. 动态顺序表的模拟实现

第一部分代码实现

SeqList.h

SeqList.c

Test.c

完整代码实现（包含菜单）

SeqList.h

SeqList.c

Test.c

4.选择笔试题练习

练习1

练习2

练习3

练习4

答案

5. 顺序表的优缺点

本篇完。

热门文章

最新文章

相关课程

相关电子书

相关实验场景