Code,  Study,  Tech

顺序表实现-C

在头文件里进行表的结构体定义及相关函数操作的声明,为便于统一,将数组第一个元素s[0]闲置不用。实现最主要的插入元素,删除元素及按值查找功能。

  • SqList.h源码:
#include <stdio.h>

#define MAXLEN 100

/*为便于统一,将数组第一个元素s[0]闲置不用*/

typedef int ElemType;

typedef struct
{
    ElemType s[MAXLEN];
    int len;
}SqList;

//在线性表的inst_pst插入值为inst_vl的新元素
int DeleteSqList(SqList *sql, int i, ElemType *x);
//删除顺序表中第i个元素,用指针参数x返回其值
int InsertSqList(SqList *sql, int i, ElemType x);
//在线性表中查找值为x的元素,若找到,返回其下标
int SearchSqList(SqList sql, ElemType x);

/***插入函数***/
int InsertSqList(SqList *sql, int i, ElemType x)
{
    //Step1: 判断插入位置是否合法

     /*插入位置在第一个到最后一个后一个位置之间
      *即共有 len+1 个可插入点 */
    if((i < 1) || (i > sql -> len + 1))
    {
        printf("提示:插入位置%d不合法!\n", i);
        return 0; //插入失败,返回0
    }

     /*判断表的状态是否已满,若已满,无法执行插入*/
     if(sql -> len >= MAXLEN) //表长len在0~MAXLEN之间
     {
         printf("提示:表已满,无法插入!\n");
         return 0;  //插入失败,返回0
     }

    //Step2: 从后向前遍历

     /*依次往后移动元素,腾出位置给i号*/
     for(int j = sql -> len; j >= i; j--)
        {
            sql -> s[j + 1] = sql -> s[j];
        }
     sql -> s[i] = x; //将x放到第i号位置上

    //Step3:使表长加1
     (sql -> len) ++;

     return 1; //插入成功,返回1
}

/***删除函数***/
int DeleteSqList(SqList *sql, int i, ElemType *x)
{
    //i的合法取值为1~sql.len
    if( (i < 1) || (i > sql->len))
    {
        printf("提示:删除位置不合法!\n");
        return 0;
    }

    //保存删除元素到x
    *x = sql->s[i];

    //将删除元素位置i后面的元素依次前移
    for(int j = i + 1; j <= sql -> len; j++)
    {
        sql -> s[j - 1] = sql -> s[j];
    }

    //将表长减1
    (sql -> len)--;

    return 1;
}

/***查找函数***/
int SearchSqList(SqList sql, ElemType x)
{
    int i;
    for(i = 1; i <= sql.len; i++)
    {
        if(sql.s[i] == x)
            return i;
    }

    return 0; //退出循环,则查找失败
}

在main函数中进行建表及测试。

  • SqL_main.c源码:
#include <stdio.h>
#include "SqList.h"

int main()
{
    SqList *seq; //初始化表
    seq = (SqList*)malloc(sizeof(SqList));
    int s_len; //表长

    //读入表长
    printf("/***请输入线性表的长度:***/\n");
    scanf("%d", &s_len);
    seq -> len = s_len;

    //依次读入1~len相应位置的元素
    printf("/***请输入各元素的值:***/\n");
    for(int i = 1; i <= seq -> len; i ++)
    {
        scanf("%d", &seq -> s[i]);
    }
    printf("||表已创建完成!\n");

    int op_id; //操作序号
    printf("/***请选择你想执行的操作(输入对应数字):***/\n");
    printf("/***1.插入元素***/\n");
    printf("/***2.删除元素***/\n");
    printf("/***3.按值查找***/\n");
    scanf("%d", &op_id);

    switch(op_id)
    {

    /**1->插入**/
    case 1:
        {
        printf("----------执行插入元素----------\n");
        //读取插入元素信息
        int inst_pst; //插入位置
        int inst_vl; //插入值
        printf("/***请输入要插入的位置:***/\n");
        scanf("%d", &inst_pst);
        printf("/***请输入要插入元素的值:***/\n");
        scanf("%d", &inst_vl);

        //执行插入
        InsertSqList(seq, inst_pst, inst_vl);

        //输出插入后的结果
        printf("/***插入后的线性表:***/\n");
          for(int i = 1; i <= seq -> len; i ++)
        {
            printf("%d ", seq -> s[i]);
        }
        }
        break;

    /**2->删除**/
    case 2:
        {
        printf("----------执行删除元素----------\n");
        int *del_elem = (int*)malloc(sizeof(int)); //用于保存删除元素
        int del_pst; //删除元素位置
        printf("/***请输入要删除元素的位置:***/\n");
        scanf("%d", &del_pst);
        //执行删除
        DeleteSqList(seq, del_pst, del_elem);
        printf("||删除元素的值为:%d \n", *del_elem);

        //输出删除后结果
        printf("/***删除第%d个元素后的线性表为:***/\n", del_pst);
           for(int i = 1; i <= seq -> len; i ++)
        {
            printf("%d ", seq -> s[i]);
        }
        }
        break;


    /**3->查找**/
    case 3:
        {
             printf("----------执行按值查找----------\n");
             int sc_key;
             printf("/***请输入要查找元素的值:***/\n");
             scanf("%d", &sc_key);
             //执行查找
             if(SearchSqList(*seq, sc_key))
             {
                 printf("||查找成功:值为%d的元素在第%d个位置\n",
                        sc_key, SearchSqList(*seq, sc_key));
             }
            else
                printf("||查找失败:未找到值为%d的元素\n",sc_key);
        }
        break;
    }

    return 0;
}
  • 测试输出:
    /***请输入线性表的长度:***/
    5
    /***请输入各元素的值:***/
    2 4 6 8 23
    ||表已创建完成!
    /***请选择你想执行的操作(输入对应数字):***/
    /***1.插入元素***/
    /***2.删除元素***/
    /***3.按值查找***/
    .................................................................
    1
    ----------执行插入元素----------
    /***请输入要插入的位置:***/
    3
    /***请输入要插入元素的值:***/
    5
    /***插入后的线性表:***/
    2 4 5 6 8 23
    .................................................................
    2
    ----------执行删除元素----------
    /***请输入要删除元素的位置:***/
    5
    ||删除元素的值为:23
    /***删除第5个元素后的线性表为:***/
    2 4 6 8
    .................................................................
    3
    ----------执行按值查找----------
    /***请输入要查找元素的值:***/
    5
    ||查找失败:未找到值为5的元素
    .................................................................
    3
    ----------执行按值查找----------
    /***请输入要查找元素的值:***/
    8
    ||查找成功:值为8的元素在第4个位置

     

发表评论

电子邮件地址不会被公开。 必填项已用*标注