数据结构：顺序表的基本操作

线性表的顺序存储

       线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表在逻辑结构上相邻的元素存储在连续的物理存储单元中，即：通过数据元素物理存储的连续性来反应元素之间逻辑上的相邻关系。采用顺序存储结构存储的线性表通常简称为顺序表。
       顺序存储的线性表的特点：
◆ 线性表的逻辑顺序与物理顺序一致;
◆ 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

顺序表的线性存储示意图

       假设线性表中有n个元素，每个元素占k个存储单元，第一个元素的地址为Loc(a1),则第i个元素的地址Loc(ai):

       Loc(ai) = Loc(a1) + (i-1) * k;
其中Loc(a1)称为基地址。

C语言定义线性表的顺序存储结构

#define ListSize 100      //线性表的最大长度
typedef int DataType;

typedef struct
{
    DataType data[ListSize];   //用数组存储线性表中的元素
    DataType length;           //顺序表中元素的个数
}SeqList, *PSeqList;

       DataType是数据元素类型，可以根据需要定义，可以使用SeqList定义数据表类型变量，使用*PSeqList定义数据表指针变量;

顺序表的基本操作

(1) 顺序表的初始化

       顺序表的初始化就是把顺序表 初始化为空的顺序表；只需把顺序表的长度length置为0即可；

void InitList(PSeqList L)
{
    if (L == NULL)
    {
        return;
    }
    L->length = 0;
}

(2)求顺序表的长度

       顺序表的长度就是就顺序表中的元素的个数，由于在插入和删除操作中都有对数据表的长度进行修改，所以求表长只需返回length的值即可；

int LengthList(PSeqList L)
{
    if (L == NULL)
    {
        return 0;
    }
    return L->length;
}

(3)按序号查找
       查找顺序表中第i个元素的值（按序号查找），如果找到，将将该元素值赋给e。查找第i个元素的值时，首先要判断查找的序号是否合法，如果合法，返回第i个元素对应的值。

int GetData(PSeqList L, int i)
{
    if (L->length < 1 || (L->length > LengthList(L)))
    {
        return 0;
    }
    //数据元素的序号从1开始，数组下表从0开始，第i个元素对应的数组下标为i-1;
    return L->data[i - 1];
}

(4)插入操作
       在数据表的第i个位置插入元素，在顺序表的第i个位置插入元素e，首先将顺序表第i个位置的元素依次向后移动一个位置，然后将元素e插入第i个位置，移动元素要从后往前移动元素，即：先移动最后一个元素，在移动倒数第二个元素，依次类推；插入元素之前要判断插入的位置是否合法，顺序表是否已满，在插入元素之后要将表长L->length++;

int InsList(PSeqList L, int i, DataType e)
{

    //判断插入位置是否合法
    if (i < 1 || L->length >(LengthList(L) + 1))
    {
        printf("插入位置不合法!\n");
        return 0;
    }
    //判断顺序表是否已满
    else if (L->length >= ListSize)
    {
        printf("顺序表已满，不能插入！\n");
        return 0;
    }
    else
    {
        for (k = i; k <= L->length; k--)
        {
            L->data[k + 1] = L->data[k];
        }
        L->data[i - 1] = e;
        L->length++;   //数据表的长度加1
        return 1;
    }
    return 0;
}

(5) 删除操作

       删除表中的第i个元素e，删除数据表中的第i个元素，需要将表中第i个元素之后的元素依次向前移动一位，将前面的元素覆盖掉。移动元素时要想将第i+1个元素移动到第i个位置，在将第i+2个元素移动i+1的位置，直到将最后一个元素移动到它的前一个位置，进行删除操作之前要判断顺序表是否为空，删除元素之后，将表长L->length--;

int DelList(PSeqList L, DataType i, DataType* e)
{
    if (L->length < 1)
    {
        printf("表为空！\n");
        return  0;
    }
    *e = L->data[i - 1];
    for (k = i; k < L->length; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
    return *e;
}

(6)按内容查找

       查找数据元素e在表中的位置，可以从表头开始一直遍历表中元素，如果找到与要查找元素e相等的元素，则返回元素在表中的位置，数组下标从0开始，则元素在表中对应的位置序号值应为对应数组下标加1，没有找到则返回0；

int Locate(PSeqList L, DataType e)
{
    for (k = 0; k < L->length; k++)
    {
        if (L->data[k] == e)
        {
            //k为e对应的数组下标，在表中对应序号应为k+1
            return k + 1;
        }
    }
    return 0;
}

(7)头插

       头插，即在表头插入元素e，在表头插入元素，需要将表中的元素依次后移一位，然后将要插入的元素e赋给数字的首元素，执行插入操作后将表长L->length++;需要注意的是移动元素要从顺序表的最后一个元素开始移动，如果从第1个元素开始移动，会使得第1个元素的值覆盖第2个元素的值，然后把第二个元素后移则会使第2个元素的值(原来第1个元素值)覆盖第3个元素的值，依次类推，最后出插入元素外，其余元素值均为原顺序表中第一个元素的值。

void PushFront(PSeqList L, DataType e)
{
    if (L->length == ListSize)
    {
        printf("顺序表已满，不能插入！\n");
    }
    //将表中元素依次后移一位
    for (k = L->length; k > 0; k--)
    {
        L->data[k] = L->data[k - 1];
    }
    //插入元素
    L->data[0] = e;
    L->length++;
}

(8)头删

       删除顺序表中的第一个元素，只要将顺序表中的元素从第2个开始，依次向前移动1位，覆盖原来顺序表中元素对应位置的前一个值，在删除元素之前要判断顺序表是否为空，删除顺序表元素之后将顺序表长度L->length--;

void PopFront(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("顺序表为空\n");
    }
    for (k = 1; k <= L->length - 1; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
}

(9)尾插

       在顺序表表尾插入元素e，L->data[L->length] = e;将元素e的值赋给顺序表中最后一个元素的下一个元素；尾插操作，需要判断顺序表是否已满，尾插后将顺序表长度L->length++;

void PushBack(PSeqList L, DataType e)
{
    if (L->length == ListSize)
    {
        printf("顺序表已满，不能插入!\n");
    }
    L->data[L->length] = e;
    L->length++;
}

(10) 尾删

       删除表尾元素，只需将顺序表的长度减1,类似于出栈操作，栈顶指针top –。

void PopBack(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("表为空！\n");
    }
    L->length--;

}

(11) 清空顺序表

       清空顺序表就是将表中的元素删除。删除表中的元素只需将表的长度置为0。

void ClearList(PSeqList L)
{
    L->length = 0;
}

(12)判断表是否为空

       如果顺序表的长度为0，则顺序表为空，返回1，否则，返回0；

int EmptyList(PSeqList L)
{
    if (L->length == 0)
    {
        return 1;
    }
    return 0;
}

(13)打印表中元素

       依次打印顺序表中的元素，如果顺序表为空则输出提示。

void PrintList(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("表为空！\n");
        return;
    }
    for (k = 0; k < L->length; k++)
    {
        printf("%-3d", L->data[k]);
    }
    printf("\n");
}

顺序表的基础操作完整代码

SeqList.h数据结构的定义和基本操作函数声明

#pragma once

#define ListSize 100      //线性表的最大长度
typedef int DataType;

typedef struct
{
    DataType data[ListSize];   //用数组存储线性表中的元素
    DataType length;           //顺序表的长度
}SeqList, *PSeqList;

void InitList(PSeqList L);  //顺序表的初始化操作
int LengthList(PSeqList L); //求顺序表的长度
int GetData(PSeqList L, int i); //返回数据表中第i个元素的值
int InsList(PSeqList L, int i, DataType e);   //在顺序表的第i个位置插入元素
int DelList(PSeqList L, DataType i, DataType* e); //删除顺序表L的第i个数据元素
int Locate(PSeqList L, DataType e); //查找数据元素e在表中的位置
void PushFront(PSeqList L, DataType e); //头插，在表头插入元素e
void PopFront(PSeqList L);    //头删,删除表中的第一个元素
void PushBack(PSeqList L, DataType e);  //尾插，在表尾插入元素e
void PopBack(PSeqList L); //尾删，删除表尾元素
void ClearList(PSeqList L);  //清空顺序表
int EmptyList(PSeqList L);   //判断顺序表是否为空
void PrintList(PSeqList L);  //打印表中元素

SeqList.c 函数的具体实现

#include <stdio.h>
#include "SeqList.h"

int k = 0;  //全局变量，用于作部分操作的循环变量
//初始化顺序表
void InitList(PSeqList L)
{
    if (L == NULL)
    {
        return;
    }
    L->length = 0;
}

//求顺序表的长度

int LengthList(PSeqList L)
{
    if (L == NULL)
    {
        return 0;
    }
    return L->length;
}

//返回数据表中第i个元素的值
int GetData(PSeqList L, int i)
{
    if (L->length < 1 || (L->length > LengthList(L)))
    {
        return 0;
    }
    //数据元素的序号从1开始，数组下表从0开始，第i个元素对应的数组下标为i-1;
    return L->data[i - 1];
}

//在L中第i个位置，插入新的数据元素e

int InsList(PSeqList L, int i, DataType e)
{

    //判断插入位置是否合法
    if (i < 1 || L->length >(LengthList(L) + 1))
    {
        printf("插入位置不合法!\n");
        return 0;
    }
    //判断顺序表是否已满
    else if (L->length >= ListSize)
    {
        printf("顺序表已满，不能插入！\n");
        return 0;
    }
    else
    {
        for (k = i; k <= L->length; k--)
        {
            L->data[k + 1] = L->data[k];
        }
        L->data[i - 1] = e;
        L->length++;   //数据表的长度加1
        return 1;
    }
    return 0;
}

//删除L的第i个数据元素

int DelList(PSeqList L, DataType i, DataType* e)
{
    if (L->length < 1)
    {
        printf("表为空！\n");
        return  0;
    }
    *e = L->data[i - 1];
    for (k = i; k < L->length; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
    return *e;
}

//查找e在表中的位置

int Locate(PSeqList L, DataType e)
{
    for (k = 0; k < L->length; k++)
    {
        if (L->data[k] == e)
        {
            //k为e对应的数组下标，在表中对应序号应为k+1
            return k + 1;
        }
    }
    return 0;
}

//头插，在表头插入元素e

void PushFront(PSeqList L, DataType e)
{
    if (L->length == ListSize)
    {
        printf("顺序表已满，不能插入！\n");
    }
    //将表中元素依次后移一位
    for (k = L->length; k > 0; k--)
    {
        L->data[k] = L->data[k - 1];
    }
    //插入元素
    L->data[0] = e;
    L->length++;
}

//头删,删除顺序表中的第一个元素，把顺序表中的元素依次往前移动一位

void PopFront(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("顺序表为空，不能插入！\n");
    }
    for (k = 1; k <= L->length - 1; k++)
    {
        L->data[k - 1] = L->data[k];
    }
    L->length--;
}

//尾插
void PushBack(PSeqList L, DataType e)
{
    if (L->length == ListSize)
    {
        printf("顺序表已满，不能插入!\n");
    }
    L->data[L->length] = e;
    L->length++;
}


//尾删
void PopBack(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("表为空！\n");
    }
    L->length--;

}

//清空顺序表
void ClearList(PSeqList L)
{
    L->length = 0;
}

//判断表是否为空

int EmptyList(PSeqList L)
{
    if (L->length == 0)
    {
        return 1;
    }
    return 0;
}

//打印表中元素

void PrintList(PSeqList L)
{
    if (EmptyList(L))
    {
        printf("表为空！\n");
        return;
    }
    for (k = 0; k < L->length; k++)
    {
        printf("%-3d", L->data[k]);
    }
    printf("\n");
}

mian.c函数的简单测试代码

#include <stdio.h>
#include <Windows.h>
#include "SeqList.h"

int main()
{
    SeqList L;
    DataType data;
    //初始化顺序表
    InitList(&L);
    //在表中插入元素
    printf("依次在表中插入元素(1,2,3,4,5)：\n");
    InsList(&L, 1, 1);
    InsList(&L, 2, 2);
    InsList(&L, 3, 3);
    InsList(&L, 4, 4);
    InsList(&L, 5, 5);

    //打印表中元素
    printf("表中元素有：\n");
    PrintList(&L);
    //头插
    printf("在表头依次插入元素，6,7:\n");
    PushFront(&L, 6);
    PushFront(&L, 7);
    //尾插
    printf("在表尾依次插入元素，8,9:\n");
    PushBack(&L, 8);
    PushBack(&L, 9);
    printf("表中元素有：\n");
    PrintList(&L);
    //头删
    printf("头删一个元素:\n");
    PopFront(&L);
    //尾删
    printf("尾删一个元素:\n");
    PopBack(&L);
    //输出表中第4个元素值
    PrintList(&L);
    printf("表中第4个元素值为：\n%d\n",GetData(&L, 4));
    //查找表中第 i个元素的位置
    printf("元素2在表中的位置为：\n");
    printf("%d\n",Locate(&L, 2));
    //删除表中第2个元素对应的值
    printf("删除表中第2个元素：%d\n", DelList(&L, 2, &data));
    printf("顺序表的长度为：%d\n", LengthList(&L));
    printf("表中元素为：\n");
    PrintList(&L);
    //printf("删除的元素值为：%d\n", data);
    //清空顺序表
    ClearList(&L);
    PrintList(&L);
    system("pause");
    return 0;
}