线性表

线性表建立

插入·删除·排序 元素

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define MAX 1000+5
using namespace std;
typedef struct
{
    int data[MAX];
    int length;
}SqList; //定义线性表
void Initlist(SqList *&L) //初始化线性表
{
    L = (SqList*)malloc(sizeof(SqList)); //分配空间
    L->length = 0; //长度为零
}
void DestroyList(SqList*&L) //删除线性表
{
    free(L);
}
bool ListEmpty(SqList*&L) //判断表是否为空
{
    return (L->length == 0); //若等于零，返回TRUE，证明为空，否则相反；
}
int Listlength(SqList *L) //返回线性表长度
{
    return(L->length);
}
void Display(SqList *L) //当顺序表不为空时，顺序显示L中各元素的值
{
    int i;
    if(ListEmpty(L)) //判断是否为空，如果为空，则返回值为TRUE,无任何显示
        return;
    for(i = 0; i < L->length; i++)
    {
        cout << L->data[i] << ' ';
    }
    cout << endl;
}
bool GetElem(SqList *L, int i, int &e) //求某个数据元素的值，返回第i个元素的值，存在e中
{
    if(i < 1 || i > L->length)
        return false;
    e=L->data[i-1]; //形实参共享空间
    return true;
}
int LocateElem(SqList *L,int e) //查找第一个值域和e相等的逻辑位序
{
    int i = 0;
    while(i < L->length && L->data[i] != e)
        i++;
    if(i >= L->length) //即超出范围，证明不存在，输出0
        return 0;
    else
        return i+1; //否则输出逻辑位置
}
bool ListInsert(SqList*&L, int i, int e) //在顺序表的第i个位置插入新元素e
{
    int j;
    if(i < 1 || i > L->length+1)
        return false;
    i--; //逻辑序号转化为物理序号
    for(j = L->length; j > i; j--)
    {
        L->data[j] = L->data[j-1]; //元素后移
    }
    L->data[i] = e; //剩下的i处空位置插入e
    L->length++; //顺序表长度+1
    return true; //成功插入返回true;
}
bool ListDelete(SqList*&L, int i, int &e) //删除顺序表的第i个元素（元素前移）
{
    int j;
    if(i < 1 || i > L->length)
        return false;
    i--;
    e = L->data[i]; //把要删除的值复制给e,便于输出
    for(j = i;j < L->length-1; j++) //元素前移；
    {
        L->data[j] = L->data[j+1];
    }
    L->length--;
    return true;
}
int Max(SqList*L) //求最大值
{
    int m=0;
    for(int i = 0; i < L->length; i++)
    {
        if(L->data[i] > m)
        {
            m = L->data[i];
        }
    }
    return m;
}
void sort(SqList*L) //排序
{
    int m;
    for(int i = 0; i < L->length; i++)
    {
        for(int j = 1; j < L->length; j++)
        {
            if(L->data[j-1] > L->data[j])
            {
                m=L->data[j-1];
                L->data[j-1] = L->data[j];
                L->data[j] = m;
            }
        }
    }
}

int main()
{
    int m;
    SqList *L;
    Initlist(*&L);
    printf("输入n个元素，依次填入顺序表\n");
    int n;
    cout << "请输入 n :" << endl;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin >> m;
        ListInsert(*&L, i, m);
    }
    Display(*&L);
    cout << "求最大元素？" << endl;
    printf("%d\n", Max(*&L));
    int k, t;
    cout << "请输入数字k和t,代表第k个元素之前插入数字t" << endl;
    cin >> k >> t;
    ListInsert(*&L, k, t);
    Display(*&L);
    int q;
    cout<<"请输入数字q，代表删除第几个元素"<<endl;
    cin >> q;
    int z;
    ListDelete(*&L, q, z);
    Display(*&L);
    cout << "元素顺序排序" << endl;
    sort(*&L);
    Display(*&L);
    Display(*&L);
    return 0;
}