第 02 章 线性表

顺序存储结构

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;

#define LIST_INIT_SIZE 100 // 初始分配量
#define LIST_INCREMENT 10 // 增量

typedef struct {
    ElemType *elem; // 数组
    int length; // 有效长度
    int listSize; // 分配的空间
} SqList;

/**
 * 初始化
 */
Status initList(SqList *L) {
    L->elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType)); // 开辟初始空间
    if (L->elem == NULL) {
        return ERROR;
    }
    L->length = 0;
    L->listSize = LIST_INIT_SIZE;
    return OK;
}

/**
 * 销毁
 */
Status destroyList(SqList *L) {
    free(L);
    return OK;
}

/**
 * 插入算法
 * 1，判断插入位置i的合法性
 * 2，若存储空间满了则增空间
 * 3，将i-1位置以及其往后的元素像后移动一位
 * 4，将i-1位置的元素赋值为e
 * 5，有效长度增加1
 */
Status insertList(SqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length + 1) { // 当i == L->length + 1 是插入在末尾的
        return ERROR;
    }
    if (L->length >= L->listSize) {
        ElemType *newbase = (ElemType *) realloc(L->elem, (L->listSize + LIST_INCREMENT) * sizeof(ElemType));
        if (newbase == NULL) exit(OVERFLOW);
        L->elem = newbase;
        L->listSize += LIST_INCREMENT;
    }
    for (int j = L->length - 1; j >= i - 1; --j) {
        L->elem[j + 1] = L->elem[j]; // 逐个往后移
    }
    L->elem[i - 1] = e;
    ++L->length;
    return OK;
}

/**
 * 删除操作
 * 1，判断删除位置i的合理性
 * 2，将i-1位置往后的元素前移一个位置
 * 3，有效长度减一
 */
Status deleteList(SqList *L, int i) {
    if (i < 1 || i > L->length) return ERROR;
    for (int j = i - 1; j < L->length; ++j) {
        L->elem[j] = L->elem[j + 1]; // 逐个往前移
    }
    --L->length;
    return OK;
}

/**
 * 遍历
 */
void traverseList(SqList L) {
    printf("SqList = [");
    for (int i = 0; i < L.length; ++i) {
        printf("%d", L.elem[i]);
        if (i != L.length - 1)printf(", ");
    }
    printf("]\n");
}

/**
 * 获取元素
 * 因为用的是数组，所以这个操作非常方便
 */
Status getElem(SqList L, int i, ElemType *e) {
    *e = L.elem[i - 1];
    return OK;
}

/**
 * 测试
 */
int main() {
    SqList L;
    initList(&L);
    insertList(&L, 1, 54);
    insertList(&L, 1, 78);
    insertList(&L, 1, 20);
    insertList(&L, 2, 19);
    traverseList(L);
    deleteList(&L, 1);
    traverseList(L);
    ElemType result;
    getElem(L, 2, &result);
    printf("result = %d\n", result);
    return 0;
}

链式存储结构

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;

typedef struct LNode {
    ElemType data; // 数据域
    struct LNode *next; // 指针域
} LNode,*LinkList; // LinkList是指向单链表的指针，由此唯一确定一个单链表


Status initList(LinkList *head) {
    (*head) = (LinkList) malloc(sizeof(LNode)); // 头指针指向头节点
    (*head)->next = NULL;
    return OK;
}

/**
* 头插法创建链表（为了方便测试，选择接受一个数组后写入）
 * 头插法每次新增的结点都在头部
*/
void createListFromHead(LinkList *head, int n, ElemType arr[]) {
    // 创建链表
    (*head) = (LinkList) malloc(sizeof(LNode));
    (*head)->next = NULL;
    // 循环写入
    LNode *p;
    for (int i = n - 1; i >= 0; --i) {
        p = (LNode *) malloc(sizeof(LNode));
        p->data = arr[i];

        p->next = (*head)->next;
        (*head)->next = p;
    }
}

/**
 * 尾插法创建链表（为了方便测试，选择接受一个数组后写入）
 * 尾插法每次新增加的结点都在尾部
 */
void createListFromTail(LinkList *head, int n, ElemType arr[]) {
    // 创建链表
    (*head) = (LinkList) malloc(sizeof(LNode));

    LNode *p;
    LNode *r;
    r = *head; // 尾指针

    for (int i = 0; i < n; ++i) {
        // 创建新结点并赋值
        p = (LNode *) malloc(sizeof(LNode));
        p->data = arr[i];

        r->next = p; // 尾指针的指针域指向新结点，如果是第一个结点可表示为 (*head)->next = p;
        r = p; // 尾指针指向尾部
    }
    r->next = NULL;
}

// 遍历输出
void traverList(LinkList L) {
    LNode *p = L->next;
    printf("LinkList = [");
    while (p) {
        printf("%d", p->data);
        p = p->next;
        if (p) printf(", ");
    }
    printf("]\n");
}

/**
 * 插入算法
 * 1，找到位置为i-1的元素
 * 2，生成新结点
 * 3，新节点的指针域指向位置为i的元素，位置为i-1的元素的指针域指向新结点
 */
Status insertList(LinkList *head, int i, ElemType e) {
    LNode *p = *head;
    int k = 0;
    while (p && k < i - 1) { // 这里改为 k <= i-2 可能更好理解一些，
        p = p->next;
        ++k;
    }
    if (p == NULL || k > i - 1) return ERROR; // 很明显，这里k是不可能大于i-1的，这里体现了代码的健壮性

    LNode *s = (LNode *) malloc(sizeof(LNode));
    s->data = e;

    s->next = p->next;
    p->next = s;
    return OK;
}

/**
 * 删除算法
 * 1，找到位置为i-1的元素
 * 2，令位置为i-1的元素指向位置为i+1的元素
 * 3，释放位置为i的空间
 */
Status deleteList(LinkList *head, int i) {
    LNode *p = *head;
    int k = 0;
    while (p->next && k < i - 1) {
        p = p->next;
        ++k;
    }
    if (p->next == NULL || k > i - 1) return ERROR;
    LNode *q = p->next; // 位置是i
    p->next = p->next->next;
    free(q);
    return OK;
}

/*
 * 获取元素
 * 算法：使用j来计数，到i-1个元素为止
 */
Status getElem(LinkList head, int i, ElemType *e) {
    LNode *p = head;
    int j = 0;
    while (p != NULL && j <= i-1) {
        p = p->next;
        ++j;
    }
    *e = p->data;
    return OK;
}

int main() {
    LinkList head;
    int a[] = {1, 2, 3};
    createListFromHead(&head, 3, a);
    traverList(head);
    insertList(&head, 2, 8);
    traverList(head);
    deleteList(&head, 3);
    traverList(head);
    ElemType result;
    getElem(head, 2, &result);
    printf("result = %d\n", result);
    LinkList head02;
    int b[] = {8, 12, 3, 56};
    createListFromTail(&head02, 4, b);
    traverList(head02);

    return 0;
}

第 03 章 栈与队列

顺序栈

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int SElemType;
typedef int Status;

#define STACK_INIT_SIZE 100 // 初始分配量
#define STACK_INCREMENT 10 // 增量

typedef struct {
    SElemType *base; // 栈底指针
    SElemType *top; // 栈顶指针，灵魂所在
    int stackSize; // 分配的空间
} SqStack;

Status initStack(SqStack *S) {
    S->base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SqStack));
    if (S->base == NULL) exit(OVERFLOW);
    S->top = S->base; // 表示空栈
    S->stackSize = STACK_INIT_SIZE;
    return OK;
}

/**
 * 进栈操作
 * 如果栈的长度为stackSize，扩大空间
 */
Status push(SqStack *S, SElemType e) {
    if (S->top - S->base == S->stackSize) {
        SElemType *newBase = realloc(S->base, (STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SqStack));
        if (newBase == NULL) exit(OVERFLOW);
        S->top = S->base + S->stackSize;
        S->base = newBase;
        S->stackSize += STACK_INCREMENT;
    }
    *(S->top) = e;
    S->top++;
    return OK;
}

/*
 * 出栈操作
 */
Status pop(SqStack *S) {
    if (S->top == S->base) return ERROR;
    --S->top; // 向下移动一个位置
    SElemType elem = *(S->top);
    printf("SqStack pop elem = %d\n", elem);
    return OK;
}


void getTop(SqStack S) {
    if (S.top == S.base) return;
    SElemType top = *(S.top - 1);
    printf("SqStack top = %d\n", top);
}

/*
 * 遍历
 */
void traverseStack(SqStack S) {
    SElemType *p = S.base;
    printf("SqStack = [");
    while (p < S.top) {
        printf("%d", *p);
        ++p;
        if (p != S.top) printf(", ");
    }
    printf("]\n");
}


int main() {
    SqStack S;
    initStack(&S);
    push(&S, 2);
    push(&S, 6);
    traverseStack(S);
    getTop(S);
    pop(&S);
    traverseStack(S);
    return 0;
}

链栈

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int SElemType;
typedef int Status;

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct LinkStack {
    LinkStackPtr top;
    int count;
} LinkStack;

Status push(LinkStack *S, SElemType e) {
    StackNode *p = (StackNode *) malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;
    S->top = p;
    S->count++;
    return OK;
}

Status pop(LinkStack *S, SElemType *e) {
    StackNode *p;
    *e = S->top->data;
    p = S->top;
    S->top = S->top->next;
    free(p);
    S->count--;
    return OK;
}

int main() {
    printf("Hello, World!\n");
    return 0;
}

两栈共享空间

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int SElemType;
typedef int Status;
#define MAX_SIZE 100

typedef struct {
    SElemType data[MAX_SIZE];
    int top1;
    int top2;
} SqDoubleStack;

Status initStack(SqDoubleStack *S) {
    // 指向各自的栈顶元素
    S->top1 = -1;
    S->top2 = MAX_SIZE;
}

// 压栈操作，根据stackId判断要操作哪一个栈
Status push(SqDoubleStack *S, SElemType e, int stackId) {
    // 判满
    if (S->top1 + 1 == S->top2) return ERROR;
    if (stackId == 1) S->data[++S->top1] = e;
    else S->data[--S->top2] = e;
    return OK;
}

// 压栈操作，根据stackId判断要操作哪一个栈
Status pop(SqDoubleStack *S, SElemType *e, int stackId) {
    if (S->top1 == -1 || S->top2 == MAX_SIZE) return ERROR;
    if (stackId == 1 && S->top1 != -1) {
        *e = S->data[S->top1--];
    } else if (stackId == 2 && S->top2 != MAX_SIZE) {
        *e = S->data[S->top2++];
    }
    return OK;
}

循环队列

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_SIZE 100
typedef int QElemType;
typedef int Status;

/**
 * 循环队列
 * 为了判端队列是否为满，少用一个元素，判断(Q->rear + 1) % MAX_SIZE == Q->front，为true则是队满
 */
typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;

Status initQueue(SqQueue *Q) {
    Q->base = (QElemType *) malloc(MAX_SIZE * sizeof(QElemType));
    if (Q->base == NULL) exit(OVERFLOW);
    Q->front = Q->rear = 0; // 表示空队列
    return OK;
}

/**
 * 队尾入队
 */
Status enQueue(SqQueue *Q, QElemType e) {
    // 判满
    if ((Q->rear + 1) % MAX_SIZE == Q->front) {
        return ERROR;
    }
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_SIZE; // 循环意义上的加一
    return OK;
}

/**
 * 队头出队
 */
Status deQueue(SqQueue *Q, QElemType *e) {
    // 判空
    if (Q->front == Q->rear) {
        return ERROR;
    }
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE; // 循环意义的加1，注意，这里也是加1
    return OK;
}

/**
 * 获取队列长度
 */
int getQueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAX_SIZE) % MAX_SIZE;
}

void traverQueue(SqQueue Q) {
    printf("LinkQueue = [");
    for (int i = Q.front; i < Q.rear; ++i) {
        printf("%d", Q.base[i]);
        if (i + 1 < Q.rear) printf(", ");
    }
    printf("]\n");
}

int main() {
    SqQueue Q;
    initQueue(&Q);
    enQueue(&Q, 54);
    enQueue(&Q, 80);
    enQueue(&Q, 31);
    enQueue(&Q, 26);
    traverQueue(Q);
    int result;
    deQueue(&Q, &result);
    printf("result = %d\n", result);
    traverQueue(Q);
    return 0;
}

链队列

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;

typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front; // 队头
    QueuePtr rear; // 队尾
} LinkQueue;

Status initQueue(LinkQueue *Q) {
    Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode)); // 一开始都指向头结点
    if (Q->front == NULL)exit(OVERFLOW);
    Q->front->next = NULL; // 此处也可以写成 Q->rear->next = null
    return OK;
}

/**
 * 队尾入队
 * 算法：
 * 1，声明结点p并分配空间
 * 2，rear-next = p
 * 3，rear = p
 */
Status enQueue(LinkQueue *Q, QElemType e) {
    QNode *p = (QNode *) malloc(sizeof(QNode));
    if (p == NULL) exit(OVERFLOW);
    p->data = e;
    p->next = Q->rear->next; // p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

/**
 * 队头出队
 */
Status deQueue(LinkQueue *Q, QElemType *e) {
    if (Q->rear == Q->front) return ERROR;
    QNode *p = Q->front->next; // 队头
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) Q->rear = Q->front; // 特殊情况
    free(p);
    return OK;
}

void traverQueue(LinkQueue Q) {
    QNode *p = Q.front->next;
    printf("LinkQueue = [");
    while (p != NULL) {
        printf("%d", p->data);
        p = p->next;
        if (p != NULL)printf(", ");
    }
    printf("]\n");
}


int main() {
    LinkQueue Q;
    initQueue(&Q);
    enQueue(&Q, 77);
    enQueue(&Q, 8);
    enQueue(&Q, 12);
    enQueue(&Q, 35);
    traverQueue(Q);
    QElemType elem;
    deQueue(&Q, &elem);
    traverQueue(Q);
    return 0;
}

第 04 章 串

kmp相关

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

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSTRLEN 255
typedef int Status;
typedef unsigned char SString[MAXSTRLEN + 1]; // 多出一个位置用于存放长度

/**
 * 初始化
 */
Status initStr(SString T, const char *chars) {
    int len = (int) strlen(chars);
    if (len > MAXSTRLEN) {
        return ERROR;
    }
    T[0] = len; // 定长字符串第一个元素存储长度
    for (int i = 1; i <= len; ++i) {
        T[i] = chars[i - 1];
    }
    return OK;
}

/**
 * 朴素的模式匹配算法
 */
int index_simple(SString S, SString T, int pos) {
    int i = pos;
    int j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T[0]) return i - T[0]; // ？
    else return 0;
}

/**
 * 获得kmp算法要使用的next数组
 * 1，固定的，第一位的next值为0，第二位的next值为1
 * 2，之后每第 j 个的next值时，根据第 j-1 进行比较，有如下情况
 * 3，如果 T[j-1] == T[next[j-1]] ,如果这两个值相等，那么next[j] = next[j-1] +1
 * 4，如果不等，则继续沿着next值进行寻找，若找到了相同的，则next[j] = next[x]+1
 * 5，若找不到，则 next[j] = 1
 */
void get_next(SString T, int next[]) {
    int i = 1;
    int j = 0;
    next[1] = 0; // 第一个默认为 0
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

/**
 * 获取nextval数组
 */
void get_nextval(SString T, int nextval[]) {
    int i, j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i] != T[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        } else {
            j = nextval[j];
        }
    }
}

/**
 * KMP模式匹配算法
 */
int index_kmp(SString S, SString T, int pos, int next[]) {
    int i = pos;
    int j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }
    if (j > T[0]) return i - T[0];
    else return 0;
}

/**
 * 输出打印
 */
void printString(SString S) {
    printf("SString = [ ");
    for (int i = 1; i <= S[0]; i++) {
        printf("%c", S[i]);
    }
    printf(" ]\n");
}


int main() {
    SString S;
    char *chars = "goodgoogle";
    initStr(S, chars);
    printString(S);

    SString T;
    char *tchars = "google";
    initStr(T, tchars);
    printString(T);

    // 获取next数组
    int *next = (int *) malloc((T[0] + 1) * sizeof(int));
    get_next(T, next);
    printf("next = ");
    for (int p = 1; p <= T[0]; p++) {
        printf("%d", next[p]);
    }
    printf("\n");
    // 获取nextval数组
    int *nextval = (int *) malloc((T[0] + 1) * sizeof(int));
    get_nextval(T, nextval);
    printf("nextval = ");
    for (int p = 1; p <= T[0]; p++) {
        printf("%d", nextval[p]);
    }
    printf("\n");
    // 测试kmp算法
    int kmp_result = index_kmp(S, T, 1, nextval);
    printf("kmp_result = %d\n", kmp_result);


    return 0;
}

第 05 章 数组和广义表

稀疏矩阵

// 稀疏矩阵的三元组顺序存储结构
typedef struct {
    int i, j; // 该非零元素的下标
    Element e;
} Triple;
typedef struct {
    Triple data[MAX_SIZE + 1]; // 下标为0的空间不用
    int mu, nu, tu; // 行数，列数，非零元素个数
} TSMatrix;

广义表

// 广义表的首尾链表表示法
typedef enum {
    ATOM, LIST
} ELemtag;
typedef struct GLNode {
    Elemtag tag; // 标志域，用于区分元素结点和表结点 
    union { // 元素结点和表结点的联合部分 
      Atomtype atom; // atom 是原子结点的值域 
      struct {
          struct GLNode *hp, *tp; // hp和tp分别指向表头和表尾 
      }ptr; // ptr是表结点的指针域
    };
  }*GList;                           

// 广义表的孩子兄弟链表表示法
typedef enum {
    ATOM, LIST
} ELemtag;
typedef struct GLNode {
    ELemtag tag; // 标志域
    union {
        AtomType atom; // 原子结点的值域
        struct GLNode *hp; // 表结点的指针
    };
    struct GLNode *tp;// 指向兄弟结点
} *GList;

第 06 章 树和二叉树

二叉树

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

#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef char TElemType;
typedef int Status;

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; // 左右孩子
} BiTNode, *BiTree;

/**
 * 统计二叉树中结点个数。
 */
int getSum(BiTree root) {
    int sum = 0;
    if (root != NULL) {
        sum++;
        int left = getSum(root->lchild);
        int right = getSum(root->rchild);
        return sum + left + right;
    }
    return sum;
}

/**
 * 按照先序遍历的顺序去创建二叉树
 */
void createTree(BiTree *T) {
    TElemType ch;
    // ABD##EG###C#F##
    scanf("%c", &ch);
    if ('#' == ch) {
        (*T) = NULL;
    } else {
        (*T) = (BiTree) malloc(sizeof(BiTNode));
        if (!(*T)) exit(OVERFLOW);
        (*T)->data = ch;
        createTree(&(*T)->lchild);
        createTree(&(*T)->rchild);
    }
}

/**
 * 先序遍历：根，左，右
 */
Status PreOrderTraverse(BiTree T, Status(Visit)(TElemType)) {
    if (T) {
        Visit(T->data);
        PreOrderTraverse(T->lchild, Visit);
        PreOrderTraverse(T->rchild, Visit);
        return OK;
    } else return OK;
}

/**
 * 中序遍历：左，根，右
 */
Status InOrderTraverse(BiTree T, Status(Visit)(TElemType)) {
    if (T) {
        if (InOrderTraverse(T->lchild, Visit)) {
            if (Visit(T->data)) {
                if (InOrderTraverse(T->rchild, Visit))
                    return OK;
            }
        }
        return ERROR;
    } else return OK;
}

/**
 * 后序遍历：左，右，根
 */
Status PostOrderTraverse(BiTree T, Status(Visit)(TElemType)) {
    if (T) {
        if (PostOrderTraverse(T->lchild, Visit)) {
            if (PostOrderTraverse(T->rchild, Visit)) {
                if (Visit(T->data))
                    return OK;
            }
        }
        return ERROR;
    } else return OK;
}


Status PrintElement(TElemType e) {
    printf("%c", e);
    return OK;
}


int main() {
    BiTree T;
    createTree(&T);
    PreOrderTraverse(T, PrintElement);
    printf("\n");
    InOrderTraverse(T, PrintElement);
    printf("\n");
    PostOrderTraverse(T,PrintElement);

    return 0;
}

树

// 树的双亲表示法
typedef struct PTNode {
    TElemType data;
    int parent; // 双亲位置
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r,n; // n是结点数，r是根结点的下标
}PTree;

// 带双亲的孩子链表表示法
typedef struct CTNode { // 链表结点
    int child; // 孩子的下标
    struct CTNode *next;
} *ChildPtr;
typedef struct { // 结点
    int parent; // 双亲的下标
    TElemType data;
    ChildPtr firstChild; // 指向第一个孩子的指针
} CTBox;
typedef struct { // 树结构
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; // n是结点数，r是根结点的下标
} CTree;

// 孩子兄弟表示法
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild,*nextsibling; // 第一个孩子，兄弟结点
}CSNode,*CSTree;