数据结构2.2-顺序表

定义

顺序表——用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

1
2
3
4


typedef struct {
   int num; //号数
   int people; //人数
} Customer;

顺序表的实现

静态分配

alt text

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <stdio.h>
#define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）

//基本操作-初始化一个顺序表
void InitList(SqList&L){
    for(int i=0,i<MaxSize;i++)
    L.data[i] = 0;//将所有数据元素设置为默认值，否则内存中可能会有“脏数据”
L.length = 0;
}

int main(){
    SqList L;
    InitList(L);
    return 0;
}

动态分配

alt text

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <stdlib.h>
#define InitSize 10 //顺序表的初始长度
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
} SeqList; //顺序表的类型定义（动态分配方式）

void InitList(SqList&L){
    L.data = (int *)malloc (InitSize*sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;

int main() {
    SqList L;
    InitList(L);
    return 0;
}

//延长：
void IncreaseSize(SeList &L,int len){
    int *p = L.data;
    L.data = (int *)malloc ((L.MaxSize+len)*sizeof(int));
    for(int i=0,i<L.length;i++){
        L.data[i] = p[i];
    }
    L.MaxaSize += len;
    free(p);//释放原来内存空间
}
}

总结

顺序表的特点：

①随机访问，即可以在 O(1) 时间内找到第 i 个元素。

②存储密度高，每个节点只存储数据元素

③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

④插入、删除操作不方便，需要移动大量元素 alt text