【莫问前路】 数据结构篇 第一话 线性表(上) 顺序表(动态分配)
目录
顺序表的动态分配
顺序表的基本操作
1、创建空的顺序表
2.顺序表的插入操作
3.顺序表的删除操作
4.顺序表的查找操作
5.顺序表的判空操作
顺序表的介绍及其静态分配下的操作,请看:顺序表(静态分配)
顺序表的动态分配
typedef int DataType ;struct SeqList {int MAXNUM; //顺序表的最大容量int length; //顺序表当前长度DataType* data; //指示动态分配数组的指针};typedef struct SeqList* PSeqList; //指向顺序表的指针
顺序表的基本操作
1、创建空的顺序表
PSeqList CreateSeqList(int m){PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList)); //申请结构体的内存空间if (palist != NULL) //内存空间分配成功{palist->data = (DataType*)malloc(sizeof(DataType)*m); //申请数组的内存空间if (palist->data) //数组内存分配成功{palist->MAXNUM = m; //初始化顺序表的最大容量为mpalist->length = 0; //初始化顺序表当前长度为0return palist;//返回已经创建好的顺序表}else{free(palist);//数组内存空间分配失败,释放结构体内存空间}}printf("Out of space!"); //结构体内存空间申请失败,返回空指针return NULL;}
2.顺序表的插入操作
①在顺序表的第i位置插入元素e
bool InsertSeqList(PSeqList palist, int i, DataType e){if (i palist->length + 1) //判断插入的位置是否有效{return false;}if (palist->length >= palist->MAXNUM) //顺序表是否已满,不能插入{return false;}for (int j = palist->length; j >= i; j--) //将第i个元素及之后的元素后移{palist->data[j] = palist->data[j-1];}palist->data[i-1] = e; //在位置i上插入epalist->length++; //顺序表长度加1return true;}
②在顺序表中下标为q的元素前插入元素e
bool InsertSeqList_Pre(PSeqList palist, int q, DataType e){if (q palist->length) //判断下标是否有效{return false;}if (palist->length >= palist->MAXNUM) //顺序表已满{return false;}for (int i = palist->length; i > q; i++) //将下标为q及其后的元素向后移{palist->data[i] = palist->data[i - 1];}palist->data[q-1] = e; //在下标为q-1位置上插入元素epalist->length++; //顺序表长度加1return true;}
③在顺序表下标为q的元素后插入e
bool InsertList_Post(PSeqList palist, int q, DataType e){if (q = palist->length)//判断下标是否有效{return false;}if (palist->length >= palist->MAXNUM) //顺序表已满{return false;}for (int i = palist->length; i > q + 1; i++) //将下标为q位置后的元素后移{palist->data[i] = palist->data[i - 1];}palist->data[q + 1] = e; //在下标为q+1的位置上插入epalist->length++; //顺序表长度加1return true;}
3.顺序表的删除操作
删除顺序表的第i个位置上的元素,并将删除的元素存储在e中
bool DeleteSeqList(PSeqList palist, int i, DataType* e){if (i palist->length)//判断删除的位置是否有效{return false;}*e = palist->data[i - 1];//将被删除的元素赋值给efor (int j = i; j length; j++) //将第i个位置后的元素前移{palist->data[j - 1] = palist->data[j];}palist->length--; //顺序表长度减1return true;}
4.顺序表的查找操作
①按位查找: 将第i个位置上的元素赋值给e
bool GetData(PSeqList palist, int i, DataType* e){if (i palist->length) //判断元素位置是否有效{return false;}*e = palist->data[i - 1]; //e存储第i个位置,即下标为i-1上的元素值return true;}
②按值查找:找到某元素在顺序表中的位置,将位置存储在locate中
bool GetLocate(PSeqList palist, DataType e, int* locate){for (int i = 0; i length; i++){if (e == palist->data[i]) //找到该元素的位置{*locate = i + 1; //将位置存储在locate中return true;}}return false; //没有在顺序表中找到指定元素}
5.顺序表的判空操作
判断顺序表是否为空
bool EmptySeqList(PSeqList palist){//return (palist->length == 0);if (palist->length == 0){return true; //顺序表为空}elsereturn false; //顺序表非空}
The ongoing way is long and rough. I can see no end.
But I will devote myself to the endless seeking of truth.