資結個人作業 - linked-list

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INSERT 1
#define SEARCH 2
#define DELETE 3
// #define DEBUG IHATEBUG

struct _account
{
    unsigned int ID, type, amount;
    struct _account* next;
    struct _account* prev;
};
typedef struct _account Account;

Account* AccountList;
Account* AccountListTail;

void Append(Account* new);
int Count();
void Delete(Account* account);
Account* GetAccountByIndex(int index);
void Initial();
void Insert(Account* account);
Account* Last();
Account* Search(int ID);
Account* newAccount();
void Print(Account* account);
void PrintAll();
int RandomAction();
Account* RandomExistData();
void sortList(int left, int right);
void swapValue(Account* a1, Account* a2);

void Initial()
{
    AccountList = newAccount();
    #ifdef DEBUG
        printf ("Initial -- the AccountList is located at %X\n\n", AccountList);
    #endif
    AccountListTail = AccountList;
    int i;
    for(i = 0; i < 9; i++)
    {
        Account* tmp = newAccount();
        Append(tmp);
    }
    sortList(0, Count()-1);
}

/* 題目要求的部分 */

Account* Search(int ID)
{
    #ifdef DEBUG
        printf ("Searching ID=%d\n", ID);
    #endif
    Account* it = AccountList;
    while (it)
    {
        #ifdef DEBUG
            printf ("Compare it->ID=%d with ID=%d\n", it->ID, ID);
            printf ("it->next=%X\n", it->next);
        #endif
        if(it->ID == ID) return it;
        else it = it->next;
    }
    #ifdef DEBUG
        if(it)
        {
            printf ("Account found!\n");
            Print(it);
        }
        else
            printf ("Account not found.\n");
    #endif
    return NULL;
}

void Insert(Account* account)
{
    #ifdef DEBUG
        printf ("Inserting the following item: \n");
        Print(account);
        printf("\n");
    #endif
    if(Search(account->ID)) // Item duplicated.
    {
        printf("Item duplicated.");
        return;
    }
    else
    {
        Append(account);
        sortList(0, Count()-1);
    }
}

void Delete(Account* account)
{
    #ifdef DEBUG
        printf ("Deleting the following item: \n");
        Print(account);
        printf("\n");
        printf ("Prev item: ");
        if (account->prev) Print(account->prev);
        else printf("Prev is NULL!\n");
        printf("\n");
        printf ("Next item: ");
        if (account->next) Print(account->next);
        else printf("Next is NULL!\n");
        printf("\n");
    #endif

    if(!AccountList)
    {
        printf ("Nothing in the list!");
        return;
    }
    if(account == AccountList) // Delete the first item.
    {
        #ifdef DEBUG
            printf ("Deleting the first item.\n");
        #endif

        if(!(account->next)) // There is only one item in the list.
        {
            #ifdef DEBUG
                printf ("Only one item in the list.\n");
            #endif
            AccountList = NULL;
            AccountListTail = NULL;
            free(account);
        }
        else
        {
            account->next->prev = NULL;
            AccountList = account->next;
            free(account);
        }
    }
    else if (account == AccountListTail) // Delete the last item.
    {
        #ifdef DEBUG
            printf ("Deleting the last item.\n");
        #endif
        AccountListTail = account->prev;
        account->prev->next = NULL;
        free(account);
    }
    else
    {
        #ifdef DEBUG
            printf ("The previous account's next before edit is %X", account->prev->next);
        #endif
        account->prev->next = account->next;
        account->next->prev = account->prev;
        #ifdef DEBUG
            printf ("The previous account's next after edit is %X", account->prev->next);
        #endif
        free(account);
    }

}

/* 題目要求的部分 */

/* 其他直接用到的部分 */

void Print(Account* account)
{
    #ifdef DEBUG
        printf("This account is located at %X\n", account);
        printf("next=%X  prev=%X\n", account->next, account->prev);
    #endif
    printf ("ID: %d\ntype: %d\namount: %d\n\n", account->ID, account->type, account->amount);
}

void PrintAll()
{
    Account* it = AccountList;
    #ifdef DEBUG
        printf ("There are %d items in the list.\n", Count());
        printf("The link of the whole list :\n");
        while(it)
        {
            printf ("%d(%X) -> ", it->ID, it);
            it = it->next;
        }
        printf ("\n");
        it = Last();
        printf("The link of the whole list (reversed) :\n");
        while(it)
        {
            printf ("%d(%X) -> ", it->ID, it);
            it = it->prev;
        }
        printf ("\n");
        it = AccountList;
        printf ("Dumping the list.\n");
    #endif

    while(it)
    {
        Print(it);
        it = it->next;
    }
}

int RandomAction()
{
    int action[] = {INSERT, SEARCH, DELETE};
    return action[rand()%3];
}

Account* RandomExistData()
{
    return GetAccountByIndex(rand()%Count());
}

Account* newAccount()
{
    Account* newac = (Account*)malloc(sizeof(Account));
RandomID:
    newac->ID = rand()%(RAND_MAX-1000000000)+1000000000;
    if(Search(newac->ID)) { printf ("Duplicated! Re-generating ID...\n"); goto RandomID; }
    newac->type = rand()%90+10;
    newac->amount = rand();
    newac->next = NULL;
    newac->prev = NULL;
    return newac;
}

/* 其他直接用到的部分 */

/* 內部用到的功能 */
void Append(Account* newac)
{
    #ifdef DEBUG
        printf ("Appending the following item to the list.\n");
        Print(newac);
        printf ("\n");
    #endif
    if(!AccountList) // Nothing in the list.
    {
        #ifdef DEBUG
            printf ("Nothing in the list, point AccountList to the new item.\n");
        #endif
        AccountList = newac;
        AccountListTail = newac;
    }

    newac->prev = AccountListTail;
    AccountListTail->next = newac;
    AccountListTail = newac;
}

void swapValue(Account* a1, Account* a2)
{
    Account* temp = newAccount();
    temp->ID = a1->ID;
    temp->type = a1->type;
    temp->amount = a1->amount;
    a1->ID  = a2->ID;
    a1->type = a2->type;
    a1->amount = a2->amount;
    a2->ID = temp->ID;
    a2->type = temp->type;
    a2->amount = temp->amount;
    free(temp);
}

Account* GetAccountByIndex(int index)
{
    #ifdef DEBUG
        printf ("Getting item at index %d\n", index);
    #endif
    int i = 0;
    Account* it = AccountList;
    for (i = 0; it && i < index; i++)
        it = it->next;
    if(!it) printf ("Index %d not found!\n", index);
    return it;
}

int Count()
{
    #ifdef DEBUG
        printf ("Counting the number of item in the list.\n");
    #endif
    int count;
    Account* it = AccountList;
    for (count = 0; it; count++)
        it = it->next;
    #ifdef DEBUG
        printf ("Count = %d\n", count);
    #endif
    return count;
}

void sortList(int left, int right)
{
    #ifdef DEBUG
        printf ("Sorting the list with left=%d, right=%d\n", left, right);
    #endif

    if (left < right)
    {
        int pivot = GetAccountByIndex((left+right)/2)->ID;
        int i = left - 1, j = right + 1;
        while (i < j)
        {
            do ++i; while (GetAccountByIndex(i)->ID < pivot);
            do --j; while (GetAccountByIndex(j)->ID > pivot);
            if (i < j) swapValue(GetAccountByIndex(i), GetAccountByIndex(j));
        }

        sortList(left, i-1);
        sortList(j+1, right);
    }
}

Account* Last()
{
    return GetAccountByIndex(Count()-1);
}

/* 內部用到的功能 */

int main()
{
    srand(time(NULL));
    /* Test code. */

    // Initial();

    // printf("### Dumping the list.\n");
    // PrintAll();
    // putchar('\n');

    // printf("### There are %d items in the list.\n", Count());
    // putchar('\n');

    // printf ("### Print index 1\n");
    // Print(GetAccountByIndex(1));
    // putchar('\n');

    // printf("--------------------------------\n");
    // printf ("### Delete 1st item.\n");
    // Delete(GetAccountByIndex(0));
    // printf("### Dumping the list.\n");
    // PrintAll();
    // putchar('\n');

    // printf ("### Delete last item.\n");
    // Delete(GetAccountByIndex(Count()-1));
    // printf("### Dumping the list.\n");
    // PrintAll();
    // putchar('\n');

    // printf ("### Search ID=%d\n", GetAccountByIndex(0)->ID);
    // Print(Search((GetAccountByIndex(0))->ID));
    // putchar('\n');

    // printf("### There are %d items in the list.\n", Count());
    // putchar('\n');

    // Account* newac = newAccount();
    // printf ("### Created a new account: \n");
    // Print(newac);
    // printf("### Insert new account into the list.\n");
    // Insert(newac);
    // printf("### Dumping the list.\n");
    // PrintAll();
    // putchar('\n');

    // printf("### There are %d items in the list.\n", Count());
    // putchar('\n');

    /* Test code. */

    printf ("Program start. -- Initializing.\n\n");
    Initial();
    printf("Initialize completed. Dumping the list.\n\n");
    PrintAll();
    printf("\n\n");

    int i;
    Account* randomdata, *result;
    for (i = 0; i < 10; i++)
    {
        switch(RandomAction())
        {
            case INSERT:
                printf ("Action insert choosed!\n");
                Account* newac = newAccount();
                printf("New account created.\n");
                Print(newac);
                printf("Inserting into the list.\n");
                Insert(newac);
                printf("Insert completed. Dumping the list.\n");
                PrintAll();
            break;

            case SEARCH:
                printf ("Action search choosed!\n");
                randomdata = RandomExistData();
                if(!randomdata) { printf ("So bad! There is no data in the list!\n"); continue; }
                printf ("Going to search ID=%d\n", randomdata->ID);
                result = Search(randomdata->ID);
                if(result)
                {
                    printf ("Account found!\n");
                    Print(result);
                }
                else
                    printf ("Account not found.\n");
            break;

            case DELETE:
                printf ("Action delete choosed!\n");
                randomdata = RandomExistData();
                if(!randomdata) { printf ("So bad! There is no data in the list!\n"); continue; }
                printf ("Going to delete ID=%d\n", randomdata->ID);
                Delete(randomdata);
                printf ("Delete completed. Dumping the list.\n");
                PrintAll();
            break;
        }
        printf ("\n");
    }

    printf("Program end.\n");

    return 0;
}