赞
踩
顺序表(Sequential List)是一种线性表的存储结构,用于表示元素之间的顺序关系。顺序表中的元素在内存中是连续存储的。
顺序表可以使用数组实现,它具有以下特点:
//SeqList.h
#define N 20
typedef int SLDataType; //使用typedef可以使顺序表中元素的类容方便修改
struct SeqList
{
SLDataType a[N];//定义数组长度
int size; //定义有效数据个数
};//静态顺序表--N太小,可能不够用,N太大,可能浪费空间
在不知道所存储的内容的数量时,一般使用动态的顺序表,以节省空间。
//SeqList.h
typedef int SLDataType; //使用typedef可以使顺序表中元素的类容方便修改
typedef struct SeqList
{
SLDataType* a; //指向动态数组指针
int size; //数据个数
int capacity; //容量空间大小
}SL; //这里使用typedef创建该结构体类型变量时更方便
//SeqList.h
//初始化/销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);
//SeqList.c void SLInit(SL* ps) { ps->a = NULL; ps->size = ps->capacity = 0; } void SLDestory(SL* ps) { if (ps->a) { free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; } }
因为创建的顺序表示个动态存储的顺序表那么就得满足当容量不足的时候,能够进行扩容,而不是一开始在定义结构体的时候就将顺序表的容量写死。
这里采用的是检查容量的方式来实现顺序表的动态存储,size 是已经存入的数据个数,capacity 是可以存储数据的个数,当存入和容量相等即空间满了的时候,这里采用realloc函数对顺序表进行扩容。
因为realloc函数实在堆区申请空间的所以一次扩容不宜过多这里是一次扩容到原来的两倍。
//SeqList.h
//检查容量空间,满了扩容
void SLCheckCapacity(SL* ps);
//SeqList.c void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = realloc(ps->a, newCapacity * sizeof(SLDataType)); if (tmp == NULL)//指针判空,以防ralloc失败 { printf("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } }
realloc(void *__ptr, size_t __size):更改已经配置的内存空间,即更改由malloc()函数分配的内存空间的大小。
如果将分配的内存减少,realloc仅仅是改变索引的信息。
如果是将分配的内存扩大,则有以下情况:
注意:如果调用成功,不管当前内存段后面的空闲空间是否满足要求,都会释放掉原来的指针,重新返回一个指针,虽然返回的指针有可能和原来的指针一样,即不能再次释放掉原来的指针。
//SeqList.h
//尾插/尾删
//时间复杂度O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
//SeqList.c void SLPushBack(SL* ps, SLDataType x) { //SLCheckCapacity(ps); // ps->a[ps->size] = x; //在顺序表得尾部添加一个数据 //ps->size++; SLInsert(ps, ps->size, x);//复用SLInsert,SLPushFront相当于插入到最后一个元素 } void SLPushFront(SL* ps, SLDataType x) { //SLCheckCapacity(ps); 将所有数据向后挪一个 //int end = ps->size - 1; //while (end >= 0) //{ // ps->a[end + 1] = ps->a[end]; // --end; //} //ps->a[0] = x; //ps->size++; SLInsert(ps, 0, x);//复用SLInsert,SLPushFront相当于插入第0个元素 }
//SeqList.h
//时间复杂度O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//SeqList.c void SLPopBack(SL* ps) { //ps->a[ps->size - 1] = 0; //以防越界 //if (ps->size == 0) //{ // printf("SeqList is empty\n"); // return; //} //暴力检查 //assert(ps->size > 0); //ps->size--; SLErase(ps, ps->size - 1);//复用 } void SLPopFront(SL* ps) { //assert(ps->size > 0); //挪移 //int begin = 1; //while (begin < ps->size ) //{ // ps->a[begin - 1] = ps->a[begin]; // ++begin; //} //ps->size--; SLErase(ps, 0);//复用 }
//SeqList.h
//在任意的位置插入删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//SeqList.c void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);//可以在最后一个元素后面添加,所以用<=size SLCheckCapacity(ps); //挪用数据 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; } void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); //1. //int begin = pos; //while (begin < ps-> size - 1) //{ // ps->a[begin] = ps->a[begin + 1]; // ++begin; //} //2. int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }
//SeqList.h
//查找/修改
int* SLFind(SL* ps, SLDataType x);//找到返回数据下标数组,没有找到则返回-1
void SLModify(SL* ps, int pos, SLDataType x);
//SeqList.c int* SLFind(SL* ps, SLDataType x) { //只能找一个 //assert(ps); //for (int i = 0; i < ps->size; ++i) //{ // if (ps->a[i] == x) // { // return i; // } //} //return -1; //找多个 assert(ps); SLDataType val; int* arr; int t = 0; arr = (int*)malloc((ps->size + 1) * sizeof(int)); if (arr == NULL) //指针判空,以防malloc失败 { perror("InitContact::malloc"); exit(-1); } for (int i = 0; i < ps->size; ++i) { if (ps->a[i] == x) { arr[t++] = i; } } arr[t] = -1; return arr; } void SLModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" enum op { Exit, //0 PushBack, //1 PopBack, //2 PushFront,//3 PopFront, //4 Insert, //5 Erase, //6 Find, //7 Modify, //8 }; void menu() { printf("\n"); printf("**************************************\n"); printf("********1.PushBack 2.PopBack ******\n"); printf("********3.PushFront 4.PopFront******\n"); printf("********5.Insert 6.Erase ******\n"); printf("********7.Find 8.Modify ******\n"); printf("********0.Exit ******\n"); printf("**************************************\n"); } void MultiPushBack(SL* ps) { assert(ps); SLDataType val; printf("请连续输入你要“尾插”的数据,以-1结束:>"); scanf("%d", &val); while (val != -1) { SLPushBack(ps, val); scanf("%d", &val); } SLPrint(ps); } void MultiPopBack(SL* ps) { assert(ps); int num; printf("请连续输入你要“尾删”的个数:>"); scanf("%d", &num); for (int i = 0; i < num; i++) { SLPopBack(ps); } SLPrint(ps); } void MultiPushFront(SL* ps) { assert(ps); SLDataType val; printf("请连续输入你要“头插”的数据,以-1结束:>"); scanf("%d", &val); while (val != -1) { SLPushFront(ps, val); scanf("%d", &val); } SLPrint(ps); } void MultiPopFront(SL* ps) { assert(ps); int num; printf("请连续输入你要“头删”的个数:>"); scanf("%d", &num); for (int i = 0; i < num; i++) { SLPopFront(ps); } SLPrint(ps); } void MultiInsert(SL* ps) { assert(ps); SLDataType val; int pos; printf("请输入你要“插入”的位置:>"); scanf("%d", &pos); printf("请连续输入你要“插入”的数据,以-1结束:>"); scanf("%d", &val); while (val != -1) { SLInsert(ps, pos++, val); scanf("%d", &val); } SLPrint(ps); } void MultiErase(SL* ps) { assert(ps); int num; int pos; printf("请输入你要“删除”的位置:>"); scanf("%d", &pos); printf("请连续输入你要“删除”的数据的个数:>"); scanf("%d", &num); for (int i = 0; i < num; i++) { SLErase(ps, pos); } SLPrint(ps); } void MultiFind(SL* ps) { assert(ps); SLDataType val; int* arr; int t; arr = (int*)malloc((ps->size + 1) * sizeof(int)); if (arr == NULL) //指针判空,以防malloc失败 { perror("InitContact::malloc"); exit(-1); } printf("请输入你要找的内容:>"); scanf("%d", &val); arr = SLFind(ps, val); if (*arr == -1) { printf("你所找的内容不存在!\n"); return; } printf("你所找的内容下标分别为:"); for (int i = 0; arr[i] != -1; i++) { printf("%-5d", arr[i]); } printf("\n"); free(arr); } void MultiModify(SL* ps) { assert(ps); SLDataType val; SLDataType C_val; int* arr; int t; arr = (int*)malloc((ps->size + 1) * sizeof(int)); if (arr == NULL) //指针判空,以防malloc失败 { perror("InitContact::malloc"); exit(-1); } printf("请输入你“修改的内容”以及“修改后的值”:>"); scanf("%d%d", &val, &C_val); arr = SLFind(ps, val); if (*arr == -1) { printf("你所修改的内容不存在!\n"); return; } for (int i = 0; arr[i] != -1; i++) { SLModify(ps, arr[i], C_val); } SLPrint(ps); free(arr); } void SeqListTest() { SL sl; SLInit(&sl); int option; do { menu(); printf("请输入选项:>"); scanf("%d", &option); switch (option) { case 0: SLDestory(&sl); printf("退出程序!\n"); exit(-1); break; case PushBack: MultiPushBack(&sl); break; case PopBack: MultiPopBack(&sl); break; case PushFront: MultiPushFront(&sl); break; case PopFront: MultiPopFront(&sl); break; case Insert: MultiInsert(&sl); break; case Erase: MultiErase(&sl); break; case Find: MultiFind(&sl); break; case Modify: MultiModify(&sl); break; default: printf("输入无效!\n"); break; } } while (1); } int main() { SeqListTest(); return 0; }
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void SLPrint(SL* ps) { //assert(ps != NULL) assert(ps);//暴力的防御检查,可以指出错误地方 printf("\n"); printf("序号: "); for (int i = 0; i < ps->size; ++i) { printf("%-5d", i); } printf("\n"); printf("内容: "); for (int i = 0; i < ps->size; ++i) { printf("%-5d", ps->a[i]); } printf("\n"); } void SLInit(SL* ps) { ps->a = NULL; ps->size = ps->capacity = 0; } void SLDestory(SL* ps) { if (ps->a) { free(ps->a); ps->a = NULL; ps->capacity = ps->size = 0; } } void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = realloc(ps->a, newCapacity * sizeof(SLDataType)); if (tmp == NULL)//指针判空,以防ralloc失败 { printf("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } } /*************************************************** 因为创建的顺序表示个动态存储的顺序表那么就得满足当容量不足的时候, 能够进行扩容,而不是一开始在定义结构体的时候就将顺序表的容量写死。 这里采用的是检查容量的方式来实现顺序表的动态存储, (size)是已经存入的数据个数,(capacity)是可以存储数据的个数, 当存入和容量相等即空间满了的时候,这里采用realloc函数对顺序表进行扩容。 因为realloc函数实在堆区申请空间的所以一次扩容不宜过多这里是一次扩容到原来的两倍。 ******************************************************************************/ void SLPushBack(SL* ps, SLDataType x) { //SLCheckCapacity(ps); // ps->a[ps->size] = x; //在顺序表得尾部添加一个数据 //ps->size++; SLInsert(ps, ps->size, x);//复用SLInsert,SLPushFront相当于插入到最后一个元素 } void SLPushFront(SL* ps, SLDataType x) { //SLCheckCapacity(ps); 将所有数据向后挪一个 //int end = ps->size - 1; //while (end >= 0) //{ // ps->a[end + 1] = ps->a[end]; // --end; //} //ps->a[0] = x; //ps->size++; SLInsert(ps, 0, x);//复用SLInsert,SLPushFront相当于插入第0个元素 } void SLPopBack(SL* ps) { //ps->a[ps->size - 1] = 0; //以防越界 //if (ps->size == 0) //{ // printf("SeqList is empty\n"); // return; //} //暴力检查 //assert(ps->size > 0); //ps->size--; SLErase(ps, ps->size - 1);//复用 } void SLPopFront(SL* ps) { //assert(ps->size > 0); //挪移 //int begin = 1; //while (begin < ps->size ) //{ // ps->a[begin - 1] = ps->a[begin]; // ++begin; //} //ps->size--; SLErase(ps, 0);//复用 } void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);//可以在最后一个元素后面添加,所以用<=size SLCheckCapacity(ps); //挪用数据 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; } void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); //1. //int begin = pos; //while (begin < ps-> size - 1) //{ // ps->a[begin] = ps->a[begin + 1]; // ++begin; //} //2. int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; } int* SLFind(SL* ps, SLDataType x) { //只能找一个 //assert(ps); //for (int i = 0; i < ps->size; ++i) //{ // if (ps->a[i] == x) // { // return i; // } //} //return -1; //找多个 assert(ps); SLDataType val; int* arr; int t = 0; arr = (int*)malloc((ps->size + 1) * sizeof(int)); if (arr == NULL) //指针判空,以防malloc失败 { perror("InitContact::malloc"); exit(-1); } for (int i = 0; i < ps->size; ++i) { if (ps->a[i] == x) { arr[t++] = i; } } arr[t] = -1; return arr; } void SLModify(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //#define N 20 typedef int SLDataType; //使用typedef可以使顺序表中元素的类容方便修改 //struct SeqList //{ // SLDataType a[N];//定义数组长度 // int size; //定义有效数据个数 //};//静态顺序表--N太小,可能不够用,N太大,可能浪费空间 typedef struct SeqList { SLDataType* a; //指向动态数组指针 int size; //数据个数 int capacity; //容量空间大小 }SL; //这里使用typedef创建该结构体类型变量时更方便 //打印顺序表 void SLPrint(SL* ps); //初始化/销毁 void SLInit(SL* ps); void SLDestory(SL* ps); //检查容量空间,满了扩容 void SLCheckCapacity(SL* ps); //尾插/尾删/头插/头删/ //时间复杂度O(1) void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); //时间复杂度O(N) 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);//找到返回数据下标数组,没有找到则返回-1 void SLModify(SL* ps, int pos, SLDataType x)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。