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

[[email protected] 7]

السلام عليكم و رحمة الله و بركاته

 

كيف نقوم بترتيب بيانات مدخلة في قائمة عادية ؟ البرنامج التالي يقوم بقراءة بيانات طلبة في قائمة عادية ثم اخراجها على الشاشه ثم ترتيبها حسب معدلات الطلبة لكن عندي مشكلة في دالة الترتيب ، ارجو المساعدة بارك الله فيكم

#include<stdlib.h>#include<stdio.h>typedef struct student{	int nbr;	char fname[10];	char lname[10];	float mark;	int class;	struct student*suivant;}BAC;typedef BAC*liste;//Fonction Insertliste Insert(liste p){	liste new=(liste)malloc(sizeof(BAC));		do	{		printf("enter the mark\t");		scanf("%f",&new->mark);	}while(new->mark < 12);		printf("enter the number\t");	scanf("%d",&new->nbr);		printf("enter the first name\t");	scanf("%s",new->fname);		printf("enter the last name\t");	scanf("%s",new->lname);		if(new->mark < 13) new->class=3;	else if(new->mark < 15) new->class=2;	else new->class=1;			new->suivant=p;	p=new;	return p;}//Function Displayvoid Display(liste p){	liste temp=p;	if(temp != NULL)	{		printf("\n number:%d",temp->nbr);		printf("\n first & last name:%s %s",temp->fname,temp->lname);		printf("\n the mark:%f",temp->mark);				switch (temp->class)		{			case 3: printf("\n class:C");break;			case 2: printf("\n class:B");break;			case 1: printf("\n class:A");break;		}		printf("\n-------------------------\n");		Display(temp->suivant);	}}//Function Sortvoid Sort(list p){	list cour,av_cour=p;	for (av_cour=p ; av_cour->suivant!= NULL ; av_cour=av_cour->suivant)	{		for (cour=p->suivant ; cour->suivant!= NULL ; cour=cour->suivant)		{			if(cour->mark  <  av_cour->mark)			{				list temp=(list)malloc(sizeof(BAC));				temp=cour;				temp->suivant=av_cour;				av_cour->suivant=cour->suivant;				cour=temp;				free(temp);			}		}	}	Display(p);}main(){	list p=NULL;	int i,n;	printf("enter the number of students:\t");	scanf("%d",&n);	printf("\n<===============ENTER LIST DATA================>\n");	for(i = 1 ; i <= n ; i++)	{		p=Insert(p);	}		printf("\n<==============DISPLAY LIST DATA===============>\n");	Display(p);		printf("\n<==================SORT DATA===================>\n");	Sort(p);	return 0;system("pause")	;}

[Mr.B 667]

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

 

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

if head == NULL:    head = node

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

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

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

prev = headcurr = head.nextwhile(curr != NULL):    if node.data < curr.data:        break    prev = curr    curr = curr.nextnode.next = prev.nextprev.next = node

تطبيق سريع:

#include <stdio.h>#include <stdlib.h>typedef struct _List List;struct _List{  int data;  List *next;};List *head;voidlist_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;}intmain(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;}

تم تعديل 3 May 2014 بواسطه Mr.B

[[email protected] 7]

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

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

مثلا ما معنى :

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

[Mr.B 667]

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

 

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

[[email protected] 7]

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

[محمد علاء الدين 885]

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

 

 

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

[مصطفى 36a2 639]

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

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

ما اقترحه عليك الأستاذ 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 finishMohammadMohannadOmarNourEldinACMZCPCICPCDCPCSCPCMostafaendACMDCPCICPCMohammadMohannadMostafaNourEldinOmarSCPCZCPC

 

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

بالتوفيق