美文网首页算法与数据结构
算法与数据结构系列之[线性表的顺序存储结构]

算法与数据结构系列之[线性表的顺序存储结构]

作者: 秦老厮 | 来源:发表于2019-04-24 22:13 被阅读6次

说到线性表的顺序存储结构，我们平时最常用的数组就是顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素。说的通俗一点，就是需要为数组在内存中开辟连续的存储空间。这样连续的存储结构也是优缺点非常明显的，因为数组元素的存储地址是连续的，所以查询起来就很方便，通过数组元素的下标就可以查询到任意的数组元素，且查询的时间复杂度为O(1),对于大数据量的查询性能优势很明显，这也是随机存取的好处。但是数组元素的插入和删除操作的缺点也就很突出了，每插入和删除一个元素，就需要将从该位置起所有的元素向后或向前移动。在最好的情况下，如果元素要插入到最后一个位置，或者删除最后一个元素，此时的时间复杂度为O(1)。最坏的情况是，如果元素要插入到第一个位置或是删除第一个元素，此时的时间复杂度就是O(n)了，插入到第i个位置的平均时间复杂度也是O(n),可以得出数组的插入和删除操作的时间复杂度就是O(n)，所以对于大数据量的数组频繁的插入和删除操作，这样的性能消耗也是很大的，此时使用链表就比使用数组更合适。

C语言代码（IDE使用的是CLion,至于IDE的配置，大家可以网上找找，不懂的地方可以关注我的微信公众号：源码复兴号，加我微信联系我）：
1、SqList.c

#define INITSIZE 100  //线性表存储空间的初始分配量
#define OK 1
#define ERROR 0
#define LISTINCREMENT 10 //线性表存储空间的分配增量
#define TRUE 1
#define FALSE 0


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


typedef int ElementType;
typedef int Status;


typedef struct {
    ElementType *data;  //声明了一个名为data的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表分配的存储容量
}SqList;
/**
* 初始化顺序表
* @param L
* @return
*/
Status  InitList(SqList *L){
    L->data = (ElementType *)malloc(INITSIZE* sizeof(ElementType));  //分配存储空间为100
    if(!L->data) exit(0); //存储分配失败
    L->length = 0; //初始线性表长度为0
    L->size = INITSIZE; //初始存储容量
    return OK;
}


/**
* 查询第i个位置的元素值，并用e返回
* @param L
* @param i
* @param e
* @return
*/
Status GetElem(SqList L,int i,ElementType *e){
    if(L.length==0 || i<1 || i>L.length)
        return ERROR;
    *e=L.data[i-1];
    return OK;
}


/**
* 在第I的位置插入元素
* @param L
* @param i
* @param e
* @return
*/
Status ListInsert(SqList *L,int i,ElementType e){
    int k;
    if(i<1 || i>L->length+1) //当i不在范围内
        return ERROR;
    if(L->length >= L->size){    //当前的存储空间已满时，增加内存分配
        L->data =(ElementType *)realloc(L->data,(L->size+LISTINCREMENT)* sizeof(ElementType));
        if(!L->data)  //存储分配失败
            exit(0);
        L->size += LISTINCREMENT; //增加存储容量
    }
    if(i<=L->length){
        for (int k = L->length-1; k >=i-1 ; k--) {
            L->data[k+1]=L->data[k];
        }
    }
    L->data[i-1]=e;
    L->length++;
    return OK;
}


/**
* 删除线性表中第i个位置的元素
* @param L
* @param i
* @param e
* @return
*/
Status ListDelete(SqList *L,int i,ElementType *e){
    int k;
    if(L->length == 0)
        return ERROR;
    if(i<1 || i>L->length)  //i的值不合法
        return ERROR;
    *e=L->data[i-1];
    if(i<L->length){
        for (int k = i; k < L->length; k++) {
            L->data[k-1] = L->data[k];
        }
    }
    L->length--;
    return OK;
}


/**
* 判断线性表是否为空
* @param list
* @return
*/
Status ListEmpty(SqList list){
    if(list.length == 0)
        return TRUE;
    return FALSE;
}


/**
* 清空线性表，将线性表L置为一个空表
* @param L
* @return
*/
Status ClearList(SqList *L){
    L->length = 0;
    return OK;
}


/**
* 销毁线性表，释放内存
* @param L
* @return
*/
Status DestroyList(SqList *L){
    if(L->data){
        free(L->data);
        L->data = NULL;
        L->size =0;
        return TRUE;
    }
    return FALSE;
}


/**
* 返回线性表中元素个数
* @param L
* @return
*/
int ListLength(SqList L){
    return L.length;
}


/**
* 返回线性表的内存容量
* @param L
* @return
*/
int ListSize(SqList L){
    return L.size;
}


/**
* 遍历打印线性表元素
* @param L
*/
void DisplayList(SqList L){
    for (int i = 0; i < L.length; i++) {
        printf("%d ",L.data[i]);
    }
}

2、SqList.h

#ifndef TEST_SQLIST_H
#define TEST_SQLIST_H
typedef int ElementType;
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0


typedef struct {
    ElementType *data;  //声明了一个名为data的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表分配的存储容量
}SqList;


//初始化线性表
Status  InitList(SqList *L);


//查询第i个位置的元素
Status GetElem(SqList L,int i,ElementType *e);


//添加元素
Status ListInsert(SqList *L,int i,ElementType e);


//删除元素
Status ListDelete(SqList *L,int i,ElementType *e);


//判断线性表是否为空
Status ListEmpty(SqList list);


//清空线性表，将线性表L置为一个空表
Status ClearList(SqList *L);


//销毁线性表，释放内存
Status DestroyList(SqList *L);


//返回线性表中元素个数
int ListLength(SqList L);


//返回线性表的内存容量
int ListSize(SqList L);


//遍历打印线性表元素
void DisplayList(SqList L);
#endif //TEST_SQLIST_H

3、main.c

#include <stdio.h>
#include "src/hello.h"
#include "src/data/SqList.h"
int main() {
    //初始化一个具有20个元素的线性表
    SqList list;
    InitList(&list);
    for (int i = 1; i <=20 ; i++) {
        list.data[i-1]=i;
        list.length++;
    }


    //遍历线性表
    DisplayList(list);
    printf("\n");


    //输出线性表的长度，即线性表元素个数
    printf("%d",ListLength(list));
    printf("\n");


    //线性表是否为空
    printf("%d",ListEmpty(list));
    printf("\n");


    //打印线性表中第三个位置的元素
    int num ;
    int *n =&num;
    GetElem(list,3,n);
    printf("%d",*n);
    printf("\n");


    //给线性表添加一个元素，并重新遍历
    ListInsert(&list,5,30);
    DisplayList(list);
    printf("\n");


    //删除线性表指定位置的元素，并重新遍历,并打印出将要删除的元素
    int delete;
    int *d = &delete;
    ListDelete(&list,10,d);
    printf("%d",*d);
    printf("\n");
    DisplayList(list);
    printf("\n");


    //清空线性表
    ClearList(&list);
    DisplayList(list);  //此次遍历线性表中已经没有元素
    printf("\n");
    printf("%d",ListLength(list));  //元素个数为0
    printf("\n");
    printf("%d",ListSize(list));  //此时给线性表分配的内存容量还为100
    printf("\n");


    //销毁线性表,并释放内存
    int result = DestroyList(&list);
    DisplayList(list);  //此次遍历线性表中已经没有元素
    printf("\n");
    printf("%d",ListLength(list));  //元素个数为0
    printf("\n");
    printf("%d",ListSize(list));  //此时给线性表分配的内存容量0
    printf("\n");
    return 0;
}

4、运行结果

D:\WorkSpace\CLProject\test\cmake-build-debug\test.exe
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
0
3
1 2 3 4 30 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
9
1 2 3 4 30 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20


0
100


0
0


Process finished with exit code 0

java代码:

public class Array<E>{
    private E[] data;
    private int size;

    /**
     * 构造函数，传入数组容量capacity构造array
     * @param capacity
     */
    public Array(int capacity){
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无参构造，数组的容量默认为100
     */
    public Array(){
        this(10);
    }

    public Array(E[] arr){
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
    }
    /**
     * 获取数组的元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 获取数组容量
     * @return
     */
    public int getCapacity(){
        return data.length;
    }

    /**
     * 判断数组是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 向数组指定位置插入元素
     * @param index
     * @param e
     */
    public void add(int index,E e){
        if(index<0 || index>size){
            throw  new IllegalArgumentException("下标越界");
        }
        if(size == data.length){
            resize(2*data.length);
        }
        for(int i=size-1;i>=index;i--){
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;
    }

    /**
     * 向数组的第一个位置添加元素
     * @param e
     */
    public void addFirst(E e){
        add(0,e);
    }

    /**
     * 向数组的最后一个位置添加元素
     * @param e
     */
    public void addLast(E e){
        add(size,e);
    }

    /**
     * 当数组容量已满时自动扩容2倍
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i <size ; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 向数组中插入元素
     * @param e
     */
    public void add(E e){
        add(size,e);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n",size,data.length));
        res.append("[");
        for (int i = 0; i <size ; i++) {
            res.append(data[i]);
            if(i != size-1){
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }

    /**
     * 查询指定位置的数组元素
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("传入的数组索引值不合法");
        }
        return data[index];
    }

    /**
     * 查询数组的第一个元素
     * @return
     */
    public E getFirst(){
        return get(0);
    }

    /**
     * 查询数组的最后一个元素
     * @return
     */
    public E getLast(){
        return get(size-1);
    }

    /**
     * 修改数组指定位置的元素
     * @param index
     * @param e
     */
    public void set(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("传入的数组索引值不合法");
        }
        data[index] = e;
    }

    /**
     * 查询数组中是否包含某个元素e
     * @param e
     * @return
     */
    public boolean contains(E e){
        for (int i = 0; i <size; i++) {
            if(data[i] == e){
                return true;
            }
        }
        return false;
    }

    /**
     * 查询并返回某个元素e的下标
     * @param e
     * @return
     */
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if(data[i] == e){
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除指定索引值的元素，并返回该元素
     * @param index
     * @return
     */
    public E remove(int index){
        if(index<0 || index>size){
            throw  new IllegalArgumentException("所传入的数组索引值不合法");
        }
        E ret = data[index];
        for (int i = index + 1; i <size ; i++) {
            data[i-1] = data[i];
        }
        data[--size] = null;
        if(size == data.length/4 && data.length/2 !=0){
            resize(data.length/2);
        }
        return ret;
    }

    /**
     * 删除数组的第一个元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除数组的最后一个元素
     * @return
     */
    public E removeLast(){
        return remove(size-1);
    }

    /**
     * 从数组中删除元素e
     * @param e
     */
    public boolean removeElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
            return true;
        }
        return false;
    }

    /**
     * 数组元素交换
     * @param i
     * @param j
     */
    public void swap(int i,int j){
        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("非法索引");
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;

    }
}

微信公众号：


点点关注。点关注，不迷路

相关文章

  • 数据结构之线性表的链式存储结构

    之前写了线性表的顺序存储结构和有序线性表的顺序存储结构,今天接着写线性表的链式存储结构 数据结构之线性表的顺序存储...

  • 数据结构与算法 - 线性表

    这里我们只介绍线性表中 存储结构不同的 顺序表 和 链表，以及操作受限的 栈 和 队列 。 数据结构与算法系列文章...

  • # 数据结构和算法系列1 线性表之顺序表

    阅读目录 什么是线性表线性表的两种存储结构顺序表的存储结构表示顺序表的常见操作和代码实现 数据结构与算法这块一直是...

  • 数据结构之List(一) 手写单链表

    数据结构之List(一) 手写单链表 1.线性表 线性表有两种结构:顺序存储结构和链式存储结构.顺序存储结构的常见...

  • 数据结构与算法 - 查找

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构数据结构...

  • 数据结构与算法 - 树形结构

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构 目录 ...

  • 数据结构与算法--线性表的顺序存储结构

    数据结构与算法--线性表的顺序存储结构 线性表是一个序列，可以想象成一群有先后顺序的的元素集合。线性表是有限序列，...

  • 线性表 — 顺序存储

    前言 记录数据结构与算法学习，内附详细实现方法，方便后续回顾。 一、线性表基础概念 线性表存储方式包括：顺序存储和...

  • 【数据结构】线性表之单链表

    完整代码需结合前面一篇顺序表数据结构学习-线性表之顺序表各种操作网易云课堂小甲鱼课程链接：数据结构与算法 线性表的...

  • 数据结构与算法--单链表

    数据结构与算法--单链表 链式存储结构的特点 学习线性表的顺序存储结构时，举了个例子：记忆和你住一条街的每家姓氏，...

网友评论

    本文标题：算法与数据结构系列之[线性表的顺序存储结构]

    本文链接：https://www.haomeiwen.com/subject/buangqtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    算法与数据结构

    关于我们|服务条款|联系我们|算法与数据结构系列之[线性表的顺序存储结构]|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！