【数据结构C】线性表的实现 顺序表 插入删除等操作

/*线性表 顺序表实现*/
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define INIT_SIZE 80
#define ADD_SIZE 10
typedef struct
{
    char name[8];
    float score;
} ElemType; //元素

typedef struct
{
    ElemType *elem;//动态数组首地址
    int length;//表长：实际元素个数
    int listsize;//表规模：最大容量元素个数
} SqList;//顺序表

/*InitList_Sq:构建一个长度为0的空表*/
bool InitList_Sq(SqList &L)
{
    //分配内存空间 初始化各参数
    L.elem = (ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
    L.length = 0;
    L.listsize = INIT_SIZE;
    return true;
}
/*ListInsert_Sq:在L中的第i个元素前插入元素 e*/
//注：第i个元素 实际位置为i-1
bool ListInsert_Sq(SqList &L,int i,ElemType e)
{
    //判断位置是否合法
    //注：L.length+1也可以，表示插入到最后
    if (i>=1&&i<=L.length+1)
    {
        if (L.length >= L.listsize) //空间已用完，插入前需要再追加一批空间
        {
            L.elem = (ElemType *)realloc(L.elem,(L.listsize+ADD_SIZE)*sizeof(ElemType));
            L.listsize += ADD_SIZE;//更新表的规模
        }
        //插入操作：从后往前 依次"右移"; 然后插入
        for(int j=L.length-1; j>=i-1; j--)
            L.elem[j+1]=L.elem[j];
        L.elem[i-1] = e;//插入
        L.length++;//表长加1
        return true;
    }
    else
    {
        cout<<"插入操作 i不合法"<<endl;
        return false;
    }
}
/*ListDelete_Sq:删除L中的第i个元素，并将该删除元素赋给e*/
bool ListDelete_Sq(SqList &L,int i,ElemType &e)
{
    if (i>=0&&i<=L.length-1)
    {
        e = L.elem[i-1];
        //删除操作：从前往后 依次"左移"
        for(int j=i-1; j<=L.length-2; j++)
        {
            L.elem[j] = L.elem[j+1];
        }
        L.length--;//表长减1
        return true;
    }
    else
    {
        cout<<"删除操作 i不合法"<<endl;
        return false;
    }
}
/*GetElem：获取第i个元素，并赋给e*/
bool GetElem(SqList L,int i,ElemType &e)
{
    if (i>=0&&i<=L.length-1)
    {
        e = L.elem[i-1];
        return true;
    }
    else
    {
        cout<<"删除操作 i不合法"<<endl;
        return false;
    }
}
/*ListTraverse：以某种方法遍历线性表每个元素*/
void  ListTraverse(SqList L,void visit(ElemType e))//函数名作为参数
{
    for(int i=0;i<L.length;i++)
        visit(L.elem[i]);
}
/*Print：输出数据元素*/
void Print(ElemType e){
    cout<<e.name<<'\t'<<e.score<<endl;
}
int main()
{
    SqList L;
    InitList_Sq(L);//初始化
    ElemType e;
    strcpy(e.name,"张三");
    e.score = 88;
    ListInsert_Sq(L,1,e);//在1号元素前插入元素e

    strcpy(e.name,"李四");
    e.score = 99;
    ListInsert_Sq(L,2,e);//在2号元素前插入元素e

    strcpy(e.name,"王五");
    e.score = 100;
    ListInsert_Sq(L,2,e);//继续在2号元素前插入元素e
    ListTraverse(L,Print);//输出L，以Print函数的方式访问L的每个元素

    /*输出表长，表规模*/
    printf("表长:%d\t表规模:%d\n",L.length,L.listsize);
    /*获取第2个元素给e并输出e*/
    GetElem(L,2,e);
    printf("第二个元素为：\n");
    Print(e);
    /*删除第二个元素*/
    ListDelete_Sq(L,2,e);
    printf("删除第二个元素后为：\n");
    ListTraverse(L,Print);
    return 0;
}