【数据结构】线性表基本运算的实现


【数据结构】线性表基本运算的实现

关于数据结构中线性表的顺序表示的基本运算的实现。

/*
  author:Ab4nd0n
  Time:2021-3-11
*/

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

#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5

typedef int ElemType;
typedef struct
{
    int n;              //元素个数
    int maxlength;      //最大允许长度
    ElemType *element;  //指针变量
} SeqList;

typedef int Status; //自定义类型

//初始化
/*
为顺序表L动态分配一维数组
若动态分配一维数组失败则返回ERROR(0)
*/
Status Init(SeqList *L,int mSize)
{
    L->n=0;
    L->maxlength=mSize;
    L->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
    if(!L->element)  
    {
        return ERROR;
    }
    return OK;
}

//顺序表的查找(查找元素ai的值,直接定位下标)
/*
首先判断传入的下标i是否越界(0~n-1)
若未越界,则取出element[i]的值传给x返回

算法复杂度为O(1)
*/
Status Find(SeqList *L,int i)
{
    int x;
    if(i<0||i>L->n-1)
    {
        return ERROR;
    }
    return x=L->element[i]

}

//顺序表的插入(在ai之后插入,即ai+1的位置)
/*
判断下标i是否越界 (-1~n-1)
判断顺序表存储空间是否已满
将元素ai+1~an-1依次向后移动一个位置
将要插入元素赋值给element[i+1]
表长+1

算法复杂度为O(n)
*/
Status Insert (SeqList *L, int i,ElemType x)
{
    int j;
     if(i<-1||i>L->n-1)  //注意此处i的范围 是<-1 不是0  !!!
    {
        return ERROR;
    }
    if(L->n==L->maxlength)   //判满
    {
        return ERROR;
    }
    for(j=L->n-1;j>i;j--)       //通过循环将下标i+1到n-1的元素后移(从后往前)
    {
        L->element[j+1]=L->element[j];   //注意是j的值给j+1(从后往前)
    }
    L->element[i+1]=x; //把插入的 元素放到下标为 i+1 的位置
    L->n=L->n+1;      //表长加1
    return OK;

}

//顺序表的删除
/*
判断下标是否越界(0~n-1)
判断顺序表是否为空
将元素ai+1~an-1依次前移一个位置
表长-1

算法复杂度为O(n)
*/
Status Delete(SeqList *L,int i)
{
    int j;
    if(i<0||i>L->n-1)  return ERROR;  //此处i<0!!!注意和插入区分
    if(!L->n)  return ERROR;    //判空
    for(j=i+1;j<L->n;j++)
    {
        L->element[j-1]=L->element[j];  //从前往后逐个前移元素,j的值给j-1
    }
    L->n--;    //表长-1
    return OK;
    
}

//顺序表的输出
Status Output(SeqList *L)
{
    int i;
    if(!L->n)   return ERROR;   //判空
    for(i=0;i<L->n;i++)
    {
        printf("%d",L->element[i]);
    }
    printf("\n\n");
     return OK;
}

//顺序表的销毁
void Destroy(SeqList *L)
{
    L->n=0;
    L->maxlength=0;
    free(L->element);
    printf("Sucessfuly Destroy!\n");
}


int main()
{
    int i,k;
    SeqList List;
    k=Init(&List,10); //因为Init函数的形参是指针变量(地址),所以这里要用取地址符!!!
    printf("%d\n\n",k);   //测试返回值为 1
    for(i=0;i<10;i++)
    {
        Insert(&List,i-1,i);  //执行插入操作
    }
    Output(&List);    // 0123456789
    Delete(&List,2);
    Output(&List);    // 013456789
    Destroy(&List);   // Sucessfuly Destroy!
}

文章作者: Ab4nd0n
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Ab4nd0n !
评论
 上一篇
【数据结构】单链表的基本运算实现 【数据结构】单链表的基本运算实现
【数据结构】单链表的基本运算实现 关于数据结构中线性表的链接表示的基本运算的实现,把书上单链表的代码敲了一遍,加了些注释。 /* author:Ab4nd0n Time:2021-3-11 */ #include <std
2021-03-12
下一篇 
阿里云CDN加速域名解析冲突问题 阿里云CDN加速域名解析冲突问题
自己的个人博客搭建了也有一段时间了,以前部署在Gitee上访问速度还行,后来部署到GitHub后速度是一天不如一天了,于是想看看能不能加速一下,看了看网上的做法,我选择采用CDN加速域名。 首先,你需要将域名进行备案,备案完成后才能进行后
2020-10-11 Ab4nd0n
  目录