接続リスト-リソース構造<3>

接続リスト定義ADT

単純な接続リストのコードを1,2号の文章で解析した.
ただし、接続レポートを定義および定義するADTは、これまで実装されていません.

正しい資料構造学習順序
1.データ構造ADTの定義
2.定義されたADTの実装
3.利用資料構造

単純接続リスト定義ADT

作成する接続リストのADTを定義します.

ADT定義
1.void ListInit(List * plist)
初期化する図面のアドレス値をパラメータとして渡す
リスト作成後に最初に呼び出された関数
2.void LInsert(List * plist, LData data)
リストにデータを格納します.パラメータデータに渡される値を保存します.
3.int LFirst(List plist, LData pdata)
最初のデータはpdataが指すメモリに格納されます.
データ参照の初期化
参照成功時1失敗時0を返す
4.int LNext(List plist, LData pdata)
参照データの以下のデータはpdataが指すホームディレクトリに格納されます
連続参照のために繰り返し呼び出すことができます
参照を再起動するには、LFirst関数を呼び出す必要があります.
参照が成功した場合は1を返し、失敗した場合は0を返します.
5.LData LRemove(List * plist)//LDAT = int
1番目または2番目の関数の最後の戻りデータを削除
削除されたデータは戻されます
最後に返されたデータを削除し、連続した繰り返し呼び出しは許可されません.
6.int LCount(List * plist)
レポートに格納されているデータの数を返します.
7.void SetSortRule(List plist, int (comp)(LData d1, LData d2))
ソート基準としてリストに登録する関数

ADTを定義し,実装前に接続図面の新しいノードを追加した.
頭と尻尾にどこに格納されているかを調べてみましょう.
(この文章はあなたの頭に貼られます)

ヘッド
利点:ポインタ変数tailは不要
短所:保存順序を維持しない

尻尾
利点:保存順序の維持
欠点:ポインタ変数tailが必要

最後の貼り方は前の文章で見ましたが、貼り方を見てみましょう.

接続リストのしっぽが消えたので、ここに新しいノードを追加しましょう.

ここでは、頭に貼られた一連の順序を図で見てみましょう.

順番を見てみましょう.
1.新しいノードがheadを指すノード
2.headが新しいノードを指す
ご覧のように、tailポインタがない場合、接続リストとして新しいノードが追加されました.
(待って!!)
ADTの実装を理解する前に,スタックノードの概念を理解しておきましょう.

ヒープノード

スタックノードを使用する理由
1.スタックノードを使用して、コードのブランチ文を無効にします.

ヒープノードを無効にすると、上の図のようにポインタ変数にnullを配置し、追加したノードに基づいて
進行

ADT実施

1.スタックノード図面の初期化

図に示すようにheadはスタックノードを直接示す状態に初期化します
2.新規ノードの作成
コード#コード#

void FInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head->next;
	plist->head->next = newNode;

	(plist->numOfData)++;
}

3.クエリーデータ
コード#コード#

int LFirst(List * plist, LData * pdata)
{
	if(plist->head->next == NULL)
		return 0;

	plist->before = plist->head;
	plist->cur = plist->head->next;

	*pdata = plist->cur->data;
	return 1;
}

3-1次のデータを検索
コード#コード#

int LNext(List * plist, LData * pdata)
{
	if(plist->cur->next == NULL)
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

4.ノードの削除
コード#コード#

	LData LRemove(List * plist)
{
	Node * rpos = plist->cur;
	LData rdata = rpos->data;

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

5.ノードの位置合わせ
コード#コード#

void SInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	Node * pred = plist->head;
	newNode->data = data;

	while(pred->next != NULL &&
		plist->comp(data, pred->next->data) != 0)
	{
		pred = pred->next;
	}

	newNode->next = pred->next;
	pred->next = newNode;

	(plist->numOfData)++;
}