【数据结构】计算机考研随记【顺序表】

#include 
using namespace std;

#define Maxsize 50 // 最大长度

typedef struct // 静态表
{
    int data[Maxsize]; // 用静态的数组存放数据元素
    int length;        // 顺序表的当前长度
} SqList;              // 顺序表的类型定义（静态分配方式）

// 初始化静态顺序表
void InitList(SqList &L)
{
    for (int i = 0; i < Maxsize; i++)
        L.data[i] = 0; // 所有初始值置0
    L.length = 0;      // 顺序表初始长度为0
}

// 插入操作，返回bool表明健壮性
bool ListInsert(SqList &L, int i, int e)
{
    if (i < 1 || i > L.length + 1) //判断i的范围是否有效
        return false;
    if (L.length >= Maxsize) //当前存储空间已满，不能插入
        return false;
    for (int j = L.length; j >= i; j--) //将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e; //在位置i除放入e
    L.length++;        //长度+1
    return true;
}

// 删除操作
bool ListDelete(SqList &L, int i, int e)
{
    if (i < 1 || i > L.length) //判断i的范围是否有效
        return false;
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++) //将第i个元素之后的元素前移
        L.data[j] = L.data[j - 1];
    L.length--; //长度-1
    return true;
}

//int main()
//{
//    SqList L;    // 声明静态顺序表
//    InitList(L); //初始化顺序表
//    // ...此处省略一些代码，插入几个元素...
//    ListInsert(L, 3, 3);
//    int e = -1; //用变量e把删除的元素带回来
//    if (ListDelete(L, 3, e))
//        cout << "已删除第3个元素,删除元素值为" << e;
//    else
//        cout << "位序i不合法,删除失败";
//
//    for (int i = 0; i < L.length; i++)
//    {
//        cout << "data[" << i << "]=" << L.data[i];
//    }
//
//    return 0;
//}

#include  
#include    
using namespace std;

#define InitSize 10 // 默认最大长度

typedef struct // 动态表
{
    int *data;   // 指示动态分配数组的指针
    int MaxSize; // 顺序表的最大容量
    int length;  // 顺序表的当前长度
} SeqList;       // 顺序表的类型定义（动态分配方式）

// 初始化动态顺序表
void InitList(SeqList &L)
{
    // 用malloc函数申请一片连续的存储空间
    // malloc返回第一个空间地址，强制转化为data的类型，此处为int
    L.data = (int *)malloc(sizeof(int) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len)
{
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++)
    {
        L.data[i] = p[i]; // 将数据复制到新区域，时间开销大
    }
    L.MaxSize = L.MaxSize + len; // 顺序表最大长度增加len
    free(p);                     // 释放原来的内存空间
}

// 按位查找，和访问普通数组的方法一样
int GetElem(SeqList L, int i)
{
    return L.data[i - 1];
}

// 在顺序表L中查找第一个元素值等于e的元素并返回其位序
int LocalElem(SeqList L, int e)
{
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)
            return i + 1;
    return 0;
}

//int main()
//{
//    SeqList L;   // 声明动态顺序表
//    InitList(L); //初始化顺序表
//    // ...往顺序表中随便插入几个元素...
//    IncreaseSize(L, 5);
//    return 0;
//}