【趣学C语言和数据结构100例】

问题描述

66.已知递增有序的单链表 A，B，C分别存储了一个集合，设计算法实现 A=AU(B-C)，要求单链表仍然有序。

67.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

68.已知在一维数组 A[m+n]中依次存放两个线性表(a1,a2,a3,…,am)和(b1,b2,b3.…,bn)。编写一个函数,将数组中两个顺序表的位置互换,即将(b1,b2,b3.…,bn)放在(a1,a2,a3,…,am)的前面。

69.给定三个序列 A、B、C，长度均为 n，且均为无重复元素的递增序列，请设计一个时|上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组 A为{1.2.3]，数组 B为{2.3,4]，数组C为{-1,0.2}，则输出 2

70.已知线性表按顺序存储，且每个元素都是不相同的整型元素，设计把所有的奇数移动至偶数前面的算法。

代码分析

==66.有序的单链表 A，B，C->A=AU(B-C)==
思路：先实现B-C，并保存在B中，然后AUB。

具体分析：传入3个链表，返回链表，对ABC都操作，则函数名为：LiukList 函数名(LiukList &A,LiukList &B,LiukList &C)；

1.先实现B-C，定义pre记录B的p所到的位置，使p和分别指向B和C，两个使用while循环遍历，使他们两个值小的进行移动，到值相等。在相等时，使pre即此刻的p的前一个指向p的下一个，即跳过p,并且释放p,令p更新为现在的pre的下一个。

2.然后AUB,p和q指向A和B的头部开始，定义r作为辅助记录A的前一个，两个使用while循环遍历，如果p的值小，r更新为p，并且使用尾插法将q插入，并且更新r的位置到p,使p向后移动继续比较。如果q的值小，r更新为q，并且使用将q插入，并且更新r的位置到q,使q向后移动继续比较。直到结束，返回链表A。

==67.两个有序顺序表->新的有序顺序表==

//顺序表的数据结构
typedef struct {
   
    DataType *data;         // 数据数组
    int length;             // 当前长度
    int capacity;           // 容量
} SeqList;

分析：合并成功返回1，合并失败返回0。输入3个顺序表，AB用来参数，C用来记录合并后的数据。故函数名为：bool 函数名(SeqList A,SeqList B,SeqList C);如果A+B的长度>C的长度，则直接返回false,定义i,j,k,i为访问A，j为访问B，k为访问C,在不到最后时，使A.data[i]和B.data[j]小的存在C中，并且对应的k++和i++。在比较结束后，使i<长度，或j<长度,的把剩下的存入C中。返回1即可。

==68.将数组中两个顺序表的位置互换==
思路：先整体反转，再b1到bn反转，使a1到am反转。

具体分析：传入一个数组A[],以及n和m,还有数组的大小。先反转0到m+n-1反转,然后0到n-1反转,然后n到m+n-1反转,故一个调用。everse(A,0,m+n-1,m+n); everse(A,0,n-1,n); everse(A,n,m+n-1,m);接下来写 everse函数。输入函数A，以及左右边值，还有大小。故函数名为void everse(DataType A[],int left,int right,int arrsize)，如果左<0 或者 左>右 或者 右>数组大小，即出现失误，则返回return 0。当左<右时，进行左右值的交换，并且令左++，右--，即可完成交换。

==69.输出同时存在于这三个序列 A、B、C中的共同元素==
分析：传入abc3个数组和数组的大小n,故函数名为void func(int a[],int b[],int c[],int n)，定义i,j,k分别访问3个数组，当3个都<n时开始访问。如果3个的值相等，则输出a中的值，否则查找。先找到3个中最大的数，再<它的后进行++，直到找到3个的值相等时进行输出。

==70.线性表把所有的奇数移动至偶数前面==
分析：采用双指针，即左右同时，定义一个high和low，初始化为length-1和0。使用temp记录第一个的值，使用while循环遍历，再 low < high情况子下， 找到偶数: high 指针向左移动，直到找到一个奇数。把这个奇数的值给了low的奇数。从low开始，找到奇数: low 指针向右移动，直到找到一个偶数。把这个偶数的值给了high的偶数。重复: 重复步骤 1-3，直到 low 和 high 指针相遇。最后再把之前的temp的值还回去。

代码实现

#include<stdio.h>
int main(){
   
//    66.已知递增有序的单链表 A，B，C分别存储了一个集合，设计算法实现 A=AU(B-C)，要求单链表仍然有序。
Linklist fun(Linklist &A,Linklist &B,Linklist &C){
   
    //B-C
    Lnode *pre=B,*p=B->next,*q=C->next;
    while(p && q){
   
        if(p->data<q->data){
   
            pre=p;
            p=p->next
        }else if(p->data>q->data){
   
            q=q->next;
        }else{
   
            pre->next=p->next;
            free(p);
            p=pre->next;
        }

    }
    //AUB
    p=A->next;
    q=B->next;
    Lnode *r=A;  //为行动 
    A->next=NULL;
    while(p && q){
   
        if(p->data<q->data){
   
            r->next=p;
            r=p;
            p=p->next
        }else {
   
            r->next=q;
            r=q;
            q=q->next
        }
    }
    if(p==NULL){
   
        r->next=q;
    }else{
   
        r->next=p;
    }
    return A; 
}    

//    67.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
bool func(seqlist A,seqlist B,seqlist C){
   
    if(A.lenth+B.lenth>C.lenth){
   
        return 0;
    }
    int i=0,j=0,k=0;
    while(i<A.lenth && i<b.lenth){
   
        if(A.data[i]<=B.data[j]){
   
            C.data[k++]=A.data[i++];
        }else{
   
            C.data[k++]=B.data[j++];
        }
    }
    while(i<A.lenth){
   
        C.data[k++]=A.data[i++];
    }
    while(i<B.lenth){
   
        C.data[k++]=B.data[j++];
    }    
    C.length=k;
    return 1;
}

//    68.已知在一维数组 A[m+n]中依次存放两个线性表(a1,a2,a3,…,am)和(b;,bz,b.…,bn)。编写一个函数,将数组中两个顺序表的位置互换,即将(bi,b,,b;,,…,b)放在(a1,a2,a3,…,am)的前面。
typedef int DataType;
void everse(DataType A[],int left,int right,int arrsize){
   
    if(left>=right  || right > arrsize){
   
        return 0;
    }
    if(left<0){
   
        return 0;
    }
    int mid=(left+right)/2;
    while(left<right){
   
        DataType teap=A[left];
        A[left]=A[right];
        A[right]=teap;
        left++;
        right--;
    }
}

void func(DataType A[],int m,int n,int arrarise){
   
    everse(A,0,m+n-1,m+n);
    everse(A,0,n-1,n);
    everse(A,n,m+n-1,m);

}

//    69.给定三个序列 A、B、C，长度均为 n，且均为无重复元素的递增序列，请设计一个时|上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组 A为{1.2.3]，数组 B为{2.3,4]，数组C为{-1,0.2}，则输出 2
int max(int a,int b,int c){
   
    if(b>a){
   
        a=b;
    }
    if(c>a){
   
        a=c;
    }
    return a;
}
void func(int a[],int b[],int c[],int n){
   
    int i=0,j=0,k=0;
    while(i<n && j<n && k<n){
   
        if(a[i]==b[j] && a[i]==c[k]){
   
            printf("%d ",a[i]);
        }else{
   
            int maxnum=max(a[i],b[j],c[k]);
            if(a[i]<maxname){
   
                i++;
            }
            if(b[j]<maxname){
   
                j++;
            }
            if(c[k]<maxname){
   
                k++;
            }    
        }    
    }
}

//    70.已知线性表按顺序存储，且每个元素都是不相同的整型元素，设计把所有的奇数移动至偶数前面的算法。
void func(int a[],int len){
   
    int low=0,high=len-1;
    int temp=a[low];
    while(low<high){
   
        while(low<high && a[high]%2==0){
   
            high--;
        }
        a[low]=a[high];
        while(low<high && a[low]%2==0){
   
            low++;
        }
        a[high]=a[low];
    }
    a[low]=temp;
}



    return 0;
}

总结

本文介绍了五个数据结构问题及其C语言实现，这些问题涉及链表和数组的操作，包括有序集合的集合运算、有序序列表的合并、数组中两个顺序表的位置互换、三个递增序列的公共元素查找以及奇偶数的重新排列。这些算法不仅在理论上具有重要意义，而且在实际应用中也非常广泛。

有序集合的集合运算问题要求我们将三个有序单链表进行集合运算，实现A=AU(B-C)。这个问题的解决关键在于正确地遍历链表并根据条件将节点分配到不同的链表中，同时保持链表的有序性。

有序序列表的合并问题要求我们将两个有序序列表合并为一个新的有序序列表。这个问题可以通过比较两个序列表的元素并按顺序插入到新序列表中来解决。

数组中两个顺序表的位置互换问题要求我们在一维数组中交换两个顺序表的位置。这个问题可以通过整体反转数组、然后分别反转两个子数组来实现。

三个递增序列的公共元素查找问题要求我们找出三个无重复元素的递增序列中的公共元素。这个问题可以通过三指针法来高效解决，即同时遍历三个数组，找到公共元素。

奇偶数的重新排列问题要求我们将线性表中的所有奇数移动至偶数前面，同时保持元素的相对顺序。这个问题可以通过双指针法来解决，即同时从数组的两端开始遍历，交换奇偶数。

这些算法的实现不仅展示了C语言在处理链表和数组时的能力，也体现了算法设计的基本思想，如指针操作、条件判断和循环控制。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。