网站建设介绍推广用语,西安网站建立,网站开发需要掌握的哪些开发软件,wordpress 站群插件一、顺序表概念 二、顺序表各类接口实现 *顺序表初始化 **顺序表销毁 ***顺序表插入操作 ****顺序表删除操作 *****顺序表查找操作 ******顺序表实现打印操作 三、顺序表整体实现源码 *SeqList.h **SeqList.c ***test.c 一、顺序表概念
讲顺序表之前先引入线性表概念#xff…一、顺序表概念 二、顺序表各类接口实现 *顺序表初始化 **顺序表销毁 ***顺序表插入操作 ****顺序表删除操作 *****顺序表查找操作 ******顺序表实现打印操作 三、顺序表整体实现源码 *SeqList.h **SeqList.c ***test.c 一、顺序表概念
讲顺序表之前先引入线性表概念线性表是n个有相同特性的数据元素的有限序列而常见的线性表又有顺序表、链表、栈、队列、串而例如图、树就是非线性表 顺序表概念顺序表向内存中要了一块连续的空间然后依次存储数据就是一个一个的挨着存储而且里面存放的数据类型是同一种类型就是c语言中的一维数组。 而顺序表又可分为静态的和动态的静态顺序表就是给定一个空间这个空间大小就定死了不可再修改那样的话就会造成空间浪费或者空间不足比如电梯超重不能运行就是给定人数为13人多了就不能升降当然这只是理论上的静态顺序表的空间不可改变因此用动态顺序表比较合适按照自己的需求向堆中申请空间一次不够再第二次第三次直到申请空间足够这样不会造成空间过多的浪费。 在顺序表中要实现对数据的各种操作包括增、删、查、改。而其中增和删又可以在尾部中间头部进行
二、顺序表的各类接口实现
以下是顺序表存储的结构化以及常用头文件包含
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int SDataType;//类型想换就换不然在后面换时需要每一个都换类型
#define INIT_CAPACITY 4//对最开始空间容量为4
typedef struct SeqList
{SDataType *a;//动态分配数组int size;//有效数据个数int capacity;//数组容量
}SL;*顺序表初始化代码
void SeqInit(SL* ps)
{ps-a (SDataType*)malloc(sizeof(SDataType)*INIT_CAPACITY);//向堆动态申请内存空间if (ps-a NULL)//但凡申请都有可能失败{perror(malloc fail);return;}ps-size 0;//初始条件下数组中没有数据ps-capacity INIT_CAPACITY;//一上来就先给数组4个空间大小
}**顺序表销毁代码
void SeqDestory(SL* ps)
{free(ps-a);//堆中开辟的需要释放ps-a NULL;//释放之后置空ps-size ps-capacity 0;//空间大小置为0
}***顺序表插入代码包含头插尾插任意位置插入 顺序表插入过程就如插队一样当中午下课后去食堂排队吃饭一个挨着一个排好这时忽然走来一个人他可以选择就在队伍末尾跟上也可以在队头和其他位置插入俗称插队当然在其后面的肯定不安逸因为他们都要向后挪动一位这时顺序表插入就比如排队 顺序表插入算法思路从最末尾开始向后挪动直到空出一个位置然后将数据插入进去顺序表长度加一 其中空间容量不够需要给它扩容 尾插时间复杂度为O(1 最坏的情况下每一个元素都要向后移到所以时间复杂度为O(n)
当然在顺序表插入数据时需要考虑空间是否足够以下是对顺序表增容代码 void Checkcpacity(SL* ps) { //扩容 if (ps-size ps-capacity) { SDataType* tmp (SDataType*)realloc(ps-a, sizeof(SDataType) * ps-capacity * 2);//扩容看自己喜欢但是二倍较为合适 if (tmp NULL) { printf(“realloc fail”); exit(-1); } ps-capacity * 2;ps-a tmp;//将新开辟的空间给数组a
}}
*尾插代码
void SeqPushBack(SL* ps, SDataType x)
{扩容//if (ps-size ps-capacity)//{// SDataType* tmp (SDataType*)realloc(ps-a, sizeof(SDataType) *ps-capacity*2);//扩容看自己喜欢但是二倍较为合适// if (tmp NULL)// {// printf(realloc fail);// exit(-1);// }// ps-capacity * 2;// ps-a tmp;//将新开辟的空间给数组a//}Checkcpacity(ps);ps-a[ps-size] x;
}
头插代码
void SeqPushFront(SL* ps, SDataType x)
{assert(ps);Checkcpacity(ps);int begin 0;int end ps-size;while (end 0){ps-a[end] ps-a[end - 1];end--;}ps-a[0] x;ps-size;}
任意位置插入
void SeqInsert(SL* ps, int pos, SDataType x)
{assert(ps);Checkcpacity(ps);assert(pos 0 pos ps-size);int end ps-size;while (end pos){ps-a[end] ps-a[end - 1];end--;}ps-a[pos] x;ps-size;
}****顺序表删除操作 也包括头删尾删和任意位置删除删除可以理解为是后一个把前一个覆盖然后顺序表长度减一 删除算法在末尾删时间复杂度就是最好的情况为O(1)它不必循环 最坏的情况是在头部删除删除一个就要挪动n-1个数据其时间复杂度为O(N)删除操作的时间复杂度就为O(n)
头删
void SeqPopFront(SL* ps)
{assert(ps);int begin 0;assert(ps-size 0);while (begin ps-size - 1){ps-a[begin] ps-a[begin 1];begin;}ps-size--;}
**尾删**c
void SeqPopBack(SL* ps)
{/*if (ps-size 0){return;}*/assert(ps-size 0);//断言可以让你知道是哪里出了问题ps-size--;
}任意位置删除
void SeqErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size - 1);assert(ps-size 0);while (pos ps-size-1){ps-a[pos] ps-a[pos 1];pos;}ps-size--;}
*****顺序表查找与修改操作 查找
int SeqFind(SL* ps, SDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
}
修改
void SeqModify(SL* ps, int pos, SDataType x)
{int i 0;for (i 0; i ps-size; i){if (i pos){ps-a[i] x;}}
}******顺序表打印
void Seqprint(SL* ps)
{int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}****三、顺序表整体实现源码 SeqList.h
#includestdlib.h
#includestdio.h
#includeassert.h#define INIT_CAPACITY 4//初始容量
typedef int SDataType;//类型想换就换不然在后面换时需要每一个都换类型typedef struct SeqList
{SDataType *a;int size;//有效数据个数int capacity;//空间容量不够考虑扩容
}SL;void SeqInit(SL* ps);//顺序表初始化void SeqDestory(SL* ps);//顺序表销毁void Seqprint(SL* ps);//顺序表输出void SeqPushBack(SL* ps, SDataType x);//尾插void SeqPopBack(SL* ps);//尾删void SeqPushFront(SL* ps, SDataType x);//头插void SeqPopFront(SL* ps);//头删void SeqErase(SL* ps, int pos);//删除pos位置的元素void SeqInsert(SL* ps, int pos, SDataType x);//在pos位置插入xint SeqFind(SL* ps, SDataType x);//查找值为x的位置void SeqModify(SL* ps, int pos, SDataType x);//修改SeqList.c
#includeSeqList.hvoid SeqInit(SL* ps)
{ps-a (SDataType*)malloc(sizeof(SDataType)*INIT_CAPACITY);if (ps-a NULL){perror(malloc fail);return;}ps-size 0;ps-capacity INIT_CAPACITY;
}void SeqDestory(SL* ps)
{free(ps-a);//堆中开辟的需要释放ps-a NULL;//释放之后置空ps-size ps-capacity 0;//空间大小置为0
}void Seqprint(SL* ps)
{int i 0;for (i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}void Checkcpacity(SL* ps)
{//扩容if (ps-size ps-capacity){SDataType* tmp (SDataType*)realloc(ps-a, sizeof(SDataType) * ps-capacity * 2);//扩容看自己喜欢但是二倍较为合适if (tmp NULL){printf(realloc fail);exit(-1);}ps-capacity * 2;ps-a tmp;//将新开辟的空间给数组a}
}void SeqPushBack(SL* ps, SDataType x)
{扩容//if (ps-size ps-capacity)//{// SDataType* tmp (SDataType*)realloc(ps-a, sizeof(SDataType) *ps-capacity*2);//扩容看自己喜欢但是二倍较为合适// if (tmp NULL)// {// printf(realloc fail);// exit(-1);// }// ps-capacity * 2;// ps-a tmp;//将新开辟的空间给数组a//}Checkcpacity(ps);ps-a[ps-size] x;
}void SeqPopBack(SL* ps)
{/*if (ps-size 0){return;}*/assert(ps-size 0);//断言可以让你知道是哪里出了问题ps-size--;
}void SeqPushFront(SL* ps, SDataType x)
{assert(ps);Checkcpacity(ps);int begin 0;int end ps-size;while (end 0){ps-a[end] ps-a[end - 1];end--;}ps-a[0] x;ps-size;}void SeqPopFront(SL* ps)
{assert(ps);int begin 0;assert(ps-size 0);while (begin ps-size - 1){ps-a[begin] ps-a[begin 1];begin;}ps-size--;}void SeqInsert(SL* ps, int pos, SDataType x)
{assert(ps);Checkcpacity(ps);assert(pos 0 pos ps-size);int end ps-size;while (end pos){ps-a[end] ps-a[end - 1];end--;}ps-a[pos] x;ps-size;
}void SeqErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size - 1);assert(ps-size 0);while (pos ps-size-1){ps-a[pos] ps-a[pos 1];pos;}ps-size--;}int SeqFind(SL* ps, SDataType x)
{assert(ps);int i 0;for (i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
}void SeqModify(SL* ps, int pos, SDataType x)
{int i 0;for (i 0; i ps-size; i){if (i pos){ps-a[i] x;}}
}test.c
#includeSeqList.hvoid test()
{SL s;SeqInit(s);//传结构体地址过去形参改变实参SeqPushBack(s, 1);SeqPushBack(s, 2);SeqPushBack(s, 3);SeqPushBack(s, 4);SeqPushBack(s, 5);Seqprint(s);/*SeqPopBack(s);SeqPopBack(s);SeqPopBack(s);SeqPopBack(s);Seqprint(s);SeqPopBack(s);SeqPopBack(s);SeqPopBack(s);Seqprint(s)*/;SeqPushFront(s, 9);Seqprint(s);/*SeqPopFront(s);SeqPopFront(s);SeqPopFront(s);SeqPopFront(s);*///SeqPopFront(s);//SeqPopFront(s);//SeqPopFront(s);//SeqPopFront(s);//SeqPopFront(s);//SeqPopFront(s);//SeqPopFront(s);SeqPopFront(s);//SeqPopFront(s);//Seqprint(s);SeqInsert(s, 3, 10);Seqprint(s);SeqErase(s, 3);Seqprint(s);int pos SeqFind(s, 3);printf(%d\n, pos);if (pos ! -1){SeqModify(s, pos, 10);}Seqprint(s);SeqDestory(s);
}int main()
{test();return 0;
}总结
顺序表有优点也有缺点 优点尾插、尾删效率贼高也可以按下表来访问顺序表中的元素 缺点在顺序表中出了尾部上的插入删除外在其他位置删除或者插入效率都极低而且在空间不够扩容的时候容易造成空间浪费 好了数据结构顺序表篇就结束了球球各位佬们一键四练叭你们的支持对于我来说尤为重要
