【数据结构】 顺序表的基本操作 （C语言版）

一、顺序表

1、顺序表的定义：

线性表的顺序存储结构，即将表中的结点按逻辑顺序依次存放在一组地址连续的存储单元里。这种存储方式使得在逻辑结构上相邻的数据元素在物理存储上也是相邻的，可以通过数据元素的物理存储位置来反映其逻辑关系。

数据结构中的顺序表是一种线性表，它在计算机内存中以数组的形式保存。顺序表采用顺序存储结构，即将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。这种存储方式使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

2、顺序表的优缺点：

顺序表的优点是便于随机访问查找，时间复杂度为O(1)。缺点是不便于插入和删除操作，尤其是中间或头部的插入和删除操作，时间复杂度为O(n)。因此，顺序表适用于需要大量访问元素，尾部插入和删除较多的场景。

顺序表的优点：

1. 存储密度大：数据元素在内存中紧密排列，空间利用率高。
2. 存取速度快：可以通过下标直接访问任意位置的元素，时间复杂度为O(1)。
3. 空间连续：一次性申请一定大小的存储空间，便于管理和控制。

顺序表的缺点：

1. 插入和删除操作效率低下：需要移动大量数据元素，特别是当插入或删除的位置位于中间或头部时，时间复杂度为O(N)。
2. 长度固定：无法自由扩展或收缩，当元素个数超过预先分配的空间时会导致溢出，而元素个数远少于预先分配的空间时则会造成空间浪费。
3. 动态调整困难：顺序表的空间必须预先分配，无法根据实际需求动态调整。

二、顺序表的基本操作算法（C语言）

1、宏定义

typedef int Status;
typedef char ElemType;

2、创建结构体

//定义类型
typedef struct {
    char *elem;
    int length;
}SqList;

3、顺序表初始化

//初始化
Status InitList_sq(SqList &L){//引用型参数
//	L.elem=new char[10];
    L.elem=new ElemType[10];
    if(!L.elem){
        //exit (-1);
        exit (OVERFLOW);
    }
    L.length=0;
    return OK;
}

4、顺序表插入

在顺序表L的第 i 个元素之前插入新的元素e

1.找到第i-1个位置? ?

2.将元素e插入

时间复杂度T(n)=O(n)

顺序表的空间复杂度S(n)=O(1)? ? 没有占用辅助空间

//插入
Status InsertList_sq(SqList &L,int i,ElemType e){
    if(i<1 || i>L.length+1){
        return ERROR;
    }
    if(L.length==MAXSIZE){
        return ERROR;
    }
    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 OK;
}

4、顺序表取值?

//取值
Status GetElem(SqList L, int i, ElemType &e){
    if(i<1 || i>L.length) {
        return ERROR;
    }
    e = L.elem[i-1];
    return OK;
}

5、求顺序表的长度

//求长度
int GetLength(SqList L){
    return L.length;
}

6、顺序表查找

//查找
Status LocateElem(SqList L,ElemType e)
{
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e)
            return i + 1;
    }
    return 0;
}

7、顺序表删除

插入i-1个位置，删除第i个位置的元素

//删除
Status ListDelete(SqList &L,int i,ElemType &e)
{
    if ((i<1) || (i>L.length+1)) return ERROR;
//    if (L.length==MAXSIZE) return 0;       //不用判空
    e = L.elem[i - 1];
    for (int j=i;j<=L.length-1;j++)             //for (j=i-1;j<=L.length-1;j++)
        L.elem[j-1]=L.elem[j];             // L.elem[j]=L.elem[j+1];
    --L.length;
    return  OK;
}

四、顺序表的全部代码（C语言）

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 10


typedef int Status;
typedef char ElemType;

//定义类型
typedef struct {
    char *elem;
    int length;
} SqList;

//顺序表初始化
//int InitList_sq(SqList &L){   //引用型参数
Status InitList_sq(SqList &L) {
//	L.elem=new char[10];
    L.elem = new ElemType[10];
    if (!L.elem) {
        //exit (-1);
        exit(OVERFLOW);
    }
    L.length = 0;
//	return 1;
    return OK;
}

//功能菜单
int choice() {
    printf("==================================\n");
    printf("         顺序表操作功能菜单        \n");
    printf("          1、插入元素            \n");
    printf("          2、查询表长            \n");
    printf("          3、按位查找            \n");
    printf("          4、按值查找            \n");
    printf("          6、批量插入            \n");
    printf("          7、退出程序            \n");
    printf("==================================\n");
    return 0;
}

//顺序表插入
Status InsertList_sq(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) {
        return ERROR;
    }
    if (L.length == MAXSIZE) {
        return ERROR;
    }
    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 OK;
}

//顺序表取值
Status GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        return ERROR;
    }
    e = L.elem[i - 1];
    return OK;
}

//求顺序表长度
int GetLength(SqList L) {
    return L.length;
}

//顺序表查找
Status LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        //printf("%c",L.elem[i]);
        if (L.elem[i] == e)
            return i + 1;
    }
    return 0;
}

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


int main() {
    //printf("Hell Word");
    //struct List list;
    SqList sqList;

    printf("顺序表正在初始化....\n");
    Status returnStatus = InitList_sq(sqList);
    if (returnStatus == OK) {
        printf("顺序表初始化成功！\n");
    } else {
        printf("顺序表初始化失败！\n");
    }

    choice();

    while (1) {

        int flag;
        printf("请输入所需的功能编号：\n");
        scanf("%d", &flag);

        switch (flag) {
            case 1: {//插入
                // printf("length = %d \n", sqList.length);
                // int listLength = GetLength(sqList);
                // printf("%d ", listLength);
                int insertLocation;
                ElemType insertElem;
                printf("请输入插入元素位置及插入元素(请在英文状态下输入例如:1,a): \n");
                scanf("%d,%c", &insertLocation, &insertElem);
                Status insertStatus = InsertList_sq(sqList, insertLocation, insertElem);
                if (insertStatus == OK) {
                    printf("向顺序表中第%d个位置,插入元素%c成功！\n", insertLocation, insertElem);
                } else {
                    printf("向顺序表中插入元素失败！\n");
                }
                choice();
            }
                break;
            case 2: {//求顺序表的长度
                printf("顺序表的长度为：%d  。\n", GetLength(sqList));
                choice();
            }
                break;
            case 3: {//取值
                Status no;
                printf("请输入需要查询的元素的位置：\n");
                scanf("%d", &no);
                ElemType element;
                Status GetElemStatus = GetElem(sqList, no, element);
                //printf("element = %c ", element);
                printf("在顺序表中第%d个元素为：%c 。 \n", no, element);
                if (GetElemStatus = OK) {
                    printf("在顺序表中第%d个元素为：%c 。 \n", no, element);
                } else {
                    printf("查找顺序表中第%d个元素失败。 \n", no);
                }
                choice();
            }
                break;
            case 4: {//查找
                ElemType findElem;
                printf("请输入想要查找元素：\n");
                getchar();    //用于接收回车
                scanf("%c", &findElem);
                int locate = LocateElem(sqList, findElem);
                if (locate != 0) {
                    printf("所需查找的元素%c存在于顺序表中，它的在第%d位置。  \n", findElem, locate);
                } else {
                    printf("所需查找的元素%c不存在于顺序表中！  \n", findElem);
                }
                //printf("locate = %d ", locate);
                choice();
            }
                break;
            case 5: {//删除
                //ListDelete_DuL(list,1);
                Status delindex;
                ElemType delElem;
                printf("请输入想要删除元素的位置：\n");
                scanf("%d", &delindex);
                Status delreturn = ListDelete(sqList, delindex, delElem);
                if (delreturn == OK) {
                    printf("在顺序表中删除第%d个元素为：%c 。 \n", delindex, delElem);
                } else {
                    printf("在顺序表中删除第%d个元素失败! \n", delindex);
                }
                printf("顺序表的长度为：%d  \n", GetLength(sqList));
                //printf("delindex = %d ", delindex);
                choice();
            }
                break;
            case 6: {//批量插入
                int on;
                printf("请输入想要插入的元素个数：\n");
                scanf("%d", &on);
                ElemType array[on];
                for (int i = 1; i <= on; i++) {
                    getchar();
                    printf("向顺序表第%d个位置插入元素为:", (i));
                    scanf("%c", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status insertStatus = InsertList_sq(sqList, i, array[i]);
                    if (insertStatus == OK) {
                        printf("向顺序表中第%d个位置,插入元素%c成功！\n", i, array[i]);
                    } else {
                        printf("向顺序表中第%d个位置插入元素失败！\n", i);
                    }
                }
                choice();
            }
                break;
            case 7: {//退出程序
                return 0;
            }
                break;
            default: {
                printf("输入错误，无此功能，请检查输入:\n\n");
            }
        }
    }
}

五、结果

?

?

?

?