动态顺序表

• 以下增删查操作是索引为index的下标，具体根据要求做改动

#pragma once

#include <stdio.h>
#include <stdlib.h>

#define initSize 100
typedef int ElemType;
typedef struct {
    ElemType *data;
    int length; //当前的长度
    int maxSize;//最大长度
} SqlList;

//初始化
void initList(SqlList &L) {
    L.data = (ElemType *) malloc(initSize * sizeof(ElemType));
    L.length = 0;
    L.maxSize = initSize;
}

//开辟空间
void createLength(SqlList &L, int size) {
    ElemType *p = L.data; //备份转移数据
    L.data = (ElemType *) malloc((size + L.maxSize) * sizeof(ElemType));
    // 转移数据
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }
    L.maxSize += size;
    free(p);
}

//插入
int insertElem(SqlList &L, int index, ElemType x) {
    //判断合法性
    if (index < 0 || index > L.length)return 0;
    for (int i = L.length; i > index; --i) {
        L.data[i] = L.data[i - 1];
    }
    L.data[index] = x;
    L.length += 1;
    return 1;
}

//删除
int deleteElem(SqlList &L, int index, ElemType &e){
    //判断合法性
    if (index < 0 || index > L.length)return 0;
    e = L.data[index];
    for (int i = index; i < L.length - 1; ++i) {
        L.data[i] = L.data[i+1];
    }
    L.length -= 1;
    return 1;
}

//获取元素
ElemType getElem(SqlList L, int index){
    //判断合法性
    if (index < 0 || index > L.length)return 0;
    return L.data[index];
}

//查找元素,有就返回下标,没有就返回-1
int findElem(SqlList L, ElemType x){
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == x) return i;
    }
    return -1;
}
//打印
void showList(SqlList L){
    for (int i = 0; i < L.length; ++i) {
        printf("%d ", L.data[i]);
    }
    printf("length = %d \n", L.length);
}
int main() {

    SqlList l;
    ElemType x;
    initList(l);
    for(int i = 0;i<10;i++){
        insertElem(l, i, i);
    }
    showList(l);
    insertElem(l, 5, 999);
    showList(l);
    deleteElem(l,2, x);
    showList(l);
    printf("%d \n", getElem(l, 7));
    printf("find: %d\n", findElem(l,9));
    return 0;
}

单链表

定义

• 带头节点的

typedef int ElemType;
typedef struct Node {
    struct Node *next;
    ElemType data;
} LNode, *LinkList; //LinkList 和 LNode*是一样的

//带头结点的会更方便，这里是带头节点的
bool initList(LinkList &l) {
    l = (LNode *) malloc(sizeof(LNode));//LNode*强调的是分配一个节点，也可以l = (LinkList)malloc(sizeof(LNode));
    //判断内存够不够，其实可以不用
    if (l == NULL) return false;
    l->next = NULL;
    return true;
}

• 插入和删除本质上都是找到前面一个节点

插入操作

• 带头节点的插入

//在第i个位置插入节点，本质上要找到第i-1个节点，以头节点为第0个节点
bool insertElem(LinkList &l, int i, ElemType x) {
    if (i < 1)return false;
    LinkList p = l;     //p开始指向头节点l,Lnode* p = l;
    int j = 0;          //j表示当前p指向节点的下标
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;//i不合法,i太大，远超过节点个数

    //到这里时，p已经到了i-1这个位置,可以开辟一块空间了
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

• 如果是不带头节点的

//不带头节点的插入
bool insertElemNoH(LinkList &l, int i, ElemType x) {
    if (i < 0)return false;
    //单独处理插入第一个节点的情况
    if (i == 1) {
        LNode *s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = l;
        l = s;
        return true;
    }
    //下面操作和带头节点的操作是一样的
    LNode *p = l;
    int j = 1;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p)return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

前插操作

//前插操作，在节点p前面插入一个节点，值为x
//时间复杂度为O(1)
bool insertPriorNode(LinkList &l, LNode *p, ElemType x) {
    if (!p)return false;
    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->next = p->next;
    s->data = p->data;
    p->next = s;
    p->data = x;
    return true;
}

• 和上面本质一样，其实是交换数据

//对于指定节点的前插操作,比如在p节点前插入s节点
bool insertPNode(LNode *p, LNode *s) {
    if (!p || !s)return false;
    s->next = p->next;
    p->next = s;
    ElemType temp = s->data;
    s->data = p->data;
    p->data = temp;
    return true;
}

删除操作

//删除第i个节点,由x带回值
bool deleteElem(LinkList &l, int i, ElemType &x) {
    if (i < 1)return false;
    LNode *p = l;
    int j = 0;//p指向的节点下标
    //找到第i-1个节点
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p)return false;//i不合法
    if (!(p->next))return false;//i-1后面没有节点了
    //现在p指向i-1的位置
    LNode *q = p->next;
    x = q->data;
    p->next = q->next;
    free(q);
    return true;
}

• 删除要注意一个细节

if (!p)return false;//i不合法
if (!(p->next))return false;//i-1后面没有节点了

删除指定节点

//删除指定的节点
bool deleteTElem(LNode* p){
    if(!p || !(p->next)) return false;
    LNode *s = p->next;
    p->data = s->data;
    p->next = s->next;
    free(s);
    return true;
}

• 参考

查找

按位查找

//按位查找，找到第i个
LNode *getElem(LinkList l, int i) {
    if (i < 0) return NULL;
    LNode *p = l;
    int j = 0;//j是p的位置下标
    //让跳出循环时，p落在i的位置
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

按值查找

//按值查找
LNode * getElemByValue(LinkList l, ElemType x){
    LNode *p = l->next;
    while (p && p->data != x){
        p = p->next;
    }
    return p;//找到返回该指针，找不到返回NULL
}

求表长

• 这是带头节点的，注意表头不算如长度

//求表的长度
int getLength(LinkList l){
    int len = 0;
    LNode *p = l->next;
    while (p){
        p = p->next;
        len++;
    }
    return len;
}

单链表的建立

• 头插法
• 尾插法

尾插法

//尾插法
LinkList insertNextNode(LinkList &l) {
    int x;
    l = (LNode *) malloc(sizeof(LNode));//建立头节点
    l->next = NULL;//如果从外面传入已经初始化的l，那这里就不用写这初始化2句
    LNode *s, *p = l;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        //s->next = NULL;
        p->next = s;
        p = s;  //永远保持p指向最后一个节点
        scanf("%d", &x);
    }
    p->next = NULL;
    return l;
}

头插法

//头插法
LinkList insertHead(LinkList &l) {
    int x;
    l = (LNode *) malloc(sizeof(LNode));//建立头节点
    l->next = NULL;//如果从外面传入已经初始化的l，那这里就不用写这初始化2句
    LNode *s;//头插法只需要记住头节点就行，所以不用像尾插法多设一个p记录尾节点
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *) malloc(sizeof(LNode));
        s->data = x;
        s->next = l->next;
        l->next = s;
        scanf("%d", &x);
    }
    return l;
}

双链表

定义

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

初始化

//初始化
bool initList(DLinklist &l) {
    l = (DLinklist) malloc(sizeof(DNode));
    if (!l) return false; //内存不足，分配失败的情况
    l->next = NULL;
    l->prior = NULL;
    return true;
}

后插

//在p节点后面插入s节点
bool insertNext(DNode *p, DNode *s) {
    if (!p || !s) return false;
    s->next = p->next;
    if (p->next) p->next->prior = s;
    p->next = s;
    s->prior = p;
    return true;
}

前删

//在节点p后面删除节点q
bool deleteNext(DNode *p) {
    if (!p) return false;
    DNode *q = p->next;
    if (!q) return false;
    p->next = q->next;
    if (q->next) q->next->prior = p;
    free(q);
    return true;
}

销毁

//销毁，即每一次都删除头节点的下一个节点
void destroyList(DLinklist &l) {
    //释放各个节点
    while (l->next)
        deleteNext(l);
    free(l);
    l = NULL;
}

双向循环链表

• 更加方便
• 实现比上面简单