מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 7

לדף הקורס

תרגיל קטן לרשימה משורשרת

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

נתון הקוד הבא:

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 
 
Node* newNode(int data, Node *next) {
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->data = data; 
    p->next = next; 
    return p; 
}
 
void insertFirst(int data, Node **head) {
 
    Node *tmp = *head; 
    *head = (Node*) malloc (sizeof(Node)); 
    (*head)->data = data; 
    (*head)->next = tmp; 
 
    // An alternative implemetation of the function: 
    // *head = newNode(data,*head); 
}
 
void printList(Node *head) {
    while(head) {
	printf("%d->",head->data);
	head = head->next; 
    }
    printf("\n"); 
}
 
void freeList(Node *p) {
    if(!p)
	return; 
    freeList(p->next);
    free(p); 
}

int main() {
    int ints[] = {7,5,4,3,7,5,1,7,5,8,5,5,7,4};
    int N = sizeof(ints)/sizeof(int); 
 
    Node *head = NULL;
    int i; 
    for(i=0; i<N; ++i)
	insertFirst(ints[i], &head); 
 
    printf("The original list:\n"); 
    printList(head); 

    deleteFirst(&head); 
    printf("\nAfter deleteing the first node:\n"); 
    printList(head); 

    duplicateData(7,&head); 
    printf("\nAfter duplicating all the nodes that contain 7:\n"); 
    printList(head); 

    deleteFromList(7,&head);
    printf("\nAfter deleting all the nodes that contain 7:\n"); 
    printList(head); 

    freeList(head);
    return 0; 
}

לאחר שתוסיפו מימושים ל deleteFirst, duplicateData ו deleteFromList הפלט אמור להיות:

 
The original list:
4->7->5->5->8->5->7->1->5->7->3->4->5->7->

After deleteing the first node:
7->5->5->8->5->7->1->5->7->3->4->5->7->

After duplicating all the nodes that contain 7:
7->7->5->5->8->5->7->7->1->5->7->7->3->4->5->7->7->

After deleting all the nodes that contain 7:
5->5->8->5->1->5->3->4->5->

הגשה

מועד הגשה: יום ראשון ה - 15.1.12, עד סוף היום.

יש להגיש ב"תרגיל שביעי" במודל קובץ בודד בשם q1.c המכיל את הקוד הדרוש. אין צורך בקובץ tgz.

בהצלחה!

לדף הקורס

פתרון

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct Node {
    int data; 
    struct Node* next; 
} Node; 
 
Node* newNode(int data, Node *next) {
    Node *p = (Node*) malloc (sizeof(Node)); 
    p->data = data; 
    p->next = next; 
    return p; 
}
 
void insertFirst(int data, Node **head) {
 
    Node *tmp = *head; 
    *head = (Node*) malloc (sizeof(Node)); 
    (*head)->data = data; 
    (*head)->next = tmp; 
 
    // An alternative implemetation of the function: 
    // *head = newNode(data,*head); 
}
 
void printList(Node *head) {
    while(head) {
	printf("%d->",head->data);
	head = head->next; 
    }
    printf("\n"); 
}
 
void freeList(Node *p) {
    if(!p)
	return; 
    freeList(p->next);
    free(p); 
}

void deleteFromList(int data, Node** h) {
    if(! *h )
	return; 

    Node *p = *h;
    Node **prev = h; 
    while(p) {
	if(p->data == data) {
	    *prev = p->next; 
	    free(p);
	    p = *prev; 
	} else {
	    prev = &(p->next);
	    p = p->next; 
	}
    }
}

void deleteFirst(Node **h) {
    if(!*h)
	return; 
    Node *p = *h; 
    *h = p->next;
    free(p); 
}

void duplicateData(int data, Node ** h) {
    while(*h) 
	if( (*h)->data == data) {
	    *h = newNode(data,*h); 
	    h = &( (*h)->next->next);  
	} else
	    h = &((*h)->next); 
} 
 
int main() {
    int ints[] = {7,5,4,3,7,5,1,7,5,8,5,5,7,4};
    int N = sizeof(ints)/sizeof(int); 
 
    Node *head = NULL;
    int i; 
    for(i=0; i<N; ++i)
	insertFirst(ints[i], &head); 
 
    printf("The original list:\n"); 
    printList(head); 

    deleteFirst(&head); 
    printf("\nAfter deleteing the first node:\n"); 
    printList(head); 

    duplicateData(7,&head); 
    printf("\nAfter duplicating all the nodes that contain 7:\n"); 
    printList(head); 

    deleteFromList(7,&head);
    printf("\nAfter deleting all the nodes that contain 7:\n"); 
    printList(head); 

    freeList(head);
    return 0; 
}