线性表

约 93 个字 28 行代码预计阅读时间 1 分钟

元素的地址：元素的首地址（因为一个元素可能是多个字节）

比如int类型（4个字节） a1 :0,1,2,3 a2:4,5,6,7

随机读取 \(~O(1)\) a[i-1] = a[0] + (i-1)* d

C++

#define LIST_INIT_SIZE 100 //初始容量
#define LIST_INCREMENT 10  //追加内存时的增量 宏=全局变量+const
typedef int ElemType;

typedef struct{
    ElemType *elem; //连续内存首地址
    int length;
    int size;
} SqList;
SqList L:
L.elem;//首地址 
L.elem[0];// 第一个元素
l.length;//表长
L.size; //表容量
L.elem[L.length-1] // 取最后一个数

void init(SqList &L){
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType))
}

void getElem(SqList L,int i,ElemType &e)
{
    if (i < 1 || i > L.length)
    {
        return;
    }
    e = L.elem[i-1];
}

链表：解决插入删除

不是随机读取

循环链表元素个数：(front-rear+容量) mod 容量其中front是头指针，rear是尾指针