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

一般情况下，顺序表包括以下几个操作：

1. 初始化顺序表 2. 插入元素（尾插，头插，任意位置插） 3. 删除元素（尾删，头删，任意位置删） 4. 打印顺序表元素 5. 查找（查找下标，查找元素） 6. 排序 7. 销毁顺序表

静态顺序表

定义

#define MAX 100    typedef int DataType;

定义结构体

typedef struct SeqList{        DataType arr[MAX]; //定义一个数组        int size; //表示数组中元素的个数    }SeqList, *pSeqList;

初始化顺序表

void InitSeqList(pSeqList ps)    {        assert(ps);        ps->size = 0;    }

销毁顺序表

void DestroySeqList(pSeqList ps)    {        assert(ps);        ps->size = 0;    }

静态顺序表的初始化和销毁是一样的，都只需要将数组中元素的个数设置为0即可

打印顺序表

void PrintSeqList(pSeqList ps)    {        assert(ps);        for (int i = 0; i < ps->size; i++)        {            printf("%d ", ps->arr[i]);        }        printf("\n");    }

插入元素

尾插

void PushBack(pSeqList ps, DataType d)    {        assert(ps);        if (ps->size == MAX)        {            printf("顺序表已满，无法插入\n");            return;        }        ps->arr[ps->size] = d;        ps->size++;    }

头插

void PushPront(pSeqList ps, DataType d)    {        assert(ps);        if (ps->size == MAX)        {            printf("顺序表已满，无法插入\n");            return;        }        for (int i = ps->size; i > 0; i--)        {            ps->arr[i] = ps->arr[i - 1];        }        ps->arr[0] = d;        ps->size++;    }

任意位置插入元素

void Insert(pSeqList ps, int pos, DataType d)    {        assert(ps);        if (ps->size == MAX)        {            printf("顺序表已满，无法插入\n");            return;        }        for (int i = ps->size; i > pos; i--)        {            ps->arr[i] = ps->arr[i - 1];        }        ps->arr[pos] = d;        ps->size++;    }

删除元素

尾删

void PopBack(pSeqList ps)    {        assert(ps);        if (ps->size == 0)        {            printf("顺序表为空，无法删除\n");            return;        }        ps->size--;    }

头删

void PopFront(pSeqList ps)    {        assert(ps);        if (ps->size == 0)        {            printf("顺序表为空，无法删除\n");            return;        }        for (int i = 0; i < ps->size; i++)        {            ps->arr[i] = ps->arr[i + 1];        }        ps->size--;    }

任意位置删除

void Remove(pSeqList ps, int pos) //pos表示删除元素的下标    {        assert(ps);        if (ps->size == 0)        {            printf("顺序表为空，无法删除\n");            return;        }        for (int i = pos; i < ps->size; i++)        {            ps->arr[i] = ps->arr[i + 1];        }        ps->size--;    }

删除遇见的第一个指定元素

void RemoveFirst(pSeqList ps, DataType d)    {        assert(ps);        if (ps->size == 0)        {            printf("顺序表为空，无法删除\n");            return;        }        for (int i = 0; i < ps->size; i++)        {            if (ps->arr[i] == d)            {                for (int j = i; j < ps->size; j++)                {                    ps->arr[j] = ps->arr[j + 1];                }                break;            }        }        ps->size--;    }

删除所有的指定元素

void RemoveAll(pSeqList ps, DataType d)    {        int i = 0;        assert(ps);        if (ps->size == 0)        {            printf("顺序表为空，无法删除\n");            return;        }        while (i < ps->size)        {            int ret = i;            if (ps->arr[i] == d)            {                for (int j = i; j < ps->size; j++)                {                    ps->arr[j] = ps->arr[j + 1];                }                ps->size--;                continue;            }            i++;        }    }

查找指定元素

int Find(pSeqList ps, DataType d)    {        assert(ps);        for (int i = 0; i < ps->size; i++)        {            if (ps->arr[i] == d)            {                return i;            }        }        return -1; //如果没有返回-1    }

排序

冒泡排序

void BubbleSort(pSeqList ps)    {        assert(ps);        for (int i = 0; i < ps->size - 1; i++)        {            int flag = 0;            for (int j = 0; j < ps->size - 1 - i; j++)            {                if (ps->arr[j] > ps->arr[j + 1])                {                    DataType tmp = ps->arr[j];                    ps->arr[j] = ps->arr[j + 1];                    ps->arr[j + 1] = tmp;                    flag = 1;                }            }            if (flag == 0)            {                return;            }        }    }

选择排序

void Swap(DataType *p1, DataType *p2)    {        DataType tmp = *p1;        *p1 = *p2;        *p2 = tmp;    }    void SelectSort(pSeqList ps)    {        assert(ps);        int left = 0;        int right = ps->size - 1;        while (left < right)        {            int maxPos = left;            int minPos = left;            for (int i = left; i <= right; i++)            {                if (ps->arr[i] > ps->arr[maxPos])                {                    maxPos = i;                }                if (ps->arr[i] < ps->arr[minPos])                {                    minPos = i;                }            }            Swap(&ps->arr[minPos], &ps->arr[left]);            if (maxPos == left)            {                maxPos = minPos;            }            Swap(&ps->arr[maxPos], &ps->arr[right]);            left++;            right--;        }    }

测试函数

int main()    {        SeqList seq;        InitSeqList(&seq);        /*PushBack(&seq, 5);        PushBack(&seq, 4);        PushBack(&seq, 3);        PushBack(&seq, 2);        PushBack(&seq, 1);*/        PushPront(&seq, 1);        PushPront(&seq, 2);        PushPront(&seq, 3);        PushPront(&seq, 4);        PushPront(&seq, 4);        PushPront(&seq, 5);        PushPront(&seq, 5);        PushPront(&seq, 5);        /*Insert(&seq, 5, 6);        Insert(&seq, 5, 6);        Insert(&seq, 3, 5);*/        /*PopBack(&seq);        PopBack(&seq);*/        //PopFront(&seq);        //PopFront(&seq);        /*Remove(&seq, 3);        Remove(&seq, 0);        Remove(&seq, 4);*/        /*RemoveFirst(&seq, 3);        RemoveFirst(&seq, 5);*/        /*RemoveAll(&seq, 5);        RemoveAll(&seq, 3);*/        PrintSeqList(&seq);        BubbleSort(&seq);        PrintSeqList(&seq);        SelectSort(&seq);        PrintSeqList(&seq);        //int ret = Find(&seq, 8);        //if (ret != -1)        //{
           //  printf("%d\n", ret);        //}        //else        //{
           //  printf("没找到\n");        //}        DestroySeqList(&seq);        return 0;    }

动态顺序表

如果要将静态顺序表改成动态顺序表，要将定义的结构体改一下，在函数方面，只需要改三个函数：初始化、销毁、插入。别的操作都一模一样

定义结构体

typedef struct SeqList    {        DataType *arr;        int size;        int capacity;     }SeqList, *pSeqList;

初始化

void InitSeqList(pSeqList ps)    {        assert(ps);        const int init_capacity = 3;//表示第一次申请空间能够存放元素的大小        ps->size = 0;        ps->capacity = init_capacity;        ps->arr = (DataType *)malloc(sizeof(DataType) * init_capacity);        assert(ps->arr);    }

销毁

void DestroySeqList(pSeqList ps)    {        assert(ps);        free(ps->arr);        ps->arr = NULL;        ps->size = 0;        ps->capacity = 0;    }

插入

尾插

void ExpandIfRequired(pSeqList ps) //判断是否需要扩容，如若需要，完成扩容    {        assert(ps);        if (ps->size < ps->capacity)        {            return;        }        int newCapacity = ps->capacity * 2;        DataType *newArr = (DataType *)malloc(sizeof(DataType) * newCapacity);        assert(newArr);        for (int i = 0; i < ps->size; i++)        {            newArr[i] = ps->arr[i];        }        free(ps->arr);        ps->arr = newArr;        ps->capacity = newCapacity;    }    void PushBack(pSeqList ps, DataType d)    {        assert(ps);        ExpandIfRequired(ps);        ps->arr[ps->size++] = d;    }

头插

void PushPront(pSeqList ps, DataType d)    {        assert(ps);        ExpandIfRequired(ps);        for (int i = ps->size; i > 0; i--)        {            ps->arr[i] = ps->arr[i - 1];        }        ps->arr[0] = d;        ps->size++;    }

任意位置插入元素

void Insert(pSeqList ps, int pos, DataType d)    {        assert(ps);        ExpandIfRequired(ps);        for (int i = ps->size; i > pos; i--)        {            ps->arr[i] = ps->arr[i - 1];        }        ps->arr[pos] = d;        ps->size++;    }

转载地址：http://rbwdb.baihongyu.com/