数据结构——线性表——顺序表及C语言实现

数据结构——线性表——顺序表及C语言实现,第1张

目录

一、基础知识

二、顺序表的定义与初始化

1、静态分配(static allocation)

2、动态分配(dynamic allocation) 

三、顺序表的基本 *** 作(增删改查)

1、插入 *** 作

2、删除 *** 作

3、按位查找

4、按值查找

一、基础知识

一般线性表是线性结构的一种,属于数据的逻辑结构顺序存储是一种数据的存储结构。顺序表则是采用顺序存储一般线性表,并且有相应的运算和 *** 作,满足了数据结构的三要素。因此顺序表是一种数据结构。

二、顺序表的定义与初始化

静态分配时,顺序表的大小和空间在定义时就已经固定,一旦空间占满,有新数据加入时就会产生溢出;动态分配时,存储数据的空间是由动态存储分配语句分配的,可按照实际需要扩充存储空间,不需要一次性划分所有空间,造成浪费。

1、静态分配(static allocation)

静态顺序表的核心是一个静态数组。

#include 

typedef int ElemType;        //这里的分号第一次敲的时候漏掉了,ElemType敲成了Element
                             //此处int可替换为任意的数据类型,以满足存储类型不同的顺序表

//Defines the maximum length of the linear table 定义线性表最大长度,一旦确定不可改变
#define MaxSize 50           //第一次MaxSize和50的位置写反了                     

typedef struct{
    ElemType data[MaxSize]; 
    int length;
}SqList_s;                    //static

//初始化静态顺序表
void InitList(SqList &L)
{
    for(int i=0; i
2、动态分配(dynamic allocation) 

动态顺序表的核心其实是一个动态数组,其头指针为data。在初始化动态顺序表的时候会给头指针malloc一片连续的内存空间(大小为InitSize);所谓的动态增加长度其实是将这个头指针指向一片新malloc出的、更长的连续内存空间,在完成数据迁移后,原空间就free掉。

#include 
#include         //malloc的头文件

typedef int ElemType;

#define InitSize 20        //初始长度,仅在第一次分配时用了一次,后面 *** 作都用MaxSize

typedef struct{
    ElemType *data;           
    int MaxSize;
    int length;
}SqList_d;                    //dynamic,分号别漏掉

//初始化动态顺序表
void InitList(SqList_d L)
{
    L.data=(ElemType *)malloc(InitSize*sizeof(ElemType));
    L.length=0;
    L.MaxSize=InitSize;
}

//增加动态顺序表的长度
void IncreaseSize(SqList_d &L,int len)
{
    ElemType *p=L.data;
    L.data=(ElemType *)malloc((L.MaxSize+len)*sizeof(ElemType));
    for(int i=0; i
三、顺序表的基本 *** 作(增删改查) 1、插入 *** 作

静态顺序表的插入函数:bool ListInsert(SqList_s &L, int i, ElemType e),对表L执行插入 *** 作,i 表示插入位置(1 <= i <= length+1),e 为待插入的元素,返回bool值表示插入成功或失败。

bool ListInsert(SqList_s &L, int i, ElemType e)
{
    if(i<1 || i>L.length + 1)                //判断i是否合法
        return false;
    if(L.length >= L.MaxSize)                //判断表是否已满
        return false;
    for(int j = L.length; i <= j; j--)       //从位置i开始元素依次后移,为插入元素空出位置
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;                         //插入元素e
    L.length++;
    return true;
}
2、删除 *** 作

静态顺序表的删除函数:bool ListDelete(SqList_s &L, int i, ElemType e),对表L执行删除 *** 作,i 表示待删除元素的位置(1 <= i <= length),用 e 返回被删除的元素,返回bool值表示删除成功或失败。

bool ListDelete(SqList_s &L, int i, ElemType &e)
{
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1];
    for(int j = i; j < L.length; j++)      //填补空缺,从第i+1位开始集体前移
        L.data[j-1] = L.data[j];
    L.length--;                            //更新长度,第一次敲漏掉了
    return true;
}
3、按位查找

静态顺序表的按位查找函数:bool GetElem(SqList_s L, int i, ElemType &e),对表L执行按位查找 *** 作,i 表示待查的位置(1 <= i <= length),用 e 返回该位置的元素,返回bool值表示查找成功或失败。

bool GetElem(SqList_s L, int i, ElemType &e)
{
    if(i<1 || i>L.length)
        return false;
    e = L.data[i-1];
    return true;
}
4、按值查找

静态顺序表的按值查找函数:bool Locate(SqList_s L, ElemType e, int &i),对表L执行按值查找 *** 作,e 表示待查的值,用 i 返回该位置,返回bool值表示查找成功或失败。

bool Locate(SqList_s L, ElemType e, int &i)
{
    for(int j = 0; j < L.length; j++)
        if(e == L.data[j])
        {
            i=j+1;
            return true;
        }
    return false; 
}

修改函数在查找函数的基础上稍作修改即可。

动态顺序表的 *** 作与静态类似,只需将SqList_s改为SqList_d。

参考书目:王道数据结构考研复习指导

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/713832.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-24
下一篇 2022-04-24

发表评论

登录后才能评论

评论列表(0条)