数据结构-线性表-顺序表

静态分配

#include <stdio.h>
#define MaxSize 10  //定义最大长度

typedef struct{
    int data[MaxSize];  //用静态的数组存放数据元素，存储空间是静态的，设置的太长会造成浪费
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义

void InitList(SqList &L){
    //防止内存中遗留的脏数据，可以省略置零元素
    for(int i = 0; i < MaxSize; i++){
        L.data[i] = 0;  //所有元素置零
    }
    L.length = 0;  //Length的值置零
}

int main(){
    SqList L;  //声明一个顺序表，分配空间
    InitList(L);  //初始化顺序表
    return 0;
}

动态分配

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10

typedef struct{
    int *data;
    int MaxSize;
    int length;
}SeqList;

void InitList(SeqList &L){
    //用malloc函数申请一片连续的存储空间，需将类型设为顺序表的数据类型
    L.data = (int *)malloc(sizeof(int)*InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

//顺序表的扩展，时间开销大，使用malloc和free
void IncreaseSize(SeqList &L, int len){
    int *p = L.data;
    //malloc申请的是另一片存储空间
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i = 0; i < L.length; i++){
        L.data[i] = p[i];  //将数据复制到新区域
    }
    L.MaxSize = L.MaxSize + len;  //顺序表最大长度增加len
    free(p);  //释放原来的内存空间
}

int main(void){
    SeqList L;
    InitList(L);
    IncreaseSize(L,5);
    printf("%d", L.MaxSize);
    return 0;
}

插入和删除

#include <stdio.h>
#define MaxSize 10  //定义最大长度

typedef struct{
    int data[MaxSize];  //用静态的数组存放数据元素，存储空间是静态的，设置的太长会造成浪费
    int length;  //顺序表的当前长度
}SqList;  //顺序表的类型定义

void InitList(SqList &L){
    //防止内存中遗留的脏数据，可以省略置零元素
    for(int i = 0; i < MaxSize; i++){
        L.data[i] = 0;  //所有元素置零
    }
    L.length = 0;  //Length的值置零
}

//插入需要考虑的问题
//1. i的值的范围[1,length+1]
//2. 顺序表是否已满
bool ListInsert(SqList &L, int i, int e){
    if(i<1||i>L.length+1) return false;
    if(L.length >= MaxSize) return false;
    for(int j = L.length; j>=i; j--){  //将第i个元素及之后的元素后移
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;  //在位置i处放入e
    L.length++;  //长度加1
    return true;
}
//时间复杂度
// i = length + 1 插入一次
// i = 1 时间复杂度: O(n)
//平均时间复杂度：i = 1,n  i=2,n-1,  i=3,n-2 ..... i=n+1,0 平均循环次数 n/2
//平均时间复杂度：O(n)

bool ListDelete(SqList &L, int i, int &e){
    if(i<1||i>L.length) return false;  //判断i的范围是否有效
    e = L.data[i-1];  //将被删除的元素赋值给e
    for(int j = i; j<L.length; j++){
        L.data[j-1] = L.data[j];  //将第i个元素后的元素前移
    }
    L.length--;  //线性表长度减一
    return true;
}

int main(){
    SqList L;  //声明一个顺序表，分配空间
    InitList(L);  //初始化顺序表
    int e = -1;
    if(ListDelete(L,3,e)){
        printf("已经删除第三个元素，删除元素的值为%d\n",e);
    }else{
        printf("位序i不合法，删除失败\n");
    }
    return 0;
}

查找

#include <stdio.h>
#define MaxSize 10

typedef struct{
    int data[MaxSize];
    int length;
}SqList;

//按位查找
int GetElem(SqList L, int i){
    return L.data[i-1];
}
//时间复杂度O(1)

//按值查找
int LocateElem(SqList L, int e){
    for(int i=0; i<L.length; i++){
        if(L.data[i] == e){
            return i + 1;
        }
    }
    return 0;
}
//时间复杂度
//最好O(1)
//最坏O(n)
//平均1,1 2,2 ... n+1/2 0(n)