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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
מ Illuyanka העביר את הדף מבוא לתכנות ולמדעי המחשב/ תרגיל 7 ל־מבוא לתכנות ולמדעי המחשב/תרגיל 7 בלי להשאיר הפניה: רווח
(אין הבדלים)

גרסה מ־19:47, 31 באוקטובר 2012

לדף הקורס

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

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

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

#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; 
}