将公司网站建设成,做毕设最常去的几个网站,全球电子商务公司排行,怎么做教育培训网站功能#xff1a;选择排序(由小到大)返回#xff1a;指向链表表头的指针*//*选择排序的基本思想就是反复从还未排好序的那些节点中#xff0c;选出键值(就是用它排序的字段#xff0c;我们取学号num为键值)最小的节点#xff0c;依次重新组合成一个链表。我认为写链表这类程…功能选择排序(由小到大)返回指向链表表头的指针*//*选择排序的基本思想就是反复从还未排好序的那些节点中选出键值(就是用它排序的字段我们取学号num为键值)最小的节点依次重新组合成一个链表。我认为写链表这类程序关键是理解head存储的是第一个节点的地址head-next存储的是第二个节点的地址任意一个节点p的地址只能通过它前一个节点的next来求得。单向链表的选择排序图示----[1]----[3]----[2]。。。----[n]----[NULL](原链表)head 1-next 3-next 2-next n-next----[NULL](空链表)firsttail----[1]----[2]----[3]。。。----[n]----[NULL](排序后链表)first 1-next 2-next 3-next tail-next图10有N个节点的链表选择排序1、先在原链表中找最小的找到一个后就把它放到另一个空的链表中2、空链表中安放第一个进来的节点产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点)3、继续在原链表中找下一个最小的找到后把它放入有序链表的尾指针的next,然后它变成其尾指针*/struct student *SelectSort(struct student *head){struct student *first; /*排列后有序链的表头指针*/struct student *tail; /*排列后有序链的表尾指针*/struct student *p_min; /*保留键值更小的节点的前驱节点的指针*/struct student *min; /*存储最小节点*/struct student *p; /*当前比较的节点*/first NULL;while (head ! NULL) /*在链表中找键值最小的节点。*/{/*注意这里for语句就是体现选择排序思想的地方*/for (phead,minhead; p-next!NULL; pp-next) /*循环遍历链表中的节点找出此时最小的节点。*/{if (p-next-num num) /*找到一个比当前min小的节点。*/{p_min p; /*保存找到节点的前驱节点显然p-next的前驱节点是p。*/min p-next; /*保存键值更小的节点。*/}}/*上面for语句结束后就要做两件事一是把它放入有序链表中二是根据相应的条件判断安排它离开原来的链表。*//*第一件事*/if (first NULL) /*如果有序链表目前还是一个空链表*/{first min; /*第一次找到键值最小的节点。*/tail min; /*注意尾指针让它指向最后的一个节点。*/}else /*有序链表中已经有节点*/{tail-next min; /*把刚找到的最小节点放到最后即让尾指针的next指向它。*/tail min; /*尾指针也要指向它。*/}/*第二件事*/if (min head) /*如果找到的最小节点就是第一个节点*/{head head-next; /*显然让head指向原head-next,即第二个节点就OK*/}else /*如果不是第一个节点*/{p_min-next min-next; /*前次最小节点的next指向当前min的next,这样就让min离开了原链表。*/}}if (first ! NULL) /*循环结束得到有序链表first*/{tail-next NULL; /*单向链表的最后一个节点的next应该指向NULL*/}head first;return head;}/*功能直接插入排序(由小到大)返回指向链表表头的指针*//*直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值(就是用它排序的字段我们取学号num为键值)排好序的对于节点n在这个序列中找插入位置使得n插入后新序列仍然有序。按照这种思想依次对链表从头到尾执行一遍就可以使无序链表变为有序链表。单向链表的直接插入排序图示----[1]----[3]----[2]。。。----[n]----[NULL](原链表)head 1-next 3-next 2-next n-next----[1]----[NULL](从原链表中取第1个节点作为只有一个节点的有序链表)head图11----[3]----[2]。。。----[n]----[NULL](原链表剩下用于直接插入排序的节点)first 3-next 2-next n-next图12----[1]----[2]----[3]。。。----[n]----[NULL](排序后链表)head 1-next 2-next 3-next n-next图13有N个节点的链表直接插入排序1、先在原链表中以第一个节点为一个有序链表其余节点为待定节点。2、从图12链表中取节点到图11链表中定位插入。3、上面图示虽说画了两条链表其实只有一条链表。在排序中实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。这一点请读者务必搞清楚要不然就可能认为它和上面的选择排序法一样了。*/struct student *InsertSort(struct student *head){struct student *first; /*为原链表剩下用于直接插入排序的节点头指针*/struct student *t; /*临时指针变量插入节点*/struct student *p; /*临时指针变量*/struct student *q; /*临时指针变量*/first head-next; /*原链表剩下用于直接插入排序的节点链表可根据图12来理解。*/head-next NULL; /*只含有一个节点的链表的有序链表可根据图11来理解。*/while (first ! NULL) /*遍历剩下无序的链表*/{/*注意这里for语句就是体现直接插入排序思想的地方*/for (tfirst, qhead; ((q!NULL) (q-num num)); pq, qq-next); /*无序节点在有序链表中找插入的位置*//*退出for循环就是找到了插入的位置*//*注意按道理来说这句话可以放到下面注释了的那个位置也应该对的但是就是不能。原因你若理解了上面的第3条就知道了。*/first first-next; /*无序链表中的节点离开以便它插入到有序链表中。*/if (q head) /*插在第一个节点之前*/{head t;}else /*p是q的前驱*/{p-next t;}t-next q; /*完成插入动作*//*first first-next;*/}return head;}/*功能冒泡排序(由小到大)返回指向链表表头的指针*//*直接插入排序的基本思想就是对当前还未排好序的范围内的全部节点自上而下对相邻的两个节点依次进行比较和调整让键值(就是用它排序的字段我们取学号num为键值)较大的节点往下沉键值较小的往上冒。即每当两相邻的节点比较后发现它们的排序与排序要求相反时就将它们互换。单向链表的冒泡排序图示----[1]----[3]----[2]。。。----[n]----[NULL](原链表)head 1-next 3-next 2-next n-next----[1]----[2]----[3]。。。----[n]----[NULL](排序后链表)head 1-next 2-next 3-next n-next图14有N个节点的链表冒泡排序任意两个相邻节点p、q位置互换图示:假设p1-next指向p那么显然p1-next-next就指向q,p1-next-next-next就指向q的后继节点我们用p2保存p1-next-next指针。即p2p1-next-next则有[ ]----[p]----------[q]----[ ](排序前)p1-next p1-next-next p2-next图15[ ]----[q]----------[p]----[ ](排序后)图161、排序后q节点指向p节点在调整指向之前我们要保存原p的指向节点地址即p2p1-next-next2、顺着这一步一步往下推,排序后图16中p1-next-next要指的是p2-next,所以p1-next-nextp2-next;3、在图15中p2-next原是q发出来的指向排序后图16中q的指向要变为指向p的而原来p1-next是指向p的所以p2-nextp1-next;4、在图15中p1-next原是指向p的排序后图16中p1-next要指向q,原来p1-next-next(即p2)是指向q的所以p1-nextp2;5、至此我们完成了相邻两节点的顺序交换。6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置这样我们不必每次都从头到尾的扫描只需要扫描到记录点为止。因为后面的都已经是排好序的了。*/struct student *BubbleSort(struct student *head){struct student *endpt; /*控制循环比较*/struct student *p; /*临时指针变量*/struct student *p1;struct student *p2;p1 (struct student *)malloc(LEN);p1-next head; /*注意理解我们增加一个节点放在第一个节点的前面主要是为了便于比较。因为第一个节点没有前驱我们不能交换地址。*/head p1; /*让head指向p1节点排序完成后我们再把p1节点释放掉*/for (endptNULL; endpt!head; endptp) /*结合第6点理解*/{for (pp1head; p1-next-next!endpt; p1p1-next){if (p1-next-num p1-next-next-num) /*如果前面的节点键值比后面节点的键值大则交换*/{p2 p1-next-next; /*结合第1点理解*/p1-next-next p2-next; /*结合第2点理解*/p2-next p1-next; /*结合第3点理解*/p1-next p2; /*结合第4点理解*/p p1-next-next; /*结合第6点理解*/}}}p1 head; /*把p1的信息去掉*/head head-next; /*让head指向排序后的第一个节点*/free(p1); /*释放p1*/p1 NULL; /*p1置为NULL保证不产生“野指针”即地址不确定的指针变量*/return head;}/*功能插入有序链表的某个节点的后面(从小到大)返回指向链表表头的指针*//*有序链表插入节点示意图----[NULL](空有序链表)head图18空有序链表(空有序链表好解决直接让head指向它就是了。)以下讨论不为空的有序链表。----[1]----[2]----[3]。。。----[n]----[NULL](有序链表)head 1-next 2-next 3-next n-next图18有N个节点的有序链表插入node节点的位置有两种情况一是第一个节点前二是其它节点前或后。----[node]----[1]----[2]----[3]。。。----[n]----[NULL]head node-next 1-next 2-next 3-next n-next图19node节点插在第一个节点前----[1]----[2]----[3]。。。----[node]。。。----[n]----[NULL]head 1-next 2-next 3-next node-next n-next图20node节点插在其它节点后*/struct student *SortInsert(struct student *head, struct student *node){struct student *p; /*p保存当前需要检查的节点的地址*/struct student *t; /*临时指针变量*/if (head NULL) /*处理空的有序链表*/{head node;node-next NULL;n 1; /*插入完毕节点总数加1*/return head;}p head; /*有序链表不为空*/while (p-num num p ! NULL) /*p指向的节点的学号比插入节点的学号小并且它不等于NULL*/{t p; /*保存当前节点的前驱以便后面判断后处理*/p p-next; /*后移一个节点*/}if (p head) /*刚好插入第一个节点之前*/{node-next p;head node;}else /*插入其它节点之后*/{t-next node; /*把node节点加进去*/node-next p;}n 1; /*插入完毕节点总数加1*/return head;}/*测试代码如下*//*测试SelectSort():请编译时去掉注释块*//*head SelectSort(head);Print(head);*//*测试InsertSort():请编译时去掉注释块*//*head InsertSort(head);Print(head);*//*测试BubbleSort():请编译时去掉注释块*//*head BubbleSort(head);Print(head);*//*测试SortInsert():上面创建链表输入节点时请注意学号num从小到大的顺序。请编译时去掉注释块*//*stu (struct student *)malloc(LEN);printf(/nPlease input insert node -- num,score: );scanf(%ld,%f,stu-num,stu-score);head SortInsert(head,stu);free(stu);stu NULL;Print(head);*/转载 。全部
