数据结构实验报告——顺序表

• 实验目的与要求
• 实验步骤与内容
• 问题与说明
• 备注
• 程序清单
  实验题目：顺序表(SqList)
  姓名：金正旭
  指导教师： 刘铮

实验目的与要求

1.完成严蔚敏版《数据结构》上对线性表的基本操作，理解线性表的构造过程。

2.学会使用线性表增查改删各种功能，归纳下线性表作为线性结构的优缺点。

3.估计线性表各类操作的时间复杂度与空间复杂度。

4.掌握线性表的顺序存储结构。

5.掌握特殊矩阵的压缩方法

6.广义表的定义及理解

实验步骤与内容

顺序表

顺序表的实现并不算很难，其基本思路和数组几乎完全一致，但是有一点很关键的不同的不同是顺序表不能有中间为空的item而数组可以。下面给出顺序表ADT。

顺序表ADT：

ADT List{
    数据对象：D={ai|ai∈ElemSet,1,2,...,n, n≥0}
    数据关系：R={<ai-1,ai> | ai-1,ai∈D，i=2,...,n}
    基本操作：
    CreateList(SqList &L,ElemType a[],int n);
    InitList(SqList &L);
    DestroyList(SqList &L);
    ListEmpty(SqList L);
    ListLength(SqList L);
    DispList(SqList L);
    GetElem(SqList L,int i,ElemType &e);
    LocateElem(SqList L, ElemType e);
    ListInsert(SqList &L,int i,ElemType e);
    ListDelete(SqList &L,int i,ElemType &e);
}ADT SqList;

顺序表中元素的储存位置LOC（ai）之间

LOC(ai+1) = LOC(ai)+/;<br>
LOC(ai) = LOC(a1)+(i-1)×/<br>

顺序表为随机存取结构，查找操作的时间复杂度是O(1)；

顺序表为静态结构(表一旦装满，不能扩充)

#define MAX_SIZE 100
    typedef int Status;
    typedef int ElemType;
    typedef struct sqList{
        ElemType Elem_array[MAX_SIZE];
        int length;
    }SqList;

顺序表初始化：

Status Init_SqList(SqList *L){
    L->Elem_array=(ElemType *)malloc(MAX_SIZE*sizeof(ElemType));
    if(!L->Elem_array)
        return ERROR;
    else {
        L->Length =0;
        return OK;
    }
}

顺序表的插入：

1.L中i个到n个节点后移一位;

2.将节点e插入到节点ai-1之后;

3.顺序表长度加1.

Status Insert_SqList(SqList *L,int i,ElemType e){
    int j;
    if(i<0 || i>L->Length-1) return ERROR;
    if(L->Length >= MAX_SIZE) return ERROR:
    for(j=L->Length-1;i>=i-1;--j) L->Elem_array[j+1]=L->Elem_array[j];
    L->Elem_array[i-1]=e;
    L->Length++;
    return OK;
}

时间复杂度分析：

设在顺序表中第i个元素之前插入结点为pi，

Σ=Σpi*(n-i+1)  (1≤i≤n)
Σinsert=n/2    时间复杂度为O(n)

顺序表的删除：

ElemType Delete_SqList(SqList *L,int i){
    int k;
    ElemType x;
    if(L->length == 0) return ERROR;
    else if(i<1 || i>L->length) return ERROR;
    else {
        x=L->Elem_array[i-1];
        for(k=i;k<L->length;k++)
        L->Elemarray[k-1]=L->Elem_array[k];
        L->length--;
        return (x);
    }
}

顺序表的查找定位删除：

ElemType Delete_SqList_Locate(SqList *L,ElemType key){
    int i=0;
    int j=0;
    if(!L->length) return ERROR;
    else {
        for(i=0;i<L->length;i++){
            if(L->length==key) {
                for(j=i;j<L->length-1;j++)   L->Elem_array[j]=L->Elem_array[j+1];
                L->length--;
            } else {
            return ERROR;
        }
    }
}

时间复杂度分析：

设在顺序表中第i个位置找到相同key值的元素的概率为pi，且集合中元素key值互不相同。
首先要遍历整个元素对象集合并与key值比较

Σcompare=(n+1)/2 O(n)

然后将顺序表i后所有元素前移一位，并且长度减一

Σdelete=(n-1)/2 O(n)

所以总的时间复杂度为O(n)。

特殊矩阵的压缩存储

数组是线性表的推广，对角矩阵，三角矩阵，对称矩阵可以使用特殊的数据结构优化存储空间。

数组定义

数组的逻辑结构是偶对<下标，元素>，及相同的数据类型。数组是随机存取结构且数组的个数是固定的。

数组ADT

ADT array{
    数据对象:ji=0,1,2...,bi-1,1,2,...,n;
                     D={aj1j2...jn|n>0称为数组的维数，bi是数组的长度，ji是数组元素第i维的下标，aj1j2j3...jn∈ElemSet}
    数据关系:R={R,R1,...,Rn}
    Ri={<
    基本操作:……
}

问题与说明

严蔚敏老师给的是伪代码，其中的 & 应该是想表示C++中引用的意思，这里为了让程序能够运行我把，书里的意思按另外的方法实现了。

备注

C语言实现
CLion集成开发环境

程序清单

C语言实现

#define MaxSize 50
typedef char ElemType; 
typedef struct 
{ ElemType data[MaxSize]; 
    int length;    
} SqList;      
void CreateList(SqList *&L,ElemType a[],int n）{
    int i;
    L=(SqList *)malloc(sizeof(SqList));
    for(i=0;i<n;i++)   L->data[i]=a[i];
    L->length=n;
}
void InitList(SqList *&L){
    L=(SqList *)malloc(sizeof(SqList));
    L->length=0;
}
void DestroyList(SqList *&L){
    free(L);
    L=NULL;
}
int ListEmpty(SqList *L){
    if(L->length) return 1;
    return 0;
}

int ListLength(SqList *L){
    return L->length;
}
void DispList(SqList *L){
    int i=0;
    for(i=0;i<L->length;i++)   L->elem_array[i]=0;
    L->length=0;
    return OK;
}
int GetElem(SqList *L,int i,ElemType &e);{
    int j=0;
    if(L->length==0) return  ERROR;
    else if(i<1 || i>L->Length) return ERROR;
    else e=L->elem_array[i-1];
    return x;
}
int LocateElem(SqList *L, ElemType e){
    int i=0;
    if(!L->length) return ERROR;
    for(i=0;i<L->Length;i++) 
        if(L->elem_array[i]==e) break;
    return i;
}
int ListInsert(SqList *&L,int i,ElemType e){
    int j;
    if(i<1 || i>L->length-1) return ERROR;
    if(L->length>MAX_SIZE) return ERROR;
    else {
        for(j=L->length-1;j>=i-1;--j) L->data[j+1]=L->data[j];
        L->data[i-1]=e;
        L->length++;
    }
    return OK;
}
int ListDelete(SqList *&L,int i,ElemType &e){
    int j;
    if(!L->length) return ERROR;
    else if(i<1 || i>L->length) return ERROR;
    else {
        e=elem_array[i-1];
        for(j=L->length-1;j>=i-1;--j) L->elem_arrray[j+1]=L->elem_array[j];
    }
    return OK;    
}