顺序表的静态存储（C语言实现）

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

1.顺序表的结构体声明

#define MAX_SIZE 5       //定义数组的大小

typedef int DataType;

typedef struct SeqList

{

    DataType array[MAX_SIZE];

    size_t size;

}SeqList;

2.顺序表的初始化

void InitSeqList(SeqList* pSeq)         //址传递要用到指针

{

    assert(pSeq);

    memset(pSeq->array, , sizeof(DataType)*MAX_SIZE);    //初始化数组

    pSeq->size = ;

}

3.顺序表尾插、尾删、打印

//1.检查参数

//2.边界条件的检查

//3.完成功能函数

//尾插

void PushBack(SeqList* pSeq, DataType x)

{

    assert(pSeq);        //检查参数

    if (pSeq->size >= MAX_SIZE)      //边界条件检查

    {

        printf("SeqList is Full !");

        printf("\n");

        return;

    }

    pSeq->array[pSeq->size++] = x;

}

//尾删

void PopBack(SeqList* pSeq)

{

    assert(pSeq);      //检查参数

    if (pSeq->size <=)           //边界条件检查

    {

        printf("SeqList is empty !");

        printf("\n");

        return;

    }

    //pSeq->array[--pSeq->size] = 0;

    --pSeq->size;

}

//打印

void PrintSeqList(SeqList* pSeq)

{

    assert(pSeq);         //检查参数

    int i = ;

    for (; i < pSeq->size; i++)

    {

        printf("%d ", pSeq->array[i]);

    }

    printf("\n");

}

4.头插

void PushFront(SeqList* pSeq, DataType x)

{

    assert(pSeq);      //检查参数

    int begin = pSeq->size - ;

    if (pSeq->size >= MAX_SIZE)      //边界条件检查

    {

        printf("SeqList is Full !");

        printf("\n");

        return;

    }

    //把已经存好的数据依次向后挪动一位后，在顺序表的首位置插入x

    for (; begin >= ; --begin)

    {

        pSeq->array[begin + ] = pSeq->array[begin];

    }

    pSeq->array[] = x;

    ++pSeq->size;

}

5.头删

void PopFront(SeqList* pSeq)

{

    assert(pSeq);       //检查参数

    int begin = ;

    if (pSeq->size <= )          //检查边界条件，顺序表可能为空

    {

        printf("SeqList is empty !\n");

    }

    //把顺序表的数据依次向前挪一位

    for (; begin <pSeq->size-; begin++)

    {

        pSeq->array[begin] = pSeq->array[begin + ];

    }

    --pSeq->size;

}

6.固定位置插入数据和删除数据

//固定位置插入数据

void Insert(SeqList* pSeq, size_t pos, DataType x)

{

    assert(pSeq);         //检查参数

    assert(pos<=pSeq->size);       //检查位置的有效性

    int begin = pSeq->size - ;

    if (pSeq->size >= MAX_SIZE)     //检查边界条件，如果顺序表已满则无法插入

    {

        printf("SeqList is Full !");

        printf("\n");

        return;

    }

    //把从pos开始后面的数据依次向后挪，再在pos位置处添加数据x

    for (; begin >=(int) pos; begin--)       //begin和pos的数据类型要相同再比较

    {

        pSeq->array[begin+] = pSeq->array[begin];

    }

    pSeq->array[pos] = x;

    ++pSeq->size;        //添加数据后size自增一

}

//固定位置删除数据

void Erase(SeqList* pSeq, size_t pos)

{

    assert(pSeq);      //检查参数的有效性

    assert(pos < pSeq->size);     //检查位置的有效性

    int begin = pos;

    if (pSeq->size <= )            //检查边界条件

    {

        printf("SeqList is empty !");

        printf("\n");

        return;

    }

    //把pos后的数据依次向前挪一位

    for (; begin <= pSeq->size - ; begin++)

    {

        pSeq->array[begin] = pSeq->array[begin + ];

    }

    --pSeq->size;

}

7.查找数据、找到数据并删除它

//查找

int Find(SeqList* pSeq, size_t pos, DataType x)

{

    assert(pSeq);       //检查参数

    int i= pos;

    for (;i < pSeq->size; i++)

    {

        if (pSeq->array[i] == x)

            return i;

    }

    return -;

}

//查找并删除

int Remove(SeqList* pSeq, DataType x)

{

    assert(pSeq);                //检查参数

    int pos = Find(pSeq, ,x);   //先找到x并返回它的位置，如果找到就删了它

    if (pos != -)

    {

        Erase(pSeq, pos);

    }

    return pos;

}

8.删除顺序表中所有相同的x

//删除所有x

void RemoveAll(SeqList* pSeq, DataType x)

{

    //从第一个数开始找，找到就删除，删了后再从下一个位置接着找

    assert(pSeq);              //检查参数

    int pos = Find(pSeq, , x);

    while (pos !=-)

    {

        Erase(pSeq, pos);

        pos = Find(pSeq,pos, x);

    }

}

优化（遍历一遍就把所有的x删除，并把后面的数据向前挪动相应个的位置）

void removeall(SeqList* pSeq, DataType x)

{

    assert(pSeq);

    int i = ;

    int count = ;

    for (; i < pSeq->size; i++)

    {

        if (pSeq->array[i] == x)

        {

            count++;

        }

        else

        {

        pSeq->array[i-count] = pSeq->array[i];

        }

    }

    pSeq->size -= count;   //删完挪完后size要删多少就减多少

}

9.顺序表的二分查找

int BinarySearch(SeqList* pSeq, DataType x)

{

    assert(pSeq);

    int left = ;

    //int right = pSeq->size - 1;          //  [  ]  注意边界

    int right = pSeq->size;               //  [  )

    //while (left <= right)

    while (left<right)

    {

        int mid = left - (left - right) / ;   //防止溢出

        if (pSeq->array[mid] == x)

        {

            return mid;

        }

        else if (pSeq->array[mid]>x)

        {

            right = mid - ;

            //right = mid;

        }

        else if (pSeq->array[mid]<x)

        {

            left = mid + ;

        }

    }

    return -;

}

10.冒泡排序

void BubbleSort(SeqList* pSeq)

{

    assert(pSeq);    //检查参数

    int i, j;

    int ret = ;

    for (i = ; i < pSeq->size - ; i++)

    {

            int exchange=;

        for (j = ; j < pSeq->size - i - ; j++)

        {

            if (pSeq->array[j]> pSeq->array[j + ])

            {

                ret = pSeq->array[j];

                pSeq->array[j] = pSeq->array[j + ];

                pSeq->array[j + ] = ret;

                exchange=;

            }

        }

        if(exchange==)   //如果没有发生交换，说明次序已经排好

        {

           return ;

        }

    }

}

11.选择排序

//一次选出最大最小的数据分别放在序列的两端

void Swap(DataType* left,DataType*right)

{

    DataType tmp = *left;

    *left = *right;

    *right = tmp;

}

void SeclectSort(SeqList* pSeq)

{

    assert(pSeq);

    int left = ;

    int right = pSeq->size - ;

    int ret ,min,max;

    while (left<right)

    {

        min = left;

        max = right;

        for (int i = left; i<right; ++i)

        {

            if (pSeq->array[min]>pSeq->array[i])

            {

                Swap(&pSeq->array[min], &pSeq->array[i]);

            }

            if (pSeq->array[max]<pSeq->array[i])

            {

                Swap(&pSeq->array[max], &pSeq->array[i]);

            }

        }

        ++left;

        --right;

    }

}

简单的测试与主函数

void Test()

{

    SeqList seq;

    InitSeqList(&seq);

    PushBack(&seq, );

    PushBack(&seq, );

    PushBack(&seq, );

    PushBack(&seq, );

    PushBack(&seq, );

    PrintSeqList(&seq);

    SeclectSort(&seq);

    PrintSeqList(&seq);

}

int main()

{

    Test();

    system("pause");

    return ;

}

巴特西

顺序表的静态存储（C语言实现）

最新文章

热门文章