脚本宝典收集整理的这篇文章主要介绍了【零基础学会数据结构】--顺序表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完
成数据的增删查改。
静态顺序表的本质其实就是数组,其缺点就是空间有限,容纳的数据量有限。
#define max 100
struct Seqlist{
int arr[max];
int size;
}
函数接口:函数接口就是专门进行某一功能的函数,如顺序表的数据的尾部插入,数据的头部插入,顺序表的初始
化.....这一系列的函数都称为函数接口,有了函数接口以后,每个函数的功能变的独立,也易于程序员进行调
试操作。
顾名思义,动态顺序表就是在静态顺序表的基础上做了升级,动态顺序表可以动态的对内存空间进行扩容,可以
存储更多的数据。
#pragma once
#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int Seqlistdata;
typedef struct Seqlist {
Seqlistdata* a;
Seqlistdata size;
Seqlistdata capacity;
}SL;
void Seqlistinit(SL* ps);//顺序表的初始化
void Seqlistpushback(SL* ps, Seqlistdata x);//顺序表的尾插
void Seqlistpopback(SL* ps);//顺序表的尾删
void Seqlistpushfront(SL* ps, Seqlistdata x);//顺序表的头插
void Seqlistpopfront(SL* ps);//顺序表的头删
void Seqcheckcapacity(SL* ps); //顺序表的扩容
void Seqlistprint(SL* ps); //顺序表的打印
void Seqlistdelete(SL* ps); //顺序表的销毁
void Seqlistinsert(SL* ps, int x, int y);//顺序表的指定位置插入
int Seqlistfind(SL* ps, Seqlistdata x);//顺序表里的数据查找
void Seqlisterase(SL* ps, int x);//顺序表的指定下标位置删除
#include"seqlist.h"
void Seqlistinit(SL* ps) {//顺序表的初始化
ps->a = NULL;
ps->capacity = ps->size = 0;
}
void Seqcheckcapacity(SL* ps) {//顺序表的扩容
if (ps->size == ps->capacity) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
Seqlistdata* tmp = (Seqlistdata*)realloc(ps->a, newcapacity * sizeof(Seqlistdata));
if (tmp == NULL) {
printf("tmp failed");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
void Seqlistpushback(SL* ps, Seqlistdata x) {//顺序表的尾插
Seqcheckcapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
void Seqlistpopback(SL* ps) {//顺序表的尾删
assert(ps->size > 0);
ps->size--;
}
void Seqlistprint(SL* ps) {//顺序表的打印
for (int i = 0; i < ps->size; i++)
printf("%d", ps->a[i]);
}
void Seqlistpushfront(SL* ps, Seqlistdata x) { //顺序表的头插
Seqcheckcapacity(ps);
int end = ps->size;
while (end) {
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[0] = x;
ps->size++;
}
void Seqlistpopfront(SL* ps) {//顺序表的头删
for (int i = 0; i < ps->size; i++) {
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
void Seqlistdelete(SL* ps) {//顺序表的销毁
ps->capacity = 0;
ps->size = 0;
free(ps->a);
ps->a = NULL;
}
int Seqlistfind(SL* ps, Seqlistdata x) {//顺序表里的数据查找
for (int i = 0; i < ps->size; i++) {
if (ps->a[i] == x)
return i;
}
return -1;
}
void Seqlistinsert(SL* ps, int x,int y)顺序表的指定位置插入
{
int end = ps->size;
while (end - x) {
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[x] =y;
ps->size++;
}
void Seqlisterase(SL* ps, int x) {//顺序表的指定下标位置删除
assert(x>= 0 && x < ps->size);
int begin = x + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}
#include "SeqList.h"
#include<stdio.h>
void test03() {
SL sll;
Seqlistinit(&sll);
Seqlistpushback(&sll, 3);
Seqlistpushback(&sll, 4);
Seqlistinsert(&sll, 1, 4);
Seqlistpushfront(&sll, 8);
Seqlistpopfront(&sll);
Seqlistprint(&sll);
}
int main(){
test03();
}
typedef struct Seqlist {
Seqlistdata* a;
Seqlistdata size;
Seqlistdata capacity;
}SL;
一个顺序表的作用就是用来存储数据,这时就要用到结构体,在这个结构体中定义了三个变量
1. 结构体指针a,结构体指针a用来存储结构体的地址
2.结构体的容量大小capacity,即这个结构体可以最多存储的数据的个数。
3.结构体的使用容量size,当前结构体已经存储的数据的个数。
void Seqlistinit(SL* ps) {//顺序表的初始化
ps->a = NULL;
ps->capacity = ps->size = 0;
}
结构体的初始化需要完成三个操作。
1.将结构指针置为空指针。
2.将结构体的初始容量置为0。
3.将结构体的使用容量置为0。
void Seqcheckcapacity(SL* ps) {//顺序表的扩容
if (ps->size == ps->capacity) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
Seqlistdata* tmp = (Seqlistdata*)realloc(ps->a, newcapacity * sizeof(Seqlistdata));
if (tmp == NULL) {
printf("tmp failed");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
在对顺序表进行存储数据的时候,因为容量有限,所以为了存储更多的数据,所以需要对顺序表的空间大小进行
扩容(即申请一块更大的空间)
进行顺序表的扩容有以下几个操作
1.判断顺序表的容量是否全部用完。方法:比较使用容量size和顺序表容量capacity的大小,当使用容量size
==顺序表容量capacity时,这时有两种情况。
情况一:顺序表的使用容量===顺序表容量!=0,意味着顺序表的容量已经用完.
情况二:顺序表的使用容量==顺序表的容量==0,意味着顺序表的容量为0.
所以还需要进行顺序表初始容量的判断。这时进行判断顺序表的容量是否等于0,如果等于0,就申请4个大小的
容量,反之将其容量扩大两倍。
2.在确立了顺序表的容量大小以后,就需要进行第二步操作,为顺序表的容量大小申请一块内存空间,这时使用
到realloc函数,并且还需要判断新空间的申请是否成功。
3.最后一步操作,也是非常关键的一步操作,将申请的容量赋值给capacity,将新空间的地址赋值给结构体指针
a。
void Seqlistpushback(SL* ps, Seqlistdata x) {//顺序表的尾插
Seqcheckcapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
在对顺序表的进行尾部插入的时候有以下几个操作:
1.对顺序表进行尾部操作之前需要先对顺序表进行扩容,防止顺序表的容量不够。
2.将数据插入到顺序表的尾部,再将顺序表的使用容量进行自增的操作。
void Seqlistpopback(SL* ps) {//顺序表的尾删
assert(ps->size > 0);
ps->size--;
}
顺序表的尾部删除具有以下几个操作:
1.判断顺序表的使用容量,只有当顺序表的使用容量大于0时,才能执行顺序表的尾部删除。
2.在判断条件成立的情况下将顺序表的使用容量进行自减操作。
void Seqlistpushfront(SL* ps, Seqlistdata x) { //顺序表的头插
Seqcheckcapacity(ps);
int end = ps->size;
while (end) {
ps->a[end] = ps->a[end - 1];
end--;
}
ps->a[0] = x;
ps->size++;
}
顺序表的头部插入具有以下几个操作
1.将后面的数据进行向后移位操作,这时需要注意的是,移位操作必须从最后一个开始。如图所示
2.将数据插入到头部,使用容量进行自增
void Seqlistpopfront(SL* ps) {//顺序表的头删
assert(ps->size>0)
for (int i = 0; i < ps->size; i++) {
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
顺序表的头删具有以下几个操作
1.判断顺序表的使用容量是否大于0,如果大于0将顺序表后面的数据进行向前移位操作,这时需要从第二个数字开始移位。如图所示
2.将顺序表的使用容量进行自减的操作。
void Seqlistprint(SL* ps) {//顺序表的打印
for (int i = 0; i < ps->size; i++)
printf("%d", ps->a[i]);
}
这个函数接口的功能不难理解,观察代码即可.
void Seqlistdelete(SL* ps) {//顺序表的销毁
ps->capacity = 0;
ps->size = 0;
free(ps->a);
ps->a = NULL;
}
顺序表的销毁具有以下几个操作:
1.将顺序表所占的内存空间进行释放。
2.将结构体指针置为空。
3.将使用容量和顺序表容量置为0。
顺序表在进行一系列的操作的时候,只需要得知顺序表的首地址即可以,所以顺序表函数接口的形参都应该接收
一个结构体指针,实参传递的也都是一个结构体指针,顺序表使用这个结构体指针的下标就可以访问到顺序表里
的所有元素。并进行相应的操作。传参的这一步操作需要自己进行理解。
剩下的几个顺序表的函数接口大都是在前面的几个接口的基础上进行了升级,不做过多的赘述,留给大家自行实
现。
重要的事说三遍!!!!!
一定要理清楚顺序表中每个参数的设置原因,函数参数的传递原因,并且多动手实现,相信你一定可以敲出一个
完美的顺序表.
以上是脚本宝典为你收集整理的【零基础学会数据结构】--顺序表全部内容,希望文章能够帮你解决【零基础学会数据结构】--顺序表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。