一、顺序表

自定义：

#define MaxSize 10
typedef int ElemType;

1、静态分配

1）定义：

typedef struct {
    ElemType data[MaxSize];
    int len;
}SqList;

2）初始化顺序表：

void InitList(SqList& L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;
    }
    L.len = 0;
}

3）插入数据：

bool ListInsert(SqList& L, int i, ElemType e) {
    if (L.len + 1 >= MaxSize || i<1 || i > L.len+1) {
        return false;
    }
    for (int j = L.len; j >= i; j--) {
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.len++;
    return true;
}

4）删除：

bool ListDelete(SqList& L, int i, ElemType& e) {
    if (i < 1 || i > L.len) {
        return false;
    }
    e = L.data[i - 1];
    for (int j = i; j < L.len; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.len--;
    return true;
}

5）查找：

• 按值查找：

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.len; i++) {
        if (L.data[i] == e) {
            return i + 1; //返回的是该元素的位序
        }
    }
    return 0;
}

• 按位查找：

ElemType GetElem(SqList L, int i) { //i是位序
    if (i > L.len || i < 0) {
        return (ElemType)0;
    }
    return L.data[i - 1];
}

2、动态分配

自定义：

#define InitSize 10
typedef int ElemType;

1）定义：

typedef struct {
    ElemType* data;
    int MaxSize;
    int len;
}SeqList;

2）初始化顺序表：

void InitList(SeqList& L) {
    //用malloc函数申请一片连续空间
    L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
    L.MaxSize = InitSize;
    L.len = 0;
}

3）插入数据：
因为是动态分配，当数据超过最大空间MaxSize时，需要重新申请一个更大的空间，并把数据复制到新空间上。

//动态分配，所以得再申请大一片的空间然后把数据搬过去
void ExpandList(SeqList& L, SeqList& L_temp) {
    L_temp.data = (ElemType*)malloc(L.MaxSize * 2 * sizeof(ElemType));
    L_temp.MaxSize = L.MaxSize * 2;
    L_temp.len = L.len;
    //将L的值赋给L_temp
    for (int i = 0; i < L.len; i++) {
        L_temp.data[i] = L.data[i];
    }
    free(L.data);
    L = L_temp;
    // free(L_temp.data); 这一步是错误的！！！
}
//插入
bool ListInsert(SeqList& L, int i, ElemType e) {
    if (i<1 || i > L.len + 1)
        return false;
    if (L.len + 1 >= L.MaxSize) {//扩展空间后再进行下一步
        SeqList L_temp;
        ExpandList(L, L_temp);
    }
    for (int j = L.len; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.len++;
    return true;
}

在实现ExpandList时，我犯了一个低级错误，本来认为新空间赋给L后L_temp.data需要释放掉，运行发现L也跟着释放了。因为L=L_temp后，L.data是直接指向新的空间，并不是再复制一份数据给L.data。其实是我将L_temp与新申请的空间混淆了，L_temp是一个结构体，在ExpandList运行结束后就自动释放了。

4）删除、查找
代码与静态分配一模一样！！！

二、链表

1、单链表

1） 带头结点单链表

1）定义

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode* next; //指向下一个结点
}LNode, *LinkList; //结点和链表

2）初始化一个单链表

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) //内存不足分配失败
        return false; 
    L->next = NULL;
    return true;
}

3）获取链表长度

int L_Length(LinkList L) {
    int count = 0;
    while (L->next != NULL)
    {
        count++;
        L = L->next;
    }
    return count;
}

4）查找

• 按位查找

LNode* GetElem(LinkList L, int i) {
    if (i < 0)
        return NULL;
    int j = 1; //记录当前结点位置
    LNode* ergodic = L; //扫描结点到i-1的位置
    while (ergodic != NULL && j <= i) {
        ergodic = ergodic->next;
        j++;
    }
    return ergodic;
}

• 按值查找

LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p; //找不到返回null
}

5）插入

• 指定结点的前插操作

// 在p结点之前插入元素e
bool InsertPriorNode(LNode* p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode* temp = (LNode*)malloc(sizeof(LNode));
    if (temp == NULL)
        return false;
    //无法获取p结点之前的结点，所以使用数据的替换
    temp->data = p->data;
    p->data = e;
    temp->next = p->next;
    p->next = temp;
    return true;
}

• 指定结点的后插操作

//在p节点之后插入元素e
bool InsertNextNode(LNode* p, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode* temp = (LNode*)malloc(sizeof(LNode));
    if (temp == NULL)
        return false;
    temp->data = e;
    temp->next = p->next;
    p->next = temp;
    return true;
}

• 按位序插入

bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i<1)
        return false;
    LNode* ergodic; //遍历寻找位置为i的结点的指针
    ergodic = GetElem(L, i-1);
    if (ergodic == NULL)
        return false;
    return InsertNextNode(ergodic, e);
}

6）删除

• 按位序删除

bool ListDelete(LinkList& L, int i, ElemType &e) {
    if (i < 1)
        return false;
    LNode* ergodic; //扫描结点到i-1的位置
    ergodic = GetElem(L, i - 1);
    if (ergodic == NULL || ergodic->next == NULL)
        return false;
    LNode* temp = ergodic->next;
    e = temp->data;
    ergodic->next = temp->next;
    free(temp);
    return true;
}

• 指定结点删除

//未知前面区域的结点，所以使用数据的替换(当p为最后一个结点时不可用）
bool DeleteNode(LNode* p) {
    if (p == NULL)
        return false;
    LNode* temp = p->next;
    p->data = temp->data;
    p->next = temp->next;
    free(temp);
    return false;
}

7）建立单链表

• 单链表建立——尾插法

LinkList List_TailInsert(LinkList& L) {
    int x;
    //L = (LinkList)malloc(sizeof(LNode));//建立头结点
    LNode* temp, * r = L; //r为尾指针
    scanf("%d", &x);
    while (x != 9999) {
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        r->next = temp;
        r = temp;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

• 单链表建立——头插法

LinkList List_HeadInsert(LinkList& L) {
    LNode* temp;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        temp->next = L;
        L = temp;
        scanf("%d", &x);
    }
    return L;
}

2）不带头结点单链表

1）判断单链表是否为空

bool Empty(LinkList L) {
    if (L == NULL)
        return true;
    else
        return false;
}

2）初始化单链表

bool InitList(LinkList& L) {
    L = NULL;
    return true;
}

3）获取链表长度

int L_Length(LinkList L) {
    if (Empty(L))
        return 0;
    int count = 1;
    while (L->next != NULL)
    {
        count++;
        L = L->next;
    }
    return count;
}

4)查找

• 按位查找

LNode* GetElem(LinkList L, int i) {
    if (i < 0)
        return NULL;
    int j = 1;//记录当前结点位置
    LNode* ergodic = L;//扫描结点到i-1的位置
    while (ergodic != NULL && j < i) {
        ergodic = ergodic->next;
        j++;
    }
    return ergodic;
}

• 按值查找

LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L;
    while (p != NULL && p->data != e)
        p = p->next;
    return p; //找不到返回null
}

5）建立链表

• 尾插法

LinkList List_TailInsert(LinkList& L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));//建立头结点
    scanf("%d", &x);
    L->data = x;
    L->next = NULL;
    LNode* temp, * r = L; //r为尾指针
    while (true) {
        scanf("%d", &x);
        if (x == 9999)
            break;
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        r->next = temp;
        r = temp;
    }
    r->next = NULL;
    return L;
}

• 头插法

LinkList List_HeadInsert(LinkList& L) {
    LNode* temp;
    int x;
    scanf("%d", &x);
    L = (LinkList)malloc(sizeof(LNode));
    L->data = x;
    L->next = NULL;
    while (true) {
        scanf("%d", &x);
        if (x == 9999)
            break;
        temp = (LNode*)malloc(sizeof(LNode));
        temp->data = x;
        temp->next = L;
        L = temp;
    }
    return L;
}

3）小调试

int main(){
    LinkList L;
    InitList(L);
    List_HeadInsert(L);
    //List_TailInsert(L);

    //获取链表长度
    int len = L_Length(L);
    printf("长度为%d",len);
    //查找——按位查找
    LNode* p = GetElem(L, 2);
    //查找——按值查找
    LNode* p2 = LocateElem(L, 4);
    // 在p结点之前插入元素e
    LNode* p3 = L->next->next->next;
    InsertPriorNode(p3, 11);
    //插入——按位序插入
    ListInsert(L, 3, 12);
    //按位序删除
    ElemType e;
    ListDelete(L, 3, e);
    //指定结点删除
    LNode* p4 = L->next->next;
    DeleteNode(p4);
}

可以用此主函数断点调试，查看数据的改变过程。

2、双链表

1）定义

typedef int ElemType;
typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
}DNode, *DLinklist;

2）初始化双链表

bool InitDLinkList(DLinklist& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL)
        return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

3）判空

bool Empty(DLinklist L) {
    if (L->next == NULL)
        return true;
    else
        return false;
}

4）插入

bool InsertNextNode(DNode* p, DNode* s) {
    if (p == NULL || s == NULL)
        return false;
    s->next = p->next;
    s->prior = p;
    if (p->next != NULL)
        p->next->prior = s;
    p->next = s;
    return true;
}

5）删除

//删除p结点
bool DeleteNextNode(DNode* p) {
    if (p == NULL)
        return false;
    if (p->next != NULL) {
        p->prior->next = p->next;
        p->next->prior = p->prior;
    }
    else
    {
        p->prior->next = NULL;
    }
    free(p);
    return true;
}

3、循环链表

1）循环单链表初始化

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = L;
    return true;
}

2）循环双链表初始化

bool InitList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL)
        return false;
    L->next = L;
    L->prior = L;
    return true;
}

4、静态链表

#define MaxSize 10
typedef int ElemType;
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];