整理的一些数据结构基础算法

引言

这份文档是在2021年左右整理的一些数据结构重点，同时也是必背的基础算法。最近需要再复习一遍，在看的同时会进行Leetcode同步实践，如果有错误会随时更新。

链表

将两个递增有序的单链表设计算法成一个非递减有序的链表（链表归并）

int merge(LNode *A,LNode *B,LNode *&C){
    LNode *p=A->next;
    LNode *q=B->next;
    C = A;
    C->next = 0;
    r = C;
    while(p!= NULL && q!=NULL){
        if(p->data <= q->data){
            r->next = p;
            p = p->next;
            r = r->next;
        }
        else{
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    if(p!=NULL) r->next = p;
    if(q!=NULL) r->next = q;
}

查找链表中是否存在一个值为x的结点，若存在，则删除结点并返回1，否则返回0

int delete(LNode* &L,ElemType x){
    LNode *p = L;
    LNode *q;
    while(p->next!=NULL){
        if(p->next->data == x){
            break;
        }
        p = p->next;
    }
    if(p->next == NULL) return 0;
    else{
        q = p->next;
        p->next = q->next;
        free(q);
        return 1;
    }
}

在带头结点的单链表L中，删除所有值为x的结点，并释放空间

void delete(LNode *&L, ElemType x){
    LNode *p = L->next;
    LNode *pre = L;
    LNode *del;
    while(p != NULL){
        if(p->data == x){
            del = p;
            p = p->next;
            pre->next = p;
            free(del);
        }
        else {
            pre = p;
            p = p->next;
        }
    }
}

试编写在头节点的单链表L中删除最小值的高效算法(已知最小值)

void delete(LNode* &L){
    LNode *pre = L;
    LNode *p = L->next;
    LNode *minpre = L;
    LNode *min = L->next;
    while(p != NULL){
        if(p->data < min->data){
            min = p;
            minpre = pre;
        } 
        pre = p;
        p = p->next;
    }
    minpre->next = min->next;
    free(min);
}

A,B两个单链表递增有序，从A,B中找出公共元素产生单链表C，要求不破坏A，B结点

void create(LNode *A, LNode *B, LNode *C){
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r,*s;
    r = C;
    while(p != NULL && q != NULL){
        if(p->data < q->data) p = p->next;
        else if(q->data < q->data) q = q->next;
        else{
            s = (LNode*)malloc(sizeof(LNode));
            s->data = p->data;
            r->next = s;
            r = s;
            p = p->next;
            q = q->next;
        }
    }
    r->next = NULL;
}

查找单链表中倒数第K个结点，若成功，则输出该节点的data，并返回1，否则返回0

int find(LNode *head, int k){
    LNode *p = head->next;
    LNode *res = head;
    int i=1;
    while(p!=NULL){
        p = p->next;
        ++i;
        if(i>k) res = res->next;
    }
    if(res == head) return 0;
    else{
        printf("%d",res->data);
        return 1;
    }
}

编写一个算法将一个非负的十进制数转化为二进制数

int binary(int n){
	int stack[maxsize]; int top=-1;
	int i,result=0;
	while(n！=0){
		stack[++top]=n%2;
		n=n/2;
	}
	while(top!=-1){
		i=stack[top--];
		result = result*10+i; // 注意：特殊算法，记住就行
	}
	return result;
}

设计算法判断带头结点的单链表的全部n个字符是否中心对称，例如xyx（回文）

int fun(LNode *L,int n){
    int i;
    char s[n/2];
    LNode *p = L->next;
    for(i=0;i<n/2;++i){
        p->data = s[i];
        p=p->next;
    }
    i--;
    if(n%2==1) p=p->next;
    while(p!NULL && s[i]=p->data){
        i--;
        p=p->next;
    }
    if(i==-1) return 1;
    else return 0;
}

树

计算二叉树的所有结点个数

int count(BTNode *p){
    int n1,n2;
    if(p == NULL) return 0;
    else{
        n1 = count(p->lchild);
        n2 = count(p->rchild);
        return n1+n2+1;
    }
}

计算二叉树中所有叶子结点的个数

int count(BTNode *p){
    int n1,n2;
    if(p == NULL) return 0;
    if(p->lchild==NULL&&p->rchild==NULL) return 1;
    else{
        n1 = count(p->lchild);
        n2 = count(p->rchild);
        return n1+n2;
    }
}

计算二叉树的深度

int getDepth(BTNode *p){
    int ld,rd;
    if(p==NULL)
        return 0;
    else{
        ld = getDepth(p->lchild);
        rd = getDepth(p->rchild);
        return (ld>rd? ld : rd)+1;
    }
}

求二叉树中，值为x的层号

//DFS
int L = 1;
void fun(BTNode *p, int x){
    if(p！=NULL){
        if(p->data == x)
            printf("%d",x);
        ++L;
        fun(p->lchild,x);
        fun(p->rchild,x);
        --L;
    }
}

先序非递归遍历二叉树

void PreOrder(BiTree T){
    IniteStack(S); 
    BiTree p=T; 
    while(p||!IsEmpty(S)){
        if(p){
            vistit(p); 
            Push(S,p);
            p=p->p.lchild; 
        }else{
            Pop(S,p);
            p=p->rchild;
        }
    }
    
}

中序非递归遍历二叉树

void InOrder2(BiTree T){
    IniteStack(S); 
    BiTree p=T; 
    while(p||!IsEmpty(S)){
        if(p){
            Push(S,p);
            p=p->p.lchild;
        }else{
            Pop(S,p);
            vistit(p);
            p=p->rchild;
        }
    }
}

后序非递归遍历二叉树

void PostOrder2(BiTree T){
    IniteStack(S); 
    BiTree p,r;
    p=T;
    r = NULL;
    while(p||!IsEmpty(S)){
        if(p){
            Push(S,p);
            p->p.lchild;
        }else{
            GetTop(S,p);
            if(p->rchild&&p->rchild!=r) 
                p=p->rchild;
            else{
                pop(S,p);
                visit(p->data);
                r=p;
                p=NULL;
            }
            p=p->rchild;
        }
    }
}

:heavy_exclamation_mark:判断二叉树是否为完全二叉树

//判断是否为完全二叉树
bool judge(BTNode *p){
	if(p==NULL) return ture;
	SqQueue Q;
	InitQueue(Q);//初始化队列
	EnQueue(Q,p);//根结点入队
	while(!isEmpty(Q)){
		DeQueue(Q,p);
		if(p==NULL) break;//读到空指针则停止循环
		EnQueue(Q,p->lchild);//左孩子入队
		EnQueue(Q,p->rchild);//右孩子入队
	}
	while(!isEmpty(Q)){//检查此时队列中是否还有未访问到的结点
		DeQueue(Q,p);
		if(p != NULL) return false;
	}
	return true;
}
 

:heavy_exclamation_mark:判断二叉树是否是二叉排序树

//中序遍历思想，非递归
void judge(BiTree T){
    IniteStack(S); 
    BiTree p=T; 
    int pre = INT_MIN;
    while(p||!IsEmpty(S)){
        if(p){
            s.push(p);
            p=p->p.lchild;
        }else{
            p = s.top();
            s.pop();
            if(p->data<pre)//若父节点小于左子树
                break;
            pre = p->data;
            p=p->rchild;
        }
    }
    if(p==NULL && s.empty())
        return true;
    else
        return false;
}

:heavy_exclamation_mark:利用二叉树遍历的思想判断一个二叉树是否为平衡二叉树

int getDepth(BTNode *p){
    int ld,rd;
    if(p==NULL)
        return 0;
    else{
        ld = getDepth(p->lchild);
        rd = getDepth(p->rchild);
        return (ld>rd? ld : rd)+1;
    }
}
void judge(BTNode *p){
    if(p == NULL)
        return true;
    int ld,rd,gap;
    ld = getDepth(p->lchild);
    rd = getDepth(p->rchild);
    gap = rd - ld;
    if (gap > 1 || gap < -1)
        return 0;
    //递归判断
    return judge(p->lchild)&&judge(p->rchild);
}

二叉查找树的插入结点K

int BST_Insert(BiTree &T,KeyType k){
    if(T==Null){
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = Null;
        return 1;
    }
    else if(k==T->key) return 0; //二叉树不允许值相同
    else if(k<T->key)
        return BST_Insert(T->lchild,k);
    else if(k>T->key)
        return BST_Insert(T->rchild,k);
}

二叉查找树中删除结点K

删除情况：

​ (以删除结点z为例)

1. 若z是叶子结点，则直接删除

2. 若z只有一颗左/右子树，则让z的子树成为z的父结点的子树(替代z的位置)

3. 若z既有左又有右子树

   （1）直接后继：z的右子树最左下角结点x(右子树最小的值)，替代z的位置，然后删除原来的x。

   （2）直接前驱：z的左子树最右下角结点y(左子树最大的值)，替代z的位置，然后删除原来的y。

BiTree BST_Delete(BiTree &T,keyType k){
    BSTNode tmp;
    //未找到删除结点
    if(!T) printf("未找到删除元素");
    
    //找需要删除的结点
    else if(k < T->data)
        T->left = BST_Delete(k,T->lchild);
    else if(k > T->data)
        T->right = BST_Delete(k,T->rchild);
    
    //找到结点
    else{
        if(T->lchild && T->rchild){//类型3,直接后继
            tmp = FindMin(T->rchild);
            T->data = tmp->data;
            T->rchild = BST_Delete(T->data,T->rchild);
        }else {//类型1和2
            tmp = T;
            if(!T->lchild) //判断左孩子不存在，即只有右孩子或无子节点
                T = T->rchild;
            else if (!T->rchild)//只有左孩子或无子节点
                T= T->lchild;
            free(tmp)；
        }   
    }
}

堆

优先队列

//默认最大优先级队列
priority_queue<int,vector<int>>;
//最小优先级队列,从小到大排
priority_queue<int,vector<int>,greater<int>>;
//最大优先级，从大到小排
priority_queue<int,vector<int>,less<int>>;

排序

:heavy_exclamation_mark:插入排序

//带哨兵，A[0]空出来作为哨兵
void InsertSort(ElemType A[], int n){
    int i,j;
    for(i=2;i<=n;i++){
        if(A[i]<A[i-1]){
            A[0] = A[i]; 
            for(j = i-1; A[0] < A[j]; --j)
                A[j+1] = A[j];
			A[j+1] = A[0];
        }
    }
}

//无哨兵
void  InsertSort(ElemType A[], int n){
  int i,j,temp;
  for(int i=1; i<n; i++)
  {
    if(A[i]<A[i-1])
    {
      temp = A[i];
      for(j=i-1;j>=0&&A[j]>temp; --j)
        A[j+1] = A[j];
      A[j+1] = temp;
    }
  }
}

:heavy_exclamation_mark:折半插入

//空出A[0]
void InsertSort(ElemType A[], int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0] = A[1];
        low = 1;
        high = i-1;
        while(low <= high){
          //计算mid位置
            mid = (low + high)/2;
          //比较
            if(A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
          //依次后移
            for(j = i-1; j >= low; --j)
                A[j+1] = A[j];
			A[low] = A[0];
        }
    }
}

希尔排序

void ShellSort(int A[], int n){
    int temp;
    for(int d=n/2; d>0; d=d/2)	{	
        for(int i=d; i<n; ++i){
            temp = A[i];
            int j=i;
            while(j>=d && A[j-d]>temp){
                A[j]=A[j-d];
                j-=d;
            }
        }
    }
}

冒泡排序

void BubbleSort(ElemType A[], int n){
    int i,j,flag;
    for(i=0; i<n-1; ++i){
        flag=0;
        for(j=0; j<n-1-i; ++j){
            if(A[j]>A[j+1]){		//升序
                swap(A[j],A[j+1]);//交换
            	flag = 1;
            }
        }
        if(flag=0) return;
    }
}

快速排序

c语言版本 递归

void QuickSort(int A[], int low, int high){
    if(low < high){			//跳出条件
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos-1);
        QuickSort(A, pivotpos+1, high);
    }
}
int Partition(int A[], int low, int high){
    int pivot = A[low];
    while(low < high){
        while(low<high && A[high]>=pivot) --high;
        A[low] = A[high];
        while(low<high && A[low]<=pivot)++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return	low;
}

c++版本(改)

void quicksort(int x[], int first, int last){
    int pos;
    if(first < last){
        pos = split(x, first, last);
        quicksort(x, first, pos-1);
        quicksort(x, pos-1, last);
    }
}

int splite(int x[],int first, int last){
    int pivot = x[first]; //假定选取first位置为基准
    int left = first;
    int Right = last;
    while(left < right){
        while(pivot < x[right]) 
            --right;
        while(left < right && x[left] <= pivot) 
            ++left;
        if(left<right) 
            swap(x[left],x[right]);
    }
    int pos = right;
    x[first] = x[pos];
    x[pos] = pivot;
    return pos;
}

归并排序

int *B = (int*)malloc(n*sizeof(int));
void Merge(int A[], int low, int mid, int high){
    int i, j, k;
    for(k=low; k<=high; k++)
        B[k] = A[k];
    for(i=low,j=mid+1,k=i; i<=mid && j<=high; k++){
        if(B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }//for
    while(i<=mid)	A[k++]=B[i++];
    while(j<=high)	A[k++]=B[j++];
}
void MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high) / 2;
        MergSort(A, low, mid); 
        MergSort(A, mid+1, high);
        Merge(A, low, mid, high);	//每次递归到二路归并
    }
}

堆排序

//建立大根堆
void BuildMaxHeap(ElemType A[], int len){
    for(int i=len/2; i>0; i--){
        HeadAdjust(A,i,len);
    }
}
void HeadAdjust(ElemType A[], int len){
    A[0] = A[k];
    for(i=2*k; i<len; i*=2){
        if(i<len && A[i]<A[i+1]) i++;
        if(A[0]>=A[i]) break;
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}
//排序
void HeapSort(ElemType A[], int len){
    BuildMaxHeap(A,len);
    for(i=len; i>1; i--){
        Swap(A[i],A[1]);
        HeadAdjust(A,i,i-1)
    }
}