datastruct_1

注：本系列数据结构来自王道考研数据结构教科书内容笔记

线性表笔记

#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 备注：c语言中无引用，所以下列函数需要通过指针进行修改。（后续笔记同）
// 线性表笔记
// 顺序表相关函数：
#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;  // 静态分配
void InitList(SqList& L) {
    int i;
    for (i = 0; i < MaxSize; i++) {
        L.data[i] = 0;
    }
    L.length = 0;
}  // 顺序表初始化
#define InitSize 10
typedef struct {
    ElemType data;  // 指示动态分配数组的指针
    int MaxSize;
    int length;
} SeqList;  // 动态分配
void InitList(SeqList& L) {
    L.data = (int*)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}  // 动态分配初始化
void IncreaseSize(SeqList& L, int* len*) {
    int* p = L.data;
    L.data = (int*)malloc((L.length + len) * sizeof(int));
    int i;
    for (i = 0; i < L.length; i++) {
        L.data[i] = p[i];  // 将数据复制到新区域
    }
    L.MaxSize += len;  // 顺序表最大长度增加len
    free(P);
}  // 增加动态数组的长度
bool ListInsert(SqList& L, int i, int e) {
    // 在表L的位序i的位置插入元素e
    if (i < 1 || i > L.length + 1) {
        return false;
    }  // 判断i的范围是否有效
    if (L.length >= MaxSize) {
        return false;
    }  // 存储空间已满，不能插入
    int j;
    for (j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }  // 元素后移
    L.data[i - 1] = e;
    L.length++;
    return true;
}  // 顺序表插入

bool ListDelete(SqList& L, int i, int& e) {
    // 删除表L的位序i的位置的元素
    // ，该函数使用前要把e定义为-1把删除的元素带回来
    if (i < 1 || i > L.length) {
        return false;
    }                   // 判断i的范围是否有效
    e = L.data[i - 1];  // 将被删除的元素赋值给e
    int j;
    for (j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}  // 顺序表变量删除

ElemType GetElem(SqList L, int i) {
    return L.data[i - 1];
}  // 静（动）态分配按位查找

int LocateElem(SeqList L, ElemType e) {
    int i;
    for (i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}  // 按值查找

// 链表的相关函数：

// 单链表：

typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *LinkList;
bool InitList(LinkList& L) {
    L = NULL;
    return true;
}  // 初始化单链表（不带头结点）

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) {
        return false;
    }
    L->next = NULL;
    return true;
}  // 初始化单链表（带头结点）

bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    LNode* p;
    int j = 0;
    p = L;  // L指向头结点，头结点是第0个节点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}  // 单链表插入数据（带头结点）

bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i < 1) {
        return false;
    }
    if (i == 1) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;  // 头指针指向新节点
        return true;
    }
    LNode* p;
    int j = 1;
    p = L;  // L指向头结点，头结点是第0个节点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}  // 单链表插入数据（不带头结点）

bool InsertNextNode(LNode** P*, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;  // 内存分配失败
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}  // 指定节点的后插操作 （在p节点之后插入元素e)

bool InsertPriorNode(LNode** P*, ElemType e) {
    if (p == NULL) {
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL) {
        return false;  // 内存分配失败
    }
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}  // 指定节点的前插操作 （在p节点之前插入元素e)

bool ListDelete(LinkList& L, int i, ElemType& e) {
    if (i < 1) {
        return false;
    }
    LNode* p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) {
        return false;
    }
    if (p->next == NULL) {
        return false;
    }
    LNode* q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}  // 按位序删除（带头结点）

bool DeleteNode(LNode** p*) {
    if (p == NULL) {
        return false;
    }
    LNode* q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q);
    return true;
}  // 删除指定节点p（该代码无法处理位于最后一个位置的情况）

LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode* p;
    int j = 0;
    p = L;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;

}  // 按位查找（带头结点）
LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}  // 按值查找（带头指针）

int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}  // 求表的长度(带头指针）

LinkList List_TailInsert(LinkList& L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;
    scanf("%d", &x);
    while (x != 9999) {  // 输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}  // 尾插法建立单链表

LinkList List_HeadInsert(LinkList& L) {
    LNode* s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {  // 输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}  // 头插法建立单链表

// 双链表：

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

bool InitDLinkList(DLinklist& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL) {
        return false;
    }
    L->prior = NULL;
    L->next = NULL;
    return true;
}  // 初始化双链表

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

}  // 判断双链表是否为空（带头结点）

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

bool DeleteNextNode(DNode** p*) {
    if (p == NULL) {
        return false;
    }
    DNode* q = p->next;
    if (q == NULL) {
        return false;
    }
    p->next = q->next;
    if (q->next != NULL) {
        q->next->prior = p;
    }
    free(q);
    return true;
}  // 删除p节点的后继节点

void DestoryList(DLinklist& L) {
    while (L->next != NULL) {
        DeleteNextNode(L);
    }
    free(L);
    L = NULL;
}  // 销毁双链表

// 循环单链表：

typedef struct LNode {
    ElemType data;
    struct LNode* next;
} LNode, *LinkList;

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    if (L == NULL) {
        return false;
    }
    L->next = L;
    return true;
}  // 初始化循环单链表

bool isTail(LinkList L, LNode** p*) {
    if (p->next == L) {
        return true;
    } else {
        return false;
    }
}  // 判断节点p是否为循环单链表的表尾节点

// 循环双链表：

typedef struct LNode {
    ElemType data;
    struct LNode *prior, *next;
} DNode, *DLinkList;

bool InitDLinkList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL) {
        return false;
    }
    L->prior = L;
    L->next = L;
    return true;
}  // 初始化循环双链表

bool Empty(DLinkList L) {
    if (L->next == L) {
        return true;
    } else {
        return false;
    }
}  // 判断节循环双链表是否为空

bool isTail(DLinkList L, DNode** p*) {
    if (p->next == L) {
        return true;
    } else {
        return false;
    }
}  // 判断节点p是否为循环单链表的表尾节点

// 静态列表：
#define MaxSize 10
typedef struct LNode {
    ElemType data;
    int next;
} SLinkList[MaxSize];