データ構造のチェーンテーブル-チェーンテーブル実現及び常用操作(C++編)

18666 ワード
Algorithms C++ データ Structure
以前leetcodeと剣指offerをブラシして、チェーンテーブルを使う必要がある問題をたくさん見ましたが、チェーンテーブルを全面的にまとめる文章はあまり見られませんでした.チェーンテーブルをまとめた文章を見たばかりで、詳しくて、とてもいいです.
出典:http://www.cnblogs.com/byonecry/p/4458821.html
自分がそれ以上に補充した
データ構造のチェーンテーブル-チェーンテーブル実現及び常用操作(C++編)
0.概要
チェーンテーブルデータ構造挿入ノード(一方向チェーンテーブル)削除ノード(一方向チェーンテーブル)逆ループチェーンテーブル中間ノードを見つける
最後からk番目のノードを見つける
反転チェーンテーブル2つのチェーンテーブルが交差するか否かを判断し、交差点に戻る.
チェーンテーブルにループがあるか否かを判断する、接続点を取得し、ループの長さを算出する.
ツリーと双方向チェーンテーブル変換1.データ構造
1.1一方向チェーンテーブル
一方向チェーンテーブルのノードは次のとおりです.
≪データ・ドメイン｜Data Domain｜ldap≫:データ要素を格納する値.
ポインタドメイン(チェーンドメイン):次のノードアドレスまたは直接後続ノードを指すポインタを格納します.
struct Node{
    int value;
    Node * next;
};

1.2双方向チェーンテーブル
双方向チェーンテーブルのノードは次のとおりです.
≪データ・ドメイン｜Data Domain｜ldap≫:データ要素を格納する値.
左ポインタドメイン(左チェーンドメイン):前のノードアドレスまたは直接前継ノードを指すポインタを格納します.
右ポインタドメイン(右チェーンドメイン):次のノードアドレスまたは直接後続ノードを指すポインタを格納します.
struct DNode{
    int value;
    DNode * left;
    DNode * right;
};

2.常用操作例題
2.1ノードの挿入(一方向チェーンテーブル)
//p       i   
void insertNode(Node *p, int i){
    Node* node = new Node;
    node->value = i;
    node->next = p->next;
    p->next = node;
}

2.2ノードの削除(一方向チェーンテーブル)
1つのノードpを削除する必要がある場合、pの前のノードのnextをp>nextとして割り当てるだけであるが、一方向であり、pしか知らず、pの前のノードを知ることができないため、考え方を変換する必要がある.pの次のノードをpノードに上書きすれば、pを削除するのと同じです.
void deleteNode(Node *p){
    p->value = p->next->value;
    p->next = p->next->next;
}

2.3チェーンテーブルの逆方向遍歴
法一:逆ループチェーンテーブルは、事前にループしたノードの後出力、すなわち「先進後出」と同様であり、チェーンテーブルループをスタックに格納し、その後、ループスタックを順次スタックノードからポップアップし、逆ループ効果を達成することができる.
//1.  stack
void printLinkedListReversinglyByStack(Node *head){
    stack nodesStack;
    Node* pNode = head;
    //    
    while (pNode != NULL) {
        nodesStack.push(pNode);
        pNode = pNode->next;
    }
    while (!nodesStack.empty()) {
        pNode=nodesStack.top();
        printf("%d\t", pNode->value);
        nodesStack.pop();
    }
}//2.  
void printLinkedListReversinglyRecursively(Node *head){
    if (head!=NULL) {
        if (head->next!=NULL) {
            printLinkedListReversinglyRecursively(head->next);
        }
        printf("%d\t", head->value);
    }
}//3.  vector
vector< int > printListFromTailToHead(ListNode* head) {          vector< int > value;          if (head!=NULL){              value.insert(value.begin(),head->val);              while (head->next!=NULL){                  value.insert(value.begin(),head->next->val);                  head=head->next;              }          }          return value;      }
2.4中間ノードの特定
slowとfastポインタでマークすると、slowは一歩歩くたびに、fastは2歩歩くたびに、fastがエンドノードに着くと、slowは全長の半分、すなわち中間ノードに相当します.
//      
Node* findMidNode(Node* head){
    Node* slow = head;
    Node* fast = head;
    while (fast->next != 0&&fast->next->next!=0) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

2.5最後からk番目のノードを見つける
slowとfastポインタでマークし、fastポインタは事前にkステップを歩いてからslowとfastが同時に歩いて、fastが最後のノードに着いたとき、slowはfastの前のkノード、すなわち最後からk番目のノードです.
ListNode* FindKthFromTail(ListNode* pListHead,int k)  
{  
    if (pListHead == NULL || k == 0) //          k     0      
    {  
        return NULL;  
    }  
    ListNode* pAhead = pListHead;  
    ListNode* pBehind = NULL;  
    for (int i = 0; i < k-1; i++)  
    {  
        if (pAhead->m_pNext != NULL)  
        {  
            pAhead = pAhead->m_pNext;  
        }  
        else  
        {  
            return NULL;  
        }  
    }  
    pBehind = pListHead;  
    while(pAhead->m_pNext != NULL)  
    {  
          
        pAhead  = pAhead->m_pNext;  
        pBehind = pBehind->m_pNext;  
    }  
  
    return pBehind;    
}

2.6

， ， p1-p2-p3 p3-p2-p1。 。

， ：

       http://blog.csdn.net/feliciafay/article/details/6841115

2.7 ，

， y ， x ， 。 ， :m,n， distance＝|m-n|， distance ， ， ， ， 。

Node* findCrosspoint(Node* l1, Node* l2){
    int m = getLinkedListLength(l1);
    int n = getLinkedListLength(l2);
    int distance=0;
    Node *temp1= l1;
    Node *temp2= l2;
    if (m>n) {
        distance = m - n;
        while (distance>0) {
            distance--;
            temp1=temp1->next;
        }
    } else{
        distance = n - m;
        while (distance>0) {
            distance--;
            temp2 = temp2->next;
        }
    }
    while(temp1!=temp2&&temp1->next!=NULL&&temp2->next!=NULL){
        temp1=temp1->next;
        temp2=temp2->next;
    }
    if(temp1 == temp2){
        return temp1;
    }
    return 0;
}

2.8 ， ，

， ：http://www.cnblogs.com/xudong-bupt/p/3667729.html
：slow fast，slow ，fast ， ，fast slow（ ）， fast NULL， 。

//       
bool containLoop(Node* head){
    if (head==NULL) {
        return false;
    }
    Node* slow = head;
    Node* fast = head;
    while (slow!=fast&&fast->next!=NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast==NULL) {
        return false;
    }
    return true;
}

： ，slow fast ， ，slow length ，fast 2*length ，length 。

//      
int getLoopLength(Node* head){
    if (head==NULL) {
        return 0;
    }
    Node* slow = head;
    Node* fast = head;
    while (slow!=fast&&fast->next!=NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast==NULL) {
        return 0;
    }
    //slow fast     ，slow fast   
    //     ， slow    ，fast    
    int length = 0;
    while (slow!=fast) {
        length++;
        slow = slow->next;
        fast = fast->next->next;
    }
    return length;
}

：slow fast = ， ， 。

//       
Node* getJoinpoit(Node* head){
    if (head==NULL) {
        return NULL;
    }
    Node* slow = head;
    Node* fast = head;
    while (slow!=fast&&fast->next!=NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast==NULL) {
        return NULL;
    }
    Node* fromhead = head;
    Node* fromcrashpoint = slow;

    while (fromcrashpoint!=fromhead) {
        fromhead = fromhead->next;
        fromcrashpoint = fromcrashpoint->next;
    }
    return fromhead;
}

2.9

， ， ， 。 。 ， 。

：

struct BinaryTreeNode{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

BinaryTreeNode* convertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInLast){
    if (pNode == NULL) {
        return NULL;
    }
    BinaryTreeNode *pCurrent = pNode;
    if (pCurrent->left != NULL) {
        convertNode(pCurrent->left, pLastNodeInLast);
    }

    pCurrent->left = *pLastNodeInLast;
    if (*pLastNodeInLast != NULL) {
        (*pLastNodeInLast)->right=pCurrent;
    }

    *pLastNodeInLast = pCurrent;
    if (pCurrent->right != NULL) {
        convertNode(pCurrent->right, pLastNodeInLast);
    }
    return NULL;
}

BinaryTreeNode* convertBTToDLL(BinaryTreeNode* root){
    BinaryTreeNode *pLastNodeInLast = NULL;
    convertNode(root, &pLastNodeInLast);
    BinaryTreeNode *pHeadOfList = pLastNodeInLast;
    while (pHeadOfList != NULL && pHeadOfList->left != NULL) {
        pHeadOfList = pHeadOfList->left;
    }
    return pHeadOfList;
}
爬虫類の始まりの簡単な紹介
Androidがbitmapを使うOOMの心得と解決策について