• 周六. 3月 2nd, 2024

    数据结构笔记 3.线性表(1)顺序存储

    root

    11月 23, 2021 #数据结构, #线性表

    线性表(List):0个或多个数据元素的有限序列

    a1是a2的直接前驱, a2是a1的直接后继。a1有且仅有一个直接后继,an有且仅有一个直接前驱。

    一、线性表的抽象数据类型定义如下

    ADT 线性表(List)
    Data
        线性表的数据对象集合为{a1, a2,...an},每个元素的类型均为DataType.其中,除第一个元素a1外,每一个元素有且只有一个直接前驱,除了最后一个元素an外。每一个元素有且仅有一个直接后继元素。数据元素之间的关系是一对一的关系。
    
    Operation
        InitList(*L):   //初始化操作,建立一个空的线性表L。
        ListEmpty(L);    //若线性表为空,返回true, 否则返回false.
        ClearList(*L):  //将线性表清空
        GetElem(L, i, *e): //将线性表L中的第i个元素位置返回给e
        LocateElem(L, e): //在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则, 返回0表示失败。
        ListInsert(*L, i, e): //在线性表L中的第i个位置插入新元素e
        ListDelete(*L, i,*e): //删除线性表L中的第i个位置元素,并且e返回其值
        ListLength(L): //返回线性表L的元素个数。
    endADT

    例:实现两个线性表集合A和B的并集操作。

    分析: 我们只要循环集合B中的每个元素,判断当前元素是否存在A中,若不存在,则插入到A中即可。

    /*将所有的在线性表Lb中但不在La中的元素插入到La中*/
    void union(List *La, List Lb)
    {
        int La_len, Lb_len, i;
        ElemType e;
        La_len = ListLength(La);
        Lb_len = ListLength(Lb);
        for ( i=1; i<=Lb_len; i++) {
            GetElem(Lb, i, e);  //取Lb中第i个数据元素赋给e
            if(!LocateElem(La, e)) {   //La中不存在和e相同数据元素
                ListInsert(La, ++La_len, e);
            }
        }
    }

    二、 顺序存储结构

    顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。示意图如下

    //顺序存储的结构代码:
    #define MAXSIZE 20
    typedef int ElemType;
    typedef struct {
        ElemType data[MAXSIZE];
        int length;
    }SqList;

    我们发现描述顺序存储结构需要三个属性:

    • 存储空间的超始位置: 数组data, 它的存储位置就是存储空间的存储位置。
    • 线性表的最大存储容量:数组长度MaxSize。
    • 线性表的当前长度:length

    1、 GetElem获得元素操作

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    /*Status是函数类型,其值是函数结果状态代码, 如OK等*/
    /*初始条件:顺序线性表L已存在,1<=i<=ListLength(L)*/
    /*操作结构: 用e返回L中第i个数据元素的值*/
    Status GetElem(SqList L, int i, ElemType *e)
    {
    	if(L.length == 0 || i<1 || i>L.length) {
    		return ERROR;
    	}
    	*e = L.data[i-1];
    	return OK;
    }

    2、 插入操作ListInsert(*L, i, e)

    插入算法思路:

    • 如果插入位置不合理,抛出异常;
    • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
    • 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
    • 将要插入元素填入位置i处
    • 表长加1
    /**
     * 初始条件:顺序线性表L已存在, 1<=i<=ListLength(L)
     * 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
     */
    Status ListInsert(SqList *L, int i, ElemType e) {
    	int k;
    	if (L->length==MAXSIZE) { //顺序表已经满
    		return ERROR;
    	}
    	if (i<1 || i>L->length+1) { //当i不在范围内
    		return ERROR;
    	}
    	if(i<=L->length) {
    		for(k=L->length-1; k>=i-1; k--) { //将要插入位置后数据元素向后移动一位
    			L->data[k+1] = L->data[k];
    		}
    	}
    	L->data[i-1] = e; //将新元素插入
    	L->length++;
    	return OK;
    }

    3、删除操作

    删除算法思路:

    1. 如果删除位置不合理,抛出异常
    2. 取出删除元素
    3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
    4. 表长减1
    /**
     * 1<=i<=ListLength(L)
     * 删除L的第i个数据元素, 并用e返回其值,L的长度减1
     */
    Status ListDelete(SqList *L, int i, ElemType *e) {
    	int k;
    	if (L->length ==0) { //表为空
    		return ERROR;
    	}
    	if(i<1 || i>L->length) { //删除位置不正确
    		return ERROR;
    	}
    	*e = L->data[i-1];
    	if (i<L->length) {
    		for (k=i; k<L->length; k++) { //将删除位置后继元素前移
    			L->data[k-1] = L->data[k];
    		}
    	}
    	L->length--;
    	return OK;
    }

    插入和删除的时间复杂度分析:

    最好的情况: 如果元素插入到最后一个位置, 或者删除最后一个元素, 此时时间复杂度为O(1), 因为不需要移动元素。

    最坏的情况: 如果元素插入到第一个位置或者删除第一个元素,此时时间复杂度为O(n)。

    线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1);, 而插入或删除时,时间复杂度都是O(n)。它比较适合元素个数不太变化,而更多是存取数据的应用。

    4、 线性表顺序存储结构的优缺点

    root