网站建设售后回访话术,dede产品展示网站模板,中国建设银行官网站额度申请,淮安做网站的有多少目录 一. 数据结构相关概念
二、线性表
三、顺序表概念及结构
3.1顺序表一般可以分为#xff1a;
3.2 接口实现#xff1a;
四、基本操作实现
4.1顺序表初始化
4.2检查空间#xff0c;如果满了#xff0c;进行增容编辑
4.3顺序表打印
4.4顺序表销毁
4.5顺…目录 一. 数据结构相关概念
二、线性表
三、顺序表概念及结构
3.1顺序表一般可以分为
3.2 接口实现
四、基本操作实现
4.1顺序表初始化
4.2检查空间如果满了进行增容编辑
4.3顺序表打印
4.4顺序表销毁
4.5顺序表尾插
4.6顺序表头插
4.7顺序表头删
4.8顺序表尾删
4.9顺序表在pos位置插入x
4.10顺序表删除pos位置的值 链表相关知识:
链表基础知识二、双向链表头插、尾插、头删、尾删、查找、删除、插入-CSDN博客
链表基础知识一、单链表、头插、尾插、头删、尾删、查找、删除、插入-CSDN博客
一. 数据结构相关概念
什么是数据结构
数据结构是由“数据”和“结构”两词组合而来。 什么是数据常见的数值1、2、3、4.....、教务系统里保存的用户信息姓名、性别、年龄、学历等等、网页里肉眼可以看到的信息文字、图片、视频等等这些都是数据什么是结构 当我们想要使用大量使用同一类型的数据时通过手动定义大量的独立的变量对于程序来说可读性非常差我们可以借助数组这样的数据结构将大量的数据组织在一起结构也可以理解为组织数据的方式。 概念数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系 的数据元素的集合。数据结构反映数据的内部构成即数据由那部分构成以什么方式构成以及数据元素之间呈现的结构。 总结 1能够存储数据如顺序表、链表等结构 2存储的数据能够方便查找 2、为什么需要数据结构
通过数据结构能够有效将数据组织和管理在一起。按照我们的方式任意对数据进行增删改查等操 作。最基础的数据结构数组。 【思考】有了数组为什么还要学习其他的数据结构 假定数组有10个空间已经使用了5个向数组中插入数据步骤 求数组的长度求数组的有效数据个数向下标为数据有效个数的位置插入数据注意这里是 否要判断数组是否满了满了还能继续插入吗.....假设数据量非常庞大频繁的获取数组有效数据个数会影响程序执行效率。 结论最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。
二、线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 三、顺序表概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表和数组的区别 顺序表的底层结构是数组对数组的封装实现了常用的增删改查等接口 3.1顺序表一般可以分为 静态顺序表使用定长数组存储。
// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{SLDataType array[N]; // 定长数组size_t size; // 有效数据的个数
}SeqList; 动态顺序表使用动态开辟的数组存储。
// 顺序表的动态存储
typedef struct SeqList
2.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大
了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态
的分配空间大小所以下面我们实现动态顺序表。
{SLDataType* array; // 指向动态开辟的数组size_t size ; // 有效数据个数size_t capicity ; // 容量空间的大小
}SeqList;3.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大 了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态 的分配空间大小所以下面我们实现动态顺序表。
先解释一下预处理指令 #pragma once这是一个非标准的预处理指令它告诉预处理器这个头文件只应该被包含一次。如果尝试多次包含预处理器会忽略后续的包含。尽管它是非标准的但许多现代编译器如GCC和Clang都支持它。 #ifndef SEQLIST_H这是一个条件编译指令。它检查是否定义了一个名为SEQLIST_H的宏。如果没有定义即这个头文件还没有被包含过那么接下来的代码会被编译。 #define SEQLIST_H这定义了一个名为SEQLIST_H的宏。当这个头文件首次被包含时这个宏会被定义从而标记这个头文件已经被包含过了。 #endif这结束了之前的#ifndef条件编译块。
SeqList.h
//#pragma once
#ifndef _SEQLIST_H_
#define _SEQLIST_H_#includestdio.h
#includestring.h
#includestdlib.h#includeassert.h//增强程序的可维护性
#define MAX_SIZE 10
typedef int SQDataType;
//静态顺序表
//问题:给少了不够用,给多了用不完浪费,不能灵活控制//typedef struct SeqList
//{
// SQDataType a[MAX_SIZE];
// int size;
//}SL;typedef struct SeqList
{SQDataType *a;// 指向动态开辟的数组int size; //有效的数据的个数int capacity;//容量
}SL;//typedef struct SeqList SL;//定义为简写// 基本增删查改接口
// 顺序表初始化//增删查改等接口函数
//void SeqListInit(struct SeqList s);//顺序表初始化
void SeqListInint(SL* ps);
// 检查空间如果满了进行增容
void CheckCapacity(SeqList * psl);
//顺序表打印
void SeqListPrint(SL* ps);
// 顺序表销毁
void SeqListDestory(SL* ps);
//顺序表尾插
void SeqListPushBack(SL* ps, SQDataType x);
//顺序表头插
void SeqListPushFront(SL* ps, SQDataType x);
//顺序表头删
void SeqListPopBack(SL* ps);
//顺序表尾删
void SeqListPopFront(SL* ps);// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SQDataType x);// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);#endif四、基本操作实现
4.1顺序表初始化
void SeqListInit(SL* ps)
{ps-a NULL;ps-size 0;ps-capacity 0;
}
4.2检查空间如果满了进行增容 这个函数的主要目的是在顺序列表满时自动扩容以便能够继续添加元素。它首先检查列表是否已满然后计算新的容量并使用realloc函数尝试调整数组的大小。如果realloc失败返回NULL则打印错误信息并退出程序。如果成功就更新列表的数组指针和容量。
// 函数定义传入一个指向顺序列表SeqList的指针
void SeqListCheckCapacity(SL* ps)
{ // 检查顺序列表是否已满即当前大小size是否等于容量capacity if (ps-size ps-capacity) { // 如果满了计算新的容量。如果当前容量为0则新容量为4否则新容量为当前容量的2倍 int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2; // 使用realloc函数尝试调整顺序列表的数组大小 // realloc可能会改变原有内存块的位置因此需要使用一个临时指针来接收结果 SQDataType* tmp (SQDataType*)realloc(ps-a, newcapacity * sizeof(SQDataType)); // 检查realloc是否成功 if (tmp NULL) { // 如果失败打印错误信息并退出程序 printf(realloc fail\n); exit(-1); } else { // 如果成功更新顺序列表的数组指针和容量 ps-a tmp; ps-capacity newcapacity; } }
}
4.3顺序表打印
这个函数的主要目的是遍历顺序列表并打印出其中的每一个元素。通过循环它会依次访问列表中的每个元素并将其打印。
// 打印顺序列表中的所有元素
void SeqListPrint(SL* ps)
{ // 通过循环遍历顺序列表中的每一个元素 for (int i 0; i ps-size; i) { printf(%d , ps-a[i]); } // 打印一个换行符使得每次打印列表后都会换行输出更清晰 printf(\n);
}
4.4顺序表销毁 SeqListDestroy函数主要目的是释放顺序列表所占用的内存空间
// 销毁顺序列表的函数
void SeqListDestroy(SL* ps)
{ // 断言确保传入的顺序列表指针ps不为空 assert(ps); // 判断顺序列表的数组指针a是否不为空 if (ps-a ! NULL) { // 释放数组指针a所指向的内存空间 free(ps-a); // 将数组指针a设置为NULL避免野指针 ps-a NULL; // 将顺序列表的大小设置为0表示列表已空 ps-size 0; // 将顺序列表的容量设置为0表示已没有分配内存空间 ps-capacity 0; }
}
4.5顺序表尾插
在插入新元素之前它们都首先检查当前的容量是否足够如果不够则调用 SeqListCheckCapacity 函数进行扩容。尾插函数SeqListPushBack直接在末尾添加新元素
// 尾插法在顺序列表的末尾插入一个新元素
void SeqListPushBack(SL* ps, SQDataType x)
{ // 检查当前顺序列表的容量是否足够如果不够则进行扩容 SeqListCheckCapacity(ps); // 在顺序列表的当前末尾位置插入新元素 ps-a[ps-size] x; // 更新顺序列表的大小元素数量 ps-size;
}
4.6顺序表头插
在插入新元素之前它们都首先检查当前的容量是否足够如果不够则调用 SeqListCheckCapacity 函数进行扩容。头插函数SeqListPushFront将现有元素向后移动以腾出空间。 // 头插法在顺序列表的开头插入一个新元素
void SeqListPushFront(SL* ps, SQDataType x)
{ // 检查当前顺序列表的容量是否足够如果不够则进行扩容 SeqListCheckCapacity(ps); // 初始化设定一个变量来追踪当前需要移动的元素的位置 // 结束条件当所有元素都已移动到它们的新位置时停止 // 迭代过程从列表的末尾开始将每个元素向后移动一个位置以腾出空间 int end ps-size - 1; // 从列表的最后一个元素开始 while (end 0) // 当还有元素需要移动时继续循环 { // 将当前位置的元素向后移动一个位置 ps-a[end 1] ps-a[end]; --end; // 移动到前一个元素 } // 在顺序列表的开头现在为空插入新元素 ps-a[0] x; // 更新顺序列表的大小元素数量 ps-size;
}
4.7顺序表头删 SeqListPopFront函数用于删除顺序列表的第一个元素。它首先通过断言确保列表不为空然后通过一个循环将第一个位置之后的所有元素都向前移动一个位置从而覆盖掉第一个位置的元素并更新列表的大小。
// 头删删除顺序列表的第一个元素
void SeqListPopFront(SL* ps)
{ // 断言确保顺序列表不为空即其大小大于0 // 如果ps-size 0则触发断言错误终止程序 assert(ps-size 0); // 初始化一个变量start用于从第二个元素开始遍历 int start 1; // 当start小于列表大小时执行循环 // 这个循环用于将第一个位置之后的元素都向前移动一个位置从而覆盖掉第一个位置的元素 while (start ps-size) { // 将下一个位置的元素移动到当前位置 ps-a[start - 1] ps-a[start]; // start向后移动一个位置继续处理下一个元素 start; } // 因为第一个元素已经被覆盖所以不需要额外处理 // 更新顺序列表的大小元素数量因为删除了一个元素所以大小减1 ps-size--;
}
4.8顺序表尾删 SeqListPopBack函数用于删除顺序列表的最后一个元素。它首先通过断言确保列表不为空然后直接更新列表的大小。
// 尾删删除顺序列表的最后一个元素
void SeqListPopBack(SL* ps)
{ // 断言确保顺序列表不为空即其大小大于0 // 如果ps-size 0则触发断言错误终止程序 assert(ps-size 0); // 可以选择将最后一个元素的值设置为0或其他默认值以确保不留下未定义的值 // 但这取决于具体的应用需求有时可能不需要这样做 //ps-a[ps-size - 1] 0; // 更新顺序列表的大小元素数量因为删除了一个元素所以大小减1 ps-size--;
}
4.9顺序表在pos位置插入x SeqListInsert函数的主要作用是在顺序列表的指定位置pos插入一个新元素x。为了达到这个目的它首先确保插入的位置是有效的不会超出当前列表的大小然后检查是否需要扩容。接着它通过一个循环将pos位置及其之后的元素都向后移动一个位置以便为新元素腾出空间。最后它在pos位置插入新元素并更新列表的大小。 // 在顺序列表的指定位置插入一个元素
void SeqListInsert(SL* ps, int pos, SQDataType x)
{ // 断言确保插入的位置不会超出当前列表的大小 // 如果pos ps-size则触发断言错误终止程序 assert(pos ps-size); // 检查当前顺序列表的容量是否足够如果不够则进行扩容 SeqListCheckCapacity(ps); // 初始化一个变量end用于从列表的末尾开始遍历 int end ps-size - 1; // 当end位置大于或等于要插入的位置pos时执行循环 // 这个循环用于将pos位置及其之后的元素都向后移动一个位置为插入新元素腾出空间 while (end pos) { // 将当前位置的元素向后移动一个位置 ps-a[end 1] ps-a[end]; // end向前移动一个位置继续处理前一个元素 end--; } // 在腾出的位置pos处插入新元素x ps-a[pos] x; // 更新顺序列表的大小元素数量 ps-size;
}
4.10顺序表删除pos位置的值
SeqListErase函数用于删除顺序列表中指定位置的元素。它首先通过断言确保要删除的位置是有效的然后通过一个循环将指定位置之后的所有元素都向前移动一个位置从而覆盖掉指定位置的元素。最后它更新列表的大小。 // 删除顺序列表中指定位置的元素
void SeqListErase(SL* ps, int pos)
{ // 断言确保要删除的位置不会超出当前列表的大小 // 如果pos ps-size则触发断言错误终止程序 assert(pos ps-size); // 初始化一个变量start用于从要删除的位置的下一个元素开始遍历 int start pos 1; // 当start小于列表大小时执行循环 // 这个循环用于将pos位置之后的元素都向前移动一个位置覆盖掉pos位置的元素 while (start ps-size) { // 将下一个位置的元素移动到当前位置 ps-a[start - 1] ps-a[start]; // start向后移动一个位置继续处理下一个元素 start; } // 更新顺序列表的大小元素数量因为删除了一个元素所以大小减1 ps-size--;
}
今天就先到这了 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
