🔖尾删
//尾删 void SLPopBack(SL* ps) { //assert(ps->size > 0)//暴力检查 if (ps->size == 0)//如果size==0说明顺序表已经没有数据了，也就不用再尾删 { return; } ps->size--; }
由于顺序表是用连续的物理空间来进行数据存储的，因此尾删数据只需要把有限数据个数减一就行，这样我们就无法访问到原链表中的最后一个数据，进而实现了顺序表的尾删，删掉后，顺序表中剩下的多余空间不能单独释放，在堆上动态申请的一块连续空间只能同时释放。就类似于你参加团购，购买时是一起购买的，退货时也不允许你一个人退货。
🔖头插
//头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); //进行容量检查 SLCheckCapacity(ps); //对数据进行挪动 int end = ps->size - 1; while (end >= 0) { ps->arr[end + 1] = ps->arr[end]; end--; } ps->arr[0] = x; ps->size++; }
头插需要先进行容量检查，再把原顺序表中的元素全部往后挪动一位，最后再进行插入。
🔖头删
//头删 void SLPopFront(SL* ps) { assert(ps); assert(ps->size > 0); //从第二个元素开始把后面的元素全部往前挪动一位 int str = 1; while (str < ps->size) { ps->arr[str - 1] = ps->arr[str]; str++; } ps->size--; }
头删需要从第二个元素开始把后面的所有元素往前挪动一位。
🔖在pos位置插入
//在pos位置处插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); //把从pos位置开始的所有数据往后挪动一位 int end = ps->size - 1; while (end >= pos) { ps->arr[end + 1] = ps->arr[end]; end--; } ps->arr[pos] = x; ps->size++; }
🔖删除pos位置元素
//删除pos位置元素 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//size位置不能删，不是顺序表中的有效位置 //把pos位置后面的所有元素往前挪动一位 int str = pos + 1; while (str < ps->size) { ps->arr[str - 1] = ps->arr[str]; str++; } ps->size--; }
🔖查找
//查找 int SLFind(SL* ps, SLDataType x) { assert(ps); int str = 0; while (str < ps->size) { if (ps->arr[str] == x) { return str; } str++; } return -1; }
🔖打印顺序表元素
void SLPrint(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++)//遍历一遍 { printf("%d ", ps->arr[i]); } printf("\n"); }
🔖时间复杂度分析
尾插和尾删是直接进行的没有涉及到对顺序表的遍历，因此当插入N个数据的时候他俩的时间复杂度都是O ( N ) O(N)O(N)，而头插和头删都需要遍历顺序表将元素进行挪动，所以当头插或者头删一个数据的时候时间复杂度都是O ( N ) O(N)O(N)，当插入或者删除N个数据的时候时间复杂度就是O ( N 2 ) O(N^2)O(N 2 )。同理，在pos位置进行插入和删除以及查找的时间复杂度也是O ( N 2 ) O(N^2)O(N
2 )。
📖动态顺序表完整版源码
- SeqList.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #define N 10 #define INIT_CAPACITY 4 typedef int SLDataType; //动态顺序表，按需申请 typedef struct SeqList { SLDataType* arr; int size; //有效数据个数 int capacity; //空间容量 }SL; //增删查改 void SLInit(SL* ps); void SLDestory(SL* ps); void SLPrint(SL* ps); void SLCheckCapacity(SL* ps); void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); void SLInsert(SL* ps, int pos, SLDataType x); void SLErase(SL* ps, int pos); int SLFind(SL* ps, SLDataType x);
SeqList.c
#include "SeqList.h" void SLInit(SL* ps) { assert(ps); ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); if (ps->arr == NULL) { perror("malloc"); return; } ps->size = 0; ps->capacity = INIT_CAPACITY; } void SLDestory(SL* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->size = 0; } void SLPrint(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf("\n"); } //检查容量 void SLCheckCapacity(SL* ps) { assert(ps); if (ps->size == ps->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps->arr = tmp; ps->capacity *= 2; } } //增删查改 //尾插 void SLPushBack(SL* ps, SLDataType x) { // assert(ps); SLCheckCapacity(ps); //ps->a[ps->size] = x; //ps->size++; ps->arr[ps->size++] = x; } //尾删 void SLPopBack(SL* ps) { if (ps->size == 0) { return; } ps->size--; } //头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= 0) { ps->arr[end + 1] = ps->arr[end]; end--; } ps->arr[0] = x; ps->size++; } //头删 void SLPopFront(SL* ps) { assert(ps); assert(ps->size > 0); int str = 1; while (str < ps->size) { ps->arr[str - 1] = ps->arr[str]; str++; } ps->size--; } //在pos位置处插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->arr[end + 1] = ps->arr[end]; end--; } ps->arr[pos] = x; ps->size++; } //删除pos位置元素 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int str = pos + 1; while (str < ps->size) { ps->arr[str - 1] = ps->arr[str]; str++; } ps->size--; } //查找 int SLFind(SL* ps, SLDataType x) { assert(ps); int str = 0; while (str < ps->size) { if (ps->arr[str] == x) { return str; } str++; } return -1; }
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是春人前进的动力！
