济南做网站的哪家好,福州做企业网站,漯河网站关键词优化,网站开发工具的功能包括哪些1. 单链表的基本操作 1.1. 链表的定义1.2. 链表的创建#xff08;初始化#xff09; 1.2.1. 不带头结点的链表1.2.2. 带头结点的链表 1.3. 链表的插入和删除 1.3.1. 按位序插入 1.3.1.1. 带头结点1.3.1.2. 不带头结点 1.3.2. 指定节点的后插操作1.3.3. 指定元素的前插操作1.3…1. 单链表的基本操作 1.1. 链表的定义1.2. 链表的创建初始化 1.2.1. 不带头结点的链表1.2.2. 带头结点的链表 1.3. 链表的插入和删除 1.3.1. 按位序插入 1.3.1.1. 带头结点1.3.1.2. 不带头结点 1.3.2. 指定节点的后插操作1.3.3. 指定元素的前插操作1.3.4. 按位序删除 1.3.4.1. 带头结点1.3.4.2. 不带头结点 1.3.5. 指定元素的删除操作
1. 单链表的基本操作
链表是一种基本的数据结构在很多数据结构中都会使用链表的方式进行建立所以将链表学会学通透很有必要。
1.1. 链表的定义
链表的定义是基于结构体之上的一个链表一般需要定义两方面的东西一个是链表的节点一个是链表的指针。一个链表的定义示例如下
typedef struct ListNode {int data;struct ListNode *next;
}LNode,*List;上述代码中的val是数据域用来存放数据next是指针域用来存放下一个节点的地址。 并且该代码采用了typedef定义了一个别名LNode用来指代链表的节点List是链表的指针用来指向链表的第一个节点。
1.2. 链表的创建初始化
链表的创建有两种方式一种是带头结点的另一种是不带头节点的。
1.2.1. 不带头结点的链表
不带头结点的链表的创建方式如下
void InitList(List *L)
{LNULL;
}即使得链表的下一个节点为空。
1.2.2. 带头结点的链表
带头结点的链表的创建方式如下
void InitList(List *L)
{L(List)malloc(sizeof(LNode));if(LNULL){return ;//此时表示创建头结点失败}L-nextNULL;//头结点指向的下一个节点为空
}头结点的好处就在于当我们需要对链表进行一个操作的时候不需要专门对链表的第一个节点进行特殊操作我们只需要对所有的代码编写一个固定的函数通过传递不同的值就可以实现特定高度功能。
1.3. 链表的插入和删除
1.3.1. 按位序插入
1.3.1.1. 带头结点
链表的插入需要先找到要插入位置的前后节点然后创建一个指针使得前一个节点指向这个指针这个指针再指向下一个节点。
在按位序插入的过程中我们需要输入链表的头结点供遍历寻找目标位置要插入的位置和元素。 示例代码如下
bool ListInsert(List *L,int i,int e)
{if(i1){return false;}LNode *p; //p表示当前指向的是哪个节点int j0; //j表示的是当前指向节点的位置pL; //目前先让p指向头节点while(p!NULLji-1) //循环找到要插入节点的前一个节点{pp-next;j;}LNode *s(LNode *)malloc(sizeof(LNode));s.datae;s-nextp-next;p-nexts;return true;
}1.3.1.2. 不带头结点
不带头结点的插入与带头结点的插入类似但是相对带头节点来说更加繁琐。
bool ListInsert(List *L,int i,int e)
{if(i1){return false;}if(i1){LNode *q(LNode *)malloc(sizeof(LNode));q-datae;q-nextL;Lq;}LNode *p; //p表示当前指向的是哪个节点int j0; //j表示的是当前指向节点的位置pL; //目前先让p指向头节点while(p!NULLji-1) //循环找到要插入节点的前一个节点{pp-next;j;}LNode *s(LNode *)malloc(sizeof(LNode));s.datae;s-nextp-next;p-nexts;return true;
}同样传入的是第一个节点的地址要加入节点的位置和要加入的元素区别就在于加入要在第一个位置插入元素就需要特别处理一下。
1.3.2. 指定节点的后插操作
在给定节点后插入节点的操作相对简单示例代码如下:
bool InsertNextNode(LNode *p,int x)
{if(pNULL){return false;}LNode *s(LNode *)malloc(sizeof(LNode));s-nextp-next;p-nexts;sdatax;return true;
}1.3.3. 指定元素的前插操作
在指定元素之前要插入一个元素最容易想到的办法是将整个链表遍历一遍之后找到这个元素的前驱节点转换成后插操作。但是这种办法实现起来较为复杂所以我们转换一种思维方式采取新的方法。
我们尝试在指定节点之后先插入一个节点然后把指定节点的值赋给新节点之后再把要插入的值赋给旧节点。总而言之就是现在之后插入节点然后把两个节点的值互换就相当于将前后节点互换了。示例代码如下
bool InsertPriorNode(LNode *p,int x)
{if(pNULL){return false;}LNode *s(LNode *)malloc(sizeof(LNode));s-nextp-next;p-nexts;s-datap-data;p-datax;return true;
}1.3.4. 按位序删除
1.3.4.1. 带头结点
在带头结点的删除节点操作中我们需要给函数传递链表的第一个节点的位置要删除的位置和一个变量用来存储删除节点的元素值。
删除的主要操作是创建一个指针(不分配内存空间)指向要删除的节点然后让要删除指针前一个节点指向要删除指针的后一个节点然后将要删除的指针释放内存从而达到目的。
示例代码如下
bool ListDelete(List L,int i,int x)
{if(i1){return false;}LNode *p;int j0;pL;while(p!NULL;ji-1){pp-next;j;}if(pNULL){return false;}if(p-nextNULL){return false;}LNode *qp-next;xq-data;p-nextq-next;free(q);
}1.3.4.2. 不带头结点
与不带头结点的插入类似这里不再赘述。
1.3.5. 指定元素的删除操作
删除操作和带头结点的的相似指定元素和指定元素的插入相似这里不再赘述
