proggen.org

Code: Alles auswählen

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    ListNode* next;

    ListNode(int v) { data=v; next=NULL; }
    ListNode(int v, ListNode* n) { data=v; next=n; }
};

class LinkedList {
    ListNode* head; 
  
  public:
    LinkedList()      { head = NULL; }
    LinkedList(int v) { head = new ListNode(v); }

    // recursive functions
    void append(int v)       { append     (v,head); }
    void removeVal(int v)    { removeVal  (v,head); }
    void removeDups()        { removeDups   (head); }   
    void print()             { print        (head); }
    void printReverse()      { printReverse (head); }
    void reverse()           { reverse      (head); }
    void removeLast()        { removeLast   (head); }
    void remove(int i)       { remove     (i,head); }
    void insert(int i,int v) { insert   (i,v,head); }
    int  get(int i)          { return  get(i,head); }
    int  length()            { return length(head); }

    // alternative Version von reverse
    //void reverse()           { head = reverse(head, NULL); }
  
    // non-recursive functions
    bool empty() { return head == NULL; }
    void prepend(int v) { insert(0,v); }
    void removeFirst()  { remove(0);   }    

private:
    void remove(ListNode* &ptr) {
    // ptr is a non-null pointer of the linked list;
    // the element ptr points to is removed
        ListNode* help = ptr;
        ptr = ptr->next;
        delete help;
    }


    // recursive functions
    void removeLast(ListNode* &ptr) {
    // must be called on non-empty list
        if (ptr->next == NULL) remove(ptr);
        else removeLast(ptr->next);
    }
    void append(int v, ListNode* &ptr) {
        if (ptr == NULL) 
            ptr = new ListNode(v);
        else append(v,ptr->next);
    }
    void print(ListNode* &ptr) {
        if (ptr == NULL) return; 
        printf("%d ",ptr->data);
        print(ptr->next);
    }
    void printReverse(ListNode* &ptr) {
        if (ptr == NULL) return;
        printReverse(ptr->next);
        printf("%d ",ptr->data);
    }
    void removeVal(int v, ListNode* &ptr) {        
        if (ptr == NULL) return;       
        removeVal(v,ptr->next);
        if (ptr->data == v) remove(ptr);
    }
    void removeDups(ListNode* &ptr) {
        if (ptr == NULL) return;
        removeVal(ptr->data,ptr->next);
        removeDups(ptr->next);
    }
    int length(ListNode* &ptr) {
        if (ptr == NULL) return 0;
        return 1+length(ptr->next);
    }
    void reverse(ListNode* &ptr) {
        if (ptr == NULL || ptr->next == NULL) return;        
        ListNode* help = ptr->next;
        reverse(ptr->next);
        help->next=ptr; // help is non-null
        ptr=ptr->next;
        help->next->next = NULL;
    }
    ListNode* reverse(ListNode* ptr, ListNode* rest) { // Alternativ
    // reverse List pointed to by ptr
    // append rest to this list
        if (ptr == NULL) return rest;
        ListNode* help = ptr->next;
        ptr->next = rest;
        return reverse(help,ptr);
    }
    void remove(int i, ListNode* &ptr) {
    // requires: 0 <= i < length  
        if (i == 0) remove(ptr);
        else remove(i-1, ptr->next);
    }
    void insert(int i, int val, ListNode* &ptr) {
    // requires: 0 <= i < length
        if (i == 0) ptr = new ListNode(val,ptr);
        else insert(i-1, val, ptr->next);
    }
    int get(int i, ListNode* &ptr) {
    // requires: 0 <= i < length  
        if (i == 0) return ptr->data;
        return get(i-1,ptr->next);
    }
};


int main() {
    LinkedList* l = new LinkedList();
    l->append(1);
    l->append(2);
    l->append(3);
    l->append(4);
    l->append(2);
    l->append(5);
    l->append(2);
    l->append(4);
    l->print(); printf("\n");
    l->removeLast();
    printf("remove last:\n");
    l->print(); printf("\n");
    l->removeDups();
    printf("remove duplicates:\n");
    l->print(); printf("\n");
    l->reverse();
    printf("reverse:\n");
    l->print(); printf("\n");
    printf("element %d is %d (we start counting from 0)\n", 3, l->get(3));
    l->remove(2);
    printf("remove element number 2:\n");
    l->print(); printf("\n");
    printf("prepend 7:\n");
    l->prepend(7);
    l->print(); printf("\n");
    l->removeFirst();
    printf("remove first:\n");
    l->print(); printf("\n");
    printf("printReverse:\n");
    l->printReverse(); printf("\n");
    printf("list contains %d elements\n", l->length());
}

Code: Alles auswählen

g++ -o p d:\Files\Aufgabe.cpp