数据结构之顺序表
数据结构之顺序表
纲要：
- 什么是循序表
- 顺序表的操作
- 顺序表的一些缺点
一.什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储。
2. 动态顺序表：使用动态开辟的数组存储
如：
// 顺序表的静态存储 #define N 100 typedef int SLDataType; typedef struct SeqList { SLDataType array[N]; // 定长数组 size_t size; // 有效数据的个数 }SeqList;
// 顺序表的动态存储 typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 size_t size ; // 有效数据个数 size_t capicity ; // 容量空间的大小 }SeqList;
对于静态顺序表的操作就是简单的数组操作，我们主要重点讲解动态顺序表的操作。
二.顺序表的操作
1.顺序表的初始设定与初始化
当我们来写顺序表的时候，我们要想到我们在表里所储存的类型是否可以直接写为普通的数据类型(如 int, float ...),它是否是一成不变的，当我们有一天需要改变类型，我们又该怎么做？
所以我们就来用一个宏来实现我们的数据类型的定义：
如：
//将int作为我们的数据类型，若有改变我们多数情况下只需改变这一行即可，即将int改为别的数据类型 typedef int DataType;
然后再来定义我们的顺序表：
//将结构体重命名，是为了方便使用 typedef struct SeqList { DataType* data; // 指向动态开辟的数组 size_t size ; // 有效数据个数 size_t capicity ; // 容量空间的大小 }SeqList;
注意到定义结构体时，我们是不能进行直接赋值的，所以我们来写一个顺序表初始化函数：
void SeqListInit(SeqList *p) { //传地址进来的时候要记得断言，要保证它不为NULL，不然会造成非法访问等错误 assert(p); // 指向动态开辟的数组 p->data = NULL; // 有效数据个数 p->size = 0; // 容量空间的大小 p->capicity = 1; }
我们在写代码的时候要记得写完一个模块我们就要测试一下，防止到最终代码写完了，一运行不知道是哪的错，所谓 “码代一时爽，bug找断肠”
所以我们来测试一下：
void SeqListTest1() { //先来定义一个顺序表变量 SeqList list; //将其地址赋值于 p，我们在修改时，要传 址 进去，这样才可以改变他的值，切不可传 值 进去！ SeqList* p =&list; //对于一个结构体我们在其定义时，是不可以直接赋值进去的 //如： //typedef struct SeqList //{ // // DataType* data = NULL; // 指向动态开辟的数组 // // size_t size = 0; // 有效数据个数 // // size_t capicity =1; // 容量空间的大小 //}SeqList; //上述代码是错误示例！！！ //所以我们要写一个初始化函数 SeqListInit(p);//传 址 进去 }
运行结果：
2.顺序表特殊位置的增加与删除
初始化完了我们就该插入数据了，首先我们先来最简单的尾插，不过我们先要来想一想，插入的时候我们是不是要先检查一下我们的数据个数是否已经等于了容量，如果这样我们就需要先扩容一下。
//扩容函数 void CheckCapacity(SeqList* p) {
assert(p); //如果容量于数据个数相同就扩容,还有一种情况p->size=0的时候也需要扩容 //1.p->size = p->capacity 的时候，这时如果我们要插入数据，容量不够，造成非法访问 //2.p->size = 0的时候，这时说明我们刚刚初始化完成，此时的p->data还是NULL，我们不能直接对于NULL进行解引用和修改 if(p->size==p->capicity||p->size==0) { //扩容扩大先前容量的两倍 DataType* ptr=(DataType*)realloc(p->data,sizeof(DataType)*(p->capicity*2)); if(ptr==NULL) { //错误提示，下面两个效果相同 //printf("REALLOC ERROR!:%s",strerror(errno)); perror("REALLOC ERROR！\n"); exit(-1); } //赋值，realloc可在原地址开辟，也可在一个新的地址开辟，我们用p原接收回来 p->data = ptr; //容量扩大两倍 p->capicity*=2; } //不需要扩容就什么也不干 }
注意：
扩容的两种情况：
1.p->size = p->capacity 的时候，这时如果我们要插入数据，容量不够，造成非法访问
2.p->size = 0的时候，这时说明我们刚刚初始化完成，此时的p->data还是NULL，我们不能直接对于NULL进行解引用和修改
尾插：
void SeqListPushBack(SeqList* p,DataType InsertData) {
assert(p); //检查是否需要扩容 CheckCapacity(p); //尾插就是在末尾插入，即p->size的位置插入数据 p->data[p->size]=InsertData; //插完之后数据个数加一 p->size++; }
当然了，我们要是想看到结果，最好将它打印一下：
void SeqListPrint(SeqList* p) {
assert(p); int i =0; for(i=0;i<p->size;i++) { printf("%d ",p->data[i]); } printf("\n"); }
测试：
SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p);
运行结果：
细心一点的朋友已经发现了，我们并没有释放这块空间，所以销毁函数：
//销毁函数 void SeqListDistory(SeqList* p) { assert(p); free(p->data); }
接下来就是头插了，我们想一想头插我们应该怎么实现，能不能像尾插那样简单——当然不能了，所以我们接下来思考的重点就是怎么样将头部的位置空出来：
void SeqListPushFront(SeqList* p,DataType InsertData) { assert(p); //检查是否需要扩容 CheckCapacity(p); //头插，我们需要先将数据从后往前移 int i =0; for(i=p->size+1;i>0;i--) { //从后往前依次挪动 p->data[i]=p->data[i-1]; } //挪完以后数据数首位置插入 p->data[0]=InsertData; //插入之后数据加一 p->size++; }
SeqListInit(p);//传 址 进去 SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListDistory(p);
运行结果：
接下来是尾删：
void SeqListPopBack(SeqList* p) { assert(p); //如果p->size=0 说明就没有数据可供删除 assert(p->size>0); //因为是尾删，所以我们可以直接让 p->size - 1即可，不需要其他操作 p->size--; }
SeqListInit(p);//传 址 进去 SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListPopBack(p); SeqListPopBack(p); SeqListPopBack(p); SeqListPrint(p); SeqListDistory(p);
运行结果：
遵循上面的规律，接下来就是头删了，同样我们来想一想它的挪动
void SeqListPopFront(SeqList* p) { assert(p); //如果p->size=0 说明就没有数据可供删除 assert(p->size>0); //头删，我们采取从前往后移 int i =0; for(i=0;i<p->size;i++) { //从前往后依次挪动 p->data[i]=p->data[i+1]; } //删除之后数据减一 p->size--; }
SeqListInit(p);//传 址 进去 SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListPopBack(p); SeqListPopBack(p); SeqListPopBack(p); SeqListPrint(p); SeqListPopFront(p); SeqListPopFront(p); SeqListPopFront(p); SeqListPrint(p); SeqListDistory(p);
运行结果：
到这特殊的增加与删除就结束了，接下来我们谈谈普通位置的添加与删除
3.顺序表普通位置的增加与删除
普通位置的增加就是添加一个位置进去，以那个位置为界，采取头插的挪法：
void SeqListInsert(SeqList*p ,int pos,DataType InsertData) { assert(p); //确保插入的位置有效 assert(pos>=0); assert(pos<=p->size); //检查容量 CheckCapacity(p); int i=0; //到 pos 位停止 for(i=p->size+1;i>pos;i--) { //从后往前移 p->data[i]=p->data[i-1]; } //在pos位插入数据 p->data[pos]=InsertData; //插入之后数据数加一 p->size++; }
void SeqListTest2() { SeqList list; SeqList* p =&list; SeqListInit(p); SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListInsert(p,0,0); SeqListInsert(p,p->size,0); SeqListInsert(p,p->size/2,0); SeqListInsert(p,p->size/2/2,0); SeqListInsert(p,p->size/2+p->size/2/2,0); SeqListPrint(p); SeqListDistory(p); }
运行结果：
普通位置的删除，方法也同头删，只需将pos设为界即可：
void SeqListErase(SeqList* p,int pos) { assert(p); //确保删除的位置有效 assert(pos>=0); assert(pos<=p->size); int i =0; for(i=pos;i<p->size;i++) { //从前往后依次挪动 p->data[i]=p->data[i+1]; } //删除之后数据减一 p->size--; }
void SeqListTest2() { SeqList list; SeqList* p =&list; SeqListInit(p); SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListInsert(p,0,0); SeqListInsert(p,p->size,0); SeqListInsert(p,p->size/2,0); SeqListInsert(p,p->size/2/2,0); SeqListInsert(p,p->size/2+p->size/2/2,0); SeqListPrint(p); SeqListErase(p,0); SeqListErase(p,p->size); SeqListErase(p,p->size/2); SeqListErase(p,p->size/2/2-1); SeqListErase(p,p->size/2/2+p->size/2); SeqListPrint(p); SeqListDistory(p); }
运行结果：
注：
到这我们可以把我们的特殊位置的增加和删除与任意位置来整合一下，这样有什么好处呢？
共用一个接口的时候，要是接口没错，那么都不会错。反之，要是一个函数错误，还得去分析是哪的错误。
所以：
void SeqListPushBack(SeqList* p,DataType InsertData) { // assert(p); // //检查是否需要扩容 // CheckCapacity(p); // //尾插就是在末尾插入，即p->size的位置插入数据 // p->data[p->size]=InsertData; // //插完之后数据个数加一 // p->size++; SeqListInsert(p,p->size,InsertData); } void SeqListPushFront(SeqList* p,DataType InsertData) { // assert(p); // //检查是否需要扩容 // CheckCapacity(p); // //头插，我们需要先将数据从后往前移 // int i =0; // for(i=p->size+1;i>0;i--) // { // //从后往前依次挪动 // p->data[i]=p->data[i-1]; // } // //挪完以后数据数首位置插入 // p->data[0]=InsertData; // //插入之后数据加一 // p->size++; SeqListInsert(p,0,InsertData); } void SeqListPopBack(SeqList* p) { // assert(p); // //如果p->size=0 说明就没有数据可供删除 // assert(p->size>0); // //因为是尾删，所以我们可以直接让 p->size - 1即可，不需要其他操作 // p->size--; SeqListErase(p,p->size); } void SeqListPopFront(SeqList* p) { // assert(p); // //如果p->size=0 说明就没有数据可供删除 // assert(p->size>0); // //头删，我们采取从前往后移 // int i =0; // for(i=0;i<p->size;i++) // { // //从前往后依次挪动 // p->data[i]=p->data[i+1]; // } // //删除之后数据减一 // p->size--; SeqListErase(p,0); }
3.顺序表的修改及查找：
对于此，我们直接可以采用遍历循环的方法进行查找及修改
修改：
void SeqListModify(SeqList* p,int pos,DataType ModifyData) { assert(p); //确保修改的位置有效 assert(pos>=0); assert(pos<=p->size); //在pos位进行修改 p->data[pos]=ModifyData; }
查找：
int SeqListFind(SeqList* p,DataType SearchData) { assert(p); int i =0; for(i=0;i<p->size;i++) { if(p->data[i]==SearchData) { //找到就返回下标 return i; } } //找不到就返回-1 return -1; }
void SeqListTest2() { SeqList list; SeqList* p =&list; SeqListInit(p); SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListInsert(p,0,0); SeqListInsert(p,p->size,0); SeqListInsert(p,p->size/2,0); SeqListInsert(p,p->size/2/2,0); SeqListInsert(p,p->size/2+p->size/2/2,0); SeqListPrint(p); SeqListErase(p,0); SeqListErase(p,p->size); SeqListErase(p,p->size/2); SeqListErase(p,p->size/2/2-1); SeqListErase(p,p->size/2/2+p->size/2); SeqListPrint(p); SeqListModify(p,0,0); SeqListModify(p,p->size,0); SeqListModify(p,4,0); SeqListModify(p,5,0); SeqListPrint(p); SeqListDistory(p); }
运行结果：
三.顺序表的一些缺点
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200， 我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
最后总代码如下：
//保证编译时只包含一次，防止重复包含 #ifndef TEST_TEST_H #define TEST_TEST_H #include <stdio.h> #include <stdlib.h> #include <errno.h> #include <string.h> #include <assert.h> //将int作为我们的数据类型，若有改变我们多数情况下只需改变这一行即可，即将int改为别的数据类型 typedef int DataType; //将结构体重命名，是为了方便使用 typedef struct SeqList { DataType* data; // 指向动态开辟的数组 size_t size ; // 有效数据个数 size_t capicity ; // 容量空间的大小 }SeqList; //顺序表初始化函数 void SeqListInit(SeqList* p); //打印内容 void SeqListPrint(SeqList* p); //销毁函数 void SeqListDistory(SeqList* p); //尾插 void SeqListPushBack(SeqList* p,DataType InsertData); //头插 void SeqListPushFront(SeqList* p,DataType InsertData); //尾删 void SeqListPopBack(SeqList* p); //头删 void SeqListPopFront(SeqList* p); //任意位置插入 void SeqListInsert(SeqList*p ,int pos,DataType InsertData); //任意位置删除 void SeqListErase(SeqList* p,int pos); //修改 void SeqListModify(SeqList* p,int pos,DataType ModifyData); #endif //TEST_TEST_H
// 强调！！！ //调试请加setbuf(stdout,NULL)!!! #include "test.h" //扩容函数 void CheckCapacity(SeqList* p) { assert(p); //如果容量于数据个数相同就扩容,还有一种情况p->size=0的时候也需要扩容 //1.p->size = p->capacity 的时候，这时如果我们要插入数据，容量不够，造成非法访问 //2.p->size = 0的时候，这时说明我们刚刚初始化完成，此时的p->data还是NULL，我们不能直接对于NULL进行解引用和修改 if(p->size==p->capicity||p->size==0) { //扩容扩大先前容量的两倍 DataType* ptr=(DataType*)realloc(p->data,sizeof(DataType)*(p->capicity*2)); if(ptr==NULL) { //错误提示，下面两个效果相同 //printf("REALLOC ERROR!:%s",strerror(errno)); perror("REALLOC ERROR！\n"); exit(-1); } //赋值，realloc可在原地址开辟，也可在一个新的地址开辟，我们用p原接收回来 p->data = ptr; //容量扩大两倍 p->capicity*=2; } //不需要扩容就什么也不干 } void SeqListPrint(SeqList* p) { assert(p); int i =0; for(i=0;i<p->size;i++) { printf("%d ",p->data[i]); } printf("\n"); } void SeqListDistory(SeqList* p) { assert(p); free(p->data); } void SeqListInit(SeqList *p) { //传地址进来的时候要记得断言，要保证它不为NULL，不然会造成非法访问等错误 assert(p); // 指向动态开辟的数组 p->data = NULL; // 有效数据个数 p->size = 0; // 容量空间的大小 p->capicity = 1; } void SeqListPushBack(SeqList* p,DataType InsertData) { // assert(p); // //检查是否需要扩容 // CheckCapacity(p); // //尾插就是在末尾插入，即p->size的位置插入数据 // p->data[p->size]=InsertData; // //插完之后数据个数加一 // p->size++; SeqListInsert(p,p->size,InsertData); } void SeqListPushFront(SeqList* p,DataType InsertData) { // assert(p); // //检查是否需要扩容 // CheckCapacity(p); // //头插，我们需要先将数据从后往前移 // int i =0; // for(i=p->size+1;i>0;i--) // { // //从后往前依次挪动 // p->data[i]=p->data[i-1]; // } // //挪完以后数据数首位置插入 // p->data[0]=InsertData; // //插入之后数据加一 // p->size++; SeqListInsert(p,0,InsertData); } void SeqListPopBack(SeqList* p) { // assert(p); // //如果p->size=0 说明就没有数据可供删除 // assert(p->size>0); // //因为是尾删，所以我们可以直接让 p->size - 1即可，不需要其他操作 // p->size--; SeqListErase(p,p->size); } void SeqListPopFront(SeqList* p) { // assert(p); // //如果p->size=0 说明就没有数据可供删除 // assert(p->size>0); // //头删，我们采取从前往后移 // int i =0; // for(i=0;i<p->size;i++) // { // //从前往后依次挪动 // p->data[i]=p->data[i+1]; // } // //删除之后数据减一 // p->size--; SeqListErase(p,0); } void SeqListInsert(SeqList*p ,int pos,DataType InsertData) { assert(p); //确保插入的位置有效 assert(pos>=0); assert(pos<=p->size); //检查容量 CheckCapacity(p); int i=0; //到 pos 位停止 for(i=p->size+1;i>pos;i--) { //从后往前移 p->data[i]=p->data[i-1]; } //在pos位插入数据 p->data[pos]=InsertData; //插入之后数据数加一 p->size++; } void SeqListErase(SeqList* p,int pos) { assert(p); //确保删除的位置有效 assert(pos>=0); assert(pos<=p->size); int i =0; for(i=pos;i<p->size;i++) { //从前往后依次挪动 p->data[i]=p->data[i+1]; } //删除之后数据减一 p->size--; } void SeqListModify(SeqList* p,int pos,DataType ModifyData) { assert(p); //确保修改的位置有效 assert(pos>=0); assert(pos<=p->size); //在pos位进行修改 p->data[pos]=ModifyData; } int SeqListFind(SeqList* p,DataType SearchData) { assert(p); int i =0; for(i=0;i<p->size;i++) { if(p->data[i]==SearchData) { //找到就返回下标 return i; } } //找不到就返回-1 return -1; }
#include "test.h" //测试一 void SeqListTest1() { //先来定义一个顺序表变量 SeqList list; //将其地址赋值于 p，我们在修改时，要传 址 进去，这样才可以改变他的值，切不可传 值 进去！ SeqList* p =&list; //对于一个结构体我们在其定义时，是不可以直接赋值进去的 //如： //typedef struct SeqList //{ // // DataType* data = NULL; // 指向动态开辟的数组 // // size_t size = 0; // 有效数据个数 // // size_t capicity =1; // 容量空间的大小 //}SeqList; //上述代码是错误示例！！！ //所以我们要写一个初始化函数 SeqListInit(p);//传 址 进去 SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListPopBack(p); SeqListPopBack(p); SeqListPopBack(p); SeqListPrint(p); SeqListPopFront(p); SeqListPopFront(p); SeqListPopFront(p); SeqListPrint(p); SeqListDistory(p); } void SeqListTest2() { SeqList list; SeqList* p =&list; SeqListInit(p); SeqListPushBack(p,1); SeqListPushBack(p,2); SeqListPushBack(p,3); SeqListPushBack(p,4); SeqListPushBack(p,5); SeqListPrint(p); SeqListPushFront(p,1); SeqListPushFront(p,2); SeqListPushFront(p,3); SeqListPushFront(p,4); SeqListPushFront(p,5); SeqListPrint(p); SeqListInsert(p,0,0); SeqListInsert(p,p->size,0); SeqListInsert(p,p->size/2,0); SeqListInsert(p,p->size/2/2,0); SeqListInsert(p,p->size/2+p->size/2/2,0); SeqListPrint(p); SeqListErase(p,0); SeqListErase(p,p->size); SeqListErase(p,p->size/2); SeqListErase(p,p->size/2/2-1); SeqListErase(p,p->size/2/2+p->size/2); SeqListPrint(p); SeqListModify(p,0,0); SeqListModify(p,p->size,0); SeqListModify(p,4,0); SeqListModify(p,5,0); SeqListPrint(p); SeqListDistory(p); } int main() { //不放在main函数里写，是为了方便测试 SeqListTest1(); SeqListTest2(); return 0; }
|--------------------------------------------------------
关于顺序表的知识到这便结束了
因笔者水平有限，若有错误，还望指正