顺序表

顺序表的概念

用一组地址连续的存储单元依次存储数据元素的线性表叫做顺序表

特点：逻辑上相邻的数据元素，其物理次序也是相邻的

顺序表的定义

静态

1
2
3
4
5
6
7
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct {
    int data[MAXSIEZE];
    int length;
}Sqlist;

动态

1
2
3
4
5
6
7
#include<stdio.h>
#define INITSIZE 100
typedef struct{
    int *data;
    int Maxsize;
    int length;
}Seqlist;

顺序表的初始化

静态

1
2
3
4
5
6
void Initlist(Sqlist &L){
    for(int i=0;i<MAXSIZE;i++){
        L.data[i]=0;
    }
    L.length=0;
}

动态

1
2
3
4
void Initlist(Seqlist &L){
    L.data=(int *)malloc(sizeof(int)*INITSIZE);
   L.length=0;
}
  • 增加长度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void IncreaseSize(Seqlist &L，int len){
        int *p=L.data;
        L.data=(int *)malloc(sizeof(int)*(MAXSIZE+len));
        for(int i=0;i<MAXSIZE;i++){
            L.data[i]=p[i];
        }
        L.MaxSIze=L.MaxSize+len;
        free(p);
    }

顺序表的插入

ListInsert(&L,i,e)在表L的第i个位置插入e

时间复杂度O(n)

静态

1
2
3
4
5
6
7
8
9
10
bool ListInsert(Sqlist &L,int i,int e){
    if(i>L.length+1||i<1)return false;
    if(length>=MAXSIZE)return false;
    for(int j=L.length;j>=i;j--){
        L.data[j]=L.data[j-1]
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

动态

1
2
3
4
5
6
7
8
9
10
bool ListInsert(Seqlist &L,int i,int e){
    if(i>L.length+1||i<1)return false;
    if(length>=MAXSIZE)return false;
    for(int j=length;j<=i;j--){
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;
    L.length++;
    return true;
}

顺序表的删除

时间复杂度O(n)

静态

1
2
3
4
5
6
7
8
9
bool ListDelete(Sqlist &L,int i,int &e){
    if(i<1||i>length)return false;
    e=L.data[i-1];
    for(int j=i;j<length;j++){
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}

动态

1
2
3
4
5
6
7
8
9
bool ListDelete(Seqlist &L,int i,int &e){
    if(i<1||i>length)return false;
    e=L.data[i-1];
    for(int j=i;j<length;j++){
        L.data[j-1]=L.data[j];
    }
    L.length--;
    return true;
}