当前位置: 首页 > news >正文

江苏城乡建设局网站秦皇岛市人口

江苏城乡建设局网站,秦皇岛市人口,wordpress设置首页文章,网络规划设计师电子版教材2019年(单链表#xff09; 41.(13分)设线性表L(a1,a2,a3,...,a(n-2),a(n-1),an)采用带头结点的单链表保存#xff0c;链表中的结点定义如下#xff1a; typedef struct node {int data;struct node *next; } NODE; 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法 41.(13分)设线性表L(a1,a2,a3,...,a(n-2),a(n-1),an)采用带头结点的单链表保存链表中的结点定义如下 typedef struct node {int data;struct node *next; } NODE; 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法重新排列L中的各个结点得到线性表L(a1,an,a2,a(n-1),a3,a(n-2),...)。要求 (1)给出算法的基本设计思想 我们将n用数字代入进去比如n7那么L也就是如下图所示 a1a2a3a4a5a6a7 重新排列组合之后的L a1a7a2a6a3a5a4 很容易就能发现一下规律将链表L断开断链将链表尾进行反转(逆置)最后重新组合成一条新的链表。这个我们用三个函数(list_spilt、list_reverse、list_merge)来对链表L进行操作。 (2)根据设计思想采用C或C语言描述算法关键之处给出注释 环境Visual Studio 2022 语言C 代码如下图所示 链表断链 //链表断链 void list_spilt(LinkList L, LinkList L2) {LinkList q, p;L2 (LinkList)malloc(sizeof(Lnode));//将p和q进行初始化p q L-next;//需要对当前指针进行判断//如果当前指针为空的情况//开始遍历while (p) {p p-next;//防止链表只有一个结点的情况if (p NULL) {break;}p p-next;//为了偶数个的情况进行判断if (p NULL) {break;}q q-next;}//L2的相关操作//将L2的链表头节点指向当前链表的中间结点qL2-next q-next;//将中间结点q的next置为NULL(即为L链表的断链)q-next NULL; } 顾名思义就是将链表一分为二这里我们用快慢指针快指针p走两步慢指针q走一步保证快指针始p终走的比慢指针q多一个单位因此 ,循环的条件就是快指针p不为空考虑到p为空的情况循环即结束。 当进入到第四次循环也就是p-nextNULL的时候此时q-next指向a4如上图所示。 从q这里断链L2中的数据也就包含a5,a6,a7。 时间复杂度因为p每次移动两步(即为两个结点)故其循环的次数就是n/2忽略首项系数就是O(n)。 注意但凡涉及到链表的结构修改操作需要在函数的形参上加上(取地址符)C的引用操作 链表反转(逆置) //链表反转(逆置) void list_reverse(LinkList L2) {LinkList r, s, t;r L2-next;//链表为空的情况if (r NULL) return;s r-next;//链表只有一个结点的时候if (s NULL) return;t s-next;while (t) {s-next r;//指针反转r s;s t;t t-next;}s-next r;//逆置后链表的第一个结点即为尾结点L2-next-next NULL;//L2指向现链表的头结点sL2-next s; } 这里我们用三个指针操控r,s,t。由于链表的特性我们只需要改变指针的指向即可完成反转操作。需要判断两种情况。即链表为空的情况和链表只有一个结点的情况。直接返回即可。 这里我们用户距离最远的t作为循环的结束条件只要tNULL,循环即结束。 将s-next指向r将s赋给rt赋给stt-next即可完成一次逆置操作但因为一开始t是领先r两个位置的故判断tNULL循环结束时实际上还有一次逆置操作没有完成这里我们只需要将r的地址赋给s-next即可这样便完成了逆置操作。剩下的就是些收尾工作。 时间复杂度reverse函数只遍历了L2链表遍历次数也是n/2,故时间复杂度为O(n) 注意原先的链表头结点已经变成了尾结点我们需要手动将其next置为空 而此时的链表头既是s,将s的地址赋给L2-next即可完成链表逆置的全部工作。 链表合并 //链表合并 void list_merge(LinkList L, LinkList L2) {LinkList p, q, pcur;p L2-next;//p指L2的第一个结点pcur L-next;//pcur始终指向组后的链表q pcur-next;//q指向L1的第一个结点while (p q) {pcur-next p;p p-next;pcur pcur-next;pcur-next q;q q-next;pcur pcur-next;}//任何一个链表都可能剩余一个结点放进来即可if (p ! NULL) {pcur-next p;}if (q ! NULL) {pcur-next q;} } 链表合并操作我们同样需要三个指针一个指向L一个指向L2一个指向L’循环的条件判断L和L2链表当前不为空 因为一开始即对pcur进行赋值为L-next故往后操作只需要直接让其next指向L2-next也是p即可。个人感觉有点两个字符串交叉合并的意思。 一次操作 pcur指向p(L2-next),p往后移动一步再让pcur往后移动一步让pcur指向q(L-next)q往后移一步pcur再往后移动一步 pcur-next p;        p p-next;        pcur pcur-next;        pcur-next q;        q q-next;        pcur pcur-next;时间复杂度merge函数while的循环次数也是n/2,故时间复杂度为O(n)  即是以上六步最后奇数个数据的链表会剩余一个结点的情况我们直接将其放入新链表L’即可。 以下是全部代码 #includestdio.h #includestdlib.h //考研链表题练习 typedef int ElemType; typedef struct Lnode {ElemType data;struct Lnode* next; }Lnode, * LinkList;//尾插法建立链表 void list_tail_insert(LinkList L) {L (LinkList)malloc(sizeof(Lnode));ElemType num;LinkList q, p;q L;scanf_s(%d, num);while (num ! 9999) {p (LinkList)malloc(sizeof(Lnode));p-data num;q-next p;q p;scanf_s(%d, num);}p-next NULL; } //链表断链 void list_spilt(LinkList L, LinkList L2) {LinkList q, p;L2 (LinkList)malloc(sizeof(Lnode));//将p和q进行初始化p q L-next;//需要对当前指针进行判断//如果当前指针为空的情况//开始遍历while (p) {p p-next;//防止链表只有一个结点的情况if (p NULL) {break;}p p-next;//为了偶数个的情况进行判断if (p NULL) {break;}q q-next;}//L2的相关操作//将L2的链表头节点指向当前链表的中间结点qL2-next q-next;//将中间结点q的next置为NULL(即为L链表的断链)q-next NULL; } //链表反转(逆置) void list_reverse(LinkList L2) {LinkList r, s, t;r L2-next;//链表为空的情况if (r NULL) return;s r-next;//链表只有一个结点的时候if (s NULL) return;t s-next;while (t) {s-next r;//指针反转r s;s t;t t-next;}s-next r;//逆置后链表的第一个结点即为尾结点L2-next-next NULL;//L2指向现链表的头结点sL2-next s; } //链表合并 void list_merge(LinkList L, LinkList L2) {LinkList p, q, pcur;p L2-next;//p指L2的第一个结点pcur L-next;//pcur始终指向组后的链表q pcur-next;//q指向L1的第一个结点while (p q) {pcur-next p;p p-next;pcur pcur-next;pcur-next q;q q-next;pcur pcur-next;}//任何一个链表都可能剩余一个结点放进来即可if (p ! NULL) {pcur-next p;}if (q ! NULL) {pcur-next q;} }//链表输出 void list_printf(LinkList L) {L L-next;while (L) {printf(%3d , L-data);L L-next;} } int main() {//建立链表LinkList L, L2;//尾插法list_tail_insert(L);list_printf(L);//链表断链list_spilt(L, L2);printf(\n----------------list_spilt-----------------\n);list_printf(L2);//链表逆置list_reverse(L2);printf(\n----------------list_reverse---------------\n);list_printf(L2);//链表合并list_merge(L, L2);printf(\n----------------list_merge-----------------\n);list_printf(L);return 0; } 代码效果 偶数情况: 单数情况 (3)说明你所设计的算法的时间复杂度 以上三个函数总的运行次数为(3/2)n,忽略首项系数即为O(n)
http://www.w-s-a.com/news/680166/

相关文章:

  • 流量网站怎么做的济南优化排名公司
  • 保定网站制作套餐设计师导航网站大全
  • 惠州 商城网站建设石家庄新闻广播在线收听
  • 洪山网站建设域名购买之后怎么做网站
  • 北京网站建设公司服务哪家好wap是什么意思?
  • 怎么看公司网站做的好不好哦wordpress页面目录下
  • 做装修业务呢有多少网站平台搭建是什么
  • 潍坊优化网站排名淘宝做网站被骗
  • 建设专业网站的利弊免费logo设计生成器下载
  • 怎么在备案号添加网站网页设计动画网站
  • 网站开发 只要wordpress滑动注册
  • 跨境电商运营主要做什么静态网站如何做优化
  • 南充网站建设网站网站备案安全责任书是谁盖章
  • 怎么将网站设置为首页网站子目录怎么做
  • 做网站交互wordpress信息导出
  • 如何自己做企业网站做外贸登录国外网站
  • 郑州炫彩网站建设网站集约化建设调研报告
  • 2016年两学一做教育网站优良的定制网站建设制作商
  • 自己做网站需要哪些流程网站建设服务费如何做会计分录
  • 莆田建站培训用手机制作游戏的app软件
  • 中山建网站找哪家wordpress采集图片插件
  • 网站首页做后台链接有什么好用的模拟建站软件
  • 宁波有没有开发网站的公司网站上线除了备案还需要什么
  • 网站备案授权wordpress默认主体设置
  • 厦门微信网站广州推广策划公司
  • 集团公司网站开发asp网站怎么运行
  • 广州短视频网站开发东莞市建设信息网
  • 建设网站如果赚钱电脑可以做服务器部署网站吗
  • 网站建设的编程专门做面包和蛋糕的网站
  • 档案网站建设比较分析南京建站公司