网站这么做,wordpress官网中文版下载,沧州机械类网站建设,企业管理培训课程机构有哪些一、实验内容 二、算法思想与算法实现
1、解题思想
#xff08;1#xff09;逆序创建链表La就是使用头插法创建一个链表#xff0c;所谓头插法就是在创建链表时始终将新元素插入到头结点之后#xff0c;而正序创建链表Lb就是使用尾插法创建一个链表#xff0c;所谓尾插法…一、实验内容 二、算法思想与算法实现
1、解题思想
1逆序创建链表La就是使用头插法创建一个链表所谓头插法就是在创建链表时始终将新元素插入到头结点之后而正序创建链表Lb就是使用尾插法创建一个链表所谓尾插法创建一个链表就是在创建链表时始终将新元素插入到表尾
2合并两个升序序列这个算法很基础这里不做叙述需要注意的是由于在创建La时我们是逆序创建的也就是说此时La是降序排列所以在做两个链表的合并操作之前我们需要先将链表La逆置
3删除Lc中的多余元素这里我们可以用一个指针p表示当前链表的结点然后用一个指针t指向第一个结点元素值不等于当前结点元素值的结点然后让结点p的next指针域指向t即可如下图所示 4逆置一个链表可以借助头插法创建链表的思想即扫描当前需要逆置的链表不断将当前结点插入到表头
2、算法实现
1定义链表结点
//定义链表节点
typedef struct LNode {int data; //数据域struct LNode* next; //指针域
}LNode,*LinkList;
2头插法创建链表
//使用头插法创建一个带头结点的链表当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList L) {//对链表进行初始化操作L (LNode*)malloc(sizeof(LNode) * 1);if (L NULL){return false;}L-next NULL;LNode* p NULL;int inputs 0;printf(请输入链表元素:\n);while (1){scanf(%d, inputs);if (inputs 666)break;p (LNode*)malloc(sizeof(LNode) * 1);if (p NULL){return false;}p-data inputs;p-next L-next;L-next p;}return true;
}3尾插法创建链表 //使用尾插法创建一个带头结点的链表当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList L)
{//对链表进行初始化操作L (LNode*)malloc(sizeof(LNode) * 1);if (L NULL)return false;L-next NULL;LNode* p, * t; //p指针用于建立新结点t用于指向当前链表的尾结点int inputs;t L;printf(请输入链表元素:\n);while (1){scanf(%d, inputs);if (inputs 666)break;p (LNode*)malloc(sizeof(LNode) * 1);if (p NULL)return false;p-data inputs;p-next NULL;t-next p;t p;}return true;
}
4合并两个升序链表
//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList Lc)
{LNode* a, * b, * c, * t;a La-next;b Lb-next;//初始化链表LcLc (LNode*)malloc(sizeof(LNode) * 1);if (Lc NULL)return false;Lc-next NULL;t Lc; //t指针指向Lc的尾部结点while (a ! NULL b ! NULL){c (LNode*)malloc(sizeof(LNode) * 1);if (c NULL)return false;if (a-data b-data){c-data a-data;c-next NULL;t-next c;t c;a a-next;}else{c-data b-data;c-next NULL;t-next c;t c;b b-next;}}while (a NULL b ! NULL){c (LNode*)malloc(sizeof(LNode) * 1);c-data b-data;c-next NULL;t-next c;t c;b b-next;}while (b NULL a ! NULL){c (LNode*)malloc(sizeof(LNode) * 1);c-data a-data;c-next NULL;t-next c;t c;a a-next;}return true;
}5删除链表中的重复元素
//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList L)
{//判断是否是空表if (L-next NULL)return false;LNode* p, * e NULL; //p指针用于记录当前结点e指针用于表示值等于当前结点的最后一个结点p L-next;while (p ! NULL){e p-next;if (e NULL)break;while (p-data e-data){LNode* temp e;e e-next;free(temp);}p-next e;p p-next; }return true;
}
6逆置一个链表
//逆置一个链表从头开始扫描一个链表不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList L)
{if (L-next NULL)return false;LNode* end L-next; //指向逆置以后的表尾元素LNode* p end-next; //指向当前元素while (p ! NULL){LNode* temp p-next;p-next L-next;L-next p;p temp;}end-next NULL;return true;
}
三、代码测试
完整测试代码
//用C语言编写程序其中Lb{2,4,6,8,10} La{1,2,3,4,5,6,8},
//(1)逆序创建链表La, 正序创建链表Lb; .
//(2)将La与Lb有序合并得到有序链表LcLc { 1,2,2,3,4,4,5,6,6,8,8,10 }
//(3)删除Lc中多余的重复元素使得所有元素只保留一个;
//(4)将链表Lc倒置并输出其内容。#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdlib.h
using namespace std;//定义链表节点
typedef struct LNode {int data; //数据域struct LNode* next; //指针域
}LNode,*LinkList;//使用头插法创建一个带头结点的链表当用户输入666时表示链表创建结束
bool List_HeadInsert(LinkList L) {//对链表进行初始化操作L (LNode*)malloc(sizeof(LNode) * 1);if (L NULL){return false;}L-next NULL;LNode* p NULL;int inputs 0;printf(请输入链表元素:\n);while (1){scanf(%d, inputs);if (inputs 666)break;p (LNode*)malloc(sizeof(LNode) * 1);if (p NULL){return false;}p-data inputs;p-next L-next;L-next p;}return true;
}//使用尾插法创建一个带头结点的链表当用户输入666时表示链表创建结束
bool List_TailInsert(LinkList L)
{//对链表进行初始化操作L (LNode*)malloc(sizeof(LNode) * 1);if (L NULL)return false;L-next NULL;LNode* p, * t; //p指针用于建立新结点t用于指向当前链表的尾结点int inputs;t L;printf(请输入链表元素:\n);while (1){scanf(%d, inputs);if (inputs 666)break;p (LNode*)malloc(sizeof(LNode) * 1);if (p NULL)return false;p-data inputs;p-next NULL;t-next p;t p;}return true;
}//合并两个有序链表
bool Merge_SortedLinkList(LinkList La, LinkList Lb, LinkList Lc)
{LNode* a, * b, * c, * t;a La-next;b Lb-next;//初始化链表LcLc (LNode*)malloc(sizeof(LNode) * 1);if (Lc NULL)return false;Lc-next NULL;t Lc; //t指针指向Lc的尾部结点while (a ! NULL b ! NULL){c (LNode*)malloc(sizeof(LNode) * 1);if (c NULL)return false;if (a-data b-data){c-data a-data;c-next NULL;t-next c;t c;a a-next;}else{c-data b-data;c-next NULL;t-next c;t c;b b-next;}}while (a NULL b ! NULL){c (LNode*)malloc(sizeof(LNode) * 1);c-data b-data;c-next NULL;t-next c;t c;b b-next;}while (b NULL a ! NULL){c (LNode*)malloc(sizeof(LNode) * 1);c-data a-data;c-next NULL;t-next c;t c;a a-next;}return true;
}//删除有序链表中的重复元素
bool DeleteRpeatElem(LinkList L)
{//判断是否是空表if (L-next NULL)return false;LNode* p, * e NULL; //p指针用于记录当前结点e指针用于表示值等于当前结点的最后一个结点p L-next;while (p ! NULL){e p-next;if (e NULL)break;while (p-data e-data){LNode* temp e;e e-next;free(temp);}p-next e;p p-next; }return true;
}//逆置一个链表从头开始扫描一个链表不断将当前结点插入到链表的开始位置
bool ReverseLinkList(LinkList L)
{if (L-next NULL)return false;LNode* end L-next; //指向逆置以后的表尾元素LNode* p end-next; //指向当前元素while (p ! NULL){LNode* temp p-next;p-next L-next;L-next p;p temp;}end-next NULL;return true;
}//顺序打印一个链表中的所有元素
bool PrintLinkList(LinkList L)
{if (L-next NULL)return false;LNode* p L-next;while (p ! NULL){printf(%d\t, p-data);p p-next;}printf(\n);return true;
}//测试程序
int main()
{LinkList La, Lb, Lc;//逆序创建链表La,即使用头插法创建链表LaList_HeadInsert(La);printf(链表La\n);PrintLinkList(La);//正序创建链表Lb即使用尾插法创建链表LbList_TailInsert(Lb);printf(链表Lb\n);PrintLinkList(Lb);//合并La和Lb//先逆序LaReverseLinkList(La);printf(逆序后的链表La\n);PrintLinkList(La);//调用函数合并La和LbMerge_SortedLinkList(La, Lb, Lc);printf(合并链表La和链表Lb得到的链表Lc\n);PrintLinkList(Lc);//删除Lc中的重复元素DeleteRpeatElem(Lc);printf(删除链表Lc中的重复元素的结果\n);PrintLinkList(Lc);//将Lc逆序ReverseLinkList(Lc);printf(将链表Lc逆序之后的结果\n);PrintLinkList(Lc);return 0;}
测试结果截图
