データ構造--チェーンテーブルの実装(一)

3941 ワード

現在、単一チェーンテーブルの基本的な操作しか実現されていません.チェーンテーブルを作成し、チェーンテーブルを消去し、追加、削除、検索、印刷します.すべてのチェーンテーブル要素、2つの順序付きチェーンテーブルの合計です.
その後、チェーンテーブルの反転など、チェーンテーブルに関する一般的な問題を含む、デュアルチェーンテーブル、およびループチェーンテーブルの基本的な操作も実現される.
コード:
/**
 *FILENAME:link,c
 *AUTHOR: XIANG CHANG SHENG
 *CREATE ON:2012-2-1
 */

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


/**
 *DESCRIPTION:
 To implement some link function,such as free a link list,delete,insert,find and other things
 */
struct Link {
    int key;
    struct Link *next;
};

struct Link * createLink() {
    struct Link *link_list = (struct Link *)malloc(sizeof(struct Link));
    link_list->next = NULL;
    return link_list;
}

struct Link * findPrevious(struct Link *link_list, int key) {
    struct Link *link_node;
    for (link_node = link_list; link_node->next != NULL; link_node = link_node->next) {
        if (link_node->next->key == key) {
            break ;
        }
    }
    return link_node;
}
struct Link * findKey(struct Link *link_list, int key) {
    struct Link *link_node = link_node;
    for (link_list = link_node; link_node != NULL; link_node = link_node->next) {
        if (link_node->key == key) {
            break;
        }
    }
    return ;
}


void insert(struct Link *link_list, int key) {
    struct Link *link_node;
    struct Link *insert_node;
    for (link_node = link_list; link_node->next != NULL && link_node->next->key < key; link_node = link_node->next) {
        ;
    }
    insert_node = (struct Link *)malloc(sizeof(struct Link));
    if (insert_node == NULL) {
        printf("fatal error:out of memory");
        return ;
    }
    else {
        insert_node->key = key;
        insert_node->next = link_node->next;
        link_node->next = insert_node;
    }
}

void delete(struct Link *link_list, int key) {
    struct Link *delete_node = findPrevious(link_list, key);
    struct Link *temp_node;
    if (delete_node->next != NULL) {
        temp_node = delete_node->next;
        delete_node->next = temp_node->next;
        free(temp_node);
    }
}

void freeLinkList(struct Link *link_list) {
    struct Link *link_node;
    struct Link *temp_node;
    for (link_node = link_list; link_node != NULL; link_node = temp_node) {
        temp_node = link_node->next;
        free(link_node);
    }
}
struct Link * unionLinkList(struct Link *link_list_1, struct Link *link_list_2) {
    struct Link *result = createLink();
    struct Link *link_node_1 = link_list_1->next;
    struct Link *link_node_2 = link_list_2->next;
    struct Link *result_node = result;
    while (link_node_1 != NULL || link_node_2 != NULL) {
        if (link_node_2 == NULL || (link_node_1 != NULL && link_node_1->key < link_node_2->key)) {
            result_node->next = link_node_1;
            result_node = result_node->next;
            link_node_1 = link_node_1->next;
        }
        else {
            result_node->next = link_node_2;
            result_node = result_node->next;
            link_node_2 = link_node_2->next;
        }
    }
    return result;
}
void printAllElement(struct Link *link_list) {
    struct Link *link_node;
    for (link_node = link_list; link_node->next != NULL; link_node = link_node->next) {
        printf("%d
", link_node->next->key); } } int main() { struct Link *header = createLink(); struct Link *header_2 = createLink(); struct Link *result; insert(header, 1); insert(header, 5); insert(header, 6); insert(header, 10); insert(header_2, 2); insert(header_2, 3); printAllElement(header); printf("*********************
"); printAllElement(header_2); printf("*********************
"); result = unionLinkList(header, header_2); printAllElement(result); return 0; }