שפת C - רשימה מקושרת דו סטרית (יום רביעי)

רשימה דו סטרית

רשימה דו סטרית זהה לרשימה חד סטרית, פרט לכך שכל איבר מכיל בנוסף לשדה מצביע לאיבר שאחריו גם שדה מצביע לאיבר שלפניו.

כפי שה next של האיבר האחרון מכיל NULL, גם ה back של האיבר הראשון מכיל NULL.

struct Item{

int info;       

      stuct Item *next, *back;    

};

משימות

1. לבנות פונקציה CreatList של רשימה דו סטרית.
2. לבנות פונקציה PrintList שמדפיסה הרשימה מהסוף להתחלה וגם מההתחלה לסוף (באותה הפונקציה).
3. לבנות פונקציה DelItem של רשימה דו סטרית.
4. לבנות פונקציה המקבלת שתי רשימות מקושרות דו סטריות ומספר שלם x.
     הפונקציה מכניסה הרשימה השניה לרשימה הראשונה אחרי ההופעה הראשונה
     של  x  ברשימה.
     אם אין איבר כזה , אז לא יבוצע כלום.
5. כתוב הפונקציה:

                                                                           struct Item* head  Del_Even (struct Item* head);

    אשר מקבלת מצביע לרשימה מקושרת דו סטרית, הפונקציה מורידה את כל איברי הרשימה הזוגיים.

פתרונות לשאלות מהשיעור הקודם:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct Item {
 int info;
 struct Item* next;
};
struct Item* CreateList() {
 struct Item *head = NULL, *tail, *p;
 while( 1 ) {
  printf("Enter Esc to finish, any other key to continue\n");
  flushall();
  if(getch() == 27)
   break;
 
  p = (struct Item*) malloc( sizeof(struct Item) );
  printf("Enter number: ");
  scanf("%d",&p->info);
  p->next = NULL;
 
  if(head == NULL)
   head = tail = p;
  else {
   tail->next = p;
   tail = p;
  }
 }
 return head;
}
 
 
void PrintList(struct Item* head) {
 struct Item* p;
 for(p=head; p != NULL ; p = p->next)
  printf("%d ",p->info);
 putchar('\n');
}
 
void FreeList(struct Item* head) {
 struct Item * p;
 while( head ) {
  p = head;
  head = head->next;
  free( p );
 }
}
struct Item* DelItem(struct Item* head, int x) {
 struct Item *p, *q;
 if(head == NULL)  // A.
  return head;
 if(head->info == x) { // B.
  p = head;
  head = head->next;
  free( p );
  return head;
 }
 for(p=head, q=head->next; q && q->info != x; p = q, q = q->next) ;
 
 if( q ) {    // C.
  p->next = q->next;
  free( q );
 }
 return head;
}
 
 
 
int min_max(struct Item* head ) {    // Exe No' 1
 int max , min;
 struct Item *p;
 max = min = head->info;
 for(p=head; p != NULL ; p = p->next) {
  if(p->info > max)
   max = p->info;
  if(p->info < min)
   min = p->info;
 }
 return max - min;
}
double  average(struct Item* head) {   // Exe No' 2
 struct Item *p;
 int sum=0 , c=0;
 for(p=head; p != NULL ; p = p->next) {
  sum += p->info;
  c++;
 }
 return (double) sum / c;
}
struct Item* Del_Even (struct Item* head) {  // Exe No' 3
 struct Item *p, *q;
 if(head == NULL)  
  return head;
 while(head && head->info %2 == 0) { 
  p = head;
  head = head->next;
  free( p );
 }
 if(head == NULL) return head;
 for(p=head, q=head->next; q ;   ) {
  if( q->info%2 == 0) {    // C.
   p->next = q->next;
   free( q );
   q = p->next;
  }
  else {
   p = q;
   q = q->next;
  }
 }
 return head;
 
}
int f4(struct Item* head1, struct Item* head2, int x) {
 struct Item *p, *q;
 if(head1 == NULL || head2 == NULL)
  return 0;
 for(p=head1; p && p->info != x; p = p->next);
 if(p == NULL) return 0;
 q = p->next;
 p->next = head2;
 for(p=head2; p->next; p = p->next);
 p->next = q;
 return 1;
}
 
struct Item* Reverse(struct Item* head) {
 struct Item *p = NULL, *q = head->next;
 while( head ) {
  head->next = p;
  if(q == NULL)
   break;
  p = head;
  head = q;
  q = q->next;
 }
 return head;
}
void main() {
/* int x;
 struct Item* head , head2;
 head = CreateList();
 
 while( head ){
  PrintList( head );
  printf("Enter x to delete:   ");
  scanf("%d",&x);
  head = DelItem(head, x);
 }
 printf("%d\n",min_max(head) );
 printf("%.2f\n",average(head) );
 
 PrintList( head );
 head = Del_Even(head);
 PrintList( head );
 */
 
 struct Item* head1 , *head2;
 int x;
 printf("\t\t\tFirst List\n");
 head1 = CreateList();
 printf("\n\t\t\tSecond List\n");
 head2 = CreateList();
 printf("Enter x:  ");
 scanf("%d",&x);
 if( f4(head1, head2, x) )
  PrintList( head1 );
 
 head1 = Reverse( head1 ) ;
 PrintList( head1 );
}

בהצלחה בנאים!