基本データ構造——単一チェーンテーブル

本文概要:基本データ構造シリーズ説明の単鎖表(付源コード)
 
1.チェーンテーブル構造の紹介
チェーンテーブルの各ノードには、次の2つの部分が含まれます.
(1)データ部:ノードのデータを保存する
(2)アドレス部:次のノードアドレスを保存する
チェーンテーブルのヘッダポインタは、チェーンテーブル構造の最初のノードを指し、最後のノードまで順次、最後のノードのアドレス部分には一般的に空のポインタNULLが配置される.
チェーンテーブル構造では,ポインタによりノードの論理的隣接が実現されるが,論理的に隣接するノードはメモリにおいて必ずしも隣接していないため,チェーンテーブルを使用する際に予め1つの記憶空間を割り当てる必要はなく,プログラマはmalloc関数によりノードの記憶空間を動的に割り当て,あるノードを削除する際にfree関数で空間を解放する.
チェーンテーブル構造の欠点は、各ノードにポインタ変数を追加的に格納する必要があるため、ストレージスペースを浪費することである.
チェーンテーブルには単鎖テーブル、双方向チェーンテーブル、循環チェーンテーブルなどいくつかの種類があり、本文は主に単鎖テーブルの関連操作を説明する.
 
2.チェーンテーブルおよびデータ要素タイプの定義
本プログラムの機能は,学生情報を単一チェーンテーブルで格納することであり,学生情報には,学号key,氏名name,年齢ageが含まれる.学生情報はデータ要素タイプData,チェーンテーブルデータ構造CLType,CLType内でデータ部分をDataタイプ変数で表し,チェーンテーブル構造のポインタで次のノードを指す.

typedef struct
{
	char key[10];
	char name[15];
	int age;
}Data;

typedef struct Node
{
	Data nodeData;
	struct Node *nextNode;
}CLType;

3.ノードの追加
ノードを追加すると、チェーンテーブルの末尾にノードが追加されます.手順は次のとおりです.
(1)メモリ領域を割り当て、追加するノードを保存する.
(2)先頭ポインタheadからチェックを開始し、最後のノードを見つける.
(3)表末尾ノードのアドレスを新規ノードアドレスに設定する.
(4)新規ノードのアドレスをNULLに設定する.
プログラムはmallocを使用して新しいノードのメモリ領域を申請します.

CLType *CLAddEnd(CLType *head,Data nodeData)
{
	CLType *node,*temp;
	if(!(node=(CLType*)malloc(sizeof(CLType))))
	{
		printf("      ！
");
		return NULL;
	}
	else
	{
		node->nodeData=nodeData;
		node->nextNode=NULL;
		if(head=NULL)
		{
			head=node;
			return head;
		}
		temp=head;
		while(temp!=NULL)
		{
			temp=temp->nextNode;
		}
		temp->nextNode=node;
		return head;
	}
}

4.ヘッド接点の挿入
チェーンテーブルの先頭にノードを挿入するには、次の手順に従います.
(1)メモリ領域を割り当て、新規ノードを保存する.
(2)新規ノードをheadが指すノードに向ける.
(3)headを新規ノードに向ける.

CLType *CLAddFist(CLType *head,Data nodeData)
{
	CLType *node;
	if(!(node=(CLType *)malloc(sizeof(CLType))))
	{
		printf("      ！
");
		return NULL;
	}
	else
	{
		node->nodeData=nodeData;
		node->nextNode=head;
		head=node;
		return head;
	}
}

5.ノードの検索
キーワードkeyでノードを検索しstrcmp関数を使用して検索を比較し、見つけたらそのノードポインタを返します.
 

CLType *CLFindNode(CLType *head,char *key)
{
	CLType *temp;
	temp=head;
	while(temp)
	{
		if(strcmp(temp->nodeData.key,key)==0)
		{
			return temp;
		}
	temp=temp->nextNode;
	}
	return NULL;
}

6.接点を挿入
チェーンテーブルにノードを挿入するには、次の手順に従います.
(1)メモリ領域を割り当て、新しいノードを保存する.
(2)挿入する場所を見つける;
(3)挿入されたノードは挿入位置が指すノードを指し,挿入位置は新規ノードを指す.
このプログラムでは、キーワードを使用して挿入する場所を見つけます.

CLType *CLInsertNode(CLType *head,char *key,Data nodeData)
{
	CLType *node,*temp;
	if(!(node=(CLType *)malloc(sizeof(CLType))))
	{
		printf("      ！
");
		return 0;
	}
	node->nodeData=nodeData;
	temp=CLFindNode(head,key);
	if(temp)
	{
		node->nextNode=temp->nextNode;
		temp->nextNode=node;
	}
	else
	{
		printf("       ！
");
		free(node);
	}
	return head;
}

7.ノードの削除
チェーンテーブルからノードを削除するには、次の手順に従います.
(1)削除するターゲットノードを見つける;
(2)このノードの前のノードを後のノードに向ける.
(3)このノードを削除する.
 

int CLDeleteNode(CLType *head,char *key)
{
	CLType *node,*temp;
	temp=head;
	node=head;
	while(temp)
	{
		if(strcmp(temp->nodeData.key,key)==0)
		{
			node->nextNode=temp->nextNode;
			free(temp);
			return 1;
		}
		else
		{
			node=temp;
			temp=temp->nextNode;
		}
	}
	return 0;
}

8.チェーンテーブルの長さを計算する
チェーンテーブルはメモリに連続的に格納されていないため、チェーンテーブルの長さを計算するにはチェーンテーブル全体を巡回する必要があります.
 

int CLLength(CLType *head)
{
	int len=0;
	CLType *temp;
	temp=head;
	while(temp)
	{
		len++;
		temp=temp->nextNode;
	}
	return len;
}

9.すべてのノードを表示

void CLAllNode(CLType *head)
{
	CLType *temp;
	Data nodeData;
	temp=head;
	printf("    %d   。        ：
",CLLength(head));
	while(temp)
	{
		nodeData=temp->nodeData;
		printf("  (%s,%s,%d)
",nodeData.key,nodeData.name,nodeData.age);
		temp=temp->nextNode;
	}
}

 
本明細書のソースコード:単一チェーンテーブル操作.cpp