チェーンテーブルパリティ位置交換

タイトル:チェーンテーブルの奇数ビットと偶数ビットを入れ替えて新しいチェーンテーブルを構成する
解析:チェーンテーブルを巡回し、チェーンテーブルを奇数ビットと偶数ビットに基づいて2つのチェーンテーブルに分解し、偶数ビットチェーンテーブルの各ノードの後ろに奇数ビットチェーンテーブルの対応する位置の各ノードを順次挿入します.2つの関数を定義します.1つはチェーンヘッダーノードを削除し、もう1つは指定したノードの後ろにノードを挿入します.チェーンテーブルを再編成するプロセスは、奇数ビットチェーンテーブルのヘッダノードを削除し、偶数ビットチェーンテーブルで指定した位置に挿入します.
時間複雑度O(N)

/*
 *                   
 */
#include <stdio.h>

struct Node {
    int   m_nValue;
    Node* m_pNext;
};


Node* DeleteHeadNode(Node** pHead) {
	if (!pHead || *pHead == NULL) return NULL;
	Node* pNode = *pHead;
	*pHead = pNode->m_pNext;
	pNode->m_pNext = NULL;
	return pNode;
}


void InsertAfterNode(Node* pNode, Node* pInsertedNode) {
	if (!pNode) return;
	pInsertedNode->m_pNext = pNode->m_pNext;
	pNode->m_pNext = pInsertedNode;
}

チェーンテーブルの分割:

Node* SeperateList(Node* pHead) {
    if (!pHead) return NULL;
    Node* pNode = pHead;
    Node* pNext = pNode->m_pNext;
    Node* pEvenHead = pNext; // second list head in even position
    while (pNext) {
        pNode->m_pNext = pNext->m_pNext;
        pNode = pNext;
        pNext = pNext->m_pNext;
    }
    return pEvenHead;
}

チェーンテーブルの再構築:

void RebuildList(Node** pHead) {
    if (!pHead || *pHead == NULL) return;
    Node* pOddNode = *pHead;
    Node* pEvenNode = SeperateList(pOddNode);
    if (!pEvenNode) {  // list has one node
        *pHead = pOddNode;
        return;
    }
    *pHead = pEvenNode;
    
	while (pEvenNode && pOddNode) {
		Node* pNode = DeleteHeadNode(&pOddNode);
		InsertAfterNode(pEvenNode, pNode);
		if (!pNode->m_pNext)
			break;
		pEvenNode = pNode->m_pNext;
	}
	if (pOddNode) {  // numbers of nodes in oddlist > numbers of nodes in evenlist
		pEvenNode->m_pNext->m_pNext = pOddNode;
	}
}

注意:ポインタに関するパラメータの伝達には、ポインタ(Node*)を伝達するか、ポインタを伝達するポインタ(Node**)を伝達するかなど、いくつかの点に注意する必要があります.
1、関数体の内部にポインタそのもの(すなわちポインタが指すアドレス、例えばpHead、非ポインタが指すアドレスの内容、例えばpHead->m_pNextなど)を修正し、関数体の外部でこのような変化に反応する必要がある場合は、必ずポインタのポインタ、例えば上述のDeleteHeadNode()、RebuidList()を用いる.
2、ポインタが指す内容だけを関数内で修正し、ポインタ自体の指向(のアドレス)を修正しない場合、すなわちpHead=pOtherPointerのような変更がなければ、ポインタを伝達すればよいし、pHead->m_nValue=0は、上記のSeperateList(),InsertAfterNode()のように、ポインタが指すアドレスが変わらないため、関数の外部でそのポインタが指すメモリにアクセスする際にメモリ内容の変化を読み取ることができる.
3、パラメータ伝達ポインタはNode*のように、関数体内で修正しても意味がありません.これはただの伝達値(伝達アドレスや伝達参照ではなく)であり、関数体内での変更は関数体の外部では見えません.関数体の外部は元の値に戻ります.基本的なデータ型のように、その指向する内容操作だけが意味があります.関数内のポインタの変化を体外で反応させるには、アドレスNode**(ポインタのアドレス)またはリファレンスNode*&(ポインタのリファレンス)を転送します.
4、ポインタのポインタは理解しにくい場合があります.ポインタを再定義すれば、typedef Node*pNodeなどの基本データ型の定義で理解できます.パラメータを渡すときにpNode pHeadを以下のように定義することができます.pNode* pHead;またはpNode&pHead;第1の定義は関数体内の変化であり、外部では体現できない、すなわち伝値である.その後、両者は、アドレスと参照(参照、別名、同じメモリを指す)という変化に反応することができる.
5、ポインタの指向(すなわちアドレス)、ポインタの指向するメモリ(すなわち内容)とを分けて考えると、上記パラメータ伝達の問題が容易に理解できる.
参照先:
[1]http://blog.csdn.net/sunnyskyliu/article/details/8099402