库易网网站,阿里巴巴外贸平台费用,网站备案需要多少天,体育新闻最新消息今天1.前言
哈喽大家好喔#xff0c;今天博主继续进行数据结构的分享与学习#xff0c;今天的主要内容是顺序表与链表#xff0c;是最简单但又相当重要的数据结构#xff0c;为以后的学习有重要的铺垫#xff0c;希望大家一起交流学习#xff0c;互相进步#xff0c;让我们…
1.前言
哈喽大家好喔今天博主继续进行数据结构的分享与学习今天的主要内容是顺序表与链表是最简单但又相当重要的数据结构为以后的学习有重要的铺垫希望大家一起交流学习互相进步让我们开始吧。
2.正文
数据结构是计算机科学中非常重要的一部分用于组织和管理数据以便高效地访问和修改。顺序表和链表是两种常见且基础的数据结构它们各有特点和适用场景。以下是对这两种数据结构的详细分析
2.1顺序表
顺序表是在计算机内存中以数组的形式保存的线性表。其有点类似数组但添加了几个额外的概念。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。
这里面有俩个定义顺序表功能的俩个变量分别是count和size变量size是用来确定顺序表的存储空间大小的count是用来标记顺序表中当前元素位置的。
2.1.1结构特点 物理存储连续性顺序表中的所有元素在内存中占有一段连续的存储空间。随机访问顺序表支持通过下标快速访问任意位置的元素访问时间复杂度为O(1)。空间分配 静态顺序表使用定长数组存储元素适用于数据大小已知的场景但灵活性较差。动态顺序表使用动态开辟的数组存储可以根据需要动态调整存储空间大小更加灵活。插入和删除操作由于物理连续性插入和删除操作需要移动元素效率较低时间复杂度为O(n)。 2.1.2结构定义
typedef struct vector {int size, count;int *data;//总大小,元素数量
//指针指向连续的存储区
} vector;
//初始化
vector *getNewVector(int n) {vector *p (vector *)malloc(sizeof(vector));p-size n;//存储上限p-count 0;p-data (int *)malloc(sizeof(int) * n);return p;
}
2.1.3结构操作 2.1.3.1插入操作
//插入操作
int insert(vector *v, int pos, int val) {if (pos 0 || pos v-count) return 0;if (v-size v-count !expand(v)) return 0;for (int i v-count - 1; i pos; i--) {v-data[i 1] v-data[i];}v-data[pos] val;v-count 1;return 1;
} 2.1.3.2删除操作
//删除操作
void clear(vector *v) {if (v NULL) return ;free(v-data);free(v);return ;
} 2.1.3.3销毁操作
//销毁操作
int erase(vector *v, int pos) {if (pos 0 || pos v-count) return 0;for (int i pos 1; i v-count; i) {v-data[i - 1] v-data[i];}v-count - 1;return 1;
} 2.1.3.4自动扩容操作 需要顺序表扩容的俩个条件 插入到非法位置即位置小于0或大于等于size。顺序表满了之后如果还需要添加新的元素就需要扩容。 realloc是 C 标准库中的一个函数用于调整已经分配的内存块的大小。这个函数常用于动态内存管理特别是在需要扩展或缩小已经分配的内存时。 realloc开辟内存的三种情况 如果当前内存段后面有足够的空间来满足新的大小要求realloc 会尝试扩展这段内存空间并返回原指针。如果当前内存段后面的空闲字节不够realloc 会在堆中查找一个能够满足新大小要求的内存块将原数据复制到新的位置并释放原来的内存块然后返回新内存块的首地址。如果重新分配失败例如因为内存不足realloc 会返回 NULL但此时原始内存块仍然保持有效。 注意事项 返回值处理使用 realloc 时应始终检查其返回值。如果返回 NULL表示重新分配失败此时原始内存块仍然有效需要适当处理如释放原始内存块。指针更新如果 realloc 成功并返回一个新的地址不同于原始地址则需要更新指向该内存块的指针以避免内存泄漏或野指针问题。内存释放当内存不再使用时应使用 free() 函数释放内存块。如果 realloc 失败且原始内存块仍需保留则不应调用 free() 释放它。数据保留realloc 会保留原始内存块中的数据并将其复制到新的内存块如果分配了新的内存块。但是如果新大小小于原大小则超出的数据可能会丢失。 //扩容操作
int expand(vector *v) {if (v NULL) return 0;printf(expand v from %d to %d\n, v-size, 2 * v-size);int *p (int *)realloc(v-data, sizeof(int) * 2 * v-size);if (p NULL) return 0;v-data p;v-size * 2;return 1;
}完整调试代码
#include stdio.h
#include stdlib.h
#include time.htypedef struct vector {int size, count;int *data;//总大小,元素数量
//指针指向连续的存储区
} vector;
//初始化
vector *getNewVector(int n) {vector *p (vector *)malloc(sizeof(vector));p-size n;//存储上限p-count 0;p-data (int *)malloc(sizeof(int) * n);return p;
}int expand(vector *v) {if (v NULL) return 0;printf(expand v from %d to %d\n, v-size, 2 * v-size);int *p (int *)realloc(v-data, sizeof(int) * 2 * v-size);if (p NULL) return 0;v-data p;v-size * 2;return 1;
}
//插入操作
int insert(vector *v, int pos, int val) {if (pos 0 || pos v-count) return 0;if (v-size v-count !expand(v)) return 0;for (int i v-count - 1; i pos; i--) {v-data[i 1] v-data[i];}v-data[pos] val;v-count 1;return 1;
}
//销毁操作
int erase(vector *v, int pos) {if (pos 0 || pos v-count) return 0;for (int i pos 1; i v-count; i) {v-data[i - 1] v-data[i];}v-count - 1;return 1;
}void output_vector(vector *v) {int len 0;for (int i 0; i v-size; i) {len printf(%3d, i);}printf(\n);for (int i 0; i len; i) printf(-);printf(\n);for (int i 0; i v-count; i) {printf(%3d, v-data[i]);}printf(\n);printf(\n\n);return ;
}
//删除操作
void clear(vector *v) {if (v NULL) return ;free(v-data);free(v);return ;
}int main() {srand(time(0));#define MAX_OP 20vector *v getNewVector(2);for (int i 0; i MAX_OP; i) {int op rand() % 4, pos, val, ret;switch (op) {case 0:case 1:case 2:pos rand() % (v-count 2);//为了可以看到插入到非法位置时程序的反应val rand() % 100;ret insert(v, pos, val);printf(insert %d at %d to vector %d\n, val, pos, ret);break;case 3:pos rand() % (v-count 2);ret erase(v, pos);printf(erase item at %d in vector %d\n, pos, ret);break;}output_vector(v);}clear(v);return 0;
} 2.2链表
链表是一种物理存储结构上非 连续、非顺序的存储结构但逻辑上是顺序的。链表由一系列结点链表中每一个元素称为结点组成每个结点包含两个部分数据域和指针域。数据域用来存储数据而指针域则用来指向下一个结点。
2.2.1链表的分类 单链表每个节点只包含一个指针指向下一个节点。双链表每个节点包含两个指针一个指向前一个节点另一个指向下一个节点。循环链表链表的最后一个节点的指针域指向第一个节点形成一个环。 2.2.2结构特点 物理存储非连续性链表中的元素可以存储在内存中的任意位置通过指针链接。插入和删除操作高效链表的插入和删除操作只需要修改指针指向不需要移动大量元素时间复杂度为O(1)。不支持随机访问链表的访问需要从头节点开始依次遍历到目标节点访问效率较低。空间利用链表中的每个节点都需要额外的空间来存储指针但链表可以动态增长不需要预分配固定大小的空间。 2.2.3结构定义
typedef struct Lnode
{int data;struct Lnode *next;
} Lnode, *Linklist;void InitList (Linklist *L) //二级指针的目的是地址传递因为该函数没有返回值用地址传递带回头节点地址。
{Linklist p;p (Linklist)malloc(sizeof(Lnode));if(p NULL)cout 申请内存空间失败。 endl;p-nextNULL;*L p;flag;
}//初始化一个空的链表
2.2.4结构操作 接下来主要介绍几个链表的基础关键操作 2.2.4.1创建链表操作
void Creatlist(Linklist L,int n)
{int i; Lnode *p,*pt;ptL;for(i1;in;i){ p(Linklist)malloc(sizeof(Lnode));if(pNULL)cout 申请内存空间失败。 endl;cout 请输入链表中元素 endl;cin p-data; p-nextpt-next;pt-nextp;ptp;}//flag;
}//创建链表 2.2.4.2查找操作
int Getelem(Linklist L, int i)
{Lnode *p;int e;int j;pL-next;j1;while (p ji){pp-next;j;}if(!p || ji)cout 该位序不存在。 endl;else{ep-data;cout 第 i 个元素为 e endl;}return OK;
}//用e返回L中第i个数据元素的值. 2.2.4.3插入操作
int Listinsert(Linklist L,int i,int e)
{int j;Lnode *p,*s;pL; j0;while(p ji-1){pp-next;j;}if(!p || ji-1)return ERROR;s(Linklist)malloc(sizeof(Lnode));if(sNULL)cout 申请内存空间失败。 endl;s-datae;s-nextp-next;p-nexts;cout 插入的元素是 e endl;return OK;
}//在第i个位置插入元素e 2.2.4.1销毁链表操作
int DestroyList(Linklist L)
{Lnode *p;pNULL;if(L flag!0){while(L){ pL;LL-next;free(p); }cout 链表已销毁。 endl;}elsecout 链表不存在。 endl;return OK;flag;
}//销毁链表 2.3顺序表和链表的比较
这边列举一个表格方便大家对着俩个功能类似的数据结构的特点有更加充分的理解
特点顺序表链表存储方式连续存储非连续存储随机访问支持O(1)不支持需要遍历插入/删除操作效率低O(n)效率高O(1)空间利用较高无额外指针空间较低每个节点需额外空间存储指针灵活性较低需要预分配空间较高可以动态增长
3.小结
今天数据结构第二讲顺序表与链表到这里就结束了未来俩天会有链表相关延展问题实现的博客出炉不要忘了点一手关注再走哦希望喜欢的朋友多多支持我哦~
