顺序表

数据结构——顺序表

Content
　　代码及其注释
　　 写在最后

代码及其注释

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
using namespace std;// 头文件说明：此代码为C++代码，使用的是C++头文件

/**********线性表---顺序表**********/
// 说明：本代码主观性比较强，仅供参考，欢迎交流和学习
// 宏定义常量
#define LIST_INIT_SIZE 100 // 初始分配空间
#define LISTINCREMENT 10   // 空间分配增值
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASBLE -1
#define OVERFLOW -2

typedef int ElemType;
typedef int Status;

typedef struct
{
    ElemType *elem; // 头指针
    int length;     // 顺序表使用长度
    int listsize;   // 顺序表总长
} SqList;

// 基本操作：
Status InitList_Sq(SqList *L);                      // 构造空的顺序表(算法2.2)
void DestoryList(SqList *L);                        // 销毁顺序表
void QuitList(SqList *L);                           // 清空顺序表
Status ListLength(SqList *L);                       // 返回顺序表长度
Status ListInsert_Sq(SqList &L, int i, ElemType e); // 在第i个位置前插入新的元素(算法2.3)
Status ListDelet_Sq(SqList &L, int i, ElemType &e); // 删除位置i处的元素并用e返回被删除元素(算法2.4)
void ListPrint(SqList *L);                          // 打印顺序表
int LocateElem_Sq(SqList *L, ElemType e, Status (*compare)(ElemType, ElemType));
/**/                                               // 找查顺序表中元素位置(算法2.5)
void MergList(SqList *La, SqList *Lb, SqList *Lc); // 合并降序顺序表为新的大顺序表(算法2.6)
void GetElem(SqList *L, int i, ElemType &e);       // 取出顺序表中为序为 i 的元素
Status compare(ElemType elem1, ElemType elem2);
void ListDescendingSort(SqList *L); // 顺序表降序排序

int main()
{
    SqList L; // 定义表头
    ElemType e;
    // 函数功能展示：
    // 1 创建初始化顺序表
    InitList_Sq(&L);

    // 2 插入元素
    for (int i = 10; i > 0; i--)
        ListInsert_Sq(L, 1, i);

    // 3 输出顺序表
    printf("PRINT_LIST-> L: ");
    ListPrint(&L);

    // 3 删除顺序表某个位序上的元素
    ListDelet_Sq(L, 10, e);
    printf("已删除：%d
", e);
    printf("PRINT_LIST-> L: ");
    ListPrint(&L);

    // 4 找查元素位序
    printf("元素5在位序-%d-
", LocateElem_Sq(&L, 5, compare));

    // 降序排序 L 与 LL
    SqList LL;
    InitList_Sq(&LL);
    for (int i = 5; i > 0; i--)
        ListInsert_Sq(LL, 1, i);
    ListDescendingSort(&L);// 使L降序
    printf("PRINT_LIST-> L：");
    ListPrint(&L);
    ListDescendingSort(&LL);// 使LL降序
    printf("PRINT_LIST-> LL：");
    ListPrint(&LL);

    // 合并顺序表 L 与 LL 到 LLL
    SqList LLL;
    InitList_Sq(&LLL);
    MergList(&L, &LL, &LLL);// 合并L与LL到LLL
    printf("PRINT_LIST-> LLL：");
    ListPrint(&LLL);
    return 0;
}

// 构造线性表
Status InitList_Sq(SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    /* 
    malloc申请内存    使用格式：(类型*)malloc(空间大小)
    elem 指向所申请内存空间的首地址
    malloc函数申请空间失败返回值是NULL，若失败L->elem == NULL  */
    if (!L->elem) // 等效于 L->elem == NULL
        exit(OVERFLOW);
    L->length = 0; // 此函数仅仅是创造一片空间，为储存数据时为空表
    L->listsize = LIST_INIT_SIZE;
    return OK;
} // 函数作用：开辟一连串"物理空间连续"的内存用于数据存储，创建顺序表完后任务结束

// 销毁线性表
void DestoryList(SqList *L)
{
    free(L);
    return;
}
// 清空顺序表
void QuitList(SqList *L)
{
    L->length = 0;
    return;
}

Status ListLength(SqList *L)
{
    return L->length; // 返回顺序表长度
}

Status compare(ElemType c1, ElemType c2)
{
    if (c1 == c2) // 比较两个元素是否相同
        return TRUE;
    else
        return FALSE;
}

// 在第i个位置前插入新的元素
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
    if (i < 1 || i > L.listsize)
        return ERROR; // 插入位置只能是开始-->末尾(1 <= i <= listsize)
    if (L.length >= L.listsize)
    {
        ElemType *newbase =
            (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        // 由于空间不够将申请新的空间使用，用newbase记录新的空间的首地址
        if (!newbase)
            exit(OVERFLOW);
        L.elem = newbase; // 让链表头指针指向重新分配的内存
        free(newbase);
        L.listsize += LISTINCREMENT;
    }
    ElemType *InsertPozition = &(L.elem[i - 1]); // 记录插入位置的地址
    for (ElemType *p = &(L.elem[L.length]); p >= InsertPozition; --p)
        *(p + 1) = *p; // 将a[j]位置的元素拷贝到a[j+1](i <= j <= length+1)
    L.length++;
    *InsertPozition = e; // 插入新的元素
    return OK;
} // 函数作用：将插入位置i后的所有元素往尾挪动一位，空出位置i以存储新的元素

// 删除位置i处的元素并用e返回被删除元素
Status ListDelet_Sq(SqList &L, int i, ElemType &e)
{
    if (i < 1 || i > L.length)
        return ERROR;               // 保证将删除数据合法
    ElemType *p = &(L.elem[i - 1]); // 记录被删除数据的位置
    e = L.elem[i - 1];
    for (ElemType *end = &(L.elem[L.length - 1]); p <= end; ++p)
        *p = *(p + 1); // end记录结尾位置，p只移动到end
    L.length--;
    return OK;
} // 函数作用：将i --> 最后的元素全部往头挪动一位;用e返回删除的i处的元素

void ListPrint(SqList *L)
{
    for (int i = 0; i < L->length; i++)
        // printf("List[%d] = %d
", i, L->elem[i - 1]);
        printf("%d ", L->elem[i]); // 逐个输出表中的元素
    putchar('
');
}

/*函数说明：
1. 两个降序序顺序表合并为一个顺序表
2. La Lb 一定是提前按照降序排序好了的否则运行结果很惊喜
3. 实现思路：通过不断比较La、Lb中的数值，取较大的写入Lc
*/
void MergList(SqList *La, SqList *Lb, SqList *Lc)
{
    ElemType *pa = La->elem, *pb = Lb->elem; // 获取la、lb的首地址
    Lc->listsize = La->length + Lb->length;  // 确定顺序表Lc的大小
    ElemType *pc = (ElemType *)malloc(Lc->listsize * sizeof(ElemType));
    Lc->elem = pc; // 申请新的空间并让Lc->elem指向新的空间的首地址
    if (!Lc->elem)
        return exit(OVERFLOW); // 内存分配失败
    ElemType *La_last, *Lb_last;
    La_last = La->elem + La->length,
    Lb_last = Lb->elem + Lb->length; // 记录顺序表的末位置
    while (pa < La_last && pb < La_last)
        if (*pa > *pb)
            *pc++ = *pa;
        else
            *pc++ = *pb; // 选择较大的元素存入Lc
    while (pa < La_last)
        *pc++ = *pa++;   // La中剩余元素拷贝至Lc
    while (pb < Lb_last)
        *pc++ = *pb++;   // Lb中剩余元素拷贝至Lc
    Lc->length = La->length + Lb->length; // 更新顺序表的长度
    return;
}

// 查找顺序表中的第一个元素e，找到则返回它的位序，否则返回0
int LocateElem_Sq(SqList *L, ElemType e, Status (*compare)(ElemType, ElemType))
{
    ElemType *p = L->elem;
    int index = 1;
    while (index <= L->length && !compare(*p++, e))
        index++;
    // 循环条件为i在顺序表范围内，并且未找到该元素(未找到指定元素compare的返回值是0)
    // 如果到最后一个元素了，还未找到只当元素，就会使i++，这样的话 i 就比L->length大 1
    if (index <= L->length)
        return index; // 如果i在顺序表的长度范围内说明找到了该元素
    else
        return 0;
}

// 取出顺序表中为序为 i 的元素
void GetElem(SqList *L, int i, ElemType &e)
{
    ElemType *p = L->elem;
    int j = 1;
    while (j++ < i && p++)
        ; // 循环使得指针指向为序为 i 的位置
    e = *p;
}

// 顺序表降序排序
// 特别说明，ELemType为int型可以使用此方法，换做为别的类型，此思路仅供参考
void ListDescendingSort(SqList *L)
{
    ElemType *p = L->elem, *q;
    for (int i = 0; i <= L->length; i++, p++)
    {
        q = p + 1;
        for (int j = i; j <= L->length; j++, q++)
            if (*p < *q)
            {
                ElemType temp = *p;
                *p = *q;
                *q = temp;
            }
    } // 冒泡排序
    return;
}

写在最后
本代码主观性比较强，仅供参考，欢迎交流和学习。代码若有不足之处还希望大佬们指出反馈，Kirk再这里先谢谢了。每一个能读到这里的reader，你将来一定会很不错，一起加油吧！