银行网站开发,重庆公共资源交易中心,网站建设结束的售后服务,石景山网站建设公司排行文章目录 前言线性表的定义和基本操作1.线性表的定义2.线性表的基本操作 顺序表的定义1.静态分配方式2.动态分配方式 顺序表的插入和删除1.顺序表的插入2.顺序表的删除 顺序表的查找1.按位查找#xff08;简单#xff09;2.按值查找 单链表的定义1.代码定义一个单链表2.不带头… 文章目录 前言线性表的定义和基本操作1.线性表的定义2.线性表的基本操作 顺序表的定义1.静态分配方式2.动态分配方式 顺序表的插入和删除1.顺序表的插入2.顺序表的删除 顺序表的查找1.按位查找简单2.按值查找 单链表的定义1.代码定义一个单链表2.不带头节点的单链表3.带头节点的单链表 单链表的插入和删除1.按位序插入带头节点2.按位序插入不带头节点3.指定结点的后插操作4.指定结点的前插操作5.指定结点的删除操作 总结 前言
提示这里可以添加本文要记录的大概内容
前言 数据结构是计算机科学中一个重要的基础概念它研究的是如何组织和管理计算机中的数据。线性表是一种常见的数据结构它由一组具有相同数据类型的元素组成这些元素之间存在着线性关系。
线性表具有许多重要的应用例如
存储和管理数据实现各种算法构建其他数据结构 在本文中我们将对线性表的概念、特点、实现和应用进行详细的介绍。 提示以下是本篇文章正文内容下面案例可供参考
线性表的定义和基本操作
知识总览 注意存储结构不同运算的实现方式也会不同 1.线性表的定义
线性表定义的是数据结构中的逻辑结构 对于图片中关于如果所有整数按递增次序排列是线性表吗 答案是否定的因为从定义中我们可以知道有限二字然后整数是可以无穷无尽的 2.线性表的基本操作
这个图大家看看就行 这里建议大家把其中的每个操作都动手写一写或者在编译器上多写一下熟悉几遍
对于为什么没有说明各个参数的具体类型 数据结构书籍中没有说明各个参数的具体类型是为了提高书籍的通用性、简洁性、灵活性和易读性并强调对数据结构思想和原理的理解。读者可以通过阅读代码示例和查阅相关资料来了解具体的参数类型。 最后来一个总结的图
顺序表的定义 顺序表——用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。 1.静态分配方式
我们需要知道顺序表的静态分配方式使用一个数组来实现的数组的长度一旦确定就无法改变 关于图片中把各个数据元素的值设为默认值可省略的原因 因为在顺序表结构中有一个length字段表示的是顺序表中已有元素的个数因此只要我们初始化了length就行不根据length来遍历顺序表的行为都是非法的 代码
#define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
#define MAXSIZE 10//定义顺序表的最大空间typedef struct
{int data[MAXSIZE];//利用静态分配方式实现顺序表int length;//顺序表中有效元素的个数
}Sqlist;//类型重命名取名为Sqlist//初始化一个顺序表
void InitList(Sqlist L)//利用引用传参
{for (int i 0; i MAXSIZE; i)//这里对数组元素的初始化不进行也可以因为到时候遍历利用的也是length字段的值去遍历的{L.data[i] 0;//将数组中的值都初始化为0}L.length 0;
}int main()
{Sqlist L;InitList(L);return 0;
}思考 这里需要注意length在初始化的时候不能被省略如果省略了后果很严重省略了那么length就是一个随机值 改进后的写法
#define _CRT_SECURE_NO_WARNINGS 1
#include iostream
using namespace std;
#define MAXSIZE 10//定义顺序表的最大空间typedef struct
{int data[MAXSIZE];//利用静态分配方式实现顺序表int length;//顺序表中有效元素的个数
}Sqlist;//类型重命名取名为Sqlist//初始化一个顺序表
void InitList(Sqlist L)//利用引用传参
{//for (int i 0; i MAXSIZE; i)//这里对数组元素的初始化不进行也可以因为到时候遍历利用的也是length字段的值去遍历的//{// L.data[i] 0;//将数组中的值都初始化为0//}L.length 0;
}//遍历顺序表
void Print(const SqlistL)
{for (int i 0; i L.length; i){cout L.data[i] ;}cout endl;
}
int main()
{Sqlist L;InitList(L);Print(L);return 0;
}如果数组存满了那么我们会想到两种解决办法1.开始的时候就开辟一个足够大的空间2.进行扩容 对于第一种方法显然是不可行的首先程序所需的空间我们在事前是很难预料的其次如果开辟的空间很大但是最后使用的空间很小就会造成空间上很大的浪费对于第二种方法由于我们采用的是静态分配空间的大小一定确定就无法更改所以这里的扩容也进行不下去 2.动态分配方式
通过之前的内容我们可以知道静态分配方式实现的顺序表对于扩容的时候很困难那么由此就引出了动态分配方式实现的顺序表也就是利用数组指针来实现 注意王道这里用的都是c语言的malloc函数但是我本人习惯用C的new关键字对于两者的内容可以看我的博客内容 结构体定义
#define Elemtype int //这里我把类型设置为int类型
typedef struct
{Elemtype* data;int capacity;int length;
}SqList;动态分配相关代码实现
#include iostream
using namespace std;
#define InitSize 10
#define Elemtype int //这里我把类型设置为int类型
typedef struct
{Elemtype* data;int capacity;int length;
}SeqList;void InitList(SeqList L)
{L.data new Elemtype[InitSize];L.capacity InitSize;L.length 0;
}void IncreaseSize(SeqList L, int len)//在原来的基础上多增加len个空间
{Elemtype* tmp L.data;L.data new Elemtype[len L.capacity];memcpy(L.data, tmp,L.length*sizeof(Elemtype));//这里由于元素类型是int类型也就是内置类型所以我用的是memcpy函数自定义类型慎用delete[] tmp;//释放原空间L.capacity len;
}
int main()
{SeqList L;InitList(L);IncreaseSize(L, 5);return 0;
}扩容前容量是10
扩容后可以看到容量增加到了15 同时需要注意增容操作往往需要拷贝数据拷贝数据需要比较大的时间开销 顺序表的特点 小总结
顺序表的插入和删除
1.顺序表的插入
知识总览 插入操作介绍 插入操作的代码实现
void InsertSeqList(SeqList L,int pos,int num)//在指定位序下插入元素num
{for (int i L.length; i pos; i--){L.data[i] L.data[i - 1];}L.data[pos - 1] num;L.length 1;
}对边界情况和异常情况的检查提高代码的健壮性
#include iostream
using namespace std;
#define MAXSIZE 10
typedef struct
{int data[MAXSIZE];//这里类型用intint length;
}SeqList;//初始化
void InitSeqList(SeqList L)
{L.length 0;
}
bool InsertSeqList(SeqList L,int pos,int num)//在指定位序下插入元素num
{if (pos1 || posL.length 1){return false;}if (MAXSIZE L.length)//此时空间已满不能继续插入{return false;}for (int i L.length; i pos; i--){L.data[i] L.data[i - 1];}L.data[pos - 1] num;L.length 1;return true;
}//遍历顺序表
void Print(const SeqListL)
{for (int i 0; i L.length; i){cout L.data[i] ;}cout endl;
}int main()
{SeqList L;InitSeqList(L);InsertSeqList(L, 1, 100);Print(L);return 0;
}插入操作的时间复杂度 时间复杂度这里图上说的很清楚个人觉得没有必要继续阐述了
2.顺序表的删除
顺序表的删除操作 可以看到删除操作是需要把后面元素前移的这里和插入操作恰好相反
完整代码
#include iostream
using namespace std;
#define MAXSIZE 10
typedef struct
{int data[MAXSIZE];//这里类型用intint length;
}SeqList;//初始化
void InitSeqList(SeqList L)
{L.length 0;
}
bool InsertSeqList(SeqList L,int pos,int num)//在指定位序下插入元素num
{if (pos1 || posL.length 1){return false;}if (MAXSIZE L.length)//此时空间已满不能继续插入{return false;}for (int i L.length; i pos; i--){L.data[i] L.data[i - 1];}L.data[pos - 1] num;L.length 1;return true;
}//遍历顺序表
void Print(const SeqListL)
{for (int i 0; i L.length; i){cout L.data[i] ;}cout endl;
}bool ListDelete(SeqList L, int pos, int e)//删除顺序表pos位置的值并将被删除元素的值给e
{if (pos1 || posL.length){return false;}e L.data[pos-1];for (int i pos; i L.length; i){L.data[i-1] L.data[i];}L.length--;return true;
}
int main()
{SeqList L;int num 0;InitSeqList(L);InsertSeqList(L, 1, 1);InsertSeqList(L, 2, 2);InsertSeqList(L, 3, 3);Print(L);if(ListDelete(L, 2, num))cout num endl;Print(L);return 0;
}对于图中如果参数e没加引用符号会怎么样的问题 如果参数e没加引用符号那么形参会是实参的拷贝在main函数中输出的num的值依旧是0 删除操作的时间复杂度 小总结
顺序表的查找
知识总览
1.按位查找简单 由于顺序表随机存取的特性显然他的时间复杂度是O(1)其他的没什么太多可说的都很好理解 代码 这里我的参数加了引用因为引用共用的是同一块空间如果不加引用就会多一次拷贝增加空间的开销 int GetElem(const SeqListL,int i)
{return L.data[i-1];
}2.按值查找 代码
int LocateElem(const SeqList L, int e)
{for (int i 0; i L.length; i){if (L.data[i] e)return i 1;}return -1;
}对于结构体类型的元素或是自定义类型的元素不能使用运算符c中需要使用运算符重载才可以使用c语言不能使用 解决办法 注意 时间复杂度 小总结
单链表的定义 带头结点和不带头结点
这里就是说明链式存储的存储密度比顺序存储低
1.代码定义一个单链表 改进后单链表的定义
typedef struct LNode
{int data;//数据域struct LNode* next;//指针域
}LNode,*LinkList;struct LNode
{int data;//数据域struct LNode* next;//指针域
};2.不带头节点的单链表 代码
#include iostream
using namespace std;
typedef struct LNode
{int data;//数据域struct LNode* next;//指针域
}LNode,*LinkList;//初始化
bool InitList(LinkList L)
{L NULL;return true;
}//判断单链表是否为空
bool empty(LinkList L)
{return (L NULL);
}
int main()
{LinkList L;InitList(L);cout empty(L) endl;return 0;
}3.带头节点的单链表
注意头结点不存储数据
#include iostream
using namespace std;
typedef struct LNode
{int data;//数据域struct LNode* next;//指针域
}LNode,*LinkList;//初始化
bool InitList(LinkList L)
{L new LNode;//分配一个头结点,或者用c语言的方式(LNode*)malloc(sizeof(LNode))if (L NULL)//内存不足分配失败return false;L-next NULL;return true;
}//判断单链表是否为空
bool empty(LinkList L)
{return (L -next NULL);
}
int main()
{LinkList L;InitList(L);cout empty(L) endl;return 0;
}小结 单链表的插入和删除 1.按位序插入带头节点 #include iostream
using namespace std;
typedef struct LNode
{int data;//数据域struct LNode* next;//指针域
}LNode,*LinkList;//初始化
bool InitList(LinkList L)
{L new LNode;//分配一个头结点,或者用c语言的方式(LNode*)malloc(sizeof(LNode))if (L NULL)//内存不足分配失败return false;L-next NULL;return true;
}//在第i个位置插入元素e带头节点
bool ListInsert(LinkList L, int i, int e)
{if (i 1){return false;}int j 0;//记录当前是第几个结点LNode* p L;//临时结点pwhile (p ! NULL j i-1)//找到第i-1个结点的位置{p p-next;j;}if (p NULL)return false;LNode* s new LNode;s-data e;s-next p-next;p-next s;return true;
}void Print(LinkList L)
{LNode* p L;while (p-next ! NULL){p p-next;cout p-data ;}cout endl;
}//判断单链表是否为空
bool empty(LinkList L)
{return (L -next NULL);
}
int main()
{LinkList L;InitList(L);ListInsert(L,1,1);ListInsert(L,2,2);ListInsert(L,3,3);ListInsert(L,4,4);Print(L);return 0;
}2.按位序插入不带头节点 代码
#include iostream
using namespace std;
typedef struct LNode
{int data;//数据域struct LNode* next;//指针域
}LNode, * LinkList;//初始化(不带头节点)
bool InitList(LinkList L)
{L NULL;return true;
}//在第i个位置插入元素e不带头节点
bool ListInsert(LinkList L, int i, int e)
{if (i 1){return false;}if (i 1){LNode* s new LNode;s-data e;s-next L;L s;return true;}LNode* p L;int j 1;while (p ! NULL j i - 1){p p-next;j;}if (p NULL)return false;LNode* s new LNode;s-data e;s-next p-next;p-next s;return true;
}void Print(LinkList L)
{LNode* p L;while (p ! NULL){cout p-data ;p p-next;}cout endl;
}//判断单链表是否为空
bool empty(LinkList L)
{return (L NULL);
}
int main()
{LinkList L;InitList(L);ListInsert(L, 1, 1);ListInsert(L, 2, 2);ListInsert(L, 3, 3);ListInsert(L, 4, 4);Print(L);return 0;
}3.指定结点的后插操作 代码
bool InsertNExtNode(LNode* p, int e)
{if (p NULL)return false;LNode* s new LNode;if (s NULL)return false;s-data e;s-next p-next;p-next s;return true;
}4.指定结点的前插操作 代码
bool InsertPriorNode(LNode* p, int e)
{if (p NULL)return false;LNode* s new LNode;if (s NULL)return false;s-next p-next;p-next s;s-data p-data;p-data e;return true;
}5.指定结点的删除操作 代码
bool DeleteNode(LNode* p)
{if (p NULL)return false;LNode* q p-next;p-data q-data;p-next q-next;delete q;return true;
}小结
总结
在本文中我们对线性表的概念、特点、实现和应用进行了详细的介绍。
线性表的特点是
元素之间存在着线性关系每个元素只有一个前驱和一个后继
线性表的实现方式主要有两种
顺序表链表
线性表的应用非常广泛例如
存储和管理数据实现各种算法构建其他数据结构
通过学习本文读者应该能够 理解线性表的概念和特点 掌握线性表的实现方法 了解线性表的应用
