データ構造特集2(チェーンテーブル)

チェーンテーブル処理

チェーンテーブルの概念

malloc関数またはnew演算子を使用してチェーンテーブルノードにメモリ領域を割り当てる

malloc関数

new演算子

メモリリーク

チェーンテーブルの基本動作

チェーンテーブル

を作成する

検索要素

要素をdataでソート

挿入要素

削除要素

静的チェーンテーブル

チェーンテーブルの概念
  線形表は順序表とチェーン表に分けられ、順序表は「配列」と理解できる.配列を定義すると、メモリから連続アドレスが分割されて格納され、チェーンテーブルはいくつかのノードで構成され、格納位置が不連続です.チェーンテーブルの2つのノード間は、一般的に1つのポインタによって別のノードを指します.したがって、チェーンテーブルのノードは、ポインタドメインとデータドメインの2つの部分から構成されます.

struct node{
	typename data;//   
	node* next;//   
};

 データドメインは、ノードが格納するデータを格納し、ポインタドメインは次のノードのアドレスを指す.チェーンテーブルは、ヘッダノードが存在するか否かで、ヘッダノードのチェーンテーブルと、ヘッダノードが存在しないチェーンテーブルに分けられる.ヘッダノードは、一般にheadと呼ばれ、データドメインdataには何も格納されず、ポインタドメインnextは、最初のデータドメインにコンテンツがあるノード(最初のノード)を指す.最後のノードのnextはNULLを指し、チェーンテーブルの最後を表す.
malloc関数またはnew演算子を使用してチェーンテーブルノードにメモリ領域を割り当てる
  C言語ではmalloc、C++ではnew(推奨)を使用します.
malloc関数
 malloc関数はC言語におけるstdlibである.hヘッダファイルの下で動的メモリを申請するための関数であり,戻りタイプは申請の同変数タイプのポインタである.

typename* p = (typename*)malloc(sizeof(typename));

  int型変数とnode型構造体変数を申請する例:

int* p =(int*)malloc(sizeof(int));
node* p =(node*)malloc(sizeof(node));

  申請に失敗した後、空のポインタNULLに戻ります.
new演算子
  new演算子は、C++で動的メモリを申請するために使用される関数であり、戻りタイプは申請の同変数タイプのポインタです.

typename* p = new typename;

  同様にint型変数とnode型構造体変数を申請する例を挙げる.

int* p = new int;
node* p = new node;

  「new+タイプ名」だけで、そのタイプのメモリ領域を割り当て、対応するタイプのポインタを返します.申請に失敗した場合、C++例外メカニズム処理が開始されます.(失敗したのは、大きなダイナミック配列を申請したためです)
メモリリーク
  メモリ漏洩とは、mallocまたはnewを使用して開かれたメモリ領域が使用後に解放されないことを意味します.使用後はスペースを解放する必要があります.
 free関数はmalloc関数に対応し、同様にstdlibヘッダファイルの下にあります.使用方法はfreeのパラメータに解放するメモリ空間のポインタ変数を記入するだけです:free(p); delete演算子はnew演算子に対応し、使用方法は同上:delete(p); free関数とmalloc関数、delete演算子とnew演算子はペアで表示する必要があります.
チェーンテーブルの基本操作
チェーンテーブルの作成
前述のnewでは、各ノードのnextポインタを次のノードのアドレスに向けるだけでチェーンテーブルを形成するいくつかのばらばらなノードが作成されている.forループを使用して必要なチェーンテーブルを作成します.

#include
using namespace std;
struct node{
	int data;
	node* next;
};
//    
node* create(int array[]){
	node* p,*pre,*head;//pre           ，head    
	head = new node;//     
	head->data = NULL;
	pre = head;//  pre = head 
	for(int i =0;i<5;i++){//  array   
		p =new node;
		p->data = array[i];
		p->next = NULL;
		pre->next = p;
		pre = p;
	}
	return head;//        
} 
int main(){
	int array[] = {5,3,6,1,2};
	node* L = create(array);
	L = L->next;//            
	while(L != NULL){
		printf("%d",L->data);
		L = L->next;
	} 
	return 0;
}

要素の検索
 すでにチェーンテーブルがある場合は、指定された要素xがあるかどうかをどのように検索しますか?最初のノードから、現在のノードのデータドメインがxに等しいかどうか、雨果が等しいかどうかを絶えず判断するだけで、カウンタcount++が与えられ、チェーンテーブルの最後に達すると、countの値がチェーンテーブルの要素xの個数になる.

//  head            x    
int search(node* head,int x){
	int count = 0;//    
	node* p = head->next;//         
	while(p != NULL){
		if(p->data == x) count++;
		p = p->next;
	}
	return count;
}

要素をdataでソートする
考え方は毎回最小値を最後に置くことです.例えば、ヘッドノードを除く5つの5つのノード.各ノードに5,3,1,4,2の値を割り当て始める.1回目の外循環後の結果は5,3,4,2,1になった.2回目の外循環後の結果は5,3,4,1,2になった.3回目の外循環後の結果は5,4,1,2,3になった.4回目の外循環後の結果は5,1,2,3,4になった.5回目の外循環後の結果は1,2,3,4,5になった.

void SortList(Node *pHead)//          
{
	Node *q,*tail=pHead->next,*t;
	while(tail->next!=NULL)
	{
		tail=tail->next;//    
	}
	int min,i,j;
	for(i=0;i<ListLength(pHead);i++)//ListLength(pHead)      (      )    
	{
		q=pHead;
		t=q;
		min=q->next->data;
		for(j=0;j<ListLength(pHead)-i;j++)
		{
			if(min > q->next->data)//     ，  t              
			{
				min=q->next->data;
				t=q;
			}
			q=q->next;
		}
		if(tail==t->next)//           ，    
		{
			continue;
		}
		else
		{
			tail->next=t->next;
			t->next=t->next->next;
			tail=tail->next;
			tail->next=NULL;
		}
	}
}

要素の挿入
  i番目の位置に要素xを挿入するとは、挿入が完了した後、i番目の位置の要素がxであることを意味する.

// x   head         pos   
void insert(node* head,int pos,int x){
	node* p =head;
	for(int i =0;i<pos-1;i++){
		p = p->next;//pos-1     pos         
	}
	node* q = new node;//    
	q->data = x;
	q->next = p->next; //                  
	p->next = q;//              
} 

要素の削除
  削除要素とは、チェーンテーブル上のすべての値が所定の数xであることを削除することである.

は、ポインタ変数pによってノードを列挙し、別のポインタ変数preはpの前駆ノードを表す.

pが指すノードのデータドメインがちょうどxである場合、preが指すノードのnextをpが指すノードの次のノードに向ける.②pが指すノードのメモリ領域を解放します.③pをpreが指すノードの次のノードに向ける.

//   head              x   
void del(node* head,int x){
	node* p = head->next;
	node* pre = head;
	while(p != NULL){
		if(p->data == x){
			pre->next = p->next;
			delete(p);
			p = pre->next;
		}else{
			pre = p;
			p = p->next;
		}
	}
}

静的チェーンテーブル
  上面讲的都是动态链表,即需要指针来建立结点之间的连接关系.いくつかの問題でノードのアドレスが比較的小さい整数(例えば5桁のアドレス)である場合、動的チェーンテーブルを構築する必要がなく、便利な静的チェーンテーブルを使用する必要があります.
  静的チェーンテーブルの実現原理はhashであり,構造体配列を確立し,配列の下付き文字にノードを直接表すアドレスを与えることで,配列中の要素に直接アクセスしてノードにアクセスできる効果を達成する.また、スタティックチェーンテーブルにはヘッドノードは必要ありません.

struct Node{
	typename data;//   
	int next;//   
}node[size];

 静的チェーンテーブルを使用する場合は、構造体タイプ名と構造体変数名が異なることをできるだけ保証することに注意してください.