【数据结构复习】部分知识提纲/总结

/*
  插入排序
  数组从下标1开始存储元素
 */
#include <stdio.h>
#define MAXSIZE 20//一个作为示例的小顺序表的最大长度
typedef struct
{
    int r[MAXSIZE + 1];//存储数据的数组
    int length;//数组当前长度
} SqList;
void list_insert(SqList &L, int e)
{
    //将元素e插入表L
    L.r[++L.length] = e;
}
void list_print(SqList L)
{
    //输出表中内容
    for (int i = 1; i <= L.length; i++)
    {
        printf("%d ", L.r[i]);
    }
    printf("\n");
}
void InsertSort_0(SqList &L)
{
    //书上写法
    //对顺序表L直接插入排序，书上写法
    for (int i = 2; i <= L.length; ++i)
    {
        if (L.r[i] < L.r[i - 1]) //'<'
        {
            L.r[0] = L.r[i]; //哨兵
            L.r[i] = L.r[i - 1]; //判断一次，交换一次
            int j;
            for (j = i - 2; L.r[0] < L.r[j]; --j)
            {
                L.r[j + 1] = L.r[j];
            }
            L.r[j + 1] = L.r[0];
        }
    }
}
void InsertSort_1(SqList &L)
{
    //自己瞎写
    //对顺序表L直接插入排序，无哨兵
    for (int i = 2; i <= L.length; i++)
    {
        int val = L.r[i]; //要插入的元素
        int j = i;
        while (j > 1 && val < L.r[j - 1])
        {
            L.r[j] = L.r[j - 1];
            j--;
        }
        L.r[j] = val;
    }
}
void InsertSort_2(SqList &L)
{
    //王道写法
    //对顺序表L直接插入排序，无哨兵
    for (int i = 2; i <= L.length; i++)
    {
        int val = L.r[i]; //要插入的数
        int j;
        for (j = i - 1; j >= 1 ; j--)
        {
            if (val < L.r[j])
            {
                L.r[j + 1] = L.r[j];
            }
            else
                break;
        }
        L.r[j+1]=val;
    }
}
void test0()
{
    SqList L;
    L.length = 0;
    for (int i = 1; i <= 10; i++)
        list_insert(L, 11 - i);
    list_print(L);
    //以上是表初始化,以下是排序，输出
    InsertSort_0(L);
    list_print(L);
}
void test1()
{
    SqList L;
    L.length = 0;
    for (int i = 1; i <= 10; i++)
        list_insert(L, 11 - i);
    list_print(L);
    //以上是表初始化,以下是排序，输出
    InsertSort_1(L);
    list_print(L);
}
void test2()
{
    SqList L;
    L.length = 0;
    for (int i = 1; i <= 10; i++)
        list_insert(L, 11 - i);
    list_print(L);
    //以上是表初始化,以下是排序，输出
    InsertSort_2(L);
    list_print(L);
}
int main()
{
    test0();
    test1();
    test2();
    return 0;
}