顺序表示的线性表——顺序表

一、定义

线性表是由n个类型相同的数据元素组成的有限序列,记为(a1,a2,...,ai-1,ai,ai+1,...,an)。

二、特点

逻辑上相邻的元素,在物理上也相邻。只要确定了第一个元素的起始位置,线性表的任一元素都可以随机存取,因此,线性表的顺序存储结构是一种随机存取的存储结构

三、存储结构

#define ListSize 100
typedef struct
{
    DataType list[ListSize];  //DataType表示数据类型,list用于存储线性表中的数据元素 
    int length; //length用来表示线性表中数据元素的个数 
}SeqList;  //结构体类型名 

如果要定义一个顺序表,代码如下:

SeqList L;

如果要定义一个指向顺序表的指针,代码如下:

SeqList *L;

四、基本运算

(1)初始化线性表

void InitList(SeqList *L)  //初始化线性表
{
    L->length=0;  //把线性表的长度置为0 
} 

(2)判断线性表是否为空

int InitEmpty(SeqList L)  //判断线性表是否为空,线性表为空返回1,否则返回0
{
    if(L.length==0)  //线性表的长度若为0
        return 1;  //返回1
    else
        return 0;  //返回0 
} 

(3)按照序号查找

int GetElem(SeqList L,int i,DataType *e)
//查找线性表中第i个元素。查找成功将该值返回给e,并返回1表示成功;否则返回-1表示失败
{
    if(i<1 || i>L.length)  //在查找第i个元素之前先判断该序号是否合法 
        return -1;
    *e=L.list[i-1];  //将第i个元素的值赋值给e* 
    return 1;
} 

(4)按内容查找

int LocateElem(SeqList L,DataType e)  //查找线性表中元素值为e的元素
{
    int i;
    for(i=0;i<L.length;i++)  //从第一个元素开始与e进行比较
        if(L.list[i]==e)  //若存在与e值相等的元素
            return i+1;  //返回该元素在线性表中的序号
    return 0;  //否则返回0 
} 

(5)插入操作

要在顺序表中的第i个位置上插入元素e,首先将第i个位置以后的元素依次向后移动1个位置,其次把元素e插入第i个位置。

int InsertList(SeqList *L,int i,DataType e)
//在顺序表的第i个位置插入元素e,插入成功返回1,如果插入位置不合法返回-1,顺序表满了就返回0
{
    int j;
    if(i<1 || i>L->length+1)  //在插入元素前,判断插入位置是否合法
    {
        printf("插入位置i不合法!\n");
        return -1;
    } 
    else if(L->length>=ListSize)  //在插入元素前,判断顺序表是否已经满,不能插入元素
    {
        printf("顺序表已满,不能插入元素。\n");
        return 0;
    } 
    else
    {
        for(j=L->length;j>=i;j--)  //将第i个位置以后的元素依次后移
            L->list[j]=L->list[j-1];
        L->list[i-1]=e;  //插入元素到第i个位置
        L->length=L->length+1;  //将顺序表长增1
        return 1; 
    }
} 

注:插入元素的位置i的合法范围应该是1<=i<=L->length+1。当i=1时,插入位置是在第一个元素之前;当i=L->length+1时,插入位置是最后一个元素之后。当插入位置是i=L->length+1时,不需要移动元素;当插入位置是i=0时,则需要移动所有元素。

(6)删除第i个元素

在进行删除操作时,先判断顺序表是否为空,如果不空,接着判断序号是否合法,如果不空且合法,则要将删除的元素赋给e,并把该元素删除,将表长减1。

int DeleteList(SeqList *L,int i,DataType *e)
{
    int j;
    if(L->length<=0)  //判断顺序表是否为空 
    {
        printf("顺序表已空不能进行删除\n");
        return 0;
    }
    else if(i<1 || i>L->length)  //判断序号是否合法 
    {
        printf("删除位置不合适!\n");
        return -1;
    }
    else
    {
        *e=L->list[i-1];
        for(j=i;j<=L->length-1;j++)
            L->list[j-1]=L->list[j];
        L->length=L->length-1;  //表长-1 
        return 1;
    }
}

注:删除元素的位置i的合法范围应该是1<=i<=L->length。当i=1时,表示要删除第一个元素,对应数据中的第0个元素;当i=L->length时,要删除的是最后一个元素。

(7)求线性表的长度

int ListLength(SeqList L)
{
    return L.length;
}

(8)清空顺序表

void ClearList(SeqList *L)
{
    L->length=0;
}

注:可将上述顺序表存储结构的定义及基本运算保存在一个头文件中,在使用时通过#include "  .h"引用这些基本运算即可。

五、示例

(1)分拆顺序表:左边的元素小于等于0,右边的元素大于等于0.

编写一个算法,把一个顺序表分拆成两个部分,使顺序表中不大于0的元素位于左端,大于0的元素位于右端。要求不占用额外的存储空间。例如顺序表(88,-9,-28,19,-31,22,-50,62,-76)经过分拆调整后变为(-76,-9,-28,-50,-31,22,19,62,88)。

算法思想:设置两个指示器 i 和 j,分别扫描顺序表中的元素,i 和 j 分别从顺序表的左端和右端开始扫描。如果 i 遇到小于等于0的元素,则略过不处理,继续向前扫描;如果遇到大于0的元素,则暂停扫描。如果 j 遇到大于0的元素,则略过不处理,继续向前扫描;如果遇到小于等于0的元素,则暂停扫描。如果 i 和 j 都停下来,则交换 i 和 j 指向的元素。重复执行直到 i >= j 为止。

#include <stdio.h>
#include <stdlib.h>
#define ListSize 200
typedef int DataType;
#include "SeqList.h"
void SplitSepList(SeqList *L);
void main()
{
    int i,flag,n;
    DataType e;
    SeqList L;
    int a[]={88,-9,-28,19,-31,22,-50,62,-76};
    InitList(&L);                //初始化顺序表l
    n=sizeof(a)/sizeof(a[0]);
    for(i=1;i<=n;i++)   //将数组a的元素插入顺序表L中
    {
        if(InsertList(&L,i,a[i-1])==0)
        {
            printf("位置不合法");
            return;
        }
    }
    printf("顺序表L中的元素:\n");
    for(i=1;i<=L.length;i++)  //输出顺序表L中的每个元素
    {
        flag=GetElem(L,i,&e);  //返回顺序表L中的每个元素到e中
        if(flag==1)
            printf("%4d",e);
    }
    printf("\n");
    printf("顺序表L调整后(左边元素小于等于0,右边元素大于等于0):\n");
    SplitSepList(&L);   //调整顺序表
    for(i=1;i<=L.length;i++)  //输出调整后顺序表L中所有元素
    {
        flag==GetElem(L,i,&e);
        if(flag==1)
            printf("%4d",e);
    }
    printf("\n");
}

void SplitSepList(SeqList *L)
{
    int i,j;  //定义两个指示器 i 和 j
    DataType e;
    i=0;j=(*L).length-1;  //指示器 i 和 j 分别指示顺序表的左端和右端元素
    while(i<j)
    {
        while(L->list[i]<=0)  //i 遇到小于等于0的元素
            i++;  //略过
        while(L->list[j]>0)  //j 遇到大于0的元素
            j--;   //略过
        if(i<j)   //交换 i 和 j 指向的元素
        {
            e=L->list[i];
            L->list[i]=L->list[j];
            L->list[j]=e;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-和为S的两个数字

题目描述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。 输出描述: 对应每...

3264
来自专栏Java大联盟

Java面试手册:集合框架

2453
来自专栏LinkedBear的个人空间

唠唠SE的集合-01——Collection接口

当集合中存储的对象类型不同时,那么会导致程序在运行的时候的转型异常,所以jdk1.5加入了泛型机制。

682
来自专栏Java帮帮-微信公众号-技术文章全总结

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&正则【悟空教程】

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&简单正则表达式【悟空教程】

1022
来自专栏向治洪

java 之容器

在Java中,我们想要保存对象可以使用很多种手段。我们之前了解过的数组就是其中之一。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们...

2478
来自专栏云霄雨霁

查找----基于有序数组

1680
来自专栏Bingo的深度学习杂货店

Q35 Search Insert Position

Given a sorted array and a target value, return the index if the target is found...

2937
来自专栏AILearning

Map集合

Collection |--List:元素是有序的,元素可以重复,因为该集合体系有索引 |--ArrayList:底层的数据结构使用的是数据结构。特点:查询...

2386
来自专栏用户2442861的专栏

Java中如何遍历Map对象的4种方法

既然java中的所有map都实现了Map接口,以下方法适用于任何map实现(HashMap, TreeMap, LinkedHashMap, Hashtabl...

1061
来自专栏海说

16、Collection接口及其子接口Set和List(常用类LinkedList,ArrayList,Vector和Stack)

16、Collection接口 Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(...

2260

扫码关注云+社区

领取腾讯云代金券