データ構造--チェーンテーブルの実装(一)
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;
}