ترتيب بيانات قائمة عادية

لإضافة قيم مرتبة في قائمة ما، هناك ثلاث حالات يجب أن تعالجها: الإضافة في قائمة فارغة، الإضافة في البداية، الإضافة في الوسط أو النهاية (حالة واحدة):

1. أن تكون القائمة فارغة، حينها لاحاجة لإجراء مقارنات، العقدة الجديدة ستكون الرأس:

if head == NULL:    head = node

2. أن تكون القيمة الجديدة أصغر من أول قيمة في القائمة، حينها يلزم أن تضيف في البداية وتجعل القيمة الجديدة هي الرأس:

if node.data < head.data:
    node.next = head
    head = node

3. الحالة الثالثة، الإضافة في الوسط أو النهاية، هنا نحتاج للمرور على كل العقد ونتحفظ بؤشر للعقدة السابقة، إذا حددنا مكان الإضافة نتوقف.

prev = head
curr = head.next

while(curr != NULL):
    if node.data < curr.data:
        break
    prev = curr
    curr = curr.next

node.next = prev.next
prev.next = node

تطبيق سريع:

#include <stdio.h>
#include <stdlib.h>

typedef struct _List List;

struct _List
{
  int data;
  List *next;
};

List *head;

void
list_insert(int data)
{
  List *node, *curr, *prev;

  /* أول خطوة نجهز عقدة جديدة ونملأها */
  if( (node  = (List *) malloc(sizeof(List))) == NULL )
  {
    perror("Error");
    exit(-1);
  }

  node->data = data;
  node->next = NULL;

  /* إذا كانت القائمة فارغة لاحاجة للإستمرار، هذه أول عقدة */
  if( head == NULL )
  {
    head = node;
    return;
  }

  /* إذا كانت القيمة الجديدة أصغر من أول عقدة في القائمة، نعدل الرأس ونجعله العقدة الجديدة */
  if( node->data < head->data )
  {
    node->next = head;
    head = node;
    return;
  }

  /* نحتفظ بمؤشر للعقدة السابقة ثم نمر على كل القيم ونخرج إذا حددنا مكان الإضافة */
  for( prev = head, curr = head->next ; curr ; curr = curr->next )
  {
    if( node->data < curr->data )
      break;
    prev = curr;
  }

  node->next = prev->next;
  prev->next = node;
}

int
main(int argc, char **argv)
{
  List *curr;

  list_insert(3);
  list_insert(4);
  list_insert(2);
  list_insert(1);
  list_insert(6);
  list_insert(5);

  for( curr = head ; curr ; curr = curr->next )
  {
    printf("%d\n", curr->data);
  }

  return 0;
}

عفوا اخي الكريم لكني اريد ترتيب قائمتي بعد اتمام قراءة كل البيناتات ليس اثناء الاضافه أي بعد ان انتهي من إضافة كل البيناتات بغير ترتيب اقوم بطلب دخول الدالة الخاصة بالترتيب كما في main المرفق مع الكود الخاص بي

كما انني لم افهم جيدا الكود اعلاه انا مبتدئه في لغة سي

مثلا ما معنى :

perror("Error");
    exit(-1);

لم يسبق أن جربت ترتيب قائمة، أتفادها بالترتيب عند الإدخال (لاتحتاج أن تدخل البيانات مرتبة بالمناسبة).

ممكن تختار خورزمية ترتيب بسيطة مثل الـbubble sort، ستجد في هذه الصفحة تطبيق على القوائم المتصلة: Linked List Bubble Sort

لا استطيع استعمال خوارزمية جاهزة لان الاستاذ طلب البرنامج كما هو  :( 

الحل الذى أراه هو بعد ان يتم ملء القائمه، قم بحجز مصفوفه من بنوع *student و قم بالدوران على القائمه وقم بحفظ عنوان كل عنصر بها داخل هذه المصفوفه و من ثم قم بترتيب عناصر المصفوفه و بعد ان تقوم بترتيبهم قم بتحديث العنصر suivant بناءا على الترتيب الموجود المصفوفه و بهذا فقد قمت بترتيب القائمه و لا تنسى تحرير ذاكرة المصفوفه.

و الله ولي التوفيق

اقتباس

لا استطيع استعمال خوارزمية جاهزة لان الاستاذ طلب البرنامج كما هو  :(

أخ هشام , كلمة خوارزمية لا تعني تابع أو مكتبة بل طريقة حل ,

ما اقترحه عليك الأستاذ C++er هو ما تريده

بعد ادخال عناصر القائمة تقوم بنسخ القائمة الى مصفوفة , وترتيب المصفوفة كما تريد , ثم إعادة نسخ المصفوفة إلى القائمة

هذا مثال سريع باستخدام STL

#include<list>
#include<string>
#include<iostream>

using namespace std;

int main(){
    list<string> linked_list;

    cout << " Enter strings , then 'end' to finish "<<endl;
    string input;
    cin>>input;
    while(input!="end")
        {
            linked_list.push_back(input);
            cin>>input;
        }
    //copying list to array
    unsigned int index=0,size=linked_list.size();
    string *array_list=new string [size];
    list<string>::iterator i;
    for(i=linked_list.begin(),index=0;i!=linked_list.end();i++,index++){
            array_list[index]=*i;//copy list to array
    }
    //sorting list(easy bubble sort)
    for(int i=0;i<size;i++)
        for(int j=0;j<size-1;j++)
            if(array_list[j]>array_list[j+1])
                swap(array_list[j],array_list[j+1]);
    //copying array to list
    for(i=linked_list.begin(),index=0;i!=linked_list.end();i++,index++){
            *i=array_list[index];//copy array to list
    }
    //printing list
    for(i=linked_list.begin(),index=0;i!=linked_list.end();i++){
            cout << *i <<endl;
    }
    return 0;
}

وهذه مدخلات ومثال للمخرجات

 Enter strings , then 'end' to finish
Mohammad
Mohannad
Omar
NourEldin
ACM
ZCPC
ICPC
DCPC
SCPC
Mostafa
end
ACM
DCPC
ICPC
Mohammad
Mohannad
Mostafa
NourEldin
Omar
SCPC
ZCPC

ملاحظة : بعدما قرأت سؤالك مرة اخرى , رأيت أنك تطلب تصحيح تابع الترتيب الخاص بك ..  راجع خوارزمية الترتيب bubble sort لانك تنفذها بشكل خاطئ , المقارنة تكون للعنصر j والعنصر j-1 وليس العنصرين j و i

بالتوفيق