做西点网站,seo工作内容和薪资,网站主目录权限配置,网络工程师培训学校本篇将讲解一些关于顺序表的内容#xff0c;顺序表分为静态顺序表和动态顺序表#xff0c;其中经常用到的为动态顺序表#xff0c;所以本篇将以动态顺序表为重点给出一些关于动态顺序表的操作。 因为顺序表的实现逻辑较为简单#xff0c;对于代码的讲解大多以注释给出。
1… 本篇将讲解一些关于顺序表的内容顺序表分为静态顺序表和动态顺序表其中经常用到的为动态顺序表所以本篇将以动态顺序表为重点给出一些关于动态顺序表的操作。 因为顺序表的实现逻辑较为简单对于代码的讲解大多以注释给出。
1.顺序表相关操作 以下包括顺序表的抽象类型定义、两种顺序表的定义方式、以及一些相关操作
#include stdio.h
#include stdlib.h
#include assert.h//元素类型
typedef int DataType;
//静态表元素个数
#define MAX_SIZE 10//静态顺序表
typedef struct { DataType arr[MAX_SIZE];int size;
}SL;//动态顺序表
typedef struct { DataType* arr;int size; int capacity;
}SqList;//顺序表初始化
void SLInit(SqList* ps); //顺序表尾插/头插
void SLPushBack(SqList* ps,DataType x);
void SLPushFront(SqList* ps, DataType x);//顺序表尾部删除/头部删除
void SLPopBack(SqList* ps);
void SLPopFront(SqList* ps);//指定位置之前插入/删除数据
void SLInsert(SqList* ps, int position, DataType x);
void SLErase(SqList* ps, int position);//在顺序表中找到相关的元素
int SLFind(SqList* ps, DataType x);//打印顺序表
void SLPrint(SqList* ps);
2.顺序表的插入与初始化 顺序表的插入包括头插和尾插头插就是在顺序表的第一个元素位置插入尾插就是在最后一个元素后面插入。
//顺序表的初始化
void SLInit(SqList* ps) {ps-arr NULL;ps-capacity 0;ps-size 0;
}//检查顺序表的当前容量
void SLCheckCapacity(SqList* ps) {if (ps-capacity ps-size) {//三目操作符对容量进行分配int newCapacity (ps-capacity 0) ? 4 : 2 * ps-capacity; DataType* newBase (DataType*)realloc(ps-arr, newCapacity * sizeof(DataType));if (newBase NULL) {perror(realloc:);exit(1);}ps-arr newBase;ps-capacity newCapacity;}
}//头插
void SLPushFront(SqList* ps, DataType x) {SLCheckCapacity(ps);int count ps-size;//将所有元素都向后移一位while (count ! 0) {ps-arr[count] ps-arr[count - 1];count--;}ps-arr[count] x;ps-size;
}//尾插
void SLPushBack(SqList* ps,DataType x) {SLCheckCapacity(ps);ps-arr[ps-size] x;ps-size;
}
3.顺序表的删除 以下为顺序表的头部删除和尾部删除。
//尾删
void SLPopBack(SqList* ps) {//检查顺表是否存在以及容量是否为0assert(ps);assert(ps-size);ps-size--;
}void SLPopFront(SqList* ps) {assert(ps);assert(ps-size);//将所有元素都向前覆盖for (int i 0; i ps-size - 1; i) {ps-arr[i] ps-arr[i 1];}ps-size--;
}
4.顺序表的指定插入与删除 以下的代码对指定位置的插入与删除
//指定位置插入
void SLInsert(SqList* ps, int position, DataType x) {//判断位置是否合法assert(position 0 position ps-size);assert(ps);for (int i ps-size; i position; i--) {ps-arr[i] ps-arr[i - 1];}ps-arr[position] x;ps-size;
}//指定位置删除
void SLErase(SqList* ps, int position) {assert(ps);assert(position 0 position ps-size);//从指定位置开始往前覆盖for (int i position; i ps-size - 1; i) {ps-arr[i] ps-arr[i 1];}ps-size--;
}
5.顺序表的查找以及遍历 顺序表的查找为在表中找到对应的元素遍历就是将所有元素给打印出来
//顺序表的遍历
void SLPrint(SqList* ps) {assert(ps);assert(ps-size);for (int i 0; i ps-size; i) {printf(%d , ps-arr[i]);}printf(\n);
}//顺序表的查找
int SLFind(SqList* ps, DataType x) {assert(ps);assert(ps-size);int i 0;for (i 0; i ps-size; i) {if (ps-arr[i] x) {return i 1;}}return -1;
}
6.全部代码
#include stdio.h
#include stdlib.h
#include assert.h//元素类型
typedef int DataType;//动态顺序表
typedef struct { DataType* arr;int size; int capacity;
}SqList;void SLInit(SqList* ps) {ps-arr NULL;ps-capacity 0;ps-size 0;
}void SLCheckCapacity(SqList* ps) {if (ps-capacity ps-size) {int newCapacity (ps-capacity 0) ? 4 : 2 * ps-capacity;DataType* newBase (DataType*)realloc(ps-arr, newCapacity * sizeof(DataType));if (newBase NULL) {perror(realloc:);exit(1);}ps-arr newBase;ps-capacity newCapacity;}
}//尾插
void SLPushBack(SqList* ps,DataType x) {SLCheckCapacity(ps);//检验容量ps-arr[ps-size] x;ps-size;
}//头插
void SLPushFront(SqList* ps, DataType x) {SLCheckCapacity(ps);int count ps-size;while (count ! 0) {ps-arr[count] ps-arr[count - 1];count--;}ps-arr[count] x;ps-size;
}void SLPrint(SqList* ps) {assert(ps);assert(ps-size);for (int i 0; i ps-size; i) {printf(%d , ps-arr[i]);}printf(\n);
}void SLPopBack(SqList* ps) {assert(ps);assert(ps-size);ps-size--;
}void SLPopFront(SqList* ps) {assert(ps);assert(ps-size);for (int i 0; i ps-size - 1; i) {ps-arr[i] ps-arr[i 1];}ps-size--;
}void SLInsert(SqList* ps, int position, DataType x) {assert(position 0 position ps-size);for (int i ps-size; i position; i--) {ps-arr[i] ps-arr[i - 1];}ps-arr[position] x;ps-size;
}void SLErase(SqList* ps, int position) {assert(ps);assert(position 0 position ps-size);for (int i position; i ps-size - 1; i) {ps-arr[i] ps-arr[i 1];}ps-size--;
}int SLFind(SqList* ps, DataType x) {assert(ps);assert(ps-size);int i 0;for (i 0; i ps-size; i) {if (ps-arr[i] x) {return i 1;}}return -1;
}int main() {SqList SL;SLInit(SL);SLPushBack(SL, 1);SLPushBack(SL, 2);SLPushBack(SL, 3);SLPushBack(SL, 4);SLPrint(SL); //1 2 3 4SLPushFront(SL, 7);SLPushFront(SL, 6);SLPushFront(SL, 5);SLPrint(SL); //5 6 7 1 2 3 4SLPopBack(SL);SLPopBack(SL);SLPopFront(SL);SLPrint(SL); //6 7 1 2SLErase(SL, 0);SLInsert(SL, 2, 9);SLPrint(SL); //7 1 9 2int ret SLFind(SL, 9);if (ret -1) {printf(have not the element\n);}else {printf(the location of element is %d\n, ret);}return 0;
}
7.测试
