顺序表是C语言中一种基本的结构,可以存储各种基本类型的数据,而且不但可以存储基本类型的数据,也可以存储一种结构。所以顺序表是一种在学C的过程中必须掌握的结构,通过学习整理,下面来实现一下:
首先,先要想好用什么实现,一般实现最基本的顺序表的话直接用数组实现,我们在这用一个结构体来封装这个顺序表(封装这一概念是在C++中最常用的概念)
#define ARRAY_EMPTY -2 #define ARRAY_FULL -1 #define MAX_SIZE 10000 typedef int Datatype; typedef struct Seqlist { Datatype array[MAX_SIZE]; size_t size; }Seqlist;
对于无法确定数组大小,我们可以用宏来表示。
把大体结构搭建好了之后,就可以思考一个顺序表应该具有的功能,头插,尾插,定点插入,排序等等都是一些最基本的功能:
void PrintSeqlist(Seqlist* pSeq); void InitSeqlist(Seqlist* pSeq); void PushBack(Seqlist* pSeq, Datatype x); void PushFront(Seqlist* pSeq, Datatype x); void PopBack(Seqlist* pSeq); void PopFront(Seqlist* pSeq); void Insert(Seqlist* pSeq,size_t pos, Datatype x); int Find(Seqlist* pSeq, size_t pos, Datatype x); void Erase(Seqlist* pSeq, size_t pos); int Remove(Seqlist* pSeq, Datatype x); int Removeall(Seqlist* pSeq, Datatype x); void Bubblesort(Seqlist* pSeq); void Selectsort(Seqlist* pSeq); int BinarySearch(Seqlist* pSeq, Datatype x);
下面就是一些关键函数的实现:
void PrintSeqlist(Seqlist* pSeq)//输出顺序表 { assert(pSeq); size_t i = 0; if (pSeq->size <= 0) { printf("Array is empty\n"); return; } else if (pSeq->size >= MAX_SIZE) { printf("Array is full\n"); } for (; i < pSeq->size; ++i) { printf("%-4d", pSeq->array[i]); } } void InitSeqlist(Seqlist* pSeq)//初始化顺序表 { pSeq->size = 0; //printf("Initialization is complete\n"); } void PushBack(Seqlist* pSeq, Datatype x)//后插入 { assert(pSeq); if (pSeq->size >= MAX_SIZE) { printf("Array is full, insert the failure\n"); return; } pSeq->array[pSeq->size] = x; pSeq->size++; } void PushFront(Seqlist* pSeq, Datatype x)//前插入 { assert(pSeq); size_t i = 0; if (pSeq->size >= MAX_SIZE) { printf("Array is full, insert the failure\n"); return; } for (i = pSeq->size; i > 0; --i) { pSeq->array[i] = pSeq->array[i - 1]; } pSeq->array[0] = x; pSeq->size++; } void PopBack(Seqlist* pSeq)//后删除 { assert(pSeq); if (pSeq->size <= 0) { printf("Array is empty,popback is eeror\n"); return; } pSeq->array[pSeq->size-1] = 0; pSeq->size--; } void PopFront(Seqlist* pSeq)//前删除 { assert(pSeq); size_t i = 0; if (pSeq->size <= 0) { printf("Array is empty,popback is eeror\n"); return; } for (i = 1; i < pSeq->size; i++) { pSeq->array[i - 1] = pSeq->array[i]; } pSeq->size--; } void Insert(Seqlist* pSeq, size_t pos, Datatype x)//定点删除 { assert(pSeq); size_t i = 0; if (pSeq->size >= MAX_SIZE) { printf("Array is full, insert the failure\n"); return; } for (i = pSeq->size ; i > pos; i--) { pSeq->array[i] = pSeq->array[i - 1]; } pSeq->array[pos] = x; pSeq->size++; } int Find(Seqlist* pSeq, size_t pos, Datatype x)//查找数据 { assert(pSeq); size_t i = 0; if (pSeq->size <= 0) { printf("Array is empty,erase error\n"); return ARRAY_EMPTY; } if (pos < 0 || pos >= MAX_SIZE) { printf("Began to find the position error\n"); return -1; } for (i = pos; i < pSeq->size; i++) { if (pSeq->array[i] == x) { return i; } } return -2; } void Erase(Seqlist* pSeq, size_t pos)//删除特定数据 { assert(pSeq); size_t i = 0; if (pSeq->size <= 0) { printf("Array is empty,erase error\n"); return; } if (pos < 0 || pos >= MAX_SIZE) { printf("Began to find the position error\n"); return; } for (i = pos; i < pSeq->size; i++) { pSeq->array[i] = pSeq->array[i + 1]; } pSeq->size--; } int Remove(Seqlist* pSeq, Datatype x) { assert(pSeq); size_t i = 0; if (pSeq->size <= 0) { printf("Array is empt,remove error\n"); return ARRAY_EMPTY; } for (; i < pSeq->size; i++) { if (pSeq->array[i] == x) { size_t j = i + 1; for (; j < pSeq->size; j++) { pSeq->array[j - 1] = pSeq->array[j]; } pSeq->size--; return 0; } } return -1; } int Removeall(Seqlist* pSeq, Datatype x) { assert(pSeq); size_t i = 0; int flag = 0; if (pSeq->size <= 0) { printf("Array is empt,remove error\n"); return ARRAY_EMPTY; } for (; i < pSeq->size; i++) { if (pSeq->array[i] == x) { size_t j = i + 1; for (; j < pSeq->size; j++) { pSeq->array[j - 1] = pSeq->array[j]; } pSeq->size--; flag++; if (pSeq->size <= 0)//如果顺序表的元素为空就不能再删除了,返回 { return 0; } else { i--; } } } if (flag > 0) return 0; else return -1; } void Bubblesort(Seqlist* pSeq)//冒泡排序 { assert(pSeq); size_t i = 0; for (; i < pSeq->size; i++) { size_t j = 0; for (; j < pSeq->size - i - 1; j++) { if (pSeq->array[j] > pSeq->array[j + 1]) { int tmp = pSeq->array[j]; pSeq->array[j] = pSeq->array[j + 1]; pSeq->array[j + 1] = tmp; } } } } void Selectsort(Seqlist* pSeq)//选择排序 { assert(pSeq); size_t i = 0; for (; i < pSeq->size; i++) { int flag = pSeq->array[i]; size_t j = i; for (; j < pSeq->size; j++) { if (pSeq->array[j] < flag) { int tmp = pSeq->array[j]; pSeq->array[j] = flag; flag = tmp; } } pSeq->array[i] = flag; } } int BinarySearch(Seqlist* pSeq, Datatype x)//二分查找 { assert(pSeq); size_t left = 0; size_t right = pSeq->size - 1; while (left <= right) { size_t mid = left + (right - left) / 2; if (x > pSeq->array[mid]) { left = mid + 1; } else if (x < pSeq->array[mid]) { right = mid - 1; } else if (x == pSeq->array[mid]) { return (int)mid; } } return -1; }
这只是最基本的顺序表,只能够存储基本类型的数据,如果想要存储结构体或者string之类的数据的话会涉及C++的深浅拷贝问题,而且用一个数组来存未知大小的数据结构的话是做不到的。
本人的博客后面会更新顺序表的一些优化写法,希望对朋友微小的帮助。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。