赞
踩
- 线性表的顺序存储又称顺序表。用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得**逻辑上相邻的两个元素,在物理位置上也相邻。**
- 其特点就是逻辑顺序与物理存储顺序相同
- 用来容纳顺序表元素的一维数组,可以是静态分配的,也可以是动态分配的。静态分配是指一开始就已经指定了顺序表的最大长度,动态分配是指根据需要,可以动态增加顺序表能容纳的最大长度,用realloc追加分配空间。
下面用C++演示顺序表的基本操作,相关操作已经详细注明;
需要知道的知识:C++的函数重载
/* 实现了静态顺序表和动态顺序表的初始化和新增数据操作 */ #include<iostream> using namespace std; /*定义静态顺序表的最大长度 MaxSize*/ const int MaxSize = 50; /*定义动态顺序表的初始长度,以及每次追加的空间*/ const int InitSize = 50; const int Addsize = 1; /*定义自己的数据类型 ElemType,我这里将int类型指定为 ElemType类型*/ typedef int ElemType; /*静态的顺序表,最大长度固定*/ typedef struct { /*存储数据的表,实质上是 ElemType 类型的数组*/ ElemType data[MaxSize]; /*用于记录数据表中当前的成员数量,而不是指最大长度,切勿混淆*/ int maxsize; int length; }Static_sqlist; typedef struct { /*记录动态分配数组的首元素指针*/ ElemType* data; /*记录顺序表可以容纳的最大元素个数*/ int maxsize; int addsize; /*用于记录数据表中当前的成员数量,而不是指最大长度,切勿混淆*/ int length; }Dynamic_sqlist; /*后面对表的相关操作,均采用函数重载的方法,方便统一管理*/ /*初始化静态的顺序表*/ void Init_sqlist(Static_sqlist *list) { /*数组元素的个数初始化为0*/ list->length = 0; list->maxsize = MaxSize; /*将顺序表的所有存储位置全部初始化为0*/ for (int i = 0; i < MaxSize; i++) { list->data[i] = 0; } return; } /*初始化动态顺序表*/ void Init_sqlist(Dynamic_sqlist* list) { /*给动态顺序表分配空间,并返回动态数组的首地址*/ list->data = new ElemType[InitSize]; /*异常判断*/ if (!list->data) { cout << "Dynamic_list: fail to allocate space!"; return; } for (int i = 0; i < list->maxsize; i++) { list->data[i] = 0; } list->length = 0; /*第一次分配的最大长度即为 InitSize 的长度*/ list->maxsize = InitSize; list->addsize = Addsize; return; } /*向静态顺序表中添加元素*/ void list_add(Static_sqlist* list, ElemType item) { /*判断表是否已经满了*/ if (list->length >= list->maxsize) { cout << "Static_sqlist: Maxsize is " << list->maxsize << ", there is no space for new item: " << item << "\n\n"; return; } /*这里的 ++list->length - 1 ,实际上是先将 length + 1, *但是数组的下标是 length - 1,所以减去了一个1,下同 */ list->data[++list->length - 1] = item; return; } /*向动态顺序表中添加元素*/ void list_add(Dynamic_sqlist* list, ElemType item) { /*判断表是否已经满了*/ if (list->length >= list->maxsize) { /*表满,则追加空间*/ /*由于realloc分配失败会导致内存泄露,因此先用一个new_head拿到新分配的首地址 * 对其进行判断后没问题再给list->data */ cout << "Dynamic_list: memory is full,try to allocate for item: " << item << endl; ElemType* new_head = (ElemType*)realloc(list->data, (list->length + list->addsize) * sizeof(ElemType)); if (!new_head) { cout << "Dynamic_sqlist: Maxsize is " << list->maxsize << ", there is no space for new item.\n"; return; } else { /*成功分配空间则把新的地址给 list->data*/ cout << "New memory is allocated successfully for item: " << item << "\n\n"; list->data = new_head; list->maxsize += list->addsize; } } list->data[++list->length - 1] = item; return; } /*遍历静态数组*/ void view_list(Static_sqlist& list) { for (int i = 0; i < list.length; i++) { cout << list.data[i] << " "; } cout << endl; } /*遍历动态数组*/ void view_list(Dynamic_sqlist& list) { for (int i = 0; i < list.length; i++) { cout << list.data[i] << " "; } cout << endl; } /*释放掉动态内存申请的空间*/ void space_delete(Dynamic_sqlist& list) { delete[] list.data; } int main() { Static_sqlist list1; Dynamic_sqlist list2; Init_sqlist(&list1); Init_sqlist(&list2); for (ElemType i = 1; i < 55; i++) { list_add(&list1, i); list_add(&list2, i); } cout << "The static sqlist:\n"; view_list(list1); cout << " The dynamic sqlist:\n"; view_list(list2); space_delete(list2); }
上文中的代码运行结果如下:
Static_sqlist: Maxsize is 50, there is no space for new item: 51 Dynamic_list: memory is full,try to allocate for item: 51 New memory is allocated successfully for item: 51 Static_sqlist: Maxsize is 50, there is no space for new item: 52 Dynamic_list: memory is full,try to allocate for item: 52 New memory is allocated successfully for item: 52 Static_sqlist: Maxsize is 50, there is no space for new item: 53 Dynamic_list: memory is full,try to allocate for item: 53 New memory is allocated successfully for item: 53 Static_sqlist: Maxsize is 50, there is no space for new item: 54 Dynamic_list: memory is full,try to allocate for item: 54 New memory is allocated successfully for item: 54 The static sqlist: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 The dynamic sqlist: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
/*若要作为单独的测试文件,请更改文件类型为cpp,并添加相应的头文件*/ #include<iostream> using namespace std; /*静态顺序表的查找和动态顺序表的一模一样,因此此处只给出动态顺序表的实现方法*/ int list_find(Dynamic_sqlist* list, ElemType item) { cout << "You want to add item " << item << "'s location. Try to do that: \n"; for (int i = 0; i < list->length; i++) { /*查找成功返回元素在数组中的下标*/ if (list->data[i] == item) { cout << "Find the item: " << item << ", "; cout << "Its location is " << i + 1 << ".\n\n"; return i; } } /*返回 -1 表示未查找成功*/ cout << "Can not find the item: " << item << "." << "\n\n"; return -1; } /*静态顺序表删除,基本思想是将删除点元素的后面的所有元素都往前移动一个位置*/ /*特殊情况是末尾元素,则不用移动*/ /*返回删除的位置*/ int list_delete(Dynamic_sqlist* list, ElemType item) { /*首先找到元素的位置下标,用loc记录*/ int loc = -1; for (int i = 0; i < list->length; i++) { if (list->data[i] == item) { loc = i; } } if (loc == -1) { cout << "Error,Item: " << item << "don't exist" << endl; } /*找到元素,开始开始移动其后的元素*/ /*若是末尾元素,逻辑上删除就可以了,下次添加的元素可以直接覆盖其原来的存储位置*/ if (loc == list->length - 1) { list->length--; } else { for (int i = loc; i < list->length - 1; i++) { list->data[i] = list->data[i + 1]; } list->length--; } cout << "Delete item: " << item << " successfully.\n\n"; return loc; } /*在指定的地方添加元素*/ void list_add_at_location(Dynamic_sqlist* list, ElemType item, int location) { /*判断表是否已经满了*/ cout << "You want to add item " << item << " at location " << location << ". Try to do that: \n"; if (list->length >= list->maxsize) { /*表满,则追加空间*/ /*由于realloc分配失败会导致内存泄露,因此先用一个new_head拿到新分配的首地址 * 对其进行判断后没问题再给list->data */ cout << "Dynamic_list: memory is full,try to allocate for item: " << item << endl; ElemType* new_head = (ElemType*)realloc(list->data, (list->length + list->addsize) * sizeof(ElemType)); if (!new_head) { cout << "Dynamic_sqlist: Maxsize is " << list->maxsize << ", there is no space for new item.\n"; return; } else { /*成功分配空间则把新的地址给 list->data*/ cout << "New memory is allocated successfully for item: " << item << "\n\n"; list->data = new_head; list->maxsize += list->addsize; } } if (location > list->length) { cout << "The location is out of the scope,operation failed,exit !" << "\n\n"; return; } /*如果在末尾添加元素*/ if (location == list->length) { list->data[list->length] = item; list->length++; } else { /*在添加元素的地方,将其后面的所有元素往后挪一个位置*/ /*注意,元素的数组下标是其位序 - 1,比如第 3 个元素,其数组下班实际上是 2 */ for (int i = list->length - 1; i >= location - 1; i--) { list->data[i + 1] = list->data[i]; } } cout << "The item " << item << " is added at location: " << location << "\n\n"; list->data[location - 1] = item; list->length++; return; } #if 0 int main() { Dynamic_sqlist list; Init_sqlist(&list); for (ElemType i = 1; i < 52; i++) { list_add(&list, i); } view_list(&list); list_find(&list, 10); list_add_at_location(&list, 9999, 31); view_list(&list); list_delete(&list, 9999); view_list(&list); space_delete(list); } #endif
本段代码的测试结果如下:
Dynamic_list: memory is full,try to allocate for item: 51 New memory is allocated successfully for item: 51 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 You want to add item 10's location. Try to do that: Find the item: 10, Its location is 10. You want to add item 9999 at location 31. Try to do that: Dynamic_list: memory is full,try to allocate for item: 9999 New memory is allocated successfully for item: 9999 The item 9999 is added at location: 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 9999 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 Delete item: 9999 successfully. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
代码可在我的gitee仓库找到哦
觉得博主的文章不错请点点关注点点赞哦,后面会写更好更多的内容。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。