目录
1.介绍顺序表
2.初始化
3.插入
4.删除
5.获取长度
6.按位置获取元素和查找指定元素的位置
7.完整代码
8.小问题
1.介绍顺序表
前面我们说到,既然数组无法实现这样的高级表结构,那么我就基于数组,对其进行强化,也就是说,我们存放数据还是使用数组,但是我们可以为其编写一些额外的操作来强化为线性表,像这样底层依然采用顺序存储实现的线性表,我们称为顺序表。
这里我们可以先定义一个新的结构体类型,将一些需要用到的数据保存在一起,这里我们以类型的线性表为例:int
typedef int E; //这里我们的元素类型就用int为例吧,先起个别名 struct List { E array[10]; //实现顺序表的底层数组 int capacity; //表示底层数组的容量 };
为了一会使用方便,我们可以给其起一个别名:
typedef struct List * ArrayList; //因为是数组实现,所以就叫ArrayList //这里直接将List的指针起别名
2.初始化
然后我们就可以开始编写第一个初始化操作了:
void initList(ArrayList list){ list->capacity = 10; //直接将数组的容量设定为10即可 }
但是我们发现一个问题,这样的话我们的顺序表长度不就是固定为10的了吗?而前面我们线性表要求的是长度是动态增长的,那么这个时候怎么办呢?我们可以直接使用一个指针来指向底层数组的内存区域,当装不下的时候,我们可以创建一个新的更大的内存空间来存放数据,这样就可以实现扩容了,所以我们来修改一下:
struct List { E * array; //指向顺序表的底层数组 int capacity; //数组的容量 };
接着我们修改一下初始化函数:
void initList(ArrayList list){ //这里就默认所有的顺序表初始大小都为10吧,随意 list->array = malloc(sizeof(E) * 10); //使用malloc函数申请10个int大小的内存空间 //作为底层数组使用 list->capacity = 10; //容量同样设定为10 }
但是还没完,因为我们的表里面,默认情况下是没有任何元素的,我们还需要一个变量来表示当前表中的元素数量:
struct List { E * array; //指向顺序表的底层数组 int capacity; //数组的容量 int size; //表中的元素数量 }; typedef struct List * ArrayList; void initList(ArrayList list){ //这里就默认所有的顺序表初始大小都为10吧,随意 list->array = malloc(sizeof(int) * 10);//使用malloc函数申请10个int大小的内存空间 //作为底层数组使用 list->capacity = 10; //容量同样设定为10 list->size = 0; //元素数量默认为0 }
还有一种情况我们需要考虑,也就是说如果申请内存空间失败,那么需要返回一个结果告诉调用者:
_Bool initList(ArrayList list){ list->array = malloc(sizeof(int) * 10); if(list->array == NULL) return 0;//需要判断如果申请的结果为NULL的话 list->capacity = 10; //表示内存空间申请失败 list->size = 0; return 1; //正常情况下返回true也就是1 }
这样,一个比较简单的顺序表就定义好,我们可以通过函数对其进行初始化:initList
int main() { struct List list; //创建新的结构体变量 if(initList(&list)){ //对其进行初始化,如果失败就直接结束 ... } else{ printf("顺序表初始化失败,无法启动程序!"); } }
3.插入
接着我们来编写一下插入和删除操作,也是比较难以理解的操作:
我们先设计好对应的函数:
void insertList(ArrayList list, E element, int index){ //list就是待操作的表,element就是需要插入的元素, //index就是插入的位置 //(注意顺序表的index是按位序计算的,从1开始,一般都是第index个元素) }
我们按照上面的思路来编写一下代码:
void insertList(ArrayList list, E element, int index){ for (int i = list->size; i > index - 1; i--) //先使用for循环将待插入位置 //后续的元素全部丢到后一位 list->array[i] = list->array[i - 1]; list->array[index - 1] = element;//挪完之后,位置就腾出来了,直接设定即可 list->size++; //别忘了插入之后相当于多了一个元素,记得size + 1 }
现在我们可以来测试一下了:
void printList(ArrayList list){ //编写一个函数用于打印表当前的数据 for (int i = 0; i size; ++i) //表里面每个元素都拿出来打印一次 printf("%d ", list->array[i]); printf("n"); } int main() { struct List list; if(initList(&list)){ insertList(&list, 666, 1); //每次插入操作后都打印一下表,看看当前的情况 printList(&list); //运行结果 666 insertList(&list, 777, 1); printList(&list); //运行结果 777 666 insertList(&list, 888, 2); printList(&list); //运行结果 777 888 666 } else{ printf("顺序表初始化失败,无法启动程序!"); } }
我们需要检查一下插入的位置是否合法:
转换成位序,也就是[1, size + 1]这个闭区间,所以我们在一开始的时候进行判断:
_Bool insertList(ArrayList list, E element, int index){ if(index list->size + 1) return 0;//如果在非法位置插入, //返回0表示插入操作执行失败 for (int i = list->size; i > index - 1; i--) list->array[i] = list->array[i - 1]; list->array[index - 1] = element; list->size++; return 1; //正常情况返回1 }
再来测试一下:
if(insertList(&list, 666, -1)){ printList(&list); } else{ printf("插入失败!");//运行结果 插入失败! }
不过我们还是没有考虑到一个情况,那么就是如果我们的表已经装满了,也就是说size已经达到申请的内存空间最大的大小了,那么此时我们就需要考虑进行扩容了,否则就没办法插入新的元素了:
_Bool i服务器托管网nsertList(ArrayList list, E element, int index){ if(index list->size + 1) return 0; if(list->size == list->capacity) { //如果size已经到达最大的容量了, //肯定是插不进了,那么此时就需要扩容了 int newCapacity = list->capacity + (list->capacity >> 1); //我们先计算一下新的容量大小,这里我取1.5倍原长度,当然你们也可以想扩多少扩多少 E * newArray = realloc(list->array, sizeof(E) * newCapacity); //这里我们使用新的函数realloc重新申请更大的内存空间 if(newArray == NULL) return 0; //如果申请失败,那么就确实没办法插入了,只能返回0表示插入失败了 list->array = newArray; list->capacity = newCapacity; } for (int i = list->size; i > index - 1; i--) list->array[i] = list->array[i - 1]; list->array[index - 1] = element; list->size++; return 1; }
realloc函数可以做到控制动态内存开辟的大小,重新申请的内存空间大小就是我们指定的新的大小,并且原有的数据也会放到新申请的空间中,所以非常方便。当然,如果因为内存不足之类的原因导致内存空间申请失败,那么会返回NULL,所以别忘了进行判断。
这样,我们的插入操作就编写完善了,我们可以来测试一下:
int main() { struct List list; if(initList(&list)){ for (int i = 0; i
4.删除
这样,我们就完成了顺序表的插入操作,接着我们来编写一下删除操作,其实删除操作也比较类似,也需要对元素进行批量移动,但是我们不需要考虑扩容问题,我们先设计好函数:
void deleteList(ArrayList list, int index){ //list就是待操作的表,index是要删除的元素位序 }
按照我们上面插入的思路,我们反过来想一想然后实现删除呢?首先是删除的范围:
换算成位序就是[1, size]这个闭区间内容,所以我们先来限定一下合法范围:
_Bool deleteList(ArrayList list, int index){ if(index list->size) return 0; return 1; //正常情况返回1 }
接着就是删除元素之后,我们还需要做什么呢?我们应该将删除的这个元素后面的全部元素前移一位:
我们按照这个思路,来编写一下删除操作:
_Bool deleteList(ArrayList list, int index){ if(index list->size) return 0; for (int i = index - 1; i size - 1; ++i) list->array[i] = list->array[i + 1];//实际上只需要依次把后面的元素覆盖到前一个即可 list->size--; //最后别忘了size - 1 return 1; }
删除相比插入要简单一些,我们来测试一下吧:
for (int i = 0; i
5.获取长度
int sizeList(ArrayList list){
return list->size; //直接返回size就完事
}
6.按位置获取元素和查找指定元素的位置
E * getList(ArrayList list, int index){
if(index list->size) return NULL;//如果超出范围就返回NULL
return &list->array[index - 1];
}
int findList(ArrayList list, E element){
for (int i = 0; i size; ++i) { //一直遍历,如果找到那就返回位序
if(list->array[i] == element) return i + 1;
}
return -1; //如果遍历完了都没找到,那么就返回-1
}
7.完整代码
#include
#include
typedef int E;
struct List {
E * array;
int capacity;
int size;
};
typedef struct List * ArrayList;
_Bool initList(ArrayList list){
list->array = malloc(sizeof(E) * 10);
if(list->array == NULL) return 0;
list->capacity = 10;
list->size = 0;
return 1;
}
_Bool insertList(ArrayList list, E element, int index){
if(index list->size + 1) return 0;
if(list->size == list->capacity) {
int newCapacity = list->capacity + (list->capacity >> 1);
E * newArray = realloc(list->array, newCapacity * sizeof(E));
if(newArray == NULL) return 0;
list->array = newArray;
list->capacity = newCapacity;
}
for (int i = list->size; i > index - 1; --i)
list->array[i] = list->array[i - 1];
list->array[index - 1] = element;
list->size++;
return 1;
}
_Bool deleteList(ArrayList list, int index){
if(index list->size) return 0;
for (int i = index - 1; i size - 1; ++i)
list->array[i] = list->array[i + 1];
list->size--;
return 1;
}
int sizeList(ArrayList list){
return list->size;
}
E * getList(ArrayList list, int index){
if(index list->size) return NULL;
return &list->array[index - 1];
}
int findList(ArrayList list, E element){
for (int i = 0; i size; ++i) {
if(list->array[i] == element) return i + 1;
}
return -1;
}
8.小问题
问题:请问顺序实现的线性表,插入、删除、获取元素操作的时间复杂度为?
- 插入:因为要将后续所有元素都向后移动,所以平均时间复杂度为O(n)
- 删除:同上,因为要将所有元素向前移动,所以平均时间复杂度为O(n)
- 获取元素:因为可以利用数组特性直接通过下标访问到对应元素,时间复杂度为O(1)
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net