考研数据结构

https://blog.csdn.net/HB15458755/article/details/102726035

https://blog.csdn.net/out_of_memory_error/article/details/102332332

第一部分《线性表》
全文中使用的线性表和链表都是基于以下两种定义方式：
不过个人习惯用数组表示线性表，写出来再将每一部分换成线性表更快
#define MaxSize 100 
//定义线性表
typedef int ElemType;
typedef struct SqList{
    ElemType data[MaxSize];
    int length;
}SqList;
//建立一个线性表
void Creat(SqList* &L,ElemType a[],int n){
    int i=0,j=0;
    L=(SqList*)malloc(sizeof(SqList));//这句话记住就行
    while(i<n){
        L->data[j++]=a[i++];
    }
    L->length=n;
}


//定义单链表
typedef int ElemType;
typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode; 
//头插法
void CreatListF(LNode* &L,ElemType a[],int n){
    LNode *s;
    L = (LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    for(int i=0;i<n;i++){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=a[i];               //先给s节点赋值
        s->next=L->next;            //s的next指针指向L的next节点
        L->next=s;                  //L的next指针指向s
        //上面三行务必记住，头插法的核心代码
    }
}
//尾插法
void CreatListF(LNode* &L,ElemType a[],int n){
    LNode *s,*r;
    L = (LNode*)malloc(sizeof(LNode));
    r = L;//r相当于尾指针
    for(int i=0;i<n;i++){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=a[i];               //先给s节点赋值
        r->next=s;                  //r的next指针指向s
        r=s;                        //r指针后移
        //上面三行为尾插法的核心代码
    }
    r->next = NULL;    //这一行不要忘记
}


//定义双链表：
typedef struct DNode{
    Elemtype data;
    struct DNode *pre;
    struct DNode *next;
}DLinkNode; 


//实现两个有序的顺序表a和b合并为一个顺序表a，同时要求不产生新的空间
//算法实现的文字描述：首先从a和b的最后一个元素逐个向前进行比较，将较大的元素定位在a的末尾中，直到合并结束
int comb(int a[],int &na,int b[],int nb){
    if(na + nb > maxSize)
        return -1;//如果a数组的最大长度小于a和b的数字个数和，则失败
    int i=na,j=nb;
    while(j>0){
        if(i==0||a[i-1]<b[j-1]){    //说明此时b[j-1]是第i+j大的元素
            a[j+i-1]=b[j-1];
            j--;
        }else{                      //说明此时a[j-1]是第i+j大的元素
            a[j+i-1]=a[i-1]; 
            i--;
        }
    }
    na=na+nb;
    return na;
}

//合并m个有序表
//做法和实现两个有序表基本相同，同样要求不产生新的空间
//先将一个和第二个合并，然后再和第三个合并，直到和第m个合并完成
void combm(int list[][maxSize],int len[],int m){
    int i,flag;
    for(i=1;i<m;i++){
        flag = comb(list[0],len[0],list[i],len[i]);
        if(flag==-1)
            break ;
    }
    return flag ;
}

//链表翻转

LNode Reverse(LNode &L)
{
    if(L==NULL) return ;        //链表为空，直接返回空链表
    LNode *p=L->next,*q;                //p为工作指针，q为p的后继
    L->next=NULL;               //先将头节点L的next置为NULL
    while(p!=NULL)
    {
        q=p->next;              //暂存p的后继
        p->next=L->next;         //将p节点插入到头节点后  
        L->next=p;
        p=q;
    }
    return L;
}


//定义二叉树
typedef struct BTNode{
    char data;
    struct BTNode *lchild;
    struct BTNode *Rchild;
}BTNode;

//定义线索二叉树
typedef struct TBTNode{
    char data;
    int ltag,rtag;
    struct TBTNode *lchild;
    struct TBTNode *Rchild;
}TBTNode;

//先序递归遍历
void Preorder(BTNode *p){
    if(p != NULL){
        printf("%c ",p->data);
        Preorder(p->lchild);
        Preorder(p->rchild);
    }
}
//中序递归遍历
void Inorder(BTNode *p) {
    if (p != NULL) {
        Inorder(p->lchild);
        printf("%c ", p->data);
        Inorder(p->rchild);
    }
}
//后续递归遍历
void Postorder(BTNode *p) {
    if (p != NULL) {
        postorder(p->lchild);
        postorder(p->rchild);
        printf("%c ", p->data);
    }
}
//层序遍历（借助循环队列）
void Levelorder(BTNode *p) {
    BTNode *que[maxSize];
    BTNode *q = NULL;
    int front = 0, rear = 0;  // 定义一个循环队列
    if (p != NULL) {
        rear = (rear+1)%maxSize;
        que[rear] = p;  // 让根节点入队
        while (front != rear) {  // 只要队列不空，则进行循环
            front = (front+1)%maxSize;
            q = que[front];  // 队头元素出队
            printf("%c\n", q->data);  // 访问队头元素
            if(q->lchild){  // 左子树存在，则左子树根节点入队
                rear = (rear+1) % maxSize;
                que[rear] = q->lchild;
            }
            if(q->rchild){  // 右子树存在，则右子树根节点入队
                rear = (rear+1)%maxSize;
                que[rear] = q->rchild;
            }
        }
    }
}

//先序非递归遍历
void Preorder(BTNode *p){
    if(p !== NULL){
        BTNode *stack[maxSize];
        int top = -1;
        stack[++top] = p;
        BTNode *q;
        while(top != -1){
            q = stack[top--];
            printf("%c ",q->data);
            if(q->lchild != NULL)
                stack[++top] = p->lchild;
            if(p->rchild != NULL)
                stack[++top] = p->rchild;
        }
    }
}

//中序非递归遍历
void Inorder(BTNode *bt){
    BTBode *stack[maxSize];
    int top = -1;
    BTNode *p = bt;
    if(bt != NULL){
        while(top != -1 || p != NULL){
            while(p != NULL){
                stack[++top] = p;
                p = p->lchild;
            }
            if(top != -1){
                p = stack[top--];
                printf("%c ",p->data);
                p = p->rchild;
            }
        }
    }
}
//后续非递归遍历
void PostOrder(BTNode *bt){
    if(bt != NULL){
        BTNode *stack1[maxSize]; int top1 = -1;
        BTNode *stack2[maxSize]; int top2 = -1;
        BTNode *p;
        stack1[++top1] = bt;
        while(top1 != -1){
            p = stack1[top1--];
            stack2[++top2] = p;// 注意这里与先序的区别，放入栈2中即可
            if(p->lchild)   
                stack1[++top1] = p->lchild;
            if(p->rchild)
                stack1[++top1] = p->rchild;
        }
        // 这时候循环结束，则会将逆后序遍历的结果都存放到了栈2中
        // 所以对栈2进行输出即可得到后序遍历的结果
        while(top2 != -1){
            p = stack2[top2--];
            printf("%c ",p-data);
        }
    }
}