网站建设个人工作室,旅游网站作用,wordpress作者分类,如何做360购物网站最近学校开始学习数据结构了#xff0c;没事就手搓一个顺序表。#x1f308;线性表线性表是n个具有相同特性的数据元素的有限序列#xff0c;是一种实际中广泛使用的数据结构#xff0c;常见的线性表有顺序表、链表、栈、队列、字符串。线性表在逻辑上是线性结构#xff0…最近学校开始学习数据结构了没事就手搓一个顺序表。线性表线性表是n个具有相同特性的数据元素的有限序列是一种实际中广泛使用的数据结构常见的线性表有顺序表、链表、栈、队列、字符串。线性表在逻辑上是线性结构即连续的一条直线但在物理上不一定连续线性表在物理上存储时通常以数组和链式结构的形式存储。1.1啥是顺序表顺序表是在计算机内存中以数组的形式保存的线性表线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。1.2顺序表和数组的区别两者的区别主要有1.顺序表可以实现动态增长而普通数组的长度是固定的2顺序表要求插入的数据在内存中是连续的普通数组的数据存放可以不连续。顺序表功能实现2.1初始化顺序表SLInit在实现初始化之前我们先来创建一个顺序表类型其中包括顺序表起始位置的指针容量数据个数。静态顺序表类型#define N 100
typedef int SLDateType;
//类型命名//静态顺序表--N太小可能不够用
struct Seqlist
{//int a[N];//以后我不想用int类型的a[]SLDateType a[N];int sz;
};这个的致命缺点就是如果说存储的数据多而N小的话就不行了一般写线性表都是用动态版的。动态顺序表类型#define N 100
typedef int SLDateType;typedef struct SeqList
{SLDateType* a; //记录顺序表的起始位置int capacity; //顺序表的容量int size; //记录顺序表中的数据个数
}SL;typedef为C语言的关键字作用是为一种数据类型定义一个新名字 初始化函数SLInit()void SLInit(SL* ps)
{assert(ps); //判断是否为空如果是空就不再进行了ps-a NULL; //指针赋值为空ps-capacity ps-size 0; //整形赋值为0
}上面的SL* ps之所以用到指针就是因为在进行初始化的时候需要将模板也一并改掉。所以用指针找到原来的地址来改变模板。2.2销毁顺序表SLDestory()因为顺序表所用的内存空间是动态开辟在堆区的所以我们在使用完后需要及时对其进行释放避免造成内存泄漏。void SLDestory(SL* ps)
{assert(ps); //断言如果顺序表是空就不在销毁了free(ps-a); //这一步最为关键 ,把指针释放掉ps-a NULL; //指针赋值为空ps-capacity ps-size 0; //整形赋值为0
}其实销毁和初始化基本大差不差最关键的一点就是销毁时有一个free来释放指针。assert的好处我们在其中运用到了assert函数它包含在assert.h头文件中。assert的好处就是判空如果一个顺序表是空的那就不需要进行初始化和销毁如果调用这两个函数就直接报错。可以让我们更快的找到漏洞。2.3打印顺序表SLPrint()需要打印的个数就是size的大小然后一个for循环就可以了。void SLPrint(SL* ps)
{assert(ps ! NULL);for (int i 0; i ps-size; i){printf(%d-, ps-a[i]);}printf(\n);
}2.4顺序表的容量检查SLCheckCapacity检查顺序表的容量是否够用是顺序表的一个很关键的问题。其实检查容量的大小很好检查的只要判断size和capacity的大小就可以了。如果capacitysize,就说明顺序表还没有存满。如果capacitysize,就说明需要扩容了。void SLCheckCapacity(SL* ps)
{if (ps-capacity ps-size) //需要扩容了{ //先扩容int newCapacity ps-capacity 0 ? 4 : 2 *ps-capacity; //1//再让指针指向这块空间SLDateType* tmp (SLDateType*)realloc(ps-a, newCapacity * sizeof(SLDateType));if (tmp NULL) {//如果扩容后的容量还是空直接报错printf(realloc fail\n);exit(-1);} ps-a tmp; //3ps-capacity newCapacity;}
}这里面1中的代码可能有些不好理解它的意思是如果说capacity是0的话就给他4个空间如果不是0就把它的空间扩大2倍然后复制给newCapacity。2中的代码是新建一个指针这个指针的目的是让原来的指针指向新开辟的空间。接下来就该实现重点功能了。顺序表的增删实现3.尾插功能SLPushBack()尾插就是在顺序表的表尾插入数据所以第一步是先判断顺序表的容量大小。容量不够就扩容。//尾插
void SLPushBack(SL* ps, SLDateType x)
{//检查容量空间SLCheckCapacity(ps);ps-a[ps-size] x;ps-size;
}之所以有两个参数这两个参数中参数1代表的是顺序表参数2代表的是要插入的数。4.头插功能SLPushFront()要想在顺序表的表头插入数据那么就需要先将顺序表原有的数据从后往前依次向后挪动一位最后再将数据插入表头。头插成功的前提是顺序表还有空间可供插入。所以第一步就是检查容量。容量够就进行插入操作。//头插
void SLPushFront(SL* ps, SLDateType x)
{//检查容量SLCheckCapacity(ps);int end ps-size - 1; //size-1代表的就是顺序表存储的最后一个数while (end 0){ps-a[end 1] ps-a[end];--end;}ps-a[0] x;ps-size;
}就是把顺序表往后挪一位然后把第一位插入x就行了。5.尾删功能SLPopBack()尾删就是把最末尾数据给干掉但是其实仔细想一下直接把顺序表元素个数-1就行了。//尾删
void SLPopBack(SL* ps)
{assert(ps-size 0);//顺序表不为空才可以进行尾删否则直接报错ps-size--;
}6.头删功能SLPopFront()头删功能和头插正好相反头删是往前覆盖。//头删
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--; //数据减少一个
}出现多删情况如果说把顺序表删成空后还继续删除那会出现啥情况这个就会报错之所以能检查出来错误就是上面咱们写的断言判断出来的。其实这几种情况用到的不很多最多的就是任意位置的插入删除操作。任意位置的插入删除7.任意位置pos插入这个pos是位置英文的缩写在任意位置我们首先就要指定位置pos.所以又加入一个形参。然后后移pos后面的数据。对于这个插入来说我们要进行两次断言首先·顺序表不为空其次指定的位置在顺序表中不能小于0不能大于size。接下来就是往后移动。//某位置插入
void SLInsert(SL * ps, int pos, SLDateType x)
{//先防止越界SLCheckCapacity(ps);assert(ps);assert(pos 0 pos ps-size);//加上可实现尾插int end ps-size - 1;//从后往前while (end pos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-size;
}8.任意位置pos删除这个跟前面的没事两样就是加一个形参pos然后把pos以后的数往前移动。//某位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);//不能等于int begin pos;for (begin pos; begin ps-size - 1; begin){ps-a[begin] ps-a[begin 1];}ps-size--;
}查改功能的实现写到这一步顺序表基本就写完了只剩下几个功能了。9.查找功能实现SLfind()要想实现查找功能还需要两个形参但是第二个形参是操作者查找的对象比如我要去顺序表中查找2那第二个形参就是2。如果找到就返回该数字没找到返回-1.//查找
int SLFind(SL* ps, SLDateType x)
{assert(ps);for (int i 0; i ps-size; i){if (ps-a[i] x)return i;}return -1;//没找到
}10.修改功能SLModify()//修改
int SLModify(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos 0 pos ps-size);ps-a[pos] x;
}这里直接在pos位置上修改就行了。总结到这顺序表的大致功能函数就解决完了但是还是要说一个问题--》为啥第一个参数要用指针形参是实参的一份临时拷贝修改功能函数里的形参并不会改变实参的任何数据。就好比你去复印户口簿复印完发现复印件的地址错了你如果说你只改复印件上的那下一次复印地址还是错的。所以必须要通过复印件连着户口本上的一起改成正确地址才行。这个用指针就是上面的意思要想改变顺序表中的数据就要通过指针把顺序表上的内容一起改变。上面的打印函数就可以不要指针但是为了更准确和一致把它也带上把。
