本文共 6763 字，大约阅读时间需要 22 分钟。

相关概念：

线性表：n（n>=0）个数据元素组成的一个有限序列，可以在其任意位置上进行插入和删除操作的线性数据结构 从数据在物理内存存储形式上线性表分为：顺序表和链表

从上图可知：

线性表中的数据与数据之间存在一对一的关系，即除了第一个元素和最后一个元素之外，每个元素都有唯一的直接前驱和唯一的直接后继，第一个元素没有前驱，最后一个元素没有后继。

顺序表

用一段地址连续的存储单元依次存储数据元素的线性结构。

地址连续的空间，我们一般采用数组，因为数组有静态数组和动态数组之分，所以顺序表分为：静态顺序表与动态顺序表。

静态顺序表的定义

#define MAX_SIZE 10typedef int DataType;typedef struct SeqList{    DataType _array[MAX_SIZE];    int _size;  //顺序表中有效元素个数}SeqList, *PSeqList;

静态顺序表的基本操作

实现基于静态数组的顺序表的以下基本操作:

• 初始化
• 尾插
• 尾删
• 头插
• 头删
• 删除任意位置元素
• 在任意位置插入元素
• 在顺序表中查找任意元素
• 冒泡排序
• 选择排序
• 二分查找
• 顺序表判空

代码实现如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       /****************************************************************///顺序表的声明#define MAX_SIZE 10typedef int DataType;typedef struct SeqList{    DataType _array[MAX_SIZE];    int _size;  //顺序表中有效元素个数}SeqList, *PSeqList;/**************************************/void InitSeqList(PSeqList pSeq);//初始化void SeqListPushBack(PSeqList pSeq, DataType data); //尾插元素datavoid SeqListPrint(PSeqList pSeq);//顺序表的打印void SeqListPopBack(PSeqList pSeq); //尾删元素void SeqListPushFront(PSeqList pSeq, DataType data);//头插元素datavoid  SeqListPopFront(PSeqList pSeq);//头删元素void SeqListInsert(PSeqList pSeq,DataType data,DataType pos);//任意位置添加元素void SeqListErase(PSeqList pSeq, DataType pos);//删除任意位置元素int FindNum(PSeqList pSeq, DataType data);//在顺序表中查找任意元素void BubbleSort(PSeqList pSeq);//冒泡排序void SelectSort(PSeqList pSeq);//选择排序int BinarySearch(PSeqList pSeq, DataType data);//二分查找void SeqListEmpty(PSeqList pSeq);//顺序表判空/**************************************/void InitSeqList(PSeqList pSeq){    assert(pSeq);   //顺序表已经定义，若传进来的pSeq是NULL属非法操作    memset(pSeq->_array, 0, MAX_SIZE* sizeof(DataType));    pSeq->_size = 0;}void SeqListPushBack(PSeqList pSeq, DataType data){    assert(pSeq);   //顺序表已经定义，若传进来的pSeq是NULL属非法操作    //需要考虑顺序表是否已经满了的情况，如果表已满，无法插入，直接返回    if (pSeq->_size >= MAX_SIZE)    {        printf("顺序表已满，无法插入！\n");        return;    }    pSeq->_array[pSeq->_size] = data;    pSeq->_size++;  //插入成功就让size++    printf("尾部插入成功！\n");}void SeqListPrint(PSeqList pSeq){    assert(pSeq);    for (int i = 0; i < pSeq->_size; i++)    {        printf("%d", pSeq->_array[i]);    }    printf("\n");}void SeqListPopBack(PSeqList pSeq){    assert(pSeq);//顺序表已经定义，若传进来的pSeq是NULL，属于非法操作    //考虑顺序表为空的情况，若为空，无法删除，直接返回    if (pSeq->_size == 0)    {        printf("顺序表为空，无法删除！\n");        return;    }    pSeq->_size--;  //顺序表不为空，直接让size--}void SeqListPushFront(PSeqList pSeq, DataType data){    assert(pSeq);    //考虑顺序表已满情况    if (pSeq->_size >= MAX_SIZE)    {        printf("顺序表已满！无法插入！\n");        return;    }    for (int i = pSeq->_size; i > 0; --i)//现将顺序表中元素向后整体向后移一位，再在头部添加元素    {        pSeq->_array[i] = pSeq->_array[i - 1];    }    pSeq->_array[0] = data;    pSeq->_size++;}void  SeqListPopFront(PSeqList pSeq){    assert(pSeq);    //考虑顺序表为空的情况，若为空，无法删除，直接返回    if (pSeq->_size == 0)    {        printf("顺序表为空，无法删除！\n");        return;    }    //pSeq->_size-1:    //因为若不减一，则会出现pSeq->_array[pSeq->_size]这个无效数组元素    for (int i = 0; i < pSeq->_size - 1; i++)    {        pSeq->_array[i] = pSeq->_array[i + 1];    }    pSeq->_size--;}void SeqListInsert(PSeqList pSeq, DataType data, DataType pos){    assert(pSeq);    //考虑插入元素位置不在顺序表合法范围内，即为越界    if (pos<0 || pos>pSeq->_size)    {        printf("数据越界！\n");        return;    }    //考虑顺序表已满情况    if (pSeq->_size >= MAX_SIZE)    {        printf("顺序表已满！无法插入！\n");        return;    }    for (int i = pSeq->_size; i > pos; --i)    {        pSeq->_array[i] = pSeq->_array[i-1];    }    pSeq->_array[pos] = data;    pSeq->_size++;}void SeqListErase(PSeqList pSeq, DataType pos){    assert(pSeq);    if (pSeq->_size == 0)    {        printf("顺序表为空，无法删除！\n");        return;    }    for (int i =pos; i
       
        _size-1; ++i)    {        pSeq->_array[i] = pSeq->_array[i + 1];    }    pSeq->_size--;}int FindNum(PSeqList pSeq, DataType data){    assert(pSeq);    for (int i = 0; i < pSeq->_size; i++)    {        if (pSeq->_array[i] == data)        {            printf("元素在第%d个位置\n", i);            return i;        }    }    printf("未找到该元素！\n");    return -1;}void BubbleSort(PSeqList pSeq){    assert(pSeq);    if (pSeq->_size == 0)    {        printf("顺序表为空，无法排序！\n");        return;    }    for (int i = 0; i < pSeq->_size - 1; ++i)    {        for (int j = 0; j < pSeq->_size - 1 - i; ++j)        {            if (pSeq->_array[j]>pSeq->_array[j + 1])            {                int tmp = pSeq->_array[j];                pSeq->_array[j] = pSeq->_array[j + 1];                pSeq->_array[j + 1] = tmp;            }        }    }    printf("排序成功！\n");}void SelectSort(PSeqList pSeq){    assert(pSeq);    if (pSeq->_size == 0)    {        printf("顺序表为空，无法排序！\n");        return;    }    for (int i = 0; i < pSeq->_size - 1; i++)    {        int min = i;        for (int j = 1; j < pSeq->_size - 1; j++)        {            if (pSeq->_array[i]>pSeq->_array[j])            {                min = j;                int tmp = pSeq->_array[j];                pSeq->_array[j] = pSeq->_array[j + 1];                pSeq->_array[j + 1] = tmp;            }        }    }    printf("排序成功！\n");}int BinarySearch(PSeqList pSeq, DataType data){    int left = 0;    int right = pSeq->_size - 1;    int mid = 0;    while (left <= right)    {        mid = left + ((right -left)>> 1);        if (pSeq->_array[mid] == data)        {            return mid;        }        else if (pSeq->_array[mid] > data)            right = mid - 1;        else if (pSeq->_array[mid] < data)            left = mid + 1;        printf("查找成功！\n");        return 1;    }    printf("未查找到！\n");    return -1;}void SeqListEmpty(PSeqList pSeq){    assert(pSeq);    if (pSeq->_size == 0)    {        printf("顺序表为空\n");        return;    }}/**************************************///测试部分void Test(){    SeqList pSeq ;    InitSeqList(&pSeq);    SeqListPushBack(&pSeq, 0);    SeqListPushBack(&pSeq, 1);    SeqListPushBack(&pSeq, 2);    SeqListPushBack(&pSeq, 3);    SeqListPushBack(&pSeq, 4);    SeqListPushBack(&pSeq, 5);    SeqListPushBack(&pSeq, 6);    SeqListPushBack(&pSeq, 7);    SeqListPrint(&pSeq);    SeqListPopBack(&pSeq);    SeqListPopBack(&pSeq);    SeqListPrint(&pSeq);    SeqListPushFront(&pSeq, 8);    SeqListPushFront(&pSeq, 9);    SeqListPrint(&pSeq);    SeqListPopFront(&pSeq);    SeqListPopFront(&pSeq);    SeqListPrint(&pSeq);    SeqListInsert(&pSeq, 11, 2);    SeqListPrint(&pSeq);    SeqListErase(&pSeq, 2);    SeqListPrint(&pSeq);    FindNum(&pSeq, 2);    FindNum(&pSeq, 8);    SeqListPushFront(&pSeq, 6);    SeqListPushFront(&pSeq, 7);    SeqListPrint(&pSeq);    BubbleSort(&pSeq);    SeqListPrint(&pSeq);    /*SeqListPushFront(&pSeq, 8);    SeqListPushFront(&pSeq, 9);    SeqListPrint(&pSeq);    SelectSort(&pSeq);    SeqListPrint(&pSeq);*/    BinarySearch(&pSeq, 4);}