数据结构

设置数据元素的默认值是可以省略的。如果没有设置数据元素的默认值，又违规访问数据元素的话，那么会因为内存中遗留的脏数据导致一些奇怪的问题。

应该使用基本操作来访问数据元素

#include<stdio.h>
#define InitSize 10 //顺序表的初始长度

typedef struct {
    ElemType *data; //指示动态分配数组的指针
    int MaxSize; //顺序表的最大容量
    int length; //顺序表的当前长度
}SeqList;//顺序表的类型定义（一维数组的动态分配方式）

C语言

C++

初始化动态分配语句返回的是对应物理存储空间的首个位置的指针

bool ListInsert(SqList &L,int i,int e) {
    if (L.length >= MaxSize)
    {
        return false; //静态分配，如果存储空间已经满了，不能插入
    }
    if (i < 1 || i > L.length + 1)
    {
        return false; //判断i的值是否有效（顺序表的存储必须是连续的）
    }
    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j-1];//将第i位之后的元素后移一位
    }
    L.data[i-1] = e; //第i位元素置为e(对应到数组实际上是下标为i-1的位置)
    L.length++; //顺序表的长度加1
}

时间复杂度（问题规模n就是顺序表的表长）

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length)
    {
        return false; //判断i的值是否有效（顺序表的存储必须是连续的）
    }
    e = L.data[i - 1]; // 将被删除的元素赋值给e(对应到数组实际上是下标为i-1的位置)
    for (int j = i; j < L.length; j++)
    {
        L.data[j-1] = L.data[j];//将第i位之后的元素前移一位
    }
    L.length--; //顺序表的长度减1
}

时间复杂度（问题规模n就是顺序表的表长）

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; //数组下标为i的元素值等于e，返回其位序为i + 1
        }
    }
    return 0; //退出循环，查找失败
}

最好：目标元素在表头

最坏：目标元素在表尾

平均：

强调是一个单链表用LinkList L

强调是一个单链表的结点用LNode * L

//不带头结点的单链表的初始化
bool InitLinkList(LinkList &L) {//初始化一个单链表
    L = NULL; //空表暂时没有任何数据（防止脏数据）
    return true;
}

//不带头结点的单链表判断是否为空
bool IsEmpty(LinkList L) {
    /*if (L == NULL)
    {
        return true;
    }
    return false; */
    return (L == NULL);
}

//带头结点的单链表的初始化
bool InitLinkList2(LinkList & L) {//初始化一个单链表
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
    if (L == NULL)
    {
        return false; //内存不足，分配失败
    }
    L->next == NULL; //头结点之后暂时没有结点
    return true;
}

//带头结点的单链表判断是否为空
bool IsEmpty2(LinkList L) {
    /*if (L->next == NULL)
    {
        return true;
    }
    return false; */
    return (L->next == NULL);
}

typedef <数据类型> <别名>

比如：栈

找出基本运算语句（执行频率最高的语句）

设执行次数为t，找出判断条件的临界值，列出一个关于t的不等式

取不等式中，随着n增长最快的项，将其系数置为1，得到时间复杂度O（f（n））

如果是单层循环，找出循环内执行语句的执行频度即可

如果是嵌套循环，内层循环的时间复杂度 乘以 外层循环的时间复杂度

找出主体语句中与T（n）成正比的循环变量，将之代入条件中进行计算

递归程序

非递归程序