数据结构知识总结

妖狐艹你老母 2022-09-05 02:00 158阅读 0赞

# 数据结构知识总结 #

持续更新…  
参考数据结构C语言版|第2版 严蔚敏…

### 文章目录 ###

*  数据结构知识总结
 *  1. 排序算法
 *   *  1.1 交互排序
     *   *  1.1.1 冒泡排序Bubble Sort
         *  1.1.2 快速排序Quick Sort

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

# 1. 排序算法 #

## 1.1 交互排序 ##

### 1.1.1 冒泡排序Bubble Sort ###

冒泡排序：是一种最简单的交换排序算法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换。

时间复杂度：O(n^2)  
空间复杂度：O(1)

改进的冒泡排序算法：

// C++
    void BubbleSort(SqList &L) {
        
        int m = L.length - 1; int flag = 1;  
        while((m > 0) && (flag == 1)) {
        
            flag = 0;
            for(int i = 1; i <= m; i++) {
        
                if(L.r[i].key > L.r[i+1].key) {
        
                    flag = 1;
                    RedType t = L.r[i]; L.r[i] = L.r[i+1]; L.r[i+1] = t;
                }
            }
            m--;
        }
    }

传统的冒泡排序算法：

// C++
    void BubbleSort2(SqList &L) {
        
        int m = L.length - 1;
        while(m > 0) {
        
            for(int i = 1; i <= m; i++) {
        
                if(L.r[i].key > L.r[i+1].key) {
        
                    RedType t = L.r[i]; L.r[i] = L.r[i+1]; L.r[i+1] = t;
                }
            }
            m--;
        }
    }

**eg:**  
冒泡排序算法：

// 冒泡排序 C++
    #include <iostream>
    using namespace std;
    
    #define MAXSIZE 20  // 设定顺序表的最大长度为20
    typedef int KeyType;  // 定义关键字类型为整型
    
    typedef struct{
        
        KeyType key;  // 关键字项
        //InfoType otherInfo;  // 其他数据类型
    }RedType;  // 记录类型
    
    typedef struct{
        
        RedType r[MAXSIZE + 1];  // 记录项 r[0]闲置或用作哨兵单元
        int length;
    }SqList;  // 顺序表类型
    
    // 改进的冒泡排序算法
    void BubbleSort(SqList &L) {
        
        /* 
        如果一共有n个记录，那么最多需要进行m = n - 1趟排序；
        flag用作标记某一趟排序是否发生交换, flag = 1时，代表那一趟排序发生了交换，flag = 0时，表示那一趟排序未发生交换；
        */
        int m = L.length - 1; int flag = 1;  
        while((m > 0) && (flag == 1)) {
        
            flag = 0;
            for(int i = 1; i <= m; i++) {
        
                if(L.r[i].key > L.r[i+1].key) {
        
                    flag = 1;
                    RedType t = L.r[i]; L.r[i] = L.r[i+1]; L.r[i+1] = t;  // 交换前后两个记录
                }
            }
            m--;
        }
    }
    
    // 传统的冒泡排序算法
    void BubbleSort2(SqList &L) {
        
        int m = L.length - 1;
        while(m > 0) {
        
            for(int i = 1; i <= m; i++) {
        
                if(L.r[i].key > L.r[i+1].key) {
        
                    RedType t = L.r[i]; L.r[i] = L.r[i+1]; L.r[i+1] = t;  // 交换前后两个记录
                }
            }
            m--;
        }
    }
    
    int main() {
        
        SqList l;
        int k, len = 1;
        
        cout<<"请输入顺序表中的数据，以空格间隔，回车结束输入："<<endl;
        while(cin>>k && (len <= MAXSIZE)) {
        
            l.r[len++].key = k;
            if(getchar() == '\n') break;
        }
        l.length = len - 1;
        cout<<"您输入了"<<l.length<<"个数字，分别是：";
        for(int i = 1 ; i <= l.length ; i++) {
        
            cout<<l.r[i].key<<" ";
        }
        ///
        BubbleSort(l);
        cout<<"\n使用改进的冒泡排序算法（升序）：";
        for(int i = 1 ; i <= l.length ; i++) {
        
            cout<<l.r[i].key<<" ";
        }
        //
        /*BubbleSort2(l);
        cout<<"\n使用传统的冒泡排序算法（升序）：";
        for(int i = 1 ; i <= l.length ; i++) {
            cout<<l.r[i].key<<" ";
        }*/
        return 0;
    }

![请添加图片描述][317a25c2ab684d7393ab5335bca7793d.gif]

### 1.1.2 快速排序Quick Sort ###

快速排序：由冒泡排序改进而得，冒泡排序每次交换两个相邻的记录时只能消除一个逆序，快速排序方法中一次交换可消除多个逆序。

[317a25c2ab684d7393ab5335bca7793d.gif]: /images/20220829/7633645df0b14056ab209c0489641dd2.png