help meeeee

[fatemeh01]

سلام من کدنویسیم خیلی ضعیفه اگه میشه کمکم کنید سه روز بیشتر وقت ندارم:گریه::گریه::گریه:
یک لیست پیوندی حلقوی برای نگهداری اعدادصحیح بنویسید که امکانات زیر را داشته باشد:
1-اضافه کردن عدد به لیست بگونه ای که لیست به صورت صعودی مرتب باشد
2-امکان جستجوی لیست بصورت دودویی و ترتیبی
3-امکان معکوس کردن لیست بصورت بازگشتی و غیربازگشتی
خواهش میکنم کمکم کنید:ناراحت:

[vahid-p]

دوست عزیز چون تعداد پست های شما "1" است معلوم است کاربر جدید هستید. پیوستن به انجمن برنامه نویسان خوش آمد میگم.

اما شرط اخلاق میگوید که تکالیف درسی توسط خود دانش آموز یا دانشجو انجام شود. اینکه ما کدی که شما میخواید رو بنویسیم، مخصوصا اگر دانشجوی کامپیوتر یا برق و... باشید که برنامه نویسی جز جدایی ناپذیر آن است، هم به اشتباه نمره گرفته اید و هم ترغیب به یادگیری نمیشوید. مطمئنا این تمرینات از این جهت به شما محول شده که خودتان یاد بگیرید نه بقیه انجام بدهند.

این حرف شخص من نیست، همه دوستان خدا رو شکر این موضوع رو درک میکنند. حتی در انجمن های خارجی هم نگاه کنید هر وقت حدس زده شود کسی میخواهد تمرینی کامل برایش نوشته شود و خودش هیچ تلاشی نمیکند، اصلا برایتان انجام نمیدهند. پیش زمینش اینه که شما خودتون دست به کار بشید، ما کمک کنیم، خودتون تکمیلش کنید.
این حالت حتی استاد درس هم هیچ اشکالی از شما نمیگیرد و خیلی از اساتید اتفاقا تشویق میکنند که از اینترنت و انجمن ها کمک بگیرید و تقلب محسوب نمیشود، اما اگر کامل کس دیگری برایتان بنویسد، حکم همان کپ زدن را دارد.

شما این فکر را کردید یک نفر وقت خود را صرف کند و تمرین شما را انجام بدهد چه فایده ای برایش دارد؟ علاوه بر آنکه کار خیلی اشتباهی هم انجام داده؟

بعضی ها هستند که با پول تمرین درسی رو انجام میدن، ولی من و خیلی از دوستان دیگر با پول هم تمرین درسی را انجام نمیدهیم.
اما در عوض کمک ( راهنمایی و آموزش نه انجام تمرین ) من و خیلی های دیگر به صورت کاملا رایگان اینجا هستیم.

[vahid-p]

امیدوارم این حرفها موجب ناراحتی نباشد، چون کاملا به نفع خودتان است. خیلی ها بودند که اول با این هدف اومدن ولی با تذکر به موقع دوستان الان خودشون به بقیه کمک می کنند و برنامه نویسیشون خیلی خوب شده.

پیشنهاد من :
شما شروع کنید هر چه میدانید بنویسید و یک تاپیک ( مثلا همین جا ) برای بخش های مختلف سوال کنید و راهنمایی میکنیم، هر چند ناقص تحویل دهید، حداقل حاصل زحمت خودتون بوده. یک نمره ارزش زیادی نداره، مهم اینه یاد بگیرید. لازم نیست حتما تمام و کمال برنامه رو بنویسید.
اول از همه شروع کنید یک لیست پیوندی رو بنویسید. بعد حلقویش رو بنویسید. تا اینجا 20 تا 30 درصد انجام شده. بقیش هم قابل انجام است.
بهانه هم نیارید. موفق باشید

[vahid-p]

سه روز هم وقت خوبیه برای اینکار. اگر تمرین داشتید، بعید میدونم بیش از نیم یا یکساعت نوشتنش براتون طول میکشید.

یکم راهنمایی میکنم : شما اول دو کلاس درست کنید که یکی اسمش linkedList هست و دیگری هم گره های لینک لیست هستند. مثلا اسمش رو بنویسید Node.
اول ساختار گره رو میگم :
سه فیلد داریم. دو تا از نوع گره داریم که قبل و بعد رو مشخص میکنه. یک فیلد هم مقدار ( یا کلید ) گره است که برای سرچ این مقدار برامون مهمه.
public class Node {
//ّفیلدها
Node next; //بعدی
Node previous; //قبلی
int value; //مقدار گره

public Node(Node next, Node previous, int value) {
this.next = next;
this.previous = previous;
this.value = value;
}
}

حالا ساختار LinkedList
public class LinkedList {

}

اینو خودتون فیلدهاش رو بنویسید. چه فیلدهایی میخواد؟ فعلا فکر method یا به گفته ای تابع هاش نباشید. ( add و delete و get و... بعدا مینویسید )

[fatemeh01]

سلام
ممنون از راهنماییتون،من تو نوشتن الگوریتم مشکل ذارم ولی برنامه نویسی رو دوس دارم امیدوارم بتونم با کمک های شما موفق بشم:لبخندساده:
class Node{
lnt Data;
Node link;
}
class linkedlist{
Node first;
Node last;
publik linkedlist()
{
first=null;
}
}

[vahid-p]

خب حالا تابع add به صورت معمولی برای linkedList بنویسید. با این فرض که ترتیب مهم نیست و همیشه به اخر لیست اضافه میشه. یکم خودتون هم هر چی رو میدونید لازمه بنویسید تا سریعتر پیش بره. با اینکه وقتتون کمه، ولی خیلی دیر به انجمن سر میزنید.
موفق باشید

[fatemeh01]

public class linkedlist {
Node first;
Node last;
public linkedlist()
{
first=null;
}
public void Insert(int x)
{
Node k = new Node;

if (first==null)
{
k.link=null;
first=k;
first.Data=x;
last=first;
}
else
{
k.link=null ;
last.link=k;
last=k;
last.Data=x;
}
}
public void Delete (int x)
{
Node k;
Node p;
p=k=first;
if(first.Data==x)
{
k=first;
first=first.link;
Delete k;
}
else
{
while(k!=last)
{
k=p.link;
if(k.Data==x)
{
if(k==last)
{
p.link=null;
Delete k;
last=p;
break;

}
else
{
p.link=k.link;
Delete k;
break;
}
}
p=p.link;
}

}
}
private int count(Node k)
{
if(k == last)
return 0 ;
return 1+count(k.link);
}
public void show()
{
Node k = last.link ;
while( k!=last)
{
System.out.print(k.Data);
k=k.link;
}
}
}
من تا اینجاشو نوشتم ولی دستور Node k=new Node و همینطور Delete k رو ارور میده

[fatemeh01]

لطفا کمکم کنید وقت زیادی ندارم:گریه::گریه:

[fatemeh01]

لطفا کمکم کنید وقت زیادی ندارم:گریه::گریه:

[vahid-p]

خب بد نیست، ولی خب مشکلات syntax هم دارید. مثلا تو متد p=k=first; زیاد جالب نیست استفاده کنید. سعی کنید جدا جدا assign کنید.
یا مثلا Node k= new Node; اشتباهه. چون کانستراکتور باید به صورت Node() باشه و اینجا چون آرگومان هم میگیره باید چنین حالتی داشته باشه :
Node k = new Node(before,next,value);
راستی حذف گره اینجا به این راحتی نیست که بنویسید delete k;
چون لیست باید بعد از حذف گره، همچنان پیوسته باشه. برای همین برای حذف یک گره، باید قسمت بعد گره قبلی x رو به گره بعدی x وصل کنی و قسمت قبل گره بعد x رو به گره قبل x وصل کنی. اینطوری پیوسته میشه. و دیگه تو جاوا لازم نیست بنویسید delete x چون همین که هیچ جوری نشه بهش دسترسی داشت اونوقت خودش اون گره رو حذف میکنه. این بهش میگن Garbage Collector جاوا.
راستی لطفا کد هاتون رو در تگ JAVA قرار بدید تا کدهاتون به هم نریزه در فروم.



خب من کدتون رو تصحیح و تکمیل کردم. تا اینجای کار add و delete و sequentialSearch و print لیست رو داره. لیست هم حلقویست و ترتیب و مرتب سازی و همه چیز در نظر گرفته شده است. اینو هم نوشتم یکم کارتون جلو بیفته.
کلاس Node.java ( نگران طولانی بودن کلاس Node نباشید و هیچ چیزی خاصی نیست فقط یه مشت متد های getter و setter هست نه چیز دیگری. اصلش همون فیلد هست و بدون توابع getter و setter هم میشد نوشت، همونطور که خودتون مثلا نوشتید k.link اینبار مثلا میشه k.getLink() )

public class Node {

private Node before;
private Node next;
private int value;

public Node(Node before, Node next, int value) {
this.before = before;
this.next = next;
this.value = value;
}

public Node getBefore() {
return before;
}

public void setBefore(Node before) {
this.before = before;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}
}



کلاس CycledLinkedList.java

public class CycledLinkedList {

Node first;
Node last;

public CycledLinkedList() {
first = null;
last = null;
}

public void add(int value) {
Node k = new Node(null, null, value);
if (first == null) {
first = k;
last = k;
k.setBefore(last);
k.setNext(last);
} else {
Node q = first;
Node p = q.getNext();
while (p != first) {
if (value > q.getValue()) {
q = p;
p = q.getNext();
} else {
break;
}
}
if (value > q.getValue()) {
q = p;
}
q.getBefore().setNext(k);
k.setBefore(q.getBefore());
k.setNext(q);
q.setBefore(k);
}
if (k.getValue() <= first.getValue()) {
first = k;
}
if (k.getValue() > last.getValue()) {
last = k;
}
}

public Node delete(int x) {
if (first == null) {
return null;
}
Node p = first;
while (p.getNext() != first && p.getValue() < x) {
p = p.getNext();
}
if (p.getValue() == x) {
if (p == first) {
first = p.getNext();
}
if (p == last) {
last = p.getBefore();
}
p.getBefore().setNext(p.getNext());
p.getNext().setBefore(p.getBefore());
}
return null;
}

public Node sequentialSearch(int x) {
if (first == null) {
return null;
}
Node p = first;
while (p.getNext() != first && p.getValue() < x) {
p = p.getNext();
}
if (p.getValue() == x) {
return p;
}
return null;
}

public void print() {
if (first != null) {
print(first);
}
}

private void print(Node p) {
System.out.println(p.getValue());
if (p.getNext() != first) {
print(p.getNext());
}
}
}

[vahid-p]

وقتتون کمه، همه این وضعیت رو دارن. اواخر ترم دیگه کسی به کسی دیگه کمک نمیکنه، همه سرشون شلوغه!
فقط این وسط یه مشکلی که وجود داره اینه که برای جستجو باینری باید دسترسی مستقیم به گره ها ( Node ) داشته باشیم. که در لینک لیست ها چنین چیزی وجود نداره.
مگر اینکه بیاییم یه آرایه ازش بسازیم. مثلا با ArrayList . ولی خود ساخت یک آرایه از روی همین عناصر خودش مرتبه زمانیش بیشتر از جستجو ترتیبی میشه. مگر اینکه از اول یک ArrayList رو هم زمان با add , delete گسترش یا کاهش بدیم و کپی لینک لیستمون باشه.
یا اصلا از اول بیاییم به جای اد کردن به لینک لیست و تو هوا بودن اینا، بیاییم و یه جایی منظم مثل arrayList داشته باشیم ( این خیلی بهتره ) . فقط یه سوال استفاده از ArrayList مجازه؟

[fatemeh01]

اینم تابع معکوس کردن لیست و شمارش تعداد نودهاش و بازگشتی جستجوی خطی امیدوارم بهتر از کدای قبلیم باشه:ناراحت:
public Node SequentialSearch(int x)
{
Node q;
q = SequentialSearch(x);
return q;
}
private int Count( Node p)
{
if( p == last )
return 0 ;
else
return 1+Count(p.getNext());
}
public void Revarse()
{
Node p = first;
Node q = first.getNext().getNext() ;
Node r = null;
while( p.getNext() != null )
{
p.getNext() = r ;
r = p ;
p = q ;
q = q.getNext();
}
p.getNext()=r;
first.getNext()=p;


}

[vahid-p]

متد searchSequential رو نمیخواد دیگه. اون بالا نوشتم، شما فقط دوباره اومدین یه متد ساختید که از همون استفاده میکنه! این لقمه دور سر چرخوندنه!
متد count درسته ولی هر وقت p==last بود باید 1 رو return کنه نه 0. گرچه کاربردشو نمیدونم، اینجا که نیازی بهش نداریم.
متد Reverse ای که نوشتید برای لینک لیست یک طرفه درسته . گرچه طبق متد های getter و setter شما برای ست کردن p.getNext()=r اشتباه است و باید بنویسید p.setNext(r) .شما کدتون رو run نمیکنید مگه؟ اگه run کنید متوجه میشید که اررور میگیره. اصلا تو نت بینز اینا اگه باشه خودش همونجا هم با خط زیر قرمز نشون میده.
اینجا چون لیست حلقوی هست هیچ وقت هیچ قسمتی نه next و نه last نال نمیشن.
البته اینجا یه چیزی رو باید مشخص میکردید که ما امکان استفاده از next و before رو داریم یا فقط میتونیم از next استفاده کنیم؟ چون بعضی وقتها اجازه میدن گره ها به دو طرف دسترسی داشته باشن، گاهی اوقات نه و وقت شما به گره بعد دسترسی دارید و یک طرفه میتونید حرکت کنید. این محدودیت بر اساس خواسته سوال هست. خیلی اوقات فقط اجازه میدن از next یا link استفاده کنی و استفاده از before رو مجاز نمیدونن. در این حالت، reverse شما درسته و فقط باید شرط خاتمش رو بر اساس last بنویسی نه null !
در این مثالی که من نوشتم و دو جهته میتونید حرکت کنید، معکوس کردن خیلی راحته. فقط جای next و before رو عوض میکنید و در انتها جای last و first. حواستون باشه برای جا به جایی دو قسمت next و before اول بیایید یه متغیری مانند n=p.getNext() و b=p.getBefore() بگیرید و بعد p.setNext(b) و p.setBefore(n)

این متد رو دوباره باز نویسی کنید.
اما یه مشکل دیگه که میمونه همون binarySearch هست. ببینید خودتون میتونید اینو پیاده سازی کنید یا نه. همانطور که گفتم بهتره از ArrayList در کلاس CycledLinkedList استفاده کنید تا دسترسی مستقیم به گرهها داشته باشید. چون متاسفانه سرم یکم شلوغه فرصت نوشتنشو ندارم.

[fatemeh01]

public Node BinerySearch(int x)
{
Node q=last.getNext();
int first=1;
int end=CycledLinkedList.Count();
int Mid;
while(first<=end)
{
Mid = (first+end)/2;
System.out.printf("s,end,Mid");
q=last.getNext();
for(int j=1;j<Mid;j++)
{
q = q.getNext();
}
System.out.printf("q.getValue()");
if( q != null && q.getValue()==x){
return q;

}
else if( q != null && q.getValue() > x )
{
end = Mid-1;
}
else if( q != null && q.getValue()< x)
{
first=Mid+1;
}
}
return null;

}

چندمدت به نت دسترسی نداشتم اینم تابع binerySaerch ولی int end=CycledLinkedList.Count(); در حساب کردن تعداد نودها در هرمرحله مشکل داره،
تابع Count
private int Count(Node p) {
if( p == last )
return 1 ;
else
return 1+Count(p.getNext());

}

[fatemeh01]

کسی نیس راهنماییم کنه:افسرده::ناراحت:

[vahid-p]

آخرین پست 22 ام بود، بعد 10 روز پست دادین. خب معلومه یادمون میره اصلا کجا بود!

ببین برای اینکه خیالت راحت بشه و نگران count نباشی ( چون مثل اینکه زیاد میخوای ازش استفاده کنی )، یه فیلد به اسم size تعریف کن که تعداد گره ها رو داشته باشه. هر وقت یک گره رو با موفقیت اد کردی size رو بعلاوه 1 کن. هر وقت هم با موفقیت یک گره رو حذف کردی ( یعنی توجه کن شاید هیچ گره ای حذف نشه پس سایز تغییر نمیکنه یا یک گره حذف بشه و سایز تغییر میکنه ) size منهای 1 کن. به همین راحتی همیشه تعداد گره ها رو داری.

اگر تابع باینری سرچتون درست کار میکنه، دیگه تمام سوالات حل شدن، مشکل چیه؟

[vahid-p]

باینری سرچتون به نظر درست میاد. من کل کلاس CycledLinkedList.java رو دوباره تصحیح شدش رو مینویسم : ( فقط متد Reverse تون اشتباهه، درستش کردید یا خیر؟ من بدون متد reverse کدهای درست رو جمع و جور تا اینجا کار میذارم )

public class CycledLinkedList {

Node first;
Node last;
int size;

public CycledLinkedList() {
first = null;
last = null;
size = 0;
}

public void add(int value) {
Node k = new Node(null, null, value);
if (first == null) {
first = k;
last = k;
k.setBefore(last);
k.setNext(last);
} else {
Node q = first;
Node p = q.getNext();
while (p != first) {
if (value > q.getValue()) {
q = p;
p = q.getNext();
} else {
break;
}
}
if (value > q.getValue()) {
q = p;
}
q.getBefore().setNext(k);
k.setBefore(q.getBefore());
k.setNext(q);
q.setBefore(k);
}
if (k.getValue() <= first.getValue()) {
first = k;
}
if (k.getValue() > last.getValue()) {
last = k;
}
size++;
}

public Node delete(int x) {
if (first == null) {
return null;
}
Node p = first;
while (p.getNext() != first && p.getValue() < x) {
p = p.getNext();
}
if (p.getValue() == x) {
if (p == first) {
first = p.getNext();
}
if (p == last) {
last = p.getBefore();
}
p.getBefore().setNext(p.getNext());
p.getNext().setBefore(p.getBefore());
size--;
return p;
}
return null;
}

public Node sequentialSearch(int x) {
if (first == null) {
return null;
}
Node p = first;
while (p.getNext() != first && p.getValue() < x) {
p = p.getNext();
}
if (p.getValue() == x) {
return p;
}
return null;
}

public void print() {
if (first != null) {
print(first);
}
}

private void print(Node p) {
System.out.println(p.getValue());
if (p.getNext() != first) {
print(p.getNext());
}
}

public Node BinerySearch(int x) {
Node q = last.getNext();
int first = 1;
int end = size;
int Mid;
while (first <= end) {
Mid = (first + end) / 2;
// System.out.printf("s,end,Mid");
q = last.getNext();
for (int j = 1; j < Mid; j++) {
q = q.getNext();
}
// System.out.printf("q.getValue()");
if (q != null && q.getValue() == x) {
return q;

} else if (q != null && q.getValue() > x) {
end = Mid - 1;
} else if (q != null && q.getValue() < x) {
first = Mid + 1;
}
}
return null;

}
}




اینم کدی که تو main برای تست نوشتم :
CycledLinkedList list=new CycledLinkedList();
list.add(12);
list.add(14);
list.add(3);
list.add(1);
list.add(-15);
list.add(8);
Node p;
if((p=list.BinerySearch(0))!=null) System.out.println("Found "+p.getValue());
else System.out.println("Not found");
if((p=list.BinerySearch(8))!=null) System.out.println("Found "+p.getValue());
else System.out.println("Not found");


خروجی :

Not found
Found 8

[vahid-p]

اینم متد reverse :
public void reverse(){
Node p=first;
Node q=null;
Node r=last;
while(q!=first){
q=p.getNext();
p.setNext(r);
r=p;
p=q;
}
p=first;
first=last;
last=p;
}

این درست کار میکنه، میشد از این راحتتر نوشت ( چون ما before هم داریم ) و میتونستیم جای next , before رو عوض کنیم ( من دو طرفه در نظر گرفتم )، ولی اینجوری نوشتم که شبیه کد شما بشه ( بهتره اینجا که از before استفاده کردیم، پس همشو از همین استفاده کنیم، چون الان در کد معکوس بالا ما فیلدهای before رو تغییر ندادیم و ممکن است برنامه در ادامه با مشکل رو برو شود. شما لیست رو یک طرفه در نظر گرفتید، کاش از اول اینو دقیق مشخص میکردید ). پس بهتر است اگر میخواهیم لیست دو طرفه باشد لا اقل متد معکوس رو اینجوری بنویسیم ( اسمشو میذارم reverse2 ) :
public void reverse2(){
Node p=first;
Node b=null;
Node n=null;
while(b!=first){
b=p.getBefore();
n=p.getNext();
p.setBefore(n);
p.setNext(b);
p=b;
}
p=first;
first=last;
last=p;
}


. الان این کد رو اگر در main اجرا کنید ( چه reverse استفاده کنید چه reverse2 یه جواب رو میده ):

CycledLinkedList list=new CycledLinkedList();
list.add(12);
list.add(14);
list.add(3);
list.add(1);
list.add(-15);
list.add(8);
list.print();
list.reverse();
System.out.println("--------------");
list.print();

خروجی :

-15
1
3
8
12
14
--------------
14
12
8
3
1
-15
توجه کنید که اگر بعد از معکوس کردن، یک عدد رو بخواید اضافه کنید، ترتیب به هم میخوره. بخواید حذف کنید، ممکنه حذف نکنه، چون فرض بر صعودی بودن بود که الان نیست. بخواید سرچ کنید جواب پیدا نمیشه و... . برای جلوگیری از این کار یا باید صعودی نزولی بودن را در متد add و delete , search ,... در نظر بگیرید یا هم اینکه قبل اون یک بار لیست رو معکوس کنید، عملیات مورد نظر رو انجام بدید و دوباره لیست رو معکوس کنید. روش دوم پیشنهاد میشه. یعنی تو کدتون همیشه وقتی لیست صعودی است عملیات انجام دهید بعد خواستید نزولی چاپ بشه معکوس کنید و اونو چاپ کنید.

و آخرین نکته، درسته در ظاهر reverse , reverse2 یه عمل رو انجام دادن، ولی من reverse2 رو بیشتر ضمانت میکنم چون مخصوص این لیست است که دو طرفست نوشته شده و مشکلی در بخش های دیگه ایجاد نخواهد شد. انتخاب با خودتون. ( در طول برنامه فقط از یکی از reverse ها استفاده کنید، اگر قاطی پاتی استفاده کنید، برنامتون اشتباه میشه - اینو تست کردم )