数据结构考研代码练习

第二章 线性表

c语言中的链表

回顾c中的链表是如何是现实的：

#include <stdio.h>
#include <stdlib.h>
struct NODE{
    int data; //数据域
    struct NODE *next;  //指向自身的指针 指针域;
};
typedef struct NODE node;
node *head;
void Init(){
    head = (node *)malloc(sizeof(node));
    node *cur = head, *s;  //cur 表示当前位置的结点指向 s 表示每次添加新的一个结点
    int cnt;
    printf("input the number of node\n");
    scanf("%d", &cnt);
    while (cnt --){
        s = (node *)malloc(sizeof (node));
        scanf("%d", &s->data);
        cur->next = s;
        s->next = NULL;
        cur = s;
    }
}
void TraverseNodes(){
    node *cur = head->next;
    while (cur != NULL){
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
void DeleteNode(){
    printf("input the value to delete \n");
    int n;
    scanf("%d", &n);
    node *cur = head->next;
    while (cur != NULL){
        if (cur->next->data == n) {
                cur->next = cur->next->next;  break;
        }
        cur = cur->next;
    }
    TraverseNodes();
}
void InsertToTail(){
    node *cur = head ->next;
    while (cur->next != NULL){
        cur = cur->next;
    }
    node *s = (node *)malloc(sizeof (node));
    printf("input the node value to be insert\n");
    scanf("%d", &s->data);
    cur->next = s;
    s->next = NULL;
    TraverseNodes();
}
void InsertMid(){ // 在特定元素之后插入一个元素
    printf("input the value to insert where after it\n");
    int n;
    scanf("%d", &n);
    node *cur = head->next;
    while (cur->data != n){ // 如果插到目标位置之前就应当找到目标位置的前驱  条件为 cur->next->data != n;
        cur = cur->next;
    }
    if (cur->data != n && cur->next == NULL) {
        printf("the value is not exist !\n");
        return ;
    }
    node *s = (node *)malloc(sizeof (node));
    printf("input the value to insert\n");
    scanf("%d", &s->data);
    s->next = cur->next;
    cur->next = s;
    TraverseNodes();
}
void InsertToHead(){ // 同样地, 也可以使用头插法来初始画链表；
    printf("int the value to insert\n");
    node *s = (node *)malloc(sizeof (node));
    scanf("%d", &s->data);
    s->next = head->next;
    head->next = s;
    TraverseNodes();
}
void BubbleSort(){
    node *t1, *t2;
    for (t1 = head->next; t1 != NULL; t1 = t1->next){
        for (t2 = head->next; t2 != NULL; t2 = t2->next){
            if (t1->data < t2->data){
                int temp = t1->data;
                t1->data = t2->data;
                t2->data = temp;
            }
        }
    }
    TraverseNodes();
}
int main(){
    Init();
    TraverseNodes();
    BubbleSort();
    return 0;
}

单向链表

#include <iostream>
#include <cstdio>
typedef struct Lnode{
    int data;
    struct Lnode *next;
}Lnode, *LinkList;

bool InitList(LinkList &head){
    head = (Lnode *)malloc(sizeof(Lnode));
    head->next = NULL;
    return head == NULL;
}

void CreateList(LinkList head, int cnt){
    Lnode *cur = head;
    printf("input the i node's value to LinkList \n");
    while (cnt --){
        Lnode *s = (Lnode *)malloc(sizeof(Lnode));
        scanf("%d", &s->data);
        s->next = NULL;
        cur->next = s;
        cur = s;
    }
}
void TravserseLinkList(LinkList head){
    Lnode *cur = head->next;
    while (cur != NULL){
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
int GetElem(LinkList head, int i ){ // 获取第i的值
    Lnode* cur = head;
    while (i -- && cur != NULL) cur = cur->next;
    return cur->data;
}

// 获取第i个元素的前驱
Lnode *PriorElem(LinkList head, int i){
    Lnode* cur = head;
    i -= 1;
    while (i -- && cur != NULL) cur = cur->next;
    return cur;
}

bool ListEmpty(LinkList head){
    return head->next == NULL;
}

void GetLen(LinkList head, int &len){ // 这里使用引用 也可以返回len
    Lnode *cur = head->next;
    while (cur != NULL){
        len ++;
        cur = cur->next;
    }
}
/*
 再第i个元素之前插入一个元素 这里 元素插入的方式就是头插法，
 也可以通过这样的方式实现结点的建立
*/
void ListInsert(LinkList head, int i, int v){
    Lnode *cur, *s;
    cur = PriorElem(head, i);
    s = (Lnode *)malloc(sizeof(Lnode));
    s->data = v;
    s->next = cur->next;
    cur->next = s;
}

void ListDelete(LinkList head, int i){ // 删除第i个结点s
    Lnode *cur = PriorElem(head, i), *t;  // cur 获取第i个结点的前驱
    t = cur->next;
    cur->next = t->next;
    free(t);
}
void ClearList(LinkList head){
    Lnode *cur = head->next, *t;
    while (cur != NULL){
        t = cur->next;
        free(cur);
        cur = t;
    }
    head->next = NULL;
}
void DestoryList(LinkList &head){
    ClearList(head);
    free(head);
    head = NULL;
}
int main(){
    LinkList head;
    InitList(head);
    CreateList(head, 4);
    ListDelete(head, 2);
    TravserseLinkList(head);
    return 0;
}

思考：

1. 链表的实现的原理是什么和顺序表有什么区别？优缺点各是什么？
2. 有无头指针有什么区别？
3. 头插法和尾插法有什么区别？
4. 元素结点的插入的操作（s->next = cur->next;cur->next = s;）可以互换顺序吗 ？ 原因是什么？
5. 为什么链表的初始化操作需要 InitList(LinkList &head) 需要使用引用的符号 ， 而创建CreateList(LinkList head, int cnt) 或者 修改操作等不需要引用符号？ 原因是什么？ 解释原理

双向链表

#include <iostream>
#include <cstdio>
typedef struct Dnode{
    int data;
    struct Dnode *next, *prior;
}Dnode, *DLinkList;

bool InitDList(DLinkList &head){
    head = (Dnode *)malloc(sizeof(Dnode));
    head->next = NULL, head->prior = NULL;
    return head == NULL;
}
void CreateDLinkList(DLinkList head, int i){
    DLinkList cur = head;
    printf("input the value of Dlinklist\n");
    while (i --){
        DLinkList s = (Dnode *)malloc(sizeof(Dnode));
        scanf("%d", &s->data);
        s->next = NULL;
        cur->next = s;
        s->prior = cur;
        cur = s;
    }
}
void TraverseDLinkList(DLinkList head){
    DLinkList cur = head->next;
    while (cur != NULL){
        printf("当前的值:%d, 当前结点的前驱为%d\n", cur->data, cur->prior->data);
        cur = cur->next;
    }
}
Dnode *GetPriorElem(DLinkList head, int i){
    Dnode *cur = head;
    i -= 1;
    while (i -- && cur != NULL) cur = cur->next;
    return cur;
}
void DLinkListInsert(DLinkList head, int i, int v){
    Dnode *cur, *s;
    cur = GetPriorElem(head, i);
    s = (Dnode *)malloc(sizeof(Dnode));
    s->data = v;
    s->next = cur->next;
    cur->next->prior = s;
    s->prior = cur;
    cur->next = s;
}
void DLinkListDelete(DLinkList head, int i){
    Dnode *t,  *cur = GetPriorElem(head,  i);
    t = cur->next;
    cur->next = t->next;
    t->next->prior = cur;
    free(t);
}
int main(){
    DLinkList head;
    InitDList(head);
    CreateDLinkList(head, 4);
    //DLinkListInsert(head, 2, 1000);
    DLinkListDelete(head, 2);
    TraverseDLinkList(head);
    return 0;
}

思考

1. 双向链表和单向链表有什么区别？
2. 双向链表中插入元素的结点（s->next = cur->next;cur->next->prior = s;s->prior = cur;cur->next = s;）的操作可以交换吗？ 说出原因 原理和方案

第三章 栈和队列

顺序栈

#include <cstdio>
#define MAXSIZE 30

typedef struct Sqstack{
    int top;
    int data[MAXSIZE];
}Sqstack;

void InitStack(Sqstack &s){
    s.top = -1;
}
bool StackEmpty(Sqstack s){
    return s.top == -1;
}
bool Push(Sqstack &s, int v){
    if (s.top == MAXSIZE - 1) return false;
    s.data[++ s.top] = v;

    return true;
}
bool Pop(Sqstack &s, int &v){
    if (s.top == -1) return false;
    v = s.data[s.top --];
    return false;
}
bool GetTop(Sqstack s, int &v){
    if (s.top == -1) return false;
    v = s.data[s.top];
    return false;
}
int main(){
    Sqstack s;
    InitStack(s);
    Push(s, 100);
}

链式栈

#include <cstdio>
#include <iostream>

typedef struct Stack{
    int data;
    struct Stack *next;
}Stack, *Listack ;

void InitStack(Listack &s){
    s = (Stack *)malloc(sizeof(Stack));
    s->next = NULL;
}
bool StackEmpty(Listack s){
    return s->next == NULL;
}
void Push(Listack s, int v){
    Stack *p;
    p = (Stack *)malloc(sizeof(Stack));
    p->data = v;
    p->next = s->next;
    s->next = p;
}
void Pop(Listack s, int &v){
    Stack *p;
    if (s->next == NULL) return;
    p = s->next;
    v = p->data;
    s->next = p->next;
    free(p);
}
void GetTop(Listack s, int &v){
    Stack *p;
    if (s->next == NULL) return;
    p = s->next;
    v = p->data;
}
int main(){
    Listack s;
    InitStack(s);
}

顺序队列

循环队列

链式队列

#include <cstdio>
#include <iostream>
typedef struct LinkNode{
    int data;               //数据域
    struct LinkNode *next;  // 指针域
}LinkNode;

typedef struct LinkQueue{
    LinkNode *front, *rear; //两个指向链表位置元素的指针 即表示队头和 队尾
}LinkQueue;

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}
bool QueueEmpty(LinkQueue Q){
    return Q.front == Q.rear; // 对头指针和队尾指针的指向相同的时候我们认为队列为空
}
void EnQueue(LinkQueue &Q, int v){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = v;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}
// 出队的元素从对头实现 原理就是带有头指针链表中删除第一个结点的元素
void DeQueue(LinkQueue Q, int &v){
    if (QueueEmpty(Q)) return;
    LinkNode *t = Q.front->next;
    v = t->data;
    Q.front->next = t->next;
    if (Q.rear == t) Q.rear == Q.front; // 如果只有一个结点时候
    free(t);
}
int main(){
    LinkQueue Q;
    InitQueue(Q);
    return 0;
}

思考

以上完成了 队列链式的基本操作思考如下问题

1. 为什么队列的对头和队尾需要用结构体组合声明 ？
2. 队列中的出队 和 入队的操作和单向链表中的基本操作有什么联系 ？
3. 观察 入队声明函数 EnQueue(LinkQueue &Q, int v) 和 出队声明函数 DeQueue(LinkQueue Q, int &v)有什么区别 ？
4. 基于第三问 为什么有这样的区别？ 请解释原因和原理？

栈与队列的应用

第四章 串

模式匹配算法

#include <cstdio>
#include <iostream>
using namespace std;
int GetIndex(string s1, string s2){
    int i = 0, j = 0;
    int len1 = s1.size(), len2 = s2.size();
    while (i < len1 && j < len2){
        if (s1[i] == s2[j])
            i ++, j ++;
        else
            j = 0, i = i - (j - 1);
    }
    if (j = len2) return i - j + 1;
    return 0;
}
int main(){
    string s1, s2;  // s1 为主串
    cin >> s1 >> s2;
    printf("字符串起始匹配为第%d个字符串", GetIndex(s1, s2));
    return 0;
}

KMP算法

next数组：

1. next[i] 以i为中点的后缀和 从1开始的前缀相等， 后缀的长度最长

   p[1, j] (前缀)= p[i - j + 1, i] （后缀）

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}

第五章 树和二叉树

二叉树的基本操作

#include <cstdio>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

typedef struct BiTnode{
    char  data;
    struct BiTnode *lchild, *rchild;
}BiTnode, *BiTree;
void CreateBiTree(BiTree &T){
    char c;
    scanf("%c", &c);
    if (c == '#'){
        T = NULL;
    }
    else {
        T = (BiTnode *)malloc(sizeof (BiTnode));
        T->data = c;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void PreOrderTraverse(BiTree T, int level){
    if (T != NULL){
        printf("当前的结点的值为%c  当前的层数%d\n", T->data, level);
        PreOrderTraverse(T->lchild, level + 1);
        PreOrderTraverse(T->rchild, level + 1);
    }
}

void InOrderTraverse(BiTree T, int level){
    if (T != NULL){
        InOrderTraverse(T->lchild, level + 1);
        printf("当前的结点的值为%c  当前的层数%d\n", T->data, level);
        InOrderTraverse(T->rchild, level + 1);
    }
}

void PostOrderTraverse(BiTree T, int level){
    if (T != NULL){
        PostOrderTraverse(T->lchild, level + 1);
        PostOrderTraverse(T->rchild, level + 1);
        printf("当前的结点的值为%c  当前的层数%d\n", T->data, level);
    }
}
// 层序遍历使用STL， 也可以使用手写的Queue
void LayerOrder1(BiTree T){
    queue<BiTree> q;
    unordered_map<BiTree, int> m;
    q.push(T);
    m[T] = 1;
    while (!q.empty()){
        BiTnode *node = q.front();
        q.pop();
        if (node->lchild != NULL) q.push(node->lchild), m[node->lchild] = m[node] + 1;
        if (node->rchild != NULL) q.push(node->rchild), m[node->rchild] = m[node] + 1;
        printf("访问到当前的结点的值为：%c 所在的层数：%d\n", node->data, m[node]);
    }
}
void Search(BiTree T, int v, int x){
    if (T = NULL) return;
    if (T->data == v) T->data = x;
    Search(T->lchild, v, x), Search(T->rchild, v, x);
}
int main(){
    BiTree T = NULL;
    CreateBiTree(T);
    PreOrderTraverse(T, 1);
    LayerOrder1(T);
}
/*
1:
AB#D##C#E##
2:
AB##C##
*/

思考

1. 二叉树建立的时候为什么CreateBiTree(BiTree &T)需要& 符号，不添加会怎么样？ 而链表中创建的过程中没有使用 &符号呢，区别是什么？
2. 二叉树的建立和链表的建立有什么联系， 解释原理？
3. 二叉树这几种遍历之间有什么关系？ 可否根据遍历的结果给出二叉树的图形， 给出具体方案

给定遍历顺序求二叉树

BST树

#include <cstdio>
#include <iostream>

typedef struct BiTnode{
    int  data;
    struct BiTnode *lchild, *rchild;
}BiTnode, *BiTree;

BiTnode* CreateNode(int v){
    BiTnode* node = (BiTnode *)malloc(sizeof (BiTnode));
    node->data = v;
    node->lchild = node->rchild = NULL;
    return node;
}
void Insert(BiTree &root, int v){
    if (root == NULL){
        root = CreateNode(v);
        return;
    }
    if (v == root->data)
        return;
    else if (v < root->data)
        Insert(root->lchild, v);
    else
        Insert(root->rchild, v);
}
BiTnode* CreateBST(int data[], int n){
    BiTnode* root = NULL;
    for (int i = 0; i < n; i++)
        Insert(root, data[i]);
    return root;
}
void InOrderTraverse(BiTnode *root){
    if (root != NULL){
        InOrderTraverse(root->lchild);
        printf("%d\n", root->data);
        InOrderTraverse(root->rchild);
    }
}
BiTnode* FindMax(BiTnode* root){
    while (root->rchild != NULL) root = root->rchild;
    return root;
}

BiTnode* FindMin(BiTnode* root){
    while (root->lchild != NULL) root = root->lchild;
    return root;
}
void DeleteNode(BiTree &root, int v){
    if (root == NULL) return;
    if (root->data == v){
        if (root->lchild == NULL && root->rchild == NULL) root = NULL;
        else if (root->lchild != NULL){
            BiTnode* pre = FindMax(root->lchild);
            root->data = pre->data;
            DeleteNode(root->lchild, pre->data);
        } else {
            BiTnode* next = FindMin(root->rchild);
            root->data = next->data;
            DeleteNode(root->rchild, next->data);
        }
    } else if (root->data > v) {
        DeleteNode(root->lchild, v);
    } else {
        DeleteNode(root->rchild, v);
    }
}
int main(){
    int data[8] = {8, 1, 6, 0, 4, 1, 5, 2};
    BiTnode *root = NULL;
    root = CreateBST(data, 8);
    DeleteNode(root, 5);
    InOrderTraverse(root);
    return 0;
}

AVL树

#include <cstdio>
#include <iostream>
using namespace std;

typedef struct BiTnode{
    int  data, height;
    struct BiTnode *lchild, *rchild;
}BiTnode, *BiTree;

BiTnode* CreateNode(int v){
    BiTnode* node = (BiTnode *)malloc(sizeof (BiTnode));
    node->data = v;
    node->height = 1;
    node->lchild = node->rchild = NULL;
    return node;
}

int getHeight(BiTree root){
    if (root == NULL) return 0;
    return root->height;
}

int getBalanceFactor(BiTree root){
    return getHeight(root->lchild) - getHeight(root->rchild);
}

void updateHeight(BiTree root){
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}

void Search(BiTree root, int x ){
    if (root == NULL){
        printf("search failed ！");
        return ;
    }
    if (x == root->data){
        printf("%d\n", root->data);
    } else if (x < root->data){
        Search(root->lchild, x);
    } else {
        Search(root->rchild, x);
    }
}
void LRotate(BiTree &root){
    BiTnode *temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    updateHeight(temp);
    updateHeight(root);
    root = temp;
}
void RRotate(BiTree &root){
    BiTnode *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

void Insert(BiTree &root, int v){
    if (root == NULL){
        root = CreateNode(v);
        return;
    }
    if (v < root->data){
        Insert(root->lchild, v);
        updateHeight(root);
        if (getBalanceFactor(root) == 2){ // L型
            if (getBalanceFactor(root->lchild) == 1){ //  LL 型
                RRotate(root);
            } else if (getBalanceFactor(root->lchild) == -1) {  // LR型
                 LRotate(root->lchild), RRotate(root);
            }
        }
    } else {
        Insert(root, v);
        updateHeight(root);
        if (getBalanceFactor(root) == -2){ //R
            if (getBalanceFactor(root->rchild) == -1){ // RR
                LRotate(root);
            }else if (getBalanceFactor(root->rchild) == 1) {  // RL
                RRotate(root->rchild), LRotate(root);
            }
        }
    }
}
BiTnode* Create(int a[], int n){
    BiTnode *node = NULL;
    for (int i = 0; i < n; i++) Insert(node, a[i]);
    return node;
}
int main(){
    int data[8] = {8, 1, 6, 0, 4, 1, 5, 2};
    BiTnode *root = NULL;
    root = Create(data, 8);
}

Huffman树

树和森林之间的转化

并查集

#include <cstdio>

const int N = 100;p
int p[N];
int Find(int x){
    if (p[x] != x) p[x] = Find(p[x]);
    return p[x];
}
void Union(int a, int b){
    a = Find(a), b = Find(b);
    if ( a!= b) p[a] = b;
}
int main(){
    return 0;
}