【データ構造——チェーン表】チェーン00——チェーンの知識点のまとめ

チェーンテーブルは動的な構造で、チェーンテーブルを作る時、チェーンテーブルの長さを知る必要がなく、ノードを挿入する時、新しいノードのためにメモリを割り当てて、ポインタを調整します.
1.一方向チェーンの定義

struct ListNode
{
	int data;
	ListNode *pNext;
};

2.チェーンテーブル挿入ノード

void InsertNode(ListNode** pHead,int data)//pHead   
{
	ListNode* pNew = new ListNode();
	pNew->data = data;
	pNew->pNext = NULL;

	if(*pHead == NULL)
	{
		*pHead = pNew;//             ，          
	}
	else
	{
		ListNode *pNode = *pHead;//    
		while(pNode->pNext != NULL)
			pNode = pNode->pNext;//          ，    

		pNode->pNext = pNew;
	}
}

3.チェーンテーブル削除ノード
リンクメモリは連続していないので、i番目のノードを探すときは、先頭から巡回する必要があります.効率はO(n).チェーンテーブルにある値を含むノードを削除します.

void DeleteNode(ListNode** pHead,int data)
{
	if(pHead == NULL || *pHead == NULL)
		return;
	ListNode* pToBeDelete = NULL;//         
	if((*pHead)->data == data)//           
	{
		pToBeDelete = *pHead;
		*pHead = (*pHead)->pNext;
	}
	else
	{
		//         ，                ，     
		ListNode* pNode = *pHead;
		while(pNode->pNext != NULL && pNode->pNext->data != data)
			pNode = pNode->pNext;

		//           ， pNode       
		if(pNode->pNext != NULL && pNode->pNext->data == data)
		{
			pToBeDelete = pNode->pNext;
			pNode->pNext = pNode->pNext->pNext;
		}
		//       
		if(pToBeDelete != NULL)
		{
			delete pToBeDelete;
			pToBeDelete = NULL;
		}
	}
}

剣指オフ
1.面接問題5——最後からチェーンを印刷します.
2.面接問題13——O(1)時間にチェーンノードを削除する
3.面接問題15——チェーンブロックの最後からk番目のノード
4.面接問題16——逆転リスト
5.面接問題17——二つの並べ替えのチェーン表を結合する
6.面接問題26——複雑チェーンのコピー
7.面接問題37——チェーン2つの最初の公共ノード
プログラミングの美しさ
8.3.4——ヘッドレスチェーンテーブルからノードを削除する
jurly
9.79——チェーンの並べ替えのアルゴリズム
10.チェーン表にリングを作る
11シングルチェーンテーブルにループがあるかどうかを検出する
12.ジョセフリング
13.双方向リンク表と二叉木