[C++知识库]王道数据结构代码实践----顺序表静态存储（C语言版）

王道数据结构代码实践----顺序表静态存储（C语言版）

前言

日期：2021年8月25日
书籍：王道2021年数据结构考研复习指导
代码内容：实现顺序表的静态存储，包括初始化，插入新元素，删除新元素，输出，查询

代码难点

1. C语言没有bool数据类型

老生常谈了，C语言没有直接定义好的bool类型，不过我们可以自己宏定义一个啊

#define bool char
#define false 0
#define true 1

2.顺序表的位序从1开始，而数组的位序从0开始

这是最让我觉得生草的地方，写代码中间弄错了好几次，最终代码里每个i代表什么意思我都已经标好了，一会儿之间看源代码吧

3.getchar（）和scanf（）函数之差

这还是个问题，我还没解决，现在先说现象，等明白了回来补

    int a;
    while (1)
    {
        text();
        scanf("%d",&a);
        // a = getchar();
        switch (a)
        {
        ......
        }

这里，使用scanf（）可以正常输入整型变量，并被switch正常识别，我记得我以前用字母作为输入时，switch抽过风，所以一开始我选择用的getchar（），然后，C99教我做了人，对，我又用回scanf了，具体原因我还没懂，等我懂了再说吧。

源代码

废话不多说了，直接上源代码

//静态分配顺序表

#include <stdio.h>
#include <stdlib.h>
//C语言自定义bool操作
#define bool char
#define false 0
#define true 1

/*数组长度及顺序表的初始化长度*/
#define MAX_SIZE 10

/*数据元素类型*/
typedef int ElemType;

/*顺序表结构定义*/
typedef struct 
{
    ElemType data[MAX_SIZE];    //顺序表的元素
    int length;                 //顺序表的当前长度
}SqList;                        //顺序表的类型定义

//基本操作----初始化一个顺序表
void InitList(SqList *L)
{
    for(int i = 0 ; i < MAX_SIZE ; i++)
        L->data[i] = 0;
    L->length = 0;
}

//基本操作----插入操作
/*
    在顺序表L的第i(1<=i<=L.length+1)个位置插入新元素e
    若输入的i不合法,则返回false,表示插入失败
    否则,将顺序表的第i个元素及其后的所有元素右移一个位置,腾出一个空位置插入新元素e,顺序表长度增加1,插入成功,返回tree
*/
bool ListInsert(SqList *L, int i, ElemType e)
{
    if(i<1||i>L->length+1) return false;    //i的位置不在1~length之间,位置出错,这里看的是表长的i,从1开始数
    if(L->length>=MAX_SIZE) return false;   //顺序表满了
    for(int j = L->length;j >= i;j--)       //循环移动元素,这里的i和j都是数组下表,从0开始数
    {
        L->data[j] = L->data[j-i];
    }
    L->data[i-1] = e;                       //在顺序表的第i个元素的左边插入新元素,即让顺序表的第i-1个元素等于e,这里的i是表长的i,从1开始数
    L->length++;
    return true;
}

//基本操作----删除操作
/*
    把顺序表L的第i(1<=i<=L.length+1)个位置的元素e删除,
    若成功则返回true,并将被删除的元素用引用变量返回
    失败则返回false
*/
bool ListDlete(SqList *L, int i,ElemType *e)
{
    if(i<1||i>L->length) return false;  //i的位置不在1~length之间,位置出错,这里看的是表长的i,从1开始数
    *e = L->data[i-1];                   //把顺序表L的第i个位置的元素,即数组的第i-1个元素赋值给e
    for(int j = i;j <L->length;j++)     //这里的i又是表长的i了,即从1开始数
    {
    L->data[j-1] = L->data[j];
    }
    L->length--;
    return true;
}

//基本操作,输出顺序表
bool OutputList(SqList *L)
{
    if (L->length == 0)
    {
        printf("表为空!");
        return false;
    }
    
    for (int i = 0; i < L->length; i++)
    {
        printf("顺序表的第%d个元素为\t%d\n",i+1,L->data[i]);
    }
    return true;
}

//基本操作,按位查找
bool GetElem(SqList *L, int i)  //i的位置不在1~length之间,位置出错,这里看的是表长的i,从1开始数
{
    if(i<1||i>L->length) 
    { 
        printf("查找失败\n"); 
        return false;
    }  
    printf("顺序表的第%d个元素为\t%d\n",i,L->data[i-1]);
}

//基本操作,按值查找(顺序查找)
int LocateElem(SqList *L,ElemType e)
{
    int i;
    for ( i = 0; i < L->length; i++)
    {
        if (L->data[i] == e)
        {
            return i+1;
        }
    }
    return 0;
}

void text()
{
    printf("********************************************************\n");
    printf("**           欢迎使用本数据表,请选择您的操作            **\n");
    printf("**   1.插入新元素                                      **\n");
    printf("**   2.插入元素                                        **\n");
    printf("**   3.删除元素                                        **\n");
    printf("**   4.输出顺序表                                      **\n");
    printf("**   5.按位查找                                        **\n");
    printf("**   6.按值查找                                        **\n");
    printf("**   0.退出程序                                        **\n");
    printf("********************************************************\n");

}

void menu(SqList *L)
{
    int a;
    while (1)
    {
        text();
        scanf("%d",&a);
        // a = getchar();
        switch (a)
        {
        case 0:
        {   
            exit(0);
            break;
        }
        case 1:
        {
            int x;
            printf("请输入您要插入的值(该值会出入到顺序表的最后一位):\n");
            scanf("%d",&x);
            bool b = ListInsert(L,L->length+1,x);
            if(b)   printf("插入成功!\n");
            else    printf("插入失败!\n");
            break ;
        }
        case 2:
        {
            int x,y;
            printf("请输入您要插入的值:\n");
            scanf("%d",&x);
            printf("请输入您要插入的位置:\n");
            scanf("%d",&y);
            bool b = ListInsert(L,y,x);
            if(b)   printf("插入成功!\n");
            else    printf("插入失败!\n");
            break ;
        }
        case 3:
        {
            int x,y;
            printf("请输入您要删除的值:\n");
            scanf("%d",&x);
            bool b = ListDlete(L,x,&y);
            if(b)   printf("删除成功!,删除的值为:%d\n",y);
            else    printf("删除失败!\n");
            break ;
        }
        case 4:
        {
            OutputList(L);
            break;
        }
        case 5:
        {
            int x;
            printf("请输入您要查看的位置:\n");
            scanf("%d",&x);
            GetElem(L,x);
            break ;
        }
        case 6:
        {
            int x;
            printf("请输入您要查找的元素的值:\n");
            scanf("%d",&x);
            int b = LocateElem(L,x);
            if(b)   printf("查找成功!,是第%d个元素\n",b);
            else    printf("查找失败!没有这个元素\n");
            break ;
        }

        default:
            printf("输入错误,请重新输入:\n");
            break;
        }
    }
}

int main()
{
    SqList *L = NULL,l;         //生成静态顺序表实体'l'和指向该实体的指针'L'
    L = &l;                     //L ---> l
    InitList(L);                //初始化
    menu(L);
    return 0;
}