顺序表的相关操作（静态&动态）

浅浅的花香味﹌ 2022-05-13 01:16 148阅读 0赞

*   *  静态顺序表
        
         *   *  定义
             *  定义结构体
             *  初始化顺序表
             *  销毁顺序表
             *  打印顺序表
             *  插入元素
                
                 *   *  尾插
                     *  头插
                     *  任意位置插入元素
             *  删除元素
                
                 *   *  尾删
                     *  头删
                     *  任意位置删除
                     *  删除遇见的第一个指定元素
                     *  删除所有的指定元素
             *  查找指定元素
             *  排序
                
                 *   *  冒泡排序
                     *  选择排序
             *  测试函数
     *  动态顺序表
        
         *   *  定义结构体
             *  初始化
             *  销毁
             *  插入
                
                 *   *  尾插
                     *  头插
                     *  任意位置插入元素

一般情况下，顺序表包括以下几个操作：  
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++;
        }