Выбор вида единственного связанного списка

Question

Мне нужно разработать алгоритм, чтобы сделать выборный вид единственного связанного списка, который не выделяет и не освобождает какую-либо память, делает ли этот код ниже? Как мне изменить этот код для использования для циклов вместо циклов while?

/************************** SortList ************************************ 

Description Arranges the singly linked list pointed to by List in 
natural order. It is assumed that the list has a dummy 
head node. 

The algorithm used is a linked variation of the selection 
sort and works like this: 
Start with EndSorted aimed at first node of list 

repeat 
Find smallest char between EndSorted and end of list 
Swap smallest element with char in EndSorted 
Change EndSorted to next node 
until we get to end of list 

None of the pointers in linked list are changed 

Parameters 
IN, List A pointer to a singly linked list with a dummy head node 
-----------------------------------------------------------------------*/ 
typedef Node* NodePtr; 
void SortList(NodePtr List) 
{ 
    NodePtr SmallNode;  //points to smallest char 
    NodePtr SearchNode;  //used to search each node in list 
    NodePtr EndSorted;  //points to list to sort 
    char TempCh; 
if (List->Link != NULL) //List is not empty 
    EndSorted = List->Link; //make EndSorted point to the beginning of List 

else //List is empty 
    EndSorted = List; //EndSorted points to dummy head Node and the following loop 

         //will never execute 

while (EndSorted->Link != NULL) //make sure EndSorted is not at the end of List 

{ 
    SmallNode = EndSorted; //give SmallNode a starting value 

    SearchNode = EndSorted->Link; //make SearchNode point to the Node after EndSorted 

    while (SearchNode != NULL) //make sure SearchNode is not at the end of List 
    { 
     if (SearchNode->Ch < SmallNode->Ch) //check the Ch value of the two Nodes 

      SmallNode = SearchNode; //if SearchNode -> Ch is smaller then SmallNode -> Ch 

            //make SmallNode point to SearchNode 

     SearchNode = SearchNode->Link; //advance SearchNode to the next Node 
    } 

    TempCh = EndSorted->Ch; //place the Ch value in EndSorted in TempCh 

    EndSorted->Ch = SmallNode->Ch; //swap SmallNode -> Ch with EndSorted -> Ch 

            //This places the smallest unsorted value in List at the beginning 
    SmallNode->Ch = TempCh; 

    EndSorted = EndSorted->Link; //advance EndSorted to the next Node 
} 
} 

Значит, это должно выглядеть так?

void SortList(NodePtr List) 
{ 
    NodePtr SmallNode;  //points to smallest char 
    NodePtr SearchNode;  //used to search each node in list 
    NodePtr EndSorted;  //points to list to sort 
    char TempCh; 

    if (List->Link != NULL) //Makes sure the list is not empty 
    { 
     /* (Points EndSorted at the first non-dummy node node; While EndSorted is not at the end of the list; 
     Advance EndSorted to the next node) */ 

     for (EndSorted = List->Link; EndSorted->Link != NULL; EndSorted = EndSorted->Link) 

     { 

      SmallNode = EndSorted; //Start SmallNode with the data of the first (Non-Dummy) Node 


      /*Points SearchNode at the Node after the Current EndSorted location; While Search Node is not at the end of the list; 
      Advance SearchNode to The next node*/ 

      for (SearchNode = EndSorted->Link; SearchNode != NULL; SearchNode = SearchNode->Link) 
      { 
       if (SearchNode->Ch < SmallNode->Ch) //compares the values of the two nodes 
       { 

        SmallNode = SearchNode; //if search node is smaller, swap them 
       }       //to update the smallest node on this pass 
              //once all values have been checked, and the smallest is found 
              //it will be moved to the front of the list, or, after the node 
              //it is slightly larger than 



      } //smallest node has been found, begin swap and end the inner while loop 

      TempCh = EndSorted->Ch; //TempCh holds the value of the Ch held by EndSorted 

      EndSorted->Ch = SmallNode->Ch; //EndSorted now holds the smallest unsorted node's value 

      SmallNode->Ch = TempCh; //SmallNode now holds the value EndSorted originally held 


     }        
    } 
} 

Answer 1

Алгоритм выбора сортировки:

int min;// min element is declared 
for (int i = 0; i < size; ++i) 
{ 
    min=i; 
    for (int j = i + 1; j < size+1; ++j) 
     { 
     if (ar[j] < ar[min]) 
      { 
      min = j; 
      } 
     } 
     swap (ar[i],ar[min]); 
} 

Я сделал для массива Но для Link Перечне также концепция применяется будет же только там будет какой-либо переменной, которая будет использоваться для обхода и ar [i] будет заменена функцией, которая вернет значение узла. И список будет проходить до конечного узла означает node.next()! = null . Для алгоритма u можете перейти по ссылке: http://www.sanfoundry.com/cplusplus-program-implement-selection-sort/