哪里有做网站的教程,企业网站需要哪些模块,常用网站建设技术是什么意思,登录全球最大的域名注册商网站原文博客链接:单链表分离(头插法和尾插法的结合,理解指针变换)_3.对任务1或者2中创建的某一个单链表{a1,b1,a2,b2,...,an,bn},编写一个算法将-CSDN博客
函数实现:
/**************************************************
函数名:separate_LinkList
功 能: 把一个链表,交叉新建…原文博客链接:单链表分离(头插法和尾插法的结合,理解指针变换)_3.对任务1或者2中创建的某一个单链表{a1,b1,a2,b2,...,an,bn},编写一个算法将-CSDN博客
函数实现:
/**************************************************
函数名:separate_LinkList
功 能: 把一个链表,交叉新建成两个表,一个尾插法,一个头插法(尾插法在原表之上)
注意:① 等构建完再置空
参 数: (1)LinkList *L:原表(2)LinkList *List_tail:原表之上尾插法建立的新表(3)LinkList*List_head: 另外新建的单链表(头插法)
原文链接:https://blog.csdn.net/qq_57484399/article/details/127132144
返回值: 无
**************************************************/
void separate_LinkList(LinkList *L,LinkList *List_tail,LinkList*List_head)
{LinkList *newNode; //新节点LinkList *rearNode; //新节点后继信息存储LinkList *Tail_pointer; //List_tail尾指针newNode L-next; //新节点从L-next开始List_tail L; //List_tail从L开始Tail_pointer List_tail;List_head (LinkList*)malloc(sizeof(LinkList)); //List_head构建新节点List_head-next NULL;while(newNode ! NULL){Tail_pointer-next newNode; //List_tail尾指针指向新节点Tail_pointer newNode; //①尾指针Tail_pointer后移,构建完成newNode newNode-next; //新节点后移rearNode newNode-next; //新节点后继信息存储newNode-next List_head-next; //新节点头插法插入List_head-next newNode;newNode rearNode; //书接上回}Tail_pointer-next NULL;
}
完整代码:
main.cpp
#include stdio.h
#include malloc.h
#include singlelist.hvoid split(LinkList *L,LinkList *L1,LinkList*L2);//分离链表
/**************************************************
函数名:separate_LinkList
功 能: 把一个链表,交叉新建成两个表,一个尾插法,一个头插法(尾插法在原表之上)
注意:① 等构建完再置空
参 数: (1)LinkList *L:原表(2)LinkList *List_tail:原表之上尾插法建立的新表(3)LinkList*List_head: 另外新建的单链表(头插法)
原文链接:https://blog.csdn.net/qq_57484399/article/details/127132144
返回值: 无
**************************************************/
void separate_LinkList(LinkList *L,LinkList *List_tail,LinkList*List_head)
{LinkList *newNode; //新节点LinkList *rearNode; //新节点后继信息存储LinkList *Tail_pointer; //List_tail尾指针newNode L-next; //新节点从L-next开始List_tail L; //List_tail从L开始Tail_pointer List_tail;List_head (LinkList*)malloc(sizeof(LinkList)); //List_head构建新节点List_head-next NULL;while(newNode ! NULL){Tail_pointer-next newNode; //List_tail尾指针指向新节点Tail_pointer newNode; //①尾指针Tail_pointer后移,构建完成newNode newNode-next; //新节点后移rearNode newNode-next; //新节点后继信息存储newNode-next List_head-next; //新节点头插法插入List_head-next newNode;newNode rearNode; //书接上回}Tail_pointer-next NULL;
}int main()
{LinkList *L1, *L2,*L;ElemType a[10] {1,10,2,9,3,8,4,7,5,6};CreatList_Tail(L, a, 10);printf(输出L表结果:);DisplayLinkList(L);separate_LinkList(L,L1,L2);printf(L1表结果);DisplayLinkList(L1);printf(L2结果);DisplayLinkList(L2);return 0;} singlelist.cpp 单链表函数库 #include singlelist.h/**************************************************
①函数名: CreatList_Head
功 能: 头插法建立单链表
参 数: (1)LinkList *L: 传入的单链表指针地址(2)ElemType Array_used[]:要用来建表的数组(3)int Array_number: 数组的长度
返回值: 无
**************************************************/
void CreatList_Head(LinkList *L, ElemType Array_used[], int Array_number)
{int counter;LinkList *newnode;L (LinkList *)malloc(sizeof(LinkList)); //创建头结点L-next NULL;for(counter 0; counter Array_number; counter){newnode (LinkList *)malloc(sizeof(LinkList)); //创建新节点newnode-data Array_used[counter];newnode-next L-next; //将newnode插在原开始结点之前,头结点之后L-next newnode;}
}
/**************************************************
②函数名: CreatList_Tail
功 能: 尾插法建立单链表
参 数: (1)LinkList *L: 传入的单链表指针地址(2)ElemType Array_used[]:要用来建表的数组(3)int Array_number:数组的长度
返回值: 无
**************************************************/
void CreatList_Tail(LinkList *L, ElemType Array_used[], int Array_number)
{int counter;LinkList *newnode,*tailnode;L (LinkList *)malloc(sizeof(LinkList));//创建头结点L-next NULL;tailnode L; //尾结点tailnode始终指向终端结点,开始指向头结点for(counter 0; counter Array_number; counter){newnode (LinkList *)malloc(sizeof(LinkList)); //创建新节点newnode-data Array_used[counter];tailnode-next newnode; //将新节点插入到尾结点之后tailnode newnode; //更新尾结点}tailnode-next NULL; //终端结点next域置空
}/**************************************************
③函数名: DisplayLinkList
功 能: 输出单链表
参 数: (1)LinkList *L:将要输出的单链表
返回值: 无
**************************************************/void DisplayLinkList(LinkList *L)
{LinkList *shownode;shownode L-next;while(shownode ! NULL){printf(%d ,shownode-data);shownode shownode-next; //一直遍历,直到指向尾-newt NULL}printf(\n);
}
/**************************************************
④函数名: DestroyLinkList
功 能: 销毁单链表
参 数: (1)LinkList *L:要销毁的单链表
注意:① 等到指引下一个节点的指针为Null时就跳出,避免出现野指针,此时再销毁destroyNode② 避免断开联系,记录 销毁节点的下一个节点
返回值: 无
**************************************************/
void DestroyLinkList(LinkList *L)
{LinkList *destoryNode,*nextNode;destoryNode L;nextNode destoryNode-next;while(nextNode ! NULL) //①{free(destoryNode);destoryNode nextNode;nextNode destoryNode-next; //②}free(destoryNode);}
/**************************************************
⑤函数名: InitLinkList
功 能: 初始化单链表
参 数: LinkList *L:要被初始化的链表指针地址
返回值: 无
**************************************************/
void InitLinkList(LinkList *L)
{L (LinkList *)malloc(sizeof(LinkList));//创建头结点L-next NULL;
}
/**************************************************
⑥函数名: LinkListEmpty
功 能: 判断单链表是否为空
参 数: (1)LinkList *L:要判断的单链表
返回值: bool: 是否为空? treu:false
**************************************************/
bool LinkListEmpty(LinkList *L)
{return (L-next NULL);
}/**************************************************
⑦函数名: LinkListLength
功 能: 返回单链表L中数据节点的个数
参 数: LinkList *L:要计算的数据节点
返回值: int: 线性表数据节点个数值
**************************************************/
int LinkListLength(LinkList *L)
{int counter 0;LinkList *nowNode L;while(nowNode-next ! NULL){counter;nowNode nowNode-next;}return counter;
}/**************************************************
⑧函数名: GetLocateValue
功 能: 求特定位置的数据元素值
参 数: (1)LinkList *L:要找的单链表(2)int location:所要找的位置(3)ElemType value: 传递回所要找的值
注意: ① 判断跳出的时候, 是查找成功, 还是抵达末尾② counter 要找到序号,则跳出,所以counter location ,nowNode指向的节点为空,则到末尾,则跳出③④ 这两条语句, 所指向的序号和节点, 是同步的, 位置到或者此节点为空,则跳出
返回值: bool: 是否查找成功? true:false
**************************************************/
bool SpecificLocate_Value(LinkList *L,int location, ElemType value)
{int counter 0;LinkList *nowNode L;while(counter location nowNode ! NULL)//②{counter; //③ 当前计数的节点nowNode nowNode-next;//④当前遍历到的节点}if(nowNode NULL) //①{return false;}else{value nowNode-data;return true;}}/**************************************************
⑨函数名:SpecificValue_Location
功 能: 查找特定数据值的节点,并返回其位置
参 数: (1)LinkList *L: 被查找的单链表(2)ElemType e:
注 意: ①从头结点后的第一个节点开始找②while循环内的两条语句是同步指向的③当nowNode为空时(到达末尾仍未找到), counter作废④当nowNode不为空时,跳出时, counter表示所指向节点存在,并符合所需
返回值:
**************************************************/
int SpecificValue_Location(LinkList *L, ElemType value)
{int counter 1;LinkList *nowNode L-next; //①while(nowNode ! NULL nowNode-data ! value){nowNode nowNode-next;counter; //②}if(nowNode NULL) //③{return 0;}else //④{return counter;}}
/**************************************************
⑩函数名: LinkList_InsertElement
功 能: 在单链表特定位置插入节点
参 数: (1)LinkList *L:要插入的单链表(2)int location:要插入的位置(3) ElemType value:插入的数据
思路: 先在单链表L中,找到第 i-1个节点(不算头结点),若存在这样的节点,将值为value的节点 插入到其后面
注意: ① 计数器和 nowNode是同步往后移动(从L-next开始算第一个节点),直到 找到counter location-1,②此时 nowNode不为空,则此时nowNode指向要插入位置的 前一个节点③ 覆盖指针前, 牢记 nowNode-next里面存放的是后继节点信息,所以要先处理newNode-next nowNode-next;然后我们才能再把 nowNode-next指向新节点 newNode
返回值: bool: 是否存在第i-1个节点,并插入成功? true : false
**************************************************/
bool LinkList_InsertElement(LinkList *L, int location, ElemType value)
{int counter 0;LinkList *nowNode L;LinkList *newNode;while((counter (location-1)) (nowNode ! NULL)) //①{counter;nowNode nowNode-next;}if(nowNode NULL)//②{return false;}else{newNode (LinkList *)malloc(sizeof(LinkList));newNode-data value;newNode-next nowNode-next;//③nowNode-next newNode;return true;}
}
/**************************************************
(11)函数名: LinkList_Delete_Location
功 能: 删除特定位置的节点元素
参 数: (1)LinkList *L:被删除的单链表 (2)int location:特定位置(3) ElemType value:被删除的元素值
思路: 找到第location-1个元素, 存储第locataion个元素值(判断null),然后free链接 location-1 和 location1
注意: ① counter和指针节点是同步的,要么找到location-1个节点,要么到末尾② 虽然可能找到location-1个元素,其可能是最后一个元素,从而导致删除失败需要判断一下,deleteNode是否为空,才能得出是否任务成功③ 指针覆盖还是老生常谈,先存储一下deleteNode(方便free),然后指针交替,然后free
返回值: bool: 是否删除成功? true:false
**************************************************/
bool LinkList_Delete_Location(LinkList *L,int location, ElemType value)
{int counter 0;LinkList *nowNode L;LinkList *deleteNode;while(counter (location-1) nowNode ! NULL) //①{counter;nowNode nowNode-next;}if(nowNode NULL){return false;}else{deleteNode nowNode-next;if(deleteNode NULL) //②{return false;}value deleteNode-data;nowNode-next deleteNode-next; //③free(deleteNode);return true;}
}/**************************************************
(12)函数名: DeleteMaxNode
功 能: 删除单链表中最大的一个节点
参 数: (1)LinkList *L:要删除节点的单链表
思路: 四个指针, 最大指针,最大指针前一个节点目前遍历的指针,遍历指针的前一个节点, 边比较,边替换,边遍历
注意:①避免只有一个头结点,造成空指针替换异常②③ 顺序不能变,因为③跳出的时候, 会利用到while的非空条件,避免对比的时候, 出现野指针,直到为空时,即可直接跳出,非空则比较替换
返回值:是否删除成功 ? true:false
**************************************************/
bool DeleteMaxNode(LinkList *L)
{LinkList *nowNode,*preNode;LinkList *maxNode,*preMaxNode;nowNode L-next;preNode L;maxNode nowNode;preMaxNode preNode;if(nowNode NULL) //①{return false;}while(nowNode ! NULL) //直到末尾{if(nowNode-data maxNode-data) //②{maxNode nowNode;preMaxNode preNode;}preNode nowNode; //接着走下一个节点nowNode nowNode-next; //③}preMaxNode-next maxNode-next;free(maxNode);return true;
}/**************************************************
(13)函数名:LinkList_sorting
功 能:对单链表中元素进行排序(至少有2个数据节点)
参 数:LinkList *L:要进行排序的单链表
注意: ① 空表,或者只有一个数据节点,则不需要排序,返回false② 开始节点必须是头结点,因为我们会用到start_compare-next,③ 把数据节点(第二个数据节点及以后)和原始链表(头结点一个数据节点)④ 在有序表中,一直找到比前一个节点大,比后一个节点小的空挡,所以时刻对比start_compare-next-data, 并且start_compare-next不能为空(为空代表到达末尾,交替空指针)⑤ 顺序不能变, 避免丢失有序表后续信息(指针覆盖的一句话)
详细链接:https://blog.csdn.net/qq_57484399/article/details/127141307
返回值:bool: 是否符合排序标准,并排序成功 ? true: false
**************************************************/
bool LinkList_sorting(LinkList *L)
{LinkList *compare,*start_compare,*Remaining_node;if(L-next NULL || L-next-next NULL)//①保证至少有2个数据节点{return false;}compare L-next-next;start_compare L; //②开始节点必须是头结点Remaining_node compare-next;L-next-next NULL; //③把数据节点(第二个数据节点及以后)和原始链表(头结点一个数据节点)while(compare ! NULL){Remaining_node compare-next;start_compare L;while((start_compare-next ! NULL) (compare-data start_compare-next-data)){start_compare start_compare-next;} //④compare-next start_compare-next;start_compare-next compare; //⑤compare Remaining_node;}return true;}singlelist.h 单链表函数库头文件 #ifndef SINGLELIST_H_INCLUDE
#define SINGLELIST_H_INCLUDE#include stdio.h
#include malloc.htypedef int ElemType; //定义单链表节点类型typedef struct LNode
{ElemType data;struct LNode *next; //指向后继节点}LinkList;
//①头插法建立单链表
void CreatList_Head(LinkList *L, ElemType Array_used[], int Array_number);
//②尾插法建立单链表
void CreatList_Tail(LinkList *L, ElemType Array_used[], int Array_number);
//③输出单链表
void DisplayLinkList(LinkList *L);
//④销毁单链表
void DestroyLinkList(LinkList *L);
//⑤ 初始化线性表
void InitLinkList(LinkList *L);
//⑥ 判断线性表是否为空表
bool LinkListEmpty(LinkList *L);
//⑦ 返回单链表L中数据节点的个数
int LinkListLength(LinkList *L);
//⑧ 求线性表L中指定位置的某个数据元素
bool SpecificLocate_Value(LinkList *L,int location, ElemType value);
//⑨ 按元素值查找特定元素的位置
int SpecificValue_Location(LinkList *L, ElemType value);
//⑩ 把元素插入到特定位置
bool LinkList_InsertElement(LinkList *L, int location, ElemType value);
//(11) 删除特定位置的节点元素
bool LinkList_Delete_Location(LinkList *L,int location, ElemType value);
//(12)单链表删除其中其最大节点元素
bool DeleteMaxNode(LinkList *L);
//(13)对单链表中元素进行排序(至少有2个数据节点)
bool LinkList_sorting(LinkList *L);
#endif // SINGLELIST_H_INCLUDE代码运行结果:
