同时做几个网站的seo,个人注册登录入口,江苏h5响应式网站建设设计,2021热点新闻事件本文的所有代码均由C编写 如果你已经看完这篇杂谈,你可以前往上一篇杂谈→数据结构杂谈#xff08;二#xff09;_尘鱼好美的小屋-CSDN博客 3 单链表 文章目录3 单链表[toc]3.1 单链表的定义3.1.1 引入2.1.2 单链表和顺序表的优劣2.1.3 单链表的代码定义3.2 单链表的初始化3.… 本文的所有代码均由C编写 如果你已经看完这篇杂谈,你可以前往上一篇杂谈→数据结构杂谈二_尘鱼好美的小屋-CSDN博客 3 单链表 文章目录3 单链表[toc]3.1 单链表的定义3.1.1 引入2.1.2 单链表和顺序表的优劣2.1.3 单链表的代码定义3.2 单链表的初始化3.2.1 不带头结点的单链表3.2.2 带头结点的单链表3.3 单链表的插入3.3.1 带头结点的单链表插入3.3.2 不带头结点的单链表插入3.3.3 指定结点后插操作3.3.4 指定结点前插操作3.4 单链表的删除3.4.1 带头结点的单链表删除3.4.2 指定结点的删除3.5 单链表的查找3.5.1 按位查找3.5.2 按值查找3.5.3 求单链表长度3.6 单链表的建立3.6.1 尾插法3.6.2 头插法3.7 补充算法3.7.1 单链表的销毁3.7.2 清空链表
3.1 单链表的定义
3.1.1 引入
线性表有两种第一个是我们前面讲到的顺序表对应顺序存储。第二个是链表对应链式存储。
物理结构逻辑结构顺序表顺序存储链表链式存储
要谈论链表我们就要先谈最简单的链表所以在这里首先要提出一个单链表的概念。单链表也叫线性链表。 线性表的链式存储结构是用一组任意的存储单元存储线性表的数据元素。由图可知每个数据元素aia_iai由两部分组成一部分放数据元素信息我们叫做数据域另外一部分放下一个数据元素地址的信息我们叫指针域两部分加起来合称为结点。指针域里面放的地址我们叫指针或者链。n个结点结成一个链表。因为每个结点只放了一个指针域所以我们又叫单链表或线性链表。 2.1.2 单链表和顺序表的优劣
顺序表优缺点单链表优缺点顺序表优点可随机存取存储密度高单链表优点不要求大片连续空间改变容量方便缺点要求大片连续空间改变容量不方便。缺点不可随机存取要耗费一定空间存放指针。
2.1.3 单链表的代码定义
在前面我们说过单链表中的每个节点都包含一个数据域和一个指针域所以在C中我们常常用结构体的方式去定义某个节点。
//定义一个结点
typedef struct LNode{ //定义单链表结点类型ElemType data; //每个节点存放一个数据元素struct LNode *next; //指针指向下一个结点
}LNode*, LinkList需要注意的是在这里我们可以看到指针域用了一个结构体嵌套这是因为下一个节点也是结构体它的地址也会是结构体指针类型。 在上面的定义中我们还使用了数据类型重命名typedef重命名了两个名字其中LNode*主要是强调他是一个结点而LinkList主要强调这个结点为整个链表用了两种命名是为了代码的可读性更强。】 对于拥有多个类型的数据元素我们常常采用嵌套结构体的方式先将数据存放某一个结构体然后再将该结构体放入定义结点的结构体中举例如下 typedef Struct{char num[8];char name[8];int score;
}ElemType;typedef struct LNode{ElemType data;//数据域struct LNode *next;//指针域
}LNode,*LinkList;3.2 单链表的初始化
对于链表来说是需要初始化的这是因为结点中可能含有脏数据。对于单链表初始化即构造一个空表。
这里我们要分为两类情况一类是不带头结点的单链表一类是带头结点的单链表。下面先说说两者的区别
所有的链表都要有个头指针first带头结点的链表的头指针指向的是头结点头结点的指针域指向首元结点不带头结点的头指针直接指向首元结点。两者在操作上有区别在删除和插入操作中无论删除和插入的位置如何带头结点的链表不需要修改头指针的值而不带头结点的有时候需要。在清空操作中带头结点的保留头结点而不带头结点的要销毁。.在结构上带头结点的单链表不管链表是否为空均含有一个头结点不带头结点的单链表不含头结点。在操作上带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点算法步骤都相同。不带头结点的单链表其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。
3.2.1 不带头结点的单链表
由于单链表不带头结点这就导致了如果初始化表那就是表全为空。其代码定义如下
#include iostream
using namespace std;//定义链表(不带头结点)
typedef struct
{//数据域int data;//指针域struct LNode* next;
}LNode,* LinkList;//初始化链表
bool InitList(LinkList L)
{L NULL;return true;
}int main()
{LinkList L;InitList(L);
}此时如果要判断单链表是否为空只需单纯判断L是否为空即可。
//判断单链表是否为空
bool Empty(LinkList L)
{if (L NULL)return true;elsereturn false;
}3.2.2 带头结点的单链表
生成新结点作头结点用头指针L指向头结点。将头结点的指针域置空防止内存中有遗留的脏数据。
#include iostream
using namespace std;//定义链表(不带头结点)
typedef struct LNode
{//数据域int data;//指针域struct LNode* next;
}LNode,* LinkList;//初始化链表
bool InitList(LinkList L)
{L new LNode;if (L NULL)//这里为了防止申请内存不足return false;L-next NULL;return true;
}int main()
{LinkList L;InitList(L);
}此时如果想判断单链表是否为空只需判断头结点中储存的指针域是否为空即可。
//判断单链表是否为空
bool Empty(LinkList L)
{if (L-next NULL)return true;elsereturn false;
}一般来说我们写的代码都是带头节点的用过都说好。 3.3 单链表的插入
在下面的基本操作中我们需要知道一些比较特殊的步骤有个这些步骤即使不看源码你也能写出类似的代码。
p L;//p指向头结点
s L-next;//s指向首元结点
p p-next;//p指向下一结点这里还要多插一句为了让我们的代码更具健壮性我们应该多考虑极端情况为了避免重复代码使我们的代码简洁易维护我们应该把基本操作封装成一个函数。
3.3.1 带头结点的单链表插入
单链表插入原理图如下 以下给出代码实现 ListInsert(L,I,e):插入操作。在表L中的第i个位置上插入指定元素e。 //按位插入
bool ListInsert(LinkList L, int i, int e)
{if (i 1)return false;LNode* p;//生成指针p用于指向插入端的前一个结点int j 0;//用于扫描计数p L;//p初始化位置指向头结点//移动p到插入位置的前一个结点while (p!NULL j i-1){p p-next;j;}//p不能移出链表之外if (p NULL)return false;//生成要插入的新结点LNode* s new LNode;s-data e;s-next p-next;p-next s;return true;
}需要注意的是s-next p-next和p-next s这两句不可颠倒否则链表的后半部分将会丢失。还有添加结点必须一个一个添加不能说第二个还没添加就添加第三个。 3.3.2 不带头结点的单链表插入
实际上不带头结点的单链表插入原理和带头结点的差不多只是在第1个位置需要做特殊处理因为头指针指着第一个元素。为此我们要在带头结点的单链表插入代码中添加如下代码
if (i 1){LNode* s new LNode;s-data e;s-next L;L s;return true;}不带头结点写代码很不方便推荐用带头结点而在考研中带头结点和不带头结点的情况均有可能考查要注意审题。 3.3.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;
}3.3.4 指定结点前插操作
对于后插来说实际上根据指定的结点是可以找到下一个结点的。可以对于前插来说指定的结点是不能找到前一个结点的这是因为结点中只存放了下一个结点的指针而没有存放上一个结点的指针域。
那么如何解决这个问题呢我们可以用后插模仿成前插什么意思呢意思就是后插一个结点然后把前一个结点的数据拷贝到后一个结点然后对前一个结点赋值即可做成前插的效果。而且这种思路的时间复杂度为O(1)用了都说好。代码实现如下
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;
}3.4 单链表的删除
3.4.1 带头结点的单链表删除
bool ListDelete(LinkList L, int i, int e)
{if (i 1) //索引处于链表之外return false;LNode* p;int j 0;p L;while (p ! NULL j i - 1){p p-next;j;}if (p NULL)//索引处于链表右边之外return false;if (p-next NULL)return false;LNode* q p-next;e q-data;p-next q-next;delete(q);return true;
}3.4.2 指定结点的删除
//删除指定结点
bool DeleteNode(LNode* p)
{if (p NULL)return false;LNode* q p-next;p-data p-next-data;p-next q-next;delete(q);return true;
}实际上上面提供的代码具有BUG因为如果p是最后一个结点那么p-next是空值无法提供data这个时候只能从表头开始依次寻找p的前驱时间复杂度为O(n)。
3.5 单链表的查找
3.5.1 按位查找
实际上对于按位查找无非就是从头找到尾直到找到第i个元素位置。由于这个算法的时间复杂度取决于i的位置所以有最好情况和最坏情况。
//按位查找
LNode* GetElem(LinkList L, int i)
{if (i 0)return NULL;LNode* p;p L;int j 0;while (p ! NULL j i){p p-next;j;}return p;
}分析算法时要时刻分析极端情况如图所示 由于有头结点头结点不允许查找而其为0号位所以i至少要为1。由于如果开辟内存不足那么ana_nan可以为NULL此时i要小于ana_nan。 还要一个需要注意的点你是否发现这段按位查找的代码好像似曾相识没错这段代码出现在插入和删除操作中所以当你把按位查找封装成一个函数基本操作的时候写插入基本操作就无需再写一次代码直接调用按位查找函数即可这样可提高代码复用性。 3.5.2 按值查找
//按值查找
LNode* LocateElem(LinkList L, int e)
{LNode* p L-next;while (p ! NULL p-data ! e)p p-next;return p;
}【注该算法时间复杂度为O(n)。】 3.5.3 求单链表长度
//求单链表长度
int Length(LinkList L)
{int len 0;LNode* p L; //初始化指针于头结点位置while (p-next ! NULL){p p-next;len;}return len;
}3.6 单链表的建立
如果给你很多个数据元素要把它们存到一个单链表里边怎么达到目的呢
3.6.1 尾插法
尾插法没什么好讲的利用我们前面所讲的定义、初始化、插入即可完成尾插法需要注意的是每次插入一个元素需要新指定一个变量length来统计表的长度。
但是如果使用普通的遍历插入每次插入都会涉及到while循环时间复杂度为O(n2)O(n^2)O(n2)这样的算法明显太垃圾了。
于是我们又思考前面在学习插入的时候我们使用过一个叫做指定结点的后插操作。其步骤如下
从一个空表L开始将新结点逐个插入到链表的尾部尾指针r指向链表的尾结点。初始时r同L均指向头结点。每读入一个数据元素则申请一个新结点将新结点插入到尾结点后r指向新结点。
为了更直观地看懂这个过程我特意花了个图 代码示例如下
//正位序输入n个元素的值建立带表头结点的单链表L
void CreateList_R(LinkList L,int n){L new LNode;L-next NULL;r L; //尾指针r指向头结点for(i 0;in;i){p new LNode;cinp-data; //生成新结点输入元素值p-next NULL;r-next p; //插入到表尾r p; //r指向新的尾结点}
}//CreateList_R【注这里尾插法的时间复杂度是O(n)】 3.6.2 头插法
头插法也很好理解本质是插入的位置一直处于头结点之后且使用指定结点的后插操作。其基本步骤如下
从一个空表开始重复读入数据生成新结点将读入数据存放到新结点的数据域中从最后一个结点开始依次将各结点插入到链表的前端
对于头插法我也画了个图 其代码示例如下
void CreateList_H(LinkList L,int n){L new LNode;L-next NULL;for(i n;i0;i--){p new LNode;cinp-data;p-next L-next;L-next p;}
}//CreateList_H【注这里头插法的算法时间复杂度是O(n)】 需要注意的是这里还能应用链表的逆置用指针扫描某一个某一个链表后利用头插法插到另外一个链表即可实现逆置。 3.7 补充算法
3.7.1 单链表的销毁 销毁链表销毁后不存在 【算法思路】从头指针开始依次释放所有结点 我们销毁的思路是我们还需要另外一个指针变量P这个指针变量用于结点的操作。若想实现变量P对某结点的操作首要任务就是让P指向该结点即把该结点的地址赋给P。那该节点的地址存于头指针L所以只需p L即可。当然当P L后不能立马删除p否则L丢失链表也跟着丢失所以我们需要在P L后把L移到下一个结点即L L-next然后再释放Pfree§即可。循环上述操作即可删除链表。 【算法描述】
Status DestroyList_L(LinkList L){//销毁单链表LLNode *p;while(L){p L;L L-next;delete(p);}return Ok;
}3.7.2 清空链表 清空链表链表仍然存在但链表中无元素成为空链表头指针和头结点仍然在 【算法思路】依次释放所有结点并将头结点指针域设置为空。 先将头指针的指针域赋给指针变量p这样的话p就定位了要删除的结点了但是如果现在直接删除那么后面的链表就会丢失了。所以这时候我们引入第三个指针变量qq来保证后面的链表不丢失当我们q移到p要删除结点的下一个结点后即q p-next我们再去释放p即delete§。直到清空列表为止。 【算法描述】
Status ClearList(LinkList L){LNode *p,*q;p L-next;while(p){pq-next;free(p);p q;}L-next NULL; //头结点指针域为空return OK;
}
