线性表的初始化及插入元素操作

线性表简要提点

• 线性表基于数组创建，利于查找（指定下标即可）。
• 线性表不利于在开头或中间删除或添加元素操作（会移动大量元素）。

C语言实现

#include<>
#include<>
#include<>
#define LIST_INIT_SIZE 100      // 初始分配空间

typedef struct {
    int *elemList;      // 定义int类型指针指向数组，elem为数组首元素地址
    int length;     // 当前长度
    int listsize;   // 当前储存容量
}Sqlist;

void InitList(Sqlist *Sq)       // 初始化线性表
{
    Sq->elemList = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!Sq->elemList)
        exit(1);
    Sq->length = 0;
    Sq->listsize = LIST_INIT_SIZE;
}

void Insert(Sqlist *Sq, int d, int index)   // d为要插入的元素，index为插入的位置
{
    int j;
    if (index<0 || index>Sq->length)
    {
        printf("index error\n");
        exit(1);
    }
    if (Sq->length >= LIST_INIT_SIZE)
    {
        printf("oversize\n");
        exit(1);
    }
    for (j = Sq->length-1;j >= index;j--)       // 元素从插入位置依次后移
    {
        Sq->elemList[j + 1] = Sq->elemList[j];
    }
    Sq->elemList[index] = d;        // 插入d
    Sq->length++;   // 长度++
}

int main()
{
    Sqlist *L = (Sqlist *)malloc(sizeof(Sqlist *)); // 初始化线性表头指针
    InitList(L);
    int n, i, v;
    printf("Input the size of Sqlist n: \n");
    scanf("%d", &n);
    printf("Input the %d values: \n", n);
    for (i = 0;i < n;i++)
    {
        scanf("%d", &v);
        Insert(L, v, i);
    }
    printf("The Sqlist contents:\n");
    for (i = 0;i < n;i++)
    {
        printf("%d ", L->elemList[i]);
    }
    system("pause");
    return 0;
}

(附) C++实现

#include<iostream>
using namespace std;
const int LIST_INIT_SIZE = 100;     // 初始分配空间

typedef struct {
    int *elemList;      // 定义int类型指针指向数组，elem为数组首元素地址
    int length;     // 当前长度
    int listsize;   // 当前储存容量
}Sqlist;

void InitList(Sqlist *Sq)       // 初始化线性表
{
    Sq->elemList = new int [LIST_INIT_SIZE];        // 分配空间
    if (!Sq->elemList)
        exit(1);
    Sq->length = 0;
    Sq->listsize = LIST_INIT_SIZE;
}

void Insert(Sqlist *Sq, int d, int index)   // d为要插入的元素，index为插入的位置
{
    int j;
    if (index<0 || index>Sq->length)
    {
        cout<<"index error\n";
        exit(1);
    }
    if (Sq->length >= LIST_INIT_SIZE)
    {
        cout<<"oversize\n";
        exit(1);
    }
    for (j = Sq->length - 1;j >= index;j--)     // 元素从插入位置依次后移
    {
        Sq->elemList[j + 1] = Sq->elemList[j];
    }
    Sq->elemList[index] = d;        // 插入d
    Sq->length++;   // 长度++
}

int main()
{
    Sqlist* L = new Sqlist; // 初始化线性指针
    InitList(L);
    int n, i, v;
    cout<<"Input the size of Sqlist n: \n";
    cin >> n;
    cout << "Input the " << n << " values: \n";
    for (i = 0;i < n;i++)
    {
        cin >> v;
        Insert(L, v, i);
    }
    cout<<"The Sqlist contents:\n";
    for (i = 0;i < n;i++)
    {
        cout<< L->elemList[i]<<' ';
    }
    cout << endl;
    system("pause");
    delete L;   // 释放空间
    return 0;
}