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

עוד על רשימות מקושרות

נתחיל מהתכנית מהשיעור הקודם (+תוספות מהשיעור הזה):

#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;
}
void main() {
 int x;
 struct Item* head;
 head = CreateList();
 
 while( head ){
  PrintList( head );
  printf("Enter x to delete:   ");
  scanf("%d",&x);
  head = DelItem(head, x);
 }
}

שאלות:

רשימות מקושרות.

כל השאלות מתייחסות להגדרות הבאות:-

struct Item{

int info;       

      stuct Item *next;    

};

1)   כתוב הפונקציה:         int min_max(struct Item* head );

      אשר מקבלת רשימה מקושרת.

      הפונקציה מחזירה ההפרש בין המספר המינימלי והמקסימלי ברשימה. 

     

2)   כתוב הפונקציה:         double  average(struct Item* head);

      אשר מקבלת רשימה מקושרת.

      הפונקציה מחשבת ומחזירה ממוצע איברי הרשימה.

3)  כתוב הפונקציה:

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

 אשר מקבלת מצביע לרשימה מקושרת חד-סטרית.

הפונקציה מורידה כל איברי הרשימה הזוגיים.

 4)  כתוב פונקציה המקבלת שתי רשימות מקושרות ומספר שלם x.

     הפונקציה מכניסה הרשימה השניה לרשימה הראשונה אחרי ההופעה הראשונה

     של  x  ברשימה.

     אם אין איבר כזה , אז לא יבוצע כלום.

     לדוגמא:   עבור: // < head1 >   2 > 14 > -13 > 33 > 10 > 12

                                                              // < head2 >   4 > 5 > 6                                                                                                                                                 x = -13

      אז אחרי הפעלת הפונקציה נקבל:

               // < head1 >   2 > 14 > -13 > 4 > 5 > 6 > 33 > 10 > 12

5)  כתוב פונקציה המקבלת מצביע לרשימה חד סטרית.

     הפונקציה מורידה מהרשימה האיבר המקסימלי.

     לדוגמא:

           עבור הרשימה:

                           1 > 4 > -5 > 6 > 3                                   

           נקבל הרשימה:

                           1 > 4 > -5 > 3                                         

6) כתוב פונקציה המקבלת מצביע לרשימה מקושרת , הופכת אותה ומחזירה ראש
    רשימה החדש.    האיבר הראשון הופך להיות אחרון. השני לפני אחרון ...

      לדוגמא:   עבור:

                                   // < head > 2 > 4 > -3 > 5

                       נקבל:

                                   // < head > 5 > -3 > 4 > 2

בהצלחה!