排序在C链表 [英] Sorting a linked list in C
问题描述
我试图通过找到最大值，从它的位置删除，然后在列表的顶部将其插入到排序链表
我遇到的困难是在顶部的实际删除和插入。这个问题似乎是在包含sortlist中的函数中while循环if条件，但我不知道如何解决它。
任何帮助将是AP preciated。
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;typedef结构节点{
INT NUM;
结构节点*接下来的;
}节点，* NODEPTR;无效的printList（NODEPTR NP）;
NODEPTR makeList（无效）;
NODEPTR makeNode（INT N）;
NODEPTR sortlist中（NODEPTR清单）;诠释主要（无效）{
NODEPTR清单;
的printf（为列表（0结束）\\ n输入数字）;
清单= makeList（）;
的printList（名单）;
清单= sortlist中（清单）;
的printList（名单）;
返回0;
}NODEPTR makeList（无效）{
NODEPTR makeNode（INT），NP，顶，最后;
INT N;
顶= NULL;
如果（scanf的（％d个，＆放大器;！N）= 1）N = 0;
而（N！= 0）{
NP = makeNode（N）;
如果（上== NULL）顶部= NP;
最后所其他＆gt;接下来= NP;
最后= NP;
如果（scanf的（％d个，＆放大器;！N）= 1）N = 0;
}
返回顶部;
}
无效的printList（NODEPTR NP）{
而（NP！= NULL）{
的printf（％d个\\ N，NP-GT＆; NUM）;
NP = NP-＆gt;接下来，
}
}NODEPTR makeNode（INT N）{
NODEPTR NP =（NODEPTR）的malloc（sizeof运算（节点））;
NP-GT＆; NUM = N;
NP-＆gt;接着= NULL;
返回NP;
}NODEPTR sortlist中（NODEPTR名单）{
NODEPTR顶部=清单;
NODEPTR CURR = NULL;
NODEPTR最大;
NODEPTR preV;
preV = NULL;
CURR =顶部;
最大=顶部; 而（CURR！= NULL）{
preV = CURR;
如果（curr-＆GT; NUM＆GT; largest-＆GT; NUM）{
最大= CURR;
preV-＆gt;接下来= curr-＆gt;接下来，
largest-＆gt;接下来=顶部;
}
CURR = curr-＆gt;接下来，
}
如果（$ P $光伏== NULL）{
largest-＆gt;接下来=顶部;
最大的回报;
}
最大的回报;
}
有在 sortlist中函数的问题。
此功能只放一些大的节点列表的开头。它不soting所有列表。您可以在一个排序算法来排序文件：快速排序/冒泡/ ...
我把code在这个答案到底在做一个排序。
这里是一个code做排序列表：
//它与第一个替换最大节点然后做与子表相同的操作（列表的第一个元素）
NODEPTR sortlist中（NODEPTR名单）
{//
如果（名单== NULL ||列表 - ＆gt;接下来== NULL）
返回列表; //列表进行排序。//与第一取代最大节点：// 1 - 找到最大的节点：
NODEPTR CURR，规模最大，最大的preV;
CURR =清单;
最大=清单;
preV =清单;
最大的preV =清单;
而（CURR！= NULL）{
如果（curr-＆GT; NUM＆GT; largest-＆GT; NUM）{
最大的preV = preV;
最大= CURR;
}
preV = CURR;
CURR = curr-＆gt;接下来， }
//最大节点处于最大。// 2 - 交换firt节点，节点最大：
NODEPTR TMP;
如果（最大！=名单）
{
最大的preV-＆gt;接下来=清单;
TMP =列表 - ＆gt;接下来，
列表 - ＆gt;接下来= largest-＆gt;接下来，
largest-＆gt;接下来= TMP;
}//现在最大是列表的第一个节点。//与子列表中再次调用该函数：
//列表减去它的第一个节点：
largest-＆gt;接下来= sortlist中（largest-＆gt;下面）;
最大的回报;
}
I'm trying to sort a linked list by finding the largest value, deleting it from its position, and then inserting it at the top of the list.
The difficulty I'm running into is the actual deleting and inserting at the top. The issue seems to be in the if condition in the while loop contained within the sortList function, but I'm not sure how to fix it.
Any help would be appreciated.
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int num;
struct node *next;
} Node, *NodePtr;
void printList(NodePtr np);
NodePtr makeList(void);
NodePtr makeNode(int n);
NodePtr sortList(NodePtr list);
int main(void) {
NodePtr list;
printf("Enter numbers for the list (0 to end)\n");
list = makeList();
printList(list);
list = sortList(list);
printList(list);
return 0;
}
NodePtr makeList(void) {
NodePtr makeNode(int), np, top, last;
int n;
top = NULL;
if(scanf("%d", &n) != 1)n = 0;
while(n != 0) {
np = makeNode(n);
if(top == NULL)top = np;
else last->next = np;
last = np;
if(scanf("%d", &n)!=1)n=0;
}
return top;
}
void printList(NodePtr np) {
while(np != NULL) {
printf("%d\n", np->num);
np = np->next;
}
}
NodePtr makeNode(int n) {
NodePtr np = (NodePtr)malloc(sizeof(Node));
np->num = n;
np->next = NULL;
return np;
}
NodePtr sortList(NodePtr list) {
NodePtr top = list;
NodePtr curr = NULL;
NodePtr largest;
NodePtr prev;
prev = NULL;
curr = top;
largest = top;
while(curr != NULL) {
prev = curr;
if(curr->num > largest->num) {
largest = curr;
prev->next = curr->next;
largest->next = top;
}
curr = curr->next;
}
if(prev == NULL) {
largest->next = top;
return largest;
}
return largest;
}
There is issues in the sortList function.
This function only put some large nodes in the beginning of the list. It is not soting all the list. you can you a sort algorithm to sort the file : quicksort/ bubblesort/... i put a code doing a sort in the end of this answer.
here is a code doing the sort of the list :
//it is replacing largest node with first one then doing the same operation with sublist (list-first element)
NodePtr sortList(NodePtr list)
{
//
if(list == null || list->next == null)
return list; // the list is sorted.
//replace largest node with the first :
//1- find largest node :
NodePtr curr, largest,largestPrev;
curr = list;
largest = list;
prev = list;
largestPrev = list;
while(curr != NULL) {
if(curr->num > largest->num) {
largestPrev = prev;
largest = curr;
}
prev = curr;
curr = curr->next;
}
//largest node is in largest.
//2- switching firt node and largest node :
NodePtr tmp;
if(largest != list)
{
largestPrev->next = list;
tmp = list->next;
list->next = largest->next;
largest->next = tmp;
}
// now largest is the first node of the list.
// calling the function again with the sub list :
// list minus its first node :
largest->next = sortList(largest->next);
return largest;
}
这篇关于排序在C链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
