【笔记】数据结构的C实现

持续更新……

线性表

#include <stdio.h>

//Status
#define OK 1
#define ERROR 0

//线性表(顺序储存)
#define MAX 20 //最大长度
typedef int ElemType;
typedef struct
{
    ElemType data[MAX];
    int len;//当前长度
}SqList;

//位置参数均从0开始
//获取元素
int GetElem(const SqList * L, int i, ElemType * e)
{
    if(i < 0 || i >= L->len)
        return ERROR;
    *e = L->data[i];
    return OK;
}

//插入元素
int InsertElem(SqList * L, int i, ElemType e)
{
    if(MAX == L->len || i < 0 || i > L->len)
        return ERROR;
    for (int n = L->len; n > i; n--)
    {
        L->data[n] = L->data[n - 1];
    }
    L->data[i] = e;
    L->len++;
    return OK;
}

//删除元素
int DelElem(SqList * L, int i, ElemType * e)
{
    if(i < 0 || i >= L->len)
        return ERROR;
    *e = L->data[i];
    for(int n = i; n < L->len - 1; n++)
        L->data[n] = L->data[n + 1];
    L->len--;
    return OK;
}

链表

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//Status
#define OK 1
#define ERROR 0

//单链表
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;

int GetElem(Node * Head, int i, ElemType * e)
{
    Node * n = Head;
    while(i > 0)
    {
        if((n = n->next) == NULL)
            return ERROR;
        i--;
    }
    *e = n->data;
    return OK;
}

//不能插入到头节点之前
int InsertElem(Node * Head, int i, ElemType e)
{
    Node * n = Head;
    //找到欲插入位置的前一个节点
    while(i > 1)
    {
        if((n = n->next) == NULL)
            return ERROR;
        i--;
    }
    Node * s = malloc(sizeof(Node));
    s->data = e;
    s->next = n->next;
    n->next = s;
    return OK;
}

//不能删除头节点
int DelElem(Node * Head, int i, ElemType * e)
{
    
    Node * n = Head;
    //找到欲删除节点的前一个节点
    while(i > 1) 
    {
        if((n = n->next) == NULL)
            return ERROR;
        i--;
    }
    Node * q = n->next;
    n->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

void CreateList(Node * Head, int n)
{
    srand(time(0));
    Node * s = Head;
    do
    {
        s->next = malloc(sizeof(Node));
        s->next->data = rand() % 100 + 1;
        s = s->next;

    }while(--n > 0);
    s->next = NULL;

}

//只保留头结点
void ClearList(Node * Head)
{
    Node * s = Head->next;
    Node * n;
    while(s)
    {
        n = s->next;
        free(s);
        s = n;
    }
    Head->next = NULL;
}

int GetLength(Node * Head)
{
    int i = 1;
    Node * s = Head;
    while(s->next)
    {
        i++;
        s = s->next;
    }
    return i;
}

链栈

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

//Status
#define OK 1
#define ERROR 0

//链栈
typedef int SElemType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode * next;

}StackNode;

typedef struct 
{
    StackNode * top;
    int count;//栈的长度
}LinkStack;


//进栈
int Push(LinkStack * S, SElemType e)
{
    StackNode * n = (StackNode *)malloc(sizeof(StackNode));
    n->data = e;
    n->next = S->top;
    S->count++;
    S->top = n;
    return OK;
}


//出栈
int Pop(LinkStack * S, SElemType * e)
{
    if(!S->count)
        return ERROR;
    *e = S->top->data;
    StackNode * t = S->top;
    S->top = S->top->next;
    free(t);
    S->count--;
    return OK;

}

//获取栈顶元素
int GetTop(LinkStack * S, SElemType * e)
{
    if(!S->count)
        return ERROR;
    *e = S->top->data;
    return OK;
}


//创建空栈
LinkStack * CreateStack()
{
    LinkStack * S = (LinkStack *)malloc(sizeof(LinkStack));
    S->top = NULL;
    S->count = 0;
    return S;
}

//销毁
void DestroyStack(LinkStack * S)
{
    SElemType e;
    while(S->count)
    {
        Pop(S, &e);
        S->count--;
    }
    free(S);
}

循环队列

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

#define MAX_SIZE 100
//Status
#define OK 1
#define ERROR 0

//循环队列(顺序储存)
typedef int QElemType;
typedef struct Queue
{
    QElemType data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void InitQueue(Queue * Q)
{
    Q->front = 0;
    Q->rear = 0;
}

int QueueLength(Queue * Q)
{
    return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}

int EnQueue(Queue * Q, QElemType e)
{
    if((Q->rear + 1) % MAX_SIZE == Q->front)
        return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_SIZE;
    return OK;
}

int DeQueue(Queue * Q, QElemType * e)
{
    if(Q->rear == Q->front)
        return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE;
    return OK;
}

int GetHead(Queue * Q, QElemType * e)
{
    if(Q->rear == Q->front)
        return ERROR;
    *e = Q->data[Q->front];
    return OK;
}

链队列

#include <stdio.h>
#include <stdlib.h>
//Status
#define OK 1
#define ERROR 0

//链队列
typedef int QElemType;
typedef struct QNode
{                                            
    QElemType data;
    struct QNode * next;
} QNode;

typedef struct LinkQueue
{
    //队头指针、队尾指针
   QNode * front, * rear; 
}LinkQueue;


//入队
int EnQueue(LinkQueue * Q, QElemType e)
{
    QNode * n = malloc(sizeof(QNode));
    if(!n)  return ERROR;
    n->data = e;
    n->next = NULL;
    Q->rear->next = n;
    Q->rear = n;
    return OK;
}


//出队                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
int DeQueue(LinkQueue * Q, QElemType * e)
{
    if(Q->front == Q->rear)
        return ERROR;
    *e = Q->front->next->data;
    QNode * n = Q->front->next;
    Q->front->next = n->next;
    if(Q->rear == n)//出队元素刚好在队尾
        Q->rear = Q->front;
    free(n);
    return 0;
}

//获取队列长度
int QueueLength(LinkQueue *Q)
{
    return (Q->rear - Q->front) / sizeof(QElemType);
}

//清空队列
void ClearQueue(LinkQueue * Q)
{
    while(Q->front->next)
    {
        QNode * n = Q->front->next;
        Q->front->next = n->next;
        free(n);
    }
    Q->rear = Q->front;
}

LinkQueue * CreateQueue()
{
    LinkQueue * Q = malloc(sizeof(LinkQueue));
    QNode * n = malloc(sizeof(QNode));
    n->data = -1;
    n->next = NULL;
    Q->front = n;
    Q->rear = n;
    return Q;
}

KMP模式匹配

//Donald Knuth(K), James H. Morris(M), Vaughan Pratt(P). 

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


int bruteForce(char * str, char * fstr)
{
    int len = strlen(str);
    int flen = strlen(fstr);
    if(0 == len || 0 == flen || flen > len)
    {
        return -1;
    }
    for(int i = 0; i < len - flen + 1; i++)
    {
        int n;
        for(n = 0; n < flen; n++)
        {
            if(str[i + n] != fstr[n])
                break;
        }
        if(n == flen)
            return i;
    }

    return -1;
}

void getNext(char * str, int * next)
{
    //首位必定为0,故i从1开始
    next[0] = 0; 
    int i = 1;
    int now = 0;
    int len = strlen(str);
    while(i < len)
    {
        if(str[now] == str[i])
        {
            now++;
            next[i++] = now;
        }
        else if(now)
        {
            now = next[now - 1];
        }
        else
        {
            next[i++] = 0;
        }
    }

}

int kmp(char * fstr, char * str, int * next)
{
    int i = 0;
    int pos = 0;
    int len = strlen(str);
    int flen = strlen(fstr);
    while(i < len)
    {
        if(str[i] == fstr[pos])
        {
            i++;
            pos++;
        }
        else if(pos)
        {
            pos = next[pos - 1];
        }
        else
        {
            i++;
        }

        if(pos == flen)
        {
            return i - pos;
            //pos = next[pos - 1];
        }
    }

}

int main(void)
{   
    char s[] = "WhatWhereWhy";
    char f[] = "Why";
    int next[strlen(s)];
    getNext(s, next);
    printf("Next:");
    for(int i = 0; i < sizeof(next) / sizeof(next[1]); i++)
    {
        printf("%d,", next[i]);
    }
    printf("\nKMP:%d", kmp(f, s, next));
    printf("\nBF:%d", bruteForce(s, f));
    getchar();

}

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

#define ERROR 0;
#define OK 1;

typedef int TElemType;
//树 链式结构
typedef struct TNode  
{
    TElemType data;
    struct TNode *parent, *firstChild, *rightSib;
}TNode, *Tree;

//创建一个只含根节点的树
Tree CreateTree(TElemType e)
{
    Tree n = malloc(sizeof(TNode));
    n->data = e;
    n->firstChild = NULL;
    n->parent = NULL;
    n->rightSib = NULL;
    return n;
}

//获取树的深度
int TreeDepth(Tree t)
{
    if(!t)
        return 0;
    TNode * n = t->firstChild;
    if(!n)
        return 1;
    int max = -1;
    while(n)
    {
        int dep = TreeDepth(n);
        if(dep > max)
            max = dep;
        n = n->rightSib;
    }
    return 1 + max;
}

//获取第i个子节点
TNode * GetChild(TNode * n, int i)
{
    TNode * s = n->firstChild;
    if(!s)
        return NULL;
    for(int n = 1; n < i; n++)
    {
        s = s->rightSib;
        if(!s)
            return NULL;
    }
    return s;
}

//插入第i个子节点
int InsertChild(TNode * n, int i, TElemType e)
{
    //无子节点,忽略i
    if(!n->firstChild)
    {
        TNode * c = malloc(sizeof(TNode));
        c->data = e;
        c->parent = n;
        c->firstChild = NULL;
        c->rightSib = NULL;
        n->firstChild = c;
        return OK;
    }
    else
    {
        TNode * c = n->firstChild;
        while(i-- > 2)
        {
            c = c->rightSib;
            if(!c)
                return ERROR;
        }
        TNode * s = malloc(sizeof(TNode));
        s->data = e;
        s->parent = n;
        s->firstChild = NULL;
        s->rightSib = c->rightSib;
        c->rightSib = s;
        return OK;
    }
}


//删除第i个子节点
int DeleteChild(TNode * n, int i)
{
    TNode * s = n->firstChild;
    TNode * child;
    if(!s)
        return ERROR;

    //若删除第一个节点
    if(i == 1)
    {
        while(child = s->firstChild)
        {
            DeleteChild(s, 1);
        }
        n->firstChild = s->rightSib;
        free(s);
        return OK;
    }

    //获取第i-1个节点
    for(int n = 1; n < i - 1; n++)
    {
        s = s->rightSib;
        if(!s)
            return ERROR
    }

    //验证第i个节点存在
    if(!s->rightSib)
        return ERROR;

    //递归销毁子节点
    while(child = s->rightSib->firstChild)
    {
        DeleteChild(s->rightSib, 1);
    }
    child = s->rightSib;
    s->rightSib = s->rightSib->rightSib;
    free(child);
    return OK;
}

//输出树
void printTree(TNode * n)
{
    TNode * s = n->firstChild;
    if(!s)
    {
        return;
    }
    do
    {
        printf("%d, ", s->data);
        printTree(s);
        s = s->rightSib;
    } while(s); 
    printf("\n");
}

int main()
{
    Tree t = CreateTree(9);
    TNode * n;
    for(int i = 0; i < 5; i++)
    {
        InsertChild(t, i + 1, i);
        n = GetChild(t, i + 1);
        InsertChild(n, 1, i + 10);
        InsertChild(n, 2, i + 20);
    }
    DeleteChild(t->firstChild, 1);
    DeleteChild(t->firstChild->rightSib, 2);
    printf("DEPTH: %d\n", TreeDepth(t));
    printf("ROOT: %d\n", t->data);
    printTree(t);
    getchar();
}


//——树的其他表示法
//树 父节点表示法
#define MAX_SIZE 100
typedef struct PTNode
{
    TElemType data;
    //父节点的下标
    int parent;

    //改进:
    //首个子节点的下标
    //int firstChild;
    //右节点的下标
    //int rightSib;
}PTNode;

typedef struct PTree
{
    PTNode nodes[MAX_SIZE];
    //结点数
    int count;
    //根的下标
    int root;
}PTree;


//树 子节点表示法
//考虑到每个节点的度不同,可以使用链表结构储存子节点
typedef struct CTNode
{
    //当前子节点的下标
    int child;
    //下一个字节点
    struct CTNode *next;
}CTNode;

typedef struct CTBox
{
    TElemType data;
    //父节点的下标
    int parent;
    //第一个子节点
    CTNode *firstChild;
}CTBox;

typedef struct CTree
{
    CTBox nodes[MAX_SIZE];   
    int root;
    int count;
}CTree;

二叉树

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

//二叉树
typedef char BTElemType;
typedef struct BTNode
{
    BTElemType data;
    struct BTNode * left, * right;
}BTNode, *BTree;

//前序遍历
void NLR(BTree T)
{
    if(!T)
        return;
    printf("%c", T->data);
    NLR(T->left);
    NLR(T->right);
}

//中序遍历
void LNR(BTree T)
{
    if(!T)
        return;
    LNR(T->left);
    printf("%c", T->data);
    LNR(T->right);
}

//后序遍历
void RNL(BTree T)
{
    if(!T)
        return;
    RNL(T->left);
    RNL(T->right);
    printf("%c", T->data);
}

//前序建立二叉树,#代表无节点
static int index;
void CreateBTree(BTree * T, char str[])
{
    BTElemType e;
    e = str[index++];
    if(!e)
        return;
    if(e == '#')
        *T = NULL;
    else
    {
        *T = malloc(sizeof(BTNode));
        if(!*T)
            return;
        (*T)->data = e;
        CreateBTree(&(*T)->left, str);       
        CreateBTree(&(*T)->right, str);   
    }

}

//销毁二叉树
void DestroyBTree(BTree * T)
{
    if(!(*T))
        return;
    DestroyBTree(&(*T)->left);
    DestroyBTree(&(*T)->right);
    free((*T));
}

int main()
{
    BTree T;
    index = 0;
    CreateBTree(&T, "AB#D##C##");
    DestroyBTree(&T);
    index = 0;
    CreateBTree(&T, "XY#Z##9##");
    NLR(T);
    printf("\n");
    LNR(T);
    printf("\n");
    RNL(T);
    getchar();
    return 0;
}

线索二叉树

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

typedef char TElemType;
typedef enum {Link, Thread} Tag;
typedef struct ThrNode
{
    TElemType data;
    struct ThrNode * left, * right;
    Tag ltag, rtag;
}ThrNode, *ThrTree;

//前序建立线索二叉树,#代表无节点
static int index;
void CreateThrTree(ThrTree * T, char str[])
{
    
    TElemType e;
    e = str[index++];
    if(!e)
        return;
    if(e == '#')
        *T = NULL;
    else
    {
        *T = malloc(sizeof(ThrNode));
        if(!*T)
            return;
        (*T)->data = e;
        CreateThrTree(&(*T)->left, str);       
        CreateThrTree(&(*T)->right, str);   
    }

}

//销毁线索二叉树
void DestroyThrTree(ThrTree * T)
{
    if(!(*T))
        return;
    if((*T)->ltag == Link)
        DestroyThrTree(&(*T)->left);
    if((*T)->rtag == Link)
        DestroyThrTree(&(*T)->right);
    free((*T));
}

//中序遍历线索化
ThrNode * pre;
void InThreading(ThrTree T)
{
    if(T)
    {
        InThreading(T->left);
        if(!T->left)
        {
            T->ltag = Thread;
            T->left = pre;
        }
        else
            T->ltag = Link;

        if(pre)
        {
            if(!pre->right)
            {
                pre->rtag = Thread;
                pre->right = T;
            }   
            else
                pre->rtag = Link;
        }    
        
        pre = T;
        InThreading(T->right);
    }
}

//普通中序遍历
void LNR(ThrTree T)
{
    if(!T)
        return;
    if(T->ltag == Link)
        LNR(T->left);
    printf("%c", T->data);
    if(T->rtag == Link)
        LNR(T->right);
}

//线索中序遍历
void ThrLNR(ThrTree T)
{
    ThrNode * n = T;
    while(n)
    {
        //到达最左下节点
        while(n->ltag == Link)
            n = n->left;

        printf("%c", n->data);
        while(n->rtag == Thread && n->right)
        {
            n = n->right;
            printf("%c", n->data);
        }
        n = n->right;
    }
    
}

int main()
{
    ThrTree T;
    //创建线索二叉树
    CreateThrTree(&T, "ABDH##I##EJ###CF##G##");
    //线索化
    InThreading(T);
    //普通中序遍历
    LNR(T);
    printf("\n");
    //线索中序遍历(非递归,效率更高)
    ThrLNR(T);
    //销毁
    DestroyThrTree(&T);
    getchar();

}