数据结构线性表部分习题(二)

最近有考研的打算，准备考研科目，先是数据结构部分。习题如下:

1.设计两个集合A和B，设计生成集合C=A并B的算法，集合A、B和C均用数组存储

算法思想描述

算法思想算是暴力找，让a中所有元素一个一个与b中元素作比较

算法代码描述如下:

void HBLinklist(Sqlist A[], Sqlist B[] ,Sqlist C[]){
    int k =0;
    for(int i = 0; i < A.len; i++){
        for(int j = 0; j < B.len; i++){
            if(A.data[i] == B.data[j]){
                C.data[k] = A.data[i];
                k++;
                C.len++;
            }
        }
    }
    for(int h = 0; h < C.len; h++){
        printf("%d",C.data[h])
    }
}

2.给定一个由n(n>1)个不同整数组成的升序序列，同时包含负数和正数，设计一个在时间和空间两方面都尽量高效的算法，求序列中绝对值最小的数，如序列{-8， -3， -1， 4， 5}中绝对值最小的数为-1

算法思想描述

利用二分法找到0元素的点或者0最近点，附近绝对值最小

算法代码描述如下:

void Minvalue(int a[],int n){
    int high = n-1;
    int weight = 0;
    int mid;
    while(weight<high){
        mid = (high + weight)/2;//利用二分法求0元素位置或者0最近位置
        if(a[mid]>=0){
            weight = mid;
        }
        else{
            high = mid+1;
        }
    }
    if(abs(a[weight]) < abs(a[weight-1]))//abs绝对值意思
        printf("%d",a[weight]);
    else 
        printf("%d",a[weight-1]);
    
}

3.设有一个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法：(要求用最少的时间和最小的空间。) (1)确定在序列中比正整数x大的数有几个(相同的数只计算一次，如序列{20，20，17，16，15，15，11，10，8，7，7，5，4}中比10大的数有5个)； (2)在单链表中将比正整数x小的数按递减次序排列； (3)将正整数(比)x大的偶数从单链表中删除

算法思想描述

1.这是个递增有序的单链表，可以遍历，找到第一个大于x的元素，如何判断与后面元素的关系，等于计数不变，否则计数+1，然后p后移一个单元，直到p的后继为NULL为止  2.找到第一个大于x的元素后，让前面所有逆置即可  3. 然后就是判断所有大于x的偶数元素直接删除就行

算法代码描述如下:

void Reverse(linklist h, linklist q){
    node *p = h->next;
    h->next = q;//q此时指向第一个大于x的元素，后序逆置相当于是在q前面进行头插法。
    while(p=!q){
        node *tem = p;
        p = p->next;
        tem->next = h->next;
        h->next = tem;
    }
}
int Function(linklist head, int x){
    node *p = head->next;//
    while(p&&p->data<x){//不停的遍历找第一个大于等于x的元素
        p = p->next;
    }
    Reverse(head, p);//当执行到这个时候相当于已经不满足上面的while了，已经到了大于等于x的元素了，然后从头到大于x的第一个元素之间进行逆置操作
    while(p&&p->data == x){//因为计数时不需要记录相等的数字，故需要跳过等于x的后续数
        p = p->next;
    }
    if (p == NULL) {//x为最后一个元素，直接退出
        return 0;
    }
    int count = 1;
    node *q = p;
    while(p->next){
        if(p->data != p->next->data){//从大于x第一个数开始不断计数
            count += 1;
        }
        p = p->next;
    }
    p = q;
    while (p->next) {
        if(p->next->data>x&&p->next->data%2 == 0){//然后大于x这个元素开始遍历判断偶数然后删除
            node *tem = p->next;
            p->next = tem->next;
            free(tem);
        }
        else {
            p = p->next;
        }
    }
    return count;
    
}

4.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计一个空间复杂度为0(1)且时间上尽可能高效的算法，去掉数值相同的元素，使表中不再有重复的元素。例如，将(7，10,10,21，30，42,42,42，51,70）变为（7，10，21，30，42，51，70)。

算法思想描述

判断当前结点值和后面结点是否一样，不一样后移，一样删除后面一个在判断

算法代码描述如下:

void Delete_Duplication(linklist head){
    if(!head->next){
        return ERROR;
    }
    node *p = head->next;
    while(p->next){
        if(p->data == p->next->data){
            node *tem = p->next;
            p->next = tem->next;
            free(tem);
        }
        else {
            p = p->next;
        }
    }
}