バックグラウンドグループ賈浩琛周報(2020.12.7-12.13)

相変わらずc言語学習内容

チェーンテーブルの応用

具体例として、チェーンテーブルの連結

を参照する.

チェーンテーブルの逆置き

チェーンテーブルサイクル

チェーンテーブル作成

チェーンテーブル表尾の判断

双方向チェーンテーブル

チェーンテーブルの応用
チェーンテーブルのマージを具体的な例で見る
タイトル:
2つの先頭ノードの学生チェーンテーブルを作成し、各ノードには名前、学号、成績が含まれており、チェーンテーブルは学号昇順に並べられ、それらを学号昇順に並べられたチェーンテーブルに統合します.
アルゴリズム解析
Merge関数でチェーンテーブルを結合し、関数の中で2つのポインタ変数p.qを定義し、それぞれHA、HBの2つのチェーンテーブルのヘッダノードを指し、rはHAのヘッダノードを結合する時に状況を分けなければならない:HAとHBはすべて処理が終わっていない;HAが終わってHBは遊んでいません;HB完了HA完了していない場合は、常に小さなチェーンテーブルをHCにリンクしてこそ、秩序を保つことができます
チェーンテーブルタイプは次のように定義されます.

typedef struct node
{
     
	char name[20];
	int number;
	int score;
	struct node *next;//nex                 
}Node,*LinkList;

連結は次のとおりです.

void Merge(LinkList HA,LinkList HB)
{
     
	LinkList HC;
	Node *p,*q,*r;
	p=HA->next;
	q=HB->next;
	r=HC=HA;
	while(p&&q)//      
	{
     
		if(p->number<=q->number)
		{
     
			r->next=p;
			r=p;
			p=p->next;
		}
		else
		{
     
			r->next=q;
			r=q;
			q=q->next;
		}
	}
	if(p)//HB     
		r->next=p;
	if(q)//HA     
		r->next=q;
	free(HB);//  HB    
}

チェーンテーブルの逆置き
アルゴリズム解析
元のチェーンテーブルの各ノードを順番に取り出し、新しいチェーンテーブルに最初のノードとして挿入します.
逆設定プログラムは次のとおりです.

void Reverse(LinkList head)
{
     
	Node *p,*q;
	p=head->next;//p      
	head->next=NULL;//      
	while(p)
	{
     
		q=p->next;
		p->next=head->next;//              
		head->next=p;
		p=q;
	}
}

チェーンテーブルサイクル
チェーンテーブルの作成
ループチェーンテーブルと単一チェーンテーブルの違いは、主に、単一チェーンテーブルの末尾ノードポインタドメインがNULLであり、ループチェーンテーブルの末尾ノードポインタがヘッダノードを指すことにある.

void CreatByRear(LinkList)
{
     
	Node *r,*s;
	char name[20];
	int number;
	r=head;
	printf("           ：
");
	while(1)
	{
     
		scanf("%s",name);
		scanf("%d",&number);
		if(number==0)
			break;
		s=(Node *)malloc(sizeof(Node));//         
		strcpy(s->name,name);
		s->number=number;
		r->next=s;//          
		r=s;//r      
	}
	r->next=head;//                
}

チェーンテーブルテールの判断
このノードのポインタドメインがヘッダノードを指しているかどうかを判断する(p->next==head).
にほうこうチェーンテーブル
双方向チェーンテーブルでは、ノードはデータドメインのほかに2つのチェーンドメインがあり、1つは直接後続のノードアドレスを格納し、右チェーンドメインと呼ばれる.左チェーンドメインと呼ばれる直接前駆ノードアドレスを格納します.C言語における双方向チェーンテーブルは以下のように定義することができる.

typedef struct node
{
     
	int data;//    
	struct node *prior;//   
	struct node *next;//    
}DLNode,*DlinkList;