首页 > 其他分享 >线性表的顺序存储

线性表的顺序存储

时间:2023-01-30 15:26:23浏览次数:36  
标签:线性表 int elem length SqList 顺序存储

线性表的顺序存储

线性表的顺序表示又称为顺序存储结构或顺序映像

顺序存储:把逻辑上相邻的数据元素(类型相同)存储在物理上相邻(中间没有空出存储单元,占用一片连续的存储空间)的存储单元中的存储结构;逻辑位序与物理位序相差1

  • 优:
    • 任一元素可以随机存取
    • 存储密度大
  • 缺:
    • 属于静态存储形式,元素个数不能自由扩充
    • 插入、删除某一元素时需要移动大量元素
    • 浪费存储空间

(a1 , a2 , a3 , ... , ai-1 , ai , ai+1 , ... ,an)

n为元素个数即表长,当n=0时为空表

线性表的第一个元素a1的存储位置成为线性表的起始地址基地址

假设线性表的每个元素需要占用l个存储单元,则元素的存储位置满足:LOC(ai)=LOC(a1)+(i-1)l


例:26个英文字母组成的英文表

(A , B , C , ... , Z)

元素都是字母,元素间是线性关系(有一个前驱、一个后继,都是一对一的)


一元多项式的计算:

线性表R=(p0+q0,p1+q1,p2+q2,p3+q3,...,pm+qm,pm+1 + qm+1)

稀疏多项式的计算:线性表P=((p1,e1),(p2,e2),(p3,e3),..., (pm,em))

例:

A(x)=7+ 3x+9x^8 +5x^17      B(x)=8x+22x^7 -9x^8

下标i 0 1 2 3
系数a[i] 7 3 9 5
指数 0 1 8 7

下标i 0 1 2
系数b[i] 8 22 -9
指数 1 7 8

线性表A=((7,0),(3,1),(9,8),(5,7))

线性表B=((8,1),(22,7),(-9,8))

创建一个新的数组C,分别重头遍历A、B的每一项:若指数相同则和相加不为0就在C中添新项指数不同将指数较小的项赋值到C中 ;一个多项式已遍历完毕,将另一个依次复制到C中即可


顺序表顺序存储结构定义

#define MAXSIZE 1000

typedef struct{
    float p;    //系数
    int e;      //指数
} Polynomial;

typedef struct {
    Polynomial *elem;   //存储空间的基地址
    int length;     //多项式中当前项的个数
}SqList;

用一维数组名表示顺序表,但线性表长可变,数组长度不可动态定义;因此可以用一变量表示顺序表的长度属性

数组静态分配:

#define List_Size 100   //线性表存储空间的初始分配量

typedef struct{
    int elem[List_Size];
    int lenth;  //当前长度
} SqList;

数组动态分配:用malloc动态分配空间

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100		//线性表存储空间的初始分配量

typedef struct {
    int *elem;
    int length;
}SqList;


int main(void)
{
    SqList L;
    L.elem=(int *)malloc(sizeof(int)*MAXSIZE);
  	free(L.elem);
}

线性表顺序存储的初始化

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct{
    int *elem;
    int length;
} SqList;


int InitList_Sq(SqList *L){  //构造一个空的顺序表
    L->elem=(int *)malloc(sizeof(int)*MAXSIZE);  //为顺序表分配空间
    if(!L->elem) printf("failed");      //存储分配失败
    L->length=0;					//表长为0
    return 1;
}
int main(void)
{
    SqList L;
    InitList_Sq(&L);
    printf("successful");
    free(L.elem);
}

线性表顺序存储的销毁

void DestroyList(SqList *L){
    if(L->elem){
        free(L->elem);                      //释放存储空间
    }
}

线性表顺序存储的清空

void ClearList(SqList *L){
    L->length=0;                            //线性表长置0
}

获取线性表顺序存储的长度

int GetLength(SqList L){
    return L.length;
}

判断线性表是否为空

int IsEmpty(SqList L){
    if(L.length==0){
        return 1;
    }
    else return 0;
}

线性表顺序存储的取值(随机存取)

int GetElem(SqList L,int i,int *e){
    if(i<1||i>L.length) return 0;       //判断i值是否合理
    e=L.elem[i-1];                      //第i-1单元存着第i个元素
    return 1;
}

线性表顺序存储的按值查找

int LocateElem(SqList L,int e){
    for (int i = 0; i <L.length ; i++) {
        if(L.elem[i]==e){
            return i+1;
        } 
    }
    return 0;
}

其基本语句执行次数与输入有关;平均时间复杂度O(n)

平均查找长度ASL:为确定记录在表中的位置,需要与给定值进行比较的关键字的个数的期望值

image


线性表顺序存储的插入

  • 插入在最后
  • 插入在中间
  • 插入在最前
  • 判断插入位置是否合法;存储空间是否已满
int ListInsert_Sq(SqList *L,int i,int e){
    if(i<1||i>L->length+1){
        return 0;
    }
    if(L->length==MAXSIZE){
        return 0;
    }
    for (int j = L->length-1; j >=i-1 ; j--) {
        L->elem[j+1]=L->elem[j];
    }
    L->elem[i-1]=e;
    L->length++;
}

平均时间复杂度O(n)


线性表顺序存储的删除元素

int ListDelete_Sq(SqList *L,int i){
    if(i<1||i>L->length) return 0;
    for (int j = i; j <L->length ; j++) {
        L->elem[j-1]=L->elem[j];
    }
    L->length--;
    return 1;
}

平均时间复杂度O(n)

标签:线性表,int,elem,length,SqList,顺序存储
From: https://www.cnblogs.com/yuanyu610/p/17076030.html

相关文章

  • 线性表
    线性表线性表是具有相同特性的数据元素的一个有限序列;是一种典型的线性结构线性表的两种存储结构:顺序存储结构链式存储结构抽象数据类型线性表抽象数据类型线性......
  • 线性表之堆栈
    什么是堆栈像叠盘子一样,先放下的在下面,先拿出来的却是最上面的,也就是,先进去的最后才出来先进后出的就是堆栈堆栈的操作生成空堆栈,其最大长度为MaxSize判断堆栈S是......
  • 线性表之队列
    目录什么是队列大众化专业性队列的操作集队列的链式存储实现链表结构体初始化删除并返回队头数据元素其他操作什么是队列大众化最常见的队列就是排队假设超市送鸡蛋......
  • 数组描述线性表(C++实现)
    线性表也称有序表,其每一个实例都是元素的一个有序集合抽象类linearList一个抽象类包含没有实现代码的成员函数,这样的成员函数称为纯虚函数,用数字0作为初始值来说明templ......
  • 第二章 线性表(上)
    一、线性表的定义及具体操作1.定义线性表(LinearList)是具有相同数据类型的n(n≥0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,则其一般表......
  • 线性表算法相关练习
    //将两个递增的有序链表合并为一个递增的有序链表。//要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据。#include<iostream>#......
  • 线性表的顺序表示
    顺序表的定义线性表的顺序存储又称顺序表.它是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使逻辑上相邻的两个元素在物理位置上也相邻。publicclassInitL......
  • C++实现线性表-顺序表的合并操作代码
    #include<iostream>#include<cstdlib>//C++动态分配存储空间usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemtype;typedefintStat......
  • 线性表之链式存储
    目录初始化一个空线性表空链式表的抽象表达查找按序号按值在位序i前插入一个新元素X删除指定位序i的元素返回线性表L的长度n吐槽初始化一个空线性表空链式表的抽象表达/......
  • 线性表
    1.定义和分类1.线性表是具有相同数据类型n个数据元素的有限序列,n为表长,其表示为:L=(a1,a2,a3,...,an),是最基本,最常见的一种数据结构2.前驱元素和后驱元素:若A元素在......