首页 DS

# 线性表方向

# 链表的合并

设计实现将两个带有头节点的有序链表合并为一个新的有序链表。

void marge(LNode *A,LNode *B,LNode *C){
    LNode p = A->next;
    LNode q = B->next;
    LNode r;
    r->next = null;
    C = A;
    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) r = p;
    if(q) r = q;
}

# 链表的逆置

设计实现将无头节点链表进行逆置

void invert(LinkList &L){
    p=L;
    q=p->next;
    while(p){
        r=q->next;
        q->next=p;
        p=q;
        q=r;
    }
    L->next=null;
    L=p;
}

# 顺序表的逆置

设计一个算法，将顺序表 L 所有的元素逆置，要求算法效率尽可能地高。

void reverse(Sqlist &L){
    ElemType temp;
    for(int i=0; i<L.length/2; i++){
        temp = L[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1] = temp;
    }
}

一种” 就地 “思想

# 统计单链表 HL 中的值等于 x 的个数

int countX(LNode *HL, ElemType x){
    int countNum = 0;
    LNode p = HL->next;
    while(p){
        if(p->data == x){
            countNum++;
        }
        p = p->next;
    }
    return countNum;
    
}

# HL 是单链表的头指针，删除头节点

ElemType DeleFront(LNode *&HL){
    if(HL == null) exit(1);
    LNode *p = HL;
    ElemType con = p->data;
    p->next =  p->netx->next;
    return com;
}

# 判断单链表是否中心对称

  1. 链表计数
  2. 动态开辟数组（逻辑栈）
  3. 奇数个要跳过最中心的那个元素
  4. 链表向后，栈向下依次检查
  5. 结束前记得 free 栈
bool isDC(LinkList *L) {
    if (L == NULL || L->next == NULL) return true;
    // 计算链表长度
    int count = 0;
    LinkList *p = L;
    while (p) {
        count++;
        p = p->next;
    }
    // 动态分配栈空间
    int *stack = (int *)malloc((count / 2) * sizeof(int));
    if (stack == NULL) return false;
    p = L;
    int top = -1;
    for (int i = 0; i < count / 2; i++) {
        stack[++top] = p->data;
        p = p->next;
    }
    // 如果链表长度为奇数，跳过中间的节点
    if (count % 2 != 0) p = p->next;
    // 开始比较
    while (p) {
        if (p->data != stack[top--]) {
            free(stack);
            return false;
        }
        p = p->next;
    }
    free(stack);
    return true;
}
# 判断单链表是否递增


bool isIncrease(LinkList *l){
    LinkList *p = l;
    int nowData = p->data;
    p = p->next;
    while(p){
        if(p->data>nowData){
            nowData = p->data;
            p = p->next;
        }else{
            return false;
        }
    }
    return true;
}
# 链表 A，链表 B，求 A 与 B 的交集生成链表 C


bool isExistence(LinkList *L,Elemtype goData){
    if(L==null) return true;
    LinkList *p = L;
    while(p){
        if(p->data == goData) return false;
        p=p->next;
    }
    return true;
}
void intersectionAB(LinkList *A,LinkList *B,LinkList *&C){
    LinkList *a=A;
    LinkList *b=B;
    LinkList *c=C;
    LinkList go;
    LinkList *goP=go;
    
    while(a){
        while(b){
            if(a->data==b->data&&isExistence(goP)){
                c = (LinkList*)malloc(sizeof(LinkList));
                go = (LinkList*)malloc(sizeof(LinkList));
                c->data = b->data;
                c = c->next;
                goP = goP->next;
            }
            b = b->next;
        }
        a = a->next;
        b = B;
    }
}
# 链式有序归并


void mergelkList(LinkList *a,LinkList *b,LinkList &*c){
    LinkList *p = a;
    LinkList *q = b;
    LinkList *temp = (Linklist*)malloc(sizeof(LinkList));
    Linklist *r = temp;
    while(p != NULL && q != NULL){
        if(p->data < q->data){
            r->next = (Linklist*)malloc(sizeof(LinkList));
            r->next->data = p->data;
            r = r->next;
            p = p->next;
        }else{
            r->next = (Linklist*)malloc(sizeof(LinkList));
            r->next->data = q->data;
            r = r->next;
            q = q->next;
        }
    }
    while(p){
        r->next = (Linklist*)malloc(sizeof(LinkList));
        r->next->data = p->data;
        r = r->next;
        p = p->next;
    }
    while(q){
         r->next = (Linklist*)malloc(sizeof(LinkList));
         r->next->data = q->data;
         r = r->next;
         q = q->next;
    }
    r->next = NULL;
    c = temp->next;
}
# 串方向


# 在顺序存储结构上实现求子串






# 堆方向


# 已知堆，新加入一个底部元素重新调整成堆


void adjustheap(int r[],int n){
    int j = n;
    int i = j/2;
    int temp = r[j-1];
    while(i>=1){
        if(temp>=r[i-1]){
            break;
        }else{
            r[j-1] = r[i-1];
            j = i;
            i = i/2;
        }
    }
    r[j-1] = temp;
}
# 设计单链表中值相同的多余节点




这段代码可能存在内存泄漏的风险，应对考试应该还是没问题的




void deleteCon(LinkList *&L){
    if (!L) return;
    LinkList *p = L;
    LinkList *q;
    LinkList *r;
    int num = 0;
    while(p){
        num++;
        p = p->next;
    }
    p = L;
    int* nodeHave = malloc(sizeof(int)*num);
    int now=1;
    nodeHave[0]=p->data;
    q=p;
    p=p->next;
    while(p){
        bool found = false;
        for(int i=0;i<now;i++){
            if(nodeHave[i] == p->data) {
                q->next=q->next->next;
                q=q->next;
                p=p->next;
                r=p;
                free(r);
                found = true;
            }
        }
        if(!found){
            nodeHave[now++]=p->data;
        	p=p->next;
        	q=q->next;
        } 
    } 
}
# 树方向


# 二叉树求树高


int getDeep(BTree b){
    int HL,HR;
    HL = HR = 0;
    HL = getDeep(b->Lchild);
    HR = getDeep(b->Rchild);
    return HL > HR ? (HL+1) : (HR+1);
    // 此处 return 就是谁大就返回谁加一
}
# 左孩子友兄弟表示法，求原树高


int hight(BTree b){
    int HL,HR;
    HL = HR = 0;
    if(b == NULL) return 0;
    HL = high(b->Lchild);
    HR = high(b->Rchild);
    if(HL+1 > HR){
        return HL + 1;
    } else{
        return HR;
    }
    
}
# 二叉树求树宽


int count[100];
int max = -1;
void width(BTree t,int k){
    if(t = NULL) return;
    count[k] ++;
    if(max < count[k]) max = count[k];
    width(t->lchild, k+1);
    width(t->rchild, k+1);
}
# 链式存储结构建立二叉树


typedef char datatype;
typedef struct node{
    datatype data;
    struct node *lchild,*rchild;
}btree
void createBtree(btree *&bt){
    datatype zData;
    scanf("%c",&zData);
    if(zData == '#') {
        bt=null;
        return;
    }
    bt = (btree*)malloc(sizeof(btree))
    bt->data=zData;
    createBtree(bt->lchild);
    createBtree(bt->rchild);
}
# 判断二叉树是否为排序二叉树 / 二叉搜索树




判断一棵二叉树是否为排序二叉树，可以通过中序遍历来实现。在 BST 中，中序遍历的结果应该是一个严格递增的序列。如果遍历过程中发现任何一个节点的值不大于前一个节点的值，则该树不是 BST。




int minnum = INT_MIN;
int isFirstNode = 1;      // 标记是否是第一个节点 (最左侧的节点)
int isBST(BTree *bt){
    if(bt==null){
        return 1;// 空树是 BST
    }
    if(!isBST(bt->lchild)){
        return 0;
    }
    if(!isFirstNode && bt->data<minnum){
        return 0;
    }
    isFirstNode =0;
    minnum = bt->data;
    return isBST(bt->rchild);
    
}
# 求节点在二叉排序树，关键字是 x 的层数


int layer = 0;
void `findXCountLayer(BTree *b,int x){
    if(b!=NULL){
        layer++;
        if(b->data == x){
            return;
        }else if(x > b->data){
            findXCountLayer(b->rchild,x);
        }else{
            findXCountLayer(b->lchild,x)
        }
    }
}
# 统计二叉树节点个数


int countNode(BTree *b){
    if(b == NULL){
        return 0;
    }
    return countNode(b->lchild) + countNode(b->rchild) + 1;
}
# 计算二叉树中所有节点之和


int sum = 0;
void bTreeSum(BTree *b){
    bTreeSum(b->lchild);
    sum += b->data;
    bTreeSum(b->rchild);
}
# 排序方向


# 快速排序


# 快速排序分区函数


int Partition(int a[],int low,int high){
    int flag = a[low];
    while(low < high){
        while(low < high && flag <= a[high]) --high;
        a[low] = a[high];
        while(low < high && flag > a[low]) ++low;
        a[high] = a[low];
    }
    a[low] = flag;
    return low;
}
# 快速排序递归函数


void QuickSort(int a[],int low,int high){
    if(low < high){
        int pivo = Partition(a,low,high);
        QuickSort(a,low,pivo-1);
        QuickSort(apivo+1,high);
    }
}
# 链式结构的简单选择排序


void easySelectSort(LinkList *l){
    if(l == NULL) return;
    int min = MAX_INT;
    int temp;
    LinkList *p = l;
    LinkList *r = p;
    while(p){
        min = p->data;
        LinkList *q = p;
        while(q){
            if(q->data < min){
                r=q;
                min = r->data;
            }
            q = q->next;
        }
        if (r != p) {
        	temp = r->data;
        	r->data = p->data;
        	p->data = temp;
        }
        p = p->next;
    }
}
# 综合代码题目


# 快速排序分区函数 + 顺序表移动




设计一个算法，调整数组 a [] 中的元素并返回分界值，使所有小于 x 的元素都出现在其左边（a [1…i]），所有大于 x 的元素都出现在其右边（a [i+1…n]）。




不严谨的代码
int div(int a[],intx){
    int rear = a.length;
    a[rear] = x;
    int start = 0;
    while(start < rear){
        while(start<rear && x>=a[start]) rear--;
        a[rear] = a[start];
        while(start<rear && x<a[rear]) start++;
        a[strat] = a[rear];
    }
    int i = start;
    for(int j=i; j>0; j--){
        a[i]=a[i-1];
    }
    return i;
}


实际上，上述代码有一些不严谨的部分，比如，可能造成数组越界。

但仍然可以帮助我们拿下绝大部分的分数。




相同逻辑更严谨的代码
int div(int a[],int h,int x){
    int i,j,t;
    i = 1;
    j = h;
    while(i<j){
        // 找到第一个小于等于 x 的元素
        while(i<j && a[j]>=x) j--;
        // 找到第一个大于 x 的元素
        while(i<j && a[i]<=x) i++;
        if(i<j){
            // 交换元素
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    // 这里可能会出现 i 跨越 j 的情况，这里做下判断
    // 如果 i 位置的数仍然比 x 要小，那么就可以返回 i
    // 反之就是 i 跨越了 j，而且最多只会跨越一步，返回 i-1
    if(a[i]<x) return i;
    else return i-1;
}


上述代码体现就是一种类似 “就地算法” 的思想，无需借助辅助空间。

找到第一个大于 x 与小于 x 的数，直接原地交换位置，然后继续寻找。




# 将奇数转移到偶数之前


void quickPass(int r[],int s,int t){
    int i = s;
    int j = t;
    int x = r[s];
    while(i < j){
        while(i < j && r[j]%2 == 1){
            j--;
        }
        if(i < j){
            r[i] = r[j];
            i++;
        }
        while(i < j && r[i]%2 == 0){
            i++;
        }
        if(i < j){
            r[j] = r[i];
            j++;
        }
    }
    r[i] = x;
}
# S 是栈，Q 是队列，将队列中的元素逆置


void Inverser(Stack &S,Queue &Q){
    int x;
    while(!QueueEmpty(Q)){
        x = DeQueue(Q);
        Push(S,x);
    }
    while(!StackEmpty(S)){
        Pop(S,x);
        EnQueue(Q,x);
    }
}

      

          
      

  


   


    

  
    
      
    
    更新于
    
  
  
      
        
      
      阅读次数
      
      次
  



      


  
  
请我喝[茶]~(￣▽￣)~*

  

      
      

        KarryLiu 微信支付
        
微信支付

      

      
      

        KarryLiu 支付宝
        
支付宝