الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

سؤال عن طريقة أخرى لعمل SWAP في الLikned List

بدأه aohammed في 22 أغسطس 2010 · 7 رد · 1,355 مشاهدة · في الأسئلة المجابة
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم

هل يوجد طريقة أخف تعقيدا ً أو ذات فكرة برمجية أخرى غير هذه في عملية الـSWAP في القوائم المتصلة Linked List

 


#include "stdafx.h"
#include<iostream>
using namespace std;
struct node
{
 int item;
 node *next;
};
void main()
{
 node *List=new node;
 node *header=List;
 int length;
 cin>>length;
 for(int i=0;i<length;++i)
 {
  List->item=i;
  List->next=new node;
  List=List->next;
 }
 List->next=NULL;
 List=header;
//   PRint
 List=header;
 while(List->next!=NULL)
 {
  cout<<List->item<<endl;
  List=List->next;
 }
 cout<<"\n==================================\n";

//     	SWAP 1 & 4
 List=header;
 node *tempA1=new node;
 node *tempA2=new node;
 int tempV1;
 int tempV2;
 for(int i=0;i<length;++i)
 {
  if(i==1)
  {

   tempV1=List->item;
   tempA1=List;
  }
  if(i==4)
  {
   tempA2=List;
   tempV2=List->item;
  }
  List=List->next;
 }
 List=tempA1;
 List->item=tempV2;
 List=tempA2;
 List->item=tempV1;

//   PRint
 List=header;
 while(List->next!=NULL)
 {
  cout<<List->item<<endl;
  List=List->next;
 }

 //pause
 int ii;cin>>ii;
}

بغض النظر عن طريقة الجمع و الطرح التي تخفف علينا استعمال المتحول temp

مع جزيل الشكر

#2

ما في أفكار يا جماعة ؟

في عندي فكرة في عقلي بس ما عم بقدر أطبقها أو عم شوف تطبيقها رح يأخذ تعقيد أكثر

و هي فكرة تبديل العناوين للـ next

شو رأيكم ؟

#3

في كودك انت تبدل نفس القيم الي داخل الـ عقد .. من غير ما تبدل العقد نفسهم ..

الطريقه الي بكودك اسهل من تبديل العقد .. ( تغير عناوين الـ next ) :wink:

#4
Don DaVinci كتب:

في كودك انت تبدل نفس القيم الي داخل الـ عقد .. من غير ما تبدل العقد نفسهم ..

الطريقه الي بكودك اسهل من تبديل العقد .. ( تغير عناوين الـ next ) :wink:

لو استخدمت طريقة تبديل قيم ال Nodes هتاخد منك وقت طويل وهتكون الخوارزمية من O(N^2) اذا كانت Single Linked List

ومن الرتبة O(N) اذا كانت Circular Linked List

الطريقة الافضل هي تبديل اتجاه المؤشر Next العكس

#5
alexsniper كتب:

لو استخدمت طريقة تبديل قيم ال Nodes هتاخد منك وقت طويل وهتكون الخوارزمية من O(N^2) اذا كانت Single Linked List

ومن الرتبة O(N) اذا كانت Circular Linked List

الطريقة الافضل هي تبديل اتجاه المؤشر Next العكس

لكن الخوارزميه الي هو كاتبها عباره عن O(n) :unsure:

#6
Don DaVinci كتب:

لكن الخوارزميه الي هو كاتبها عباره عن O(n) :unsure:

الطريقة دي لتبديل عنصرين فقط

لكن لو عايز ابدل كل عناصر القائمة المتصلة هتكون الخورزمية O(N^2)

في غلطة عندي في الرد السابق وهي

Doubly Linked List بدلا من Circular Linked List

بعتذر عليها

تم تعديل هذه المشاركة بواسطة alexsniper في 25 أغسطس 2010 في 12:19

#7

أخ أليكسندر ممكن تشرح طريقتك ؟

#8

اول طريقة هي عكس المؤشرات هكذا وهي Single Linked List

//change the node's link direction
//O(N)
void List::Swap()
{
	Node *x=NULL,*y=first,*z;

	while(y !=NULL)
	{
		z=y->next;
		y->next=x;
		x=y;y=z;
	}
}

الطريقة بسيطة وواضحة مجرد اني بستخدم 3 عقد متتالية

وهي من O(N) كما تري

الطريقة الثانية ايضا مع Single Linked List 

//Single Linked List
//O(N^2)
void List::Swap()
{
	Node *pTempFirst,*pTempLast;
	pTempFrst=first;
	int value;
	for(int i=0;i<list.Length();i++)
	{
		pTempLast=first	
		for(int j=0;j<list.Length()-i;j++)
			pTempLast=pTempLast->next;	//increment to point to element from the last	

		//swap values	
		value=pTempFirst->value;
		pTempFirst->value=pTempLast->value;
		pTempLastValue=value;

		pTempFirst=pTempFirst->next;
	}
}

ببدل قيم العقد وبالتالي مثلا اذا بدلت قيمة العقدة الاولي والاخيرة فساحتاج الي مؤشرين الاول يشر الي العقدة الاولي والثاني يشير الي الاخيرة وهكذا

المؤشر للعقدة الاولي (او من بداية القائمة المتصلة ) هو pTempFirst

المؤشر الذي يشير الي العقد من نهاية القائمة هو pTempLast

كما تري ففي كل مرة سنحتاج من المؤشر pTempLast ان يمر علي جميع العناصر من البداية حتي يشير الي العنصر المراد تبديل قيمته

وبالتالي هي من الرتبه O(N^2)

الطريقة الثالثة

مع Doubly Linked List 

//Doubly Linked List
//O(N/2)
void List::Swap()
{
	Node *pTempFirst=first,*pTempLast=last;
	int value;

	//swap values and increment pTempFirst
	//and decrement pTempLast
	for(int i=0;i<list.Lenght()/2;i++)	
	{
		value=pTempFist->value;
		pTempFirst->value=pTempLast->value;
		pTempLast->value=value;

		pTempFirst=pTempFirst->next;
		pTempLast=pTempLast->previous;
	}

}

وهنا عندي مؤشرين الاول يشير الي القائمة من البداية والثاني من النهاية

وبما انها تحتوي علي مؤشر يشير الي العنصر السابق فلن احتاج الا اني امر علي جميع العناصر كما فعلت في المثل السابق

وهي من الرتبة O(N/2)

كما تري فهي اسرع طريقة لتبديل القيم

ارجو ان اكون افدتك

مواضيع مشابهة