2021数据结构与算法实验合集

た入场券 2023-10-04 16:07 38阅读 0赞

### 文章目录  @\[toc\]  第十四周 哈希查找  A. DS哈希查找—线性探测再散列  B. DS哈希查找—二次探测再散列(关键字互不相同）  关于表长的一个小tips  C. DS哈希查找--链地址法  D. 问题 D: DS哈希查找与增补  第十五周 DS排序  A. DS排序--直接插入排序  B.DS排序--折半插入排序  c. DS排序--希尔排序  D. DS排序--冒泡排序  E. DS排序--快速排序 ###

## 第十四周 哈希查找 ##

### A. DS哈希查找—线性探测再散列 ###

题目描述
     定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。
    
    --程序要求--
    若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
    程序中若include多过一个头文件，不看代码，作0分处理
    不允许使用第三方对象或函数实现本题的要求
    输入
     测试次数t
    
    每组测试数据为：
    
    哈希表长m、关键字个数n
    
    n个关键字(关键字为互不相同的正整数）
    
    查找次数k
    
    k个待查关键字
    
    输出
    对每组测试数据，输出以下信息：
    
    构造的哈希表信息，数组中没有关键字的位置输出NULL
    
    对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
    
    样例输入
    1
    12 10
    22 19 21 8 9 30 33 4 15 14
    4
    22
    56
    30
    17
    样例输出
    22 30 33 14 4 15 NULL NULL 19 8 21 9
    1 1 1
    0 6
    1 6 2
    0 1
    提示

// 问题 A: DS哈希查找—线性探测再散列
    #include <iostream>
    using namespace std;
    
    #define INF -99
    
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            int m, n;
            cin >> m >> n;
            int *a = new int[m];
            for (int i = 0; i < m; i++)
                a[i] = INF;
    
            // 建表
            while (n--)
            {
                int num;
                cin >> num;
                int di = 1;
                int h = num % 11;
                if (a[h] == INF)
                {
                    a[h] = num;
                    continue;
                }
                while (true)
                {
                    int temp = (h + di) % m;
                    if (a[temp] == INF)
                    {
                        a[temp] = num;
                        break;
                    }
                    else
                    {
                        di++;
                    }
                }
            }
            for (int i = 0; i < m; i++)
            {
                if (a[i] == INF)
                    cout << "NULL"
                         << " ";
                else
                    cout << a[i] << " ";
            }
            cout << endl;
            int k;
            cin >> k;
            while (k--)
            {
                int f;
                cin >> f;
                int h = f % 11;
                int times = 0;
                int di = 1;
                int flag = 0;
                int tf = 0;
                int temp = h;
    
                /**************
                  * 查找分三种情况：
                  * 1. 要找的关键字的hash地址为空
                  * 2. 要找的关键字的hash地址不为空且等于关键字
                  * 3. 要找的关键字的hash地址不为空，也不等于关键字，则进行线性探测
                  * 
                  * 
                  * **********/
                if (a[h] == INF)
                { // 第一种情况
                    cout << 0 << " " << 1 << endl;
                }
                else
                {
                    if (a[h] == f)
                    { // 第二种情况
                        cout << 1 << " " << 1 << " " << h + 1 << endl;
                        continue;
                    }
                    times++;
                    while (true)
                    { // 第三种情况
                        int temp = (h + di) % m;
                        times++;
                        if (a[temp] == f)
                        {
                            cout << 1 << " " << times << " " << temp + 1 << endl;
                            flag = 1;
                            break;
                        }
                        else if (a[temp] == INF)
                        {
                            break;
                        }
                        di++;
                    } // while
                    if (flag == 0)
                    {
                        cout << 0 << " " << times << endl;
                    }
                }
            }
        }
        return 0;
    }

--------------------

### B. DS哈希查找—二次探测再散列(关键字互不相同） ###

题目描述
    定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。
    
    输入
    测试次数t
    每组测试数据格式如下：
    哈希表长m、关键字个数n
    n个关键字(关键字为互不相同的正整数）
    查找次数k
    k个待查关键字
    输出
    对每组测试数据，输出以下信息：
    构造的哈希表信息，数组中没有关键字的位置输出NULL
    对k个待查关键字，分别输出：
    0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
    样例输入
    1
    12 10
    22 19 21 8 9 30 33 4 41 13
    4
    22
    15
    30
    41
    样例输出
    22 9 13 NULL 4 41 NULL 30 19 8 21 33
    1 1 1
    0 3
    1 3 8
    1 6 6
    提示

// 问题 B: DS哈希查找—二次探测再散列(关键字互不相同）
    #include<iostream>
    using namespace std;
    
    #define INF -99
    
    
    int main()
    {
        int t;
        cin >> t;
        while( t-- ){
            int m, n;
            cin >> m >> n;
            int * a = new int[m+5]; 
            for( int i=0; i<m; i++) a[i] = INF;
            
            // 建表
            while( n-- ){
                int num ; 
                cin >> num;
                int di = 1;
                int h = num%11;
                h %= m;
                if(a[h]==INF){
                    a[h] = num;
                    continue;
                }
                while( true ){
                    int t1 = (h+di*di)%m;
                    int t2 = (h-di*di)%m;
                    
                    while(t1>=m){
                        t1-=m;
                    }
                    while(t2<0){
                        t2+=m;
                    }
    
                    /*******
                     * 重点： 这里一定要注意对t2的取值范围进行处理，小于0的时候要进行循环移位
                     * 博主在初学这个的时候，可是被他坑惨了呜呜
                     * 
                     * ******/
    
    
                    if( a[t1%m] == INF ){
                        a[t1] = num;
                        break;
                    } else if( a[t2%m] == INF ){
                        a[t2] = num;
                        break;
                    }
                    else{
                         di++;
                    }
                }
            }
            for(int i=0; i<m; i++){
                if(a[i] == INF ) cout<<"NULL"<<" ";
                else cout<<a[i]<<" ";
            }
            cout << endl;
            int k;
            cin >> k;
            while(k--) {
                int f;
                cin >> f;
                int h = f%11;
                int times = 0;
                int flag = 0;              // 没找到为0， 找到为1
                int tf = 0;
                int di = 1;
                 /**************
                  * 查找分三种情况：
                  * 1. 要找的关键字的hash地址为空
                  * 2. 要找的关键字的hash地址不为空且等于关键字
                  * 3. 要找的关键字的hash地址不为空，也不等于关键字，则进行二次探测（平方）
                  * 
                  * #### 注意比较次数自加的位置 (在进行比较之前进行次数+1)
                  *     1. 先和自身的hash地址比较
                  *     2. 和t1 = (h+di*di)%m; t1的地址比较
                  *     3. 和t2 = (h-di*di)%m; t2 的地址比较
                  * **********/
                 if(a[h]==INF){             // 第一种情况     
                     cout<<0<<" "<<1<<endl;
                 }
                 else{
                     times ++;
                     if( a[h]==f ){         // 第二种情况
                         cout<< 1 << " " << times << " " << h+1 <<endl;
                         continue;
                     }
                     while(true){           // 第三种情况
                        int t1 = (h+di*di)%m;
                        int t2 = (h-di*di)%m;
                        while(t1>=m){
                            t1-=m;
                        }
                        while(t2<0){
                            t2+=m;
                        }
                        times++;
                        if( a[t1%m]==f ){
                             cout<<1<<" "<<times<<" "<<t1+1<<endl;
                             flag = 1;
                             break;
                         }
                        if(a[t1%m]==INF ){  // 遇到NULL就跳出
                            break;
                        }
                        times++;
                        if( a[t2%m]==f ){
                             cout<<1<<" "<<times<<" "<<t2+1<<endl;
                             flag = 1;
                             break;
                         }
                        if( a[t2%m]==INF  ){   //  遇到NULL就跳出
                            break;
                        }
                         di ++;
                         if(di>m/2) {
                             break;
                         };
                     }
                     if( flag==0 ){
                         cout<<0<<" "<<times<<endl;
                     }
                 }
            }
        }
        return 0;
    }

#### 关于表长的一个小tips ####

*  1.  可以通过设置表长=`4k+3`，来获取完全剩余系，规避重复搜索
    2.  如果表长不是`4k+3`， 冲突次数达到一定的阈值，就需要重新建表

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ayxIdZYA-1623337233975)(C:\\Users\\dcs\\Desktop\\notes\\study\\MD\\03数据结构与算法\\pics\\image-20210610153428027.png)\]

--------------------

### C. DS哈希查找–链地址法 ###

题目描述
     给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入
    
    如果首次查找失败，就把数据插入到相应的位置中
    
    实现哈希查找功能
    
    输入
    多组数据，每组数据：
    
    第一行输入n，表示有n个数据
    第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
    第三行输入t，表示要查找t个数据
    从第四行起，每行输入一个要查找的数据，都是正整数
    
    输出
    每行输出对应数据的查找结果
    
    样例输入
    6
    11 23 39 48 75 62
    6
    39
    52
    52
    63
    63
    52
    样例输出
    6 1
    error
    8 1
    error
    8 1
    8 2
    提示
    注意，当两次输入要相同的查找数据，如果第一次查找不成功就会执行插入，那么第二次查找必然成功，且查找次数为1次（因为做表头插入）
    
    
    例如示例数据中输入两次52，第一次查找失败就把52插入到位置8，第二次查找就成功了，所以第一次输出error，第二次就输出8 1
    
    
    为什么第三次输入52会输出8 2
    
    
    需要考虑有多轮数据输入的情况！也就是第一个cin或者scanf需要用while来进行循环，例如 while(cin>>...)

#include<iostream>
    using namespace std;
    const int is = 11;
    int a[is][99];
    
    void move(int k){
        for(int i=a[k][0]; i>0; i--){
            a[k][i+1] = a[k][i];
        }
    }
    
    void insert(int data){
        int k = data%is;
        a[k][0] += 1;
        // 采用头插法 ，所以要移动数据
        move(k);
        a[k][ 1 ] = data;
    }
    
    void search(int data){
        int k = data%is;
        int flag = 0; 
        for(int j=1, len = a[k][0]; j<=len; j++ ){
            if(a[k][j]==data){
                cout<<k<<" "<<j<<endl;
                flag = 1;
                break;
            }
        }
        if(flag==0){
            cout<<"error"<<endl;
            insert(data);
        }
    }
    
    int main(){
        int t;
        while(cin >> t){
            for(int i=0; i<is; i++){
                a[i][0] = 0;        // 0位记录当前表项的数据元素
                for(int j=1; j<99; j++){
                    a[i][j] = -1;
                }
            }
        
            while(t--){
                int temp;
                cin>>temp;
                insert(temp);
            }
            int steps;
            cin >> steps;
            while(steps--){
                /****************
                 * 要搜索的值情况分三种：
                 * 1. 要搜索的值的记录表没有记录
                 * 2. 要搜索的值的记录表有记录，但没有要找的值
                 * 3. 要搜索的值的记录表有记录，但有要找的值
    
                 ****************/ 
                int find;
                cin >> find;
                int k = find%is;
                if( a[k][0] == 0){
                    cout<<"error"<<endl;
                    insert(find);
                }
                else{
                    search(find);
                }
            }
    
        }
        return 0;
        
    
    }

--------------------

### D. 问题 D: DS哈希查找与增补 ###

题目描述
    给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表尾插入
    
    如果首次查找失败，就把数据插入到相应的位置中
    
    实现哈希查找与增补功能
    
    输入
    第一行输入n，表示有n个数据
    第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
    第三行输入t，表示要查找t个数据
    从第四行起，每行输入一个要查找的数据，都是正整数
    
    输出
    每行输出对应数据的查找结果，每个结果表示为数据所在位置[0，11）和查找次数，中间用空格分开
    
    样例输入
    6
    11 23 39 48 75 62
    6
    39
    52
    52
    63
    63
    52
    样例输出
    6 1
    error
    8 1
    error
    8 2
    8 1
    提示

#include<iostream>
    using namespace std;
    const int is = 11;
    int a[is][99];
    
    
    void insert(int data){
        int k = data%is;
        a[k][0] += 1;
        a[k][ a[k][0] ] = data;
    }
    
    void search(int data){
        int k = data%is;
        int flag = 0; 
        for(int j=1, len = a[k][0]; j<=len; j++ ){
            if(a[k][j]==data){
                cout<<k<<" "<<j<<endl;
                flag = 1;
                break;
            }
        }
        if(flag==0){
            cout<<"error"<<endl;
            insert(data);
        }
    }
    
    int main(){
        int t;
        while(cin >> t){
            for(int i=0; i<is; i++){
                a[i][0] = 0;        // 0位记录当前表项的数据元素
                for(int j=1; j<99; j++){
                    a[i][j] = -1;
                }
            }
        
            while(t--){
                int temp;
                cin>>temp;
                insert(temp);
            }
            int steps;
            cin >> steps;
            while(steps--){
                /****************
                 * 要搜索的值情况分三种：
                 * 1. 要搜索的值的记录表没有记录
                 * 2. 要搜索的值的记录表有记录，但没有要找的值
                 * 3. 要搜索的值的记录表有记录，但有要找的值
    
                 ****************/ 
                int find;
                cin >> find;
                int k = find%is;
                if( a[k][0] == 0){
                    cout<<"error"<<endl;
                    insert(find);
                }
                else{
                    search(find);
                }
            }
    
        }
        return 0;
        
    
    }

--------------------

## 第十五周 DS排序 ##

### A. DS排序–直接插入排序 ###

题目描述
    给出一个数据序列，使用直接插入排序算法进行降序排序。
    
    输入
    第一行输入t，表示有t个测试示例
    第二行输入n，表示第一个示例有n个数据(n>1)
    第三行输入n个数据，都是正整数，数据之间用空格隔开
    以此类推
    输出
    对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。
    
    样例输入
    2
    5
    111 22 6 444 333
    6
    21 25 49 25 16 8
    样例输出
    111 22 6 444 333
    111 22 6 444 333
    444 111 22 6 333
    444 333 111 22 6
    
    25 21 49 25 16 8
    49 25 21 25 16 8
    49 25 25 21 16 8
    49 25 25 21 16 8
    49 25 25 21 16 8
    提示

#include<iostream>
    using namespace std;
    void show(int a[], int len){
        for(int i=0; i<len; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    };
    
    void z_sort(int a[], int len){
        for(int i=1; i<len; i++){
            for(int j=i; (j>0) && ( a[j]>a[j-1]) ; j-- ){
                a[j] ^= a[j-1];
                a[j-1] ^= a[j];
                a[j] ^= a[j-1];
            }
            show(a, len);
        }
    }
    int main(){
        int step;
        cin >> step;
        while(step--){
            int t;
            cin >> t;
            int *a = new int[t+5];
            for(int i=0; i<t; i++) cin>>a[i];
            z_sort(a, t);
            cout<<endl;
        } 
    
        return 0;
    }

### B.DS排序–折半插入排序 ###

题目描述
    给出一个数据序列，使用折半插入排序算法进行降序排序。
    
    输入
    第一行输入t，表示有t个测试示例
    第二行输入n，表示第一个示例有n个数据(n>1)
    第三行输入n个数据，都是正整数，数据之间用空格隔开
    以此类推
    输出
    对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。
    
    样例输入
    2
    5
    111 22 6 444 333
    8
    30 13 70 85 39 42 6 20
    样例输出
    111 22 6 444 333
    111 22 6 444 333
    444 111 22 6 333
    444 333 111 22 6
    
    30 13 70 85 39 42 6 20
    70 30 13 85 39 42 6 20
    85 70 30 13 39 42 6 20
    85 70 39 30 13 42 6 20
    85 70 42 39 30 13 6 20
    85 70 42 39 30 13 6 20
    85 70 42 39 30 20 13 6
    
    提示

#include<iostream>
    using namespace std;
    void show(int a[], int len){
        for(int i=0; i<len; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    };
    
    void z_sort(int a[], int len){
        int low = 0,high = 0,mid;
        int temp = 0;
        for (int i=1; i<len; i++) {
            low=0;
            high=i-1;
            temp=a[i];
            while (low<=high) {
                mid=(low+high)/2;
                if (a[mid]<temp) {
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            for (int j=i; j>low; j--) {
                a[j]=a[j-1];
            }
            a[low]=temp;//插入元素
            show(a, len);
        }
            
    }
    int main(){
        int step;
        cin >> step;
        while(step--){
            int t;
            cin >> t;
            int *a = new int[t+5];
            for(int i=0; i<t; i++) cin>>a[i];
            z_sort(a, t);
            cout<<endl;
        }
        
        return 0;
    }

### c. DS排序–希尔排序 ###

题目描述
    给出一个数据序列，使用希尔排序算法进行降序排序。
    
    间隔gap使用序列长度循环除2直到1
    
    输入
    第一行输入t，表示有t个测试示例
    第二行输入n，表示第一个示例有n个数据(n>1)
    第三行输入n个数据，都是正整数，数据之间用空格隔开
    以此类推
    
    输出
    对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。
    
    样例输入
    2
    6
    111 22 6 444 333 55
    8
    77 555 33 1 444 77 666 2222
    样例输出
    444 333 55 111 22 6
    444 333 111 55 22 6
    
    444 555 666 2222 77 77 33 1
    666 2222 444 555 77 77 33 1
    2222 666 555 444 77 77 33 1
    提示

#include<iostream>
    using namespace std;
    
    
    void show(int a[], int len){
        for(int i=0; i<len; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    };
    
    
    void Shell(int a[], int len){
        for( int gap = len/2; gap >= 1; gap/=2 ){
            for(int i = 0; i<gap; i++){
               for (int j = i + gap; j < len; j += gap)
                    if (a[j] > a[j - gap])
                    {
                        int temp = a[j];
                        int k = j - gap;
                        while (k >= 0 && a[k] < temp)
                        {
                            a[k + gap] = a[k];
                            k -= gap;
                        }
                        a[k + gap] = temp;
                    }
            	}
                show(a,len);
            }
            
        }
    	
    
    int main()
    {
         int step;
        cin >> step;
        while(step--){
            int t;
            cin >> t;
            int *a = new int[t+5];
            for(int i=0; i<t; i++) cin>>a[i];
            Shell(a, t);
            cout<<endl;
            delete []a;
        } 
        return 0;
    }

### D. DS排序–冒泡排序 ###

题目描述
    给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换
    
    输入
    测试数据有多组，
    
    每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。
    
    输出
    对于每组测试数据，
    
    输出交换次数
    
    样例输入
    10
    1 3 6 9 0 8 5 7 4 2
    样例输出
    22
    提示
    需要考虑有多轮数据输入的情况！也就是第一个cin或者scanf需要用while来进行循环，例如 while(cin>>...)

#include<iostream>
    using namespace std;
    void show(int a[], int len){
        for(int i=0; i<len; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    int main(){
        int t;
        while( cin>>t){
            int a[t+5];
            int ans = 0;
            for(int i=0; i<t; i++) cin>>a[i];
            for(int i=0; i<t-1; i++){
                for(int j=i+1; j<t; j++){
                    if(a[i]>a[j]){
                        int temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                        ans++;
                    }
                    // show(a,t);
                }
            }
            cout<<ans<<endl;
            
        }
        return 0;
    }

### E. DS排序–快速排序 ###

题目描述
    给出一个数据序列，使用快速排序算法进行从小到大的排序
    
    排序方式：以区间第一个数字为枢轴记录
    输出方式：每一步区间排序，都输出整个数组
    --程序要求--
    若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
    程序中若include多过一个头文件，不看代码，作0分处理
    不允许使用第三方对象或函数实现本题的要求
    输入
    第一行输入t，表示有t个测试示例
    第二行输入n，表示第一个示例有n个数据
    第三行输入n个数据，都是正整数，数据之间用空格隔开
    以此类推
    
    输出
    每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。
    
    样例输入
    2
    6
    111 22 6 444 333 55
    8
    77 555 33 1 444 77 666 2222
    样例输出
    55 22 6 111 333 444
    6 22 55 111 333 444
    6 22 55 111 333 444
    6 22 55 111 333 444
    
    1 33 77 555 444 77 666 2222
    1 33 77 555 444 77 666 2222
    1 33 77 77 444 555 666 2222
    1 33 77 77 444 555 666 2222
    1 33 77 77 444 555 666 2222
    提示

#include<iostream>
    using namespace std;
    int length;
    
    void show(int *a){
        for(int i=0; i<length; i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    };
    
    void q_sort(int a[], int left, int right){
    // left, right 左闭右开， low、high闭区间
        if(left >= right-1 ) return;
        int low = left, high = right-1, center = a[low];    
    
        while( low < high ){
            while( low<high && a[high] >= center ) high --;
            a[low] = a[high];
            while( low< high && a[low] <= center) low++;
            a[high] = a[low];
        }
        a[low] = center;
        show(a);
        q_sort(a, left, low);
        q_sort(a, low+1, right );
    }
    int main(){
        int step;
        cin>>step;
        while(step--){
            int t;
            cin >> t;
            int *a = new int[t+5];
            length = t;
            for(int i=0; i<t; i++) cin>>a[i];
            q_sort( a, 0, t);
            cout<<endl;
        }
        return 0;
    }