C言語によるアップグレード版標準双方向リンクTZListの実現

61504 ワード
アルゴリズム チェーン？メーター データ構造
目次
  • C言語によるアップグレード版標準双方向リンク表TZList
    • を実現する.
  • 概要
  • チェーン操作
  • チェーン
    • を作成します.
  • は、ノード
    • を作成する.
  • ノードデータ構造
  • 作成操作
  • ノード
    • を削除する.
  • エルゴードリンク
  • ソースコード
  • tzlist.h
  • tzlist.cn
  • テストファイルtest_tzlist.cn
    • C言語によるアップグレード版標準双方向リンクTZListの実現
    概要
    このブログのリンク:http://blog.csdn.net/jdh99jdh、転載は明記してください.
    本論文はアップグレードバージョンの標準双方向チェーンTZListを設計しました.より使いやすいです.
    チェーン操作
    チェーンのすべての操作はパッケージ化されており、より安全に使用されており、メモリの漏洩が容易ではない.
    チェーンを作成
    intptr_t list = TZListCreateList(gMid);
    チェーンを作成するとハンドルが戻ります.失敗するとリターン値はNULLです.
    ノードを作成
    ノードデータ構造
    // tNode     
typedef struct tagNode
{
    uint8_t *Data;
    int Size;

    struct tagNode *Next;
    struct tagNode *Last;
} TZListNode;
    フィールドの意味:
    フィールド
    意味
    データ
    任意のフォーマットのデータを格納することができます.
    Size
    データを格納するバイト数
    次のテキスト
    次のノードアドレス
    ラスト
    前のノードのアドレス
    次のノードが存在しない場合、NextはNULLである.このときノードはエンドノードです.前のノードが存在しない場合、LastはNULLである.ノードが先頭ノードになります.
    作成操作
    TZListNode* node = TZListCreateNode(list);
    作成に失敗した場合、戻り値はNULLです.
    一般的には、ノードにデータを格納し、格納されているものが構造体であれば、以下のように動作する.
    struct Test1
{
     int a;
     int b;
};

TZListNode* node = TZListCreateNode(list);
if (node == NULL) {
    return;
}
node->Data = TZMalloc(gMid, sizeof(struct Test1));
if (node->Data == NULL) {
    TZFree(node);
    return;
}
node->Size = sizeof(struct Test1);
struct Test1* test1 = (struct Test1*)node->Data;
test1->a = i;
test1->b = i;
TZListPrepend(list, node);
    TZListPrepend動作は、ノードをチェーンテーブルに押し込む.
    ノードを削除
    ノードを削除する操作は以下の通りです.
    // TZListRemove     
//                              
void TZListRemove(intptr_t list, TZListNode* node);
    例えば、最初のノードを削除する操作:
    TZListNode* node = TZListGetHeader(list);
if (node == NULL) {
    break;
}
struct Test1* test1 = (struct Test1*)node->Data;
printf("a = %d b = %d
    "    , test1->a, test1->b);
TZListRemove(list, node);
    チェーンを巡回する
    チェーンは双方向であり、最初のノードから巡回しても良いし、後尾ノードから巡回しても良いです.最初のノードを巡回してデータを印刷します.
    printf("         :
    "    );
TZListNode* node = TZListGetHeader(list);
for (;;) {
    if (node == NULL) {
        break;
    }

    for (int j = 0; j < node->Size; j++) {
        printf("%d\t", node->Data[j]);
    }
    printf("
    "    );
    node = node->Next;
}
    ソース
    注意してください.ソースに出てくるtzmallocはカスタマイズされたmalloc関数で、mallocに置き換えられます.
    tzlist.h
    // Copyright 2019-2020 The TZIOT Authors. All rights reserved.
//      
// Authors: jdh99 

#ifndef TZLIST_H
#define TZLIST_H

#include "tzbasedef.h"

#pragma pack(1)

// tNode     
typedef struct tagNode
{
    uint8_t *Data;
    int Size;

    struct tagNode *Next;
    struct tagNode *Last;
} TZListNode;

#pragma pack()

// TZListCreateList     
// mid tzmalloc        id
//           .      0      
intptr_t TZListCreateList(int mid);

// TZListCreateNode malloc      ,    NULL
//                      
//     Data        malloc   
TZListNode* TZListCreateNode(intptr_t list);

// TZListAppend            
void TZListAppend(intptr_t list, TZListNode* node);

// TZListPrepend            
void TZListPrepend(intptr_t list, TZListNode* node);

// TZListInsertBefore            
void TZListInsertBefore(intptr_t list, TZListNode* node, TZListNode* anchorNode);

// TZListInsertAfter            
void TZListInsertAfter(intptr_t list, TZListNode* node, TZListNode* anchorNode);

// TZListRemove     
//                              
void TZListRemove(intptr_t list, TZListNode* node);

// TZListBreakLink            
//             ,                     
void TZListBreakLink(intptr_t list, TZListNode* node);

// TZListDrop     
void TZListDrop(intptr_t list);

// TZListClear         
void TZListClear(intptr_t list);

// TZListIsEmpty      
bool TZListIsEmpty(intptr_t list);

// TZListGetNodeNum        
int TZListGetNodeNum(intptr_t list);

// TZListGetHeader      
TZListNode* TZListGetHeader(intptr_t list);

// TZListGetTail      
TZListNode* TZListGetTail(intptr_t list);

#endif
    tzlist.
    // Copyright 2019-2020 The TZIOT Authors. All rights reserved.
//      
// Authors: jdh99 

#include "tzlist.h"
#include "tzmalloc.h"

#pragma pack(1)

// tRoot    
typedef struct
{
    TZListNode* header;
    TZListNode* tail;
    int mid;
} tRoot;

#pragma pack()

// TZListCreateList     
// mid tzmalloc        id
//           .      0      
intptr_t TZListCreateList(int mid) {
    tRoot* root = TZMalloc(mid, sizeof(tRoot));
    if (root == NULL) {
        return 0;
    }
    memset(root, 0, sizeof(tRoot));
    root->mid = mid;
    return (intptr_t)root;
}

// TZListCreateNode malloc      ,    NULL
//                      
//     Data        malloc   
TZListNode* TZListCreateNode(intptr_t list) {
    if (list == 0) {
        return NULL;
    }
    tRoot* root = (tRoot*)list;
    TZListNode* node = TZMalloc(root->mid, sizeof (TZListNode));
    return node;
}

// TZListAppend            
void TZListAppend(intptr_t list, TZListNode* node) {
    if (list == 0 || node == NULL) {
        return;
    }

    tRoot* root = (tRoot*)list;
    if (root->tail == NULL) {
        root->header = node;
        root->tail = node;
        root->header->Last = NULL;
        root->tail->Next = NULL;
        return;
    }
    TZListInsertAfter(list, node, root->tail);
}

// TZListPrepend            
void TZListPrepend(intptr_t list, TZListNode* node) {
    if (list == 0 || node == NULL) {
        return;
    }

    tRoot* root = (tRoot*)list;
    if (root->header == NULL) {
        root->header = node;
        root->tail = node;
        root->header->Last = NULL;
        root->tail->Next = NULL;
        return;
    }
    TZListInsertBefore(list, node, root->header);
}

// TZListInsertBefore            
void TZListInsertBefore(intptr_t list, TZListNode* node, TZListNode* anchorNode) {
    if (list == 0 || node == NULL || anchorNode == NULL) {
        return;
    }

    tRoot* root = (tRoot*)list;
    node->Last = anchorNode->Last;
    node->Next = anchorNode;

    //                     
    if (anchorNode->Last != NULL) {
        anchorNode->Last->Next = node;
    } else {
        root->header = node;
    }
    anchorNode->Last = node;
}

// TZListInsertAfter            
void TZListInsertAfter(intptr_t list, TZListNode* node, TZListNode* anchorNode) {
    if (list == 0 || node == NULL || anchorNode == NULL) {
        return;
    }

    tRoot* root = (tRoot*)list;
    node->Last = anchorNode;
    node->Next = anchorNode->Next;

    //                     
    if (anchorNode->Next != NULL) {
        anchorNode->Next->Last = node;
    } else {
        root->tail = node;
    }
    anchorNode->Next = node;
}

// TZListRemove     
//                              
void TZListRemove(intptr_t list, TZListNode* node) {
    if (list == 0 || node == NULL) {
        return;
    }

    TZListBreakLink(list, node);
    TZFree(node->Data);
    TZFree(node);
}

// TZListBreakLink            
//             ,                     
void TZListBreakLink(intptr_t list, TZListNode* node) {
    if (list == 0 || node == NULL) {
        return;
    }

    tRoot* root = (tRoot*)list;
    //        
    if (node->Last == NULL && node->Next == NULL && root->header != node && root->tail != node) {
        return;
    }
    do {
        //          
        if (root->header == node && root->tail == node) {
            root->header = NULL;
            root->tail = NULL;
            break;
        }
        //      
        if (root->header == node) {
            root->header = node->Next;
            if (root->header != NULL) {
                root->header->Last = NULL;
            }
            break;
        }
        //      
        if (root->tail == node) {
            root->tail = node->Last;
            if (root->tail != NULL) {
                root->tail->Next = NULL;
            }
            break;
        }
        //       
        node->Last->Next = node->Next;
        node->Next->Last = node->Last;
    } while (0);

    node->Last = NULL;
    node->Next = NULL;
}

// TZListDrop     
void TZListDrop(intptr_t list) {
    if (list == 0) {
        return;
    }

    tRoot* root = (tRoot*)list;
    TZListClear(list);
    TZFree(root);
}

// TZListClear         
void TZListClear(intptr_t list) {
    if (list == 0) {
        return;
    }

    tRoot* root = (tRoot*)list;
    for (;;) {
        if (root->header == NULL) {
            break;
        }
        TZListRemove(list, root->header);
    }
}

// TZListIsEmpty      
bool TZListIsEmpty(intptr_t list) {
    if (list == 0) {
        return 0;
    }

    tRoot* root = (tRoot*)list;
    return root->header == NULL;
}

// TZListGetNodeNum        
int TZListGetNodeNum(intptr_t list) {
    if (list == 0) {
        return 0;
    }

    tRoot* root = (tRoot*)list;
    TZListNode* node = root->header;
    int num = 0;
    for (;;) {
        if (node == NULL) {
            break;
        }
        num++;
        node = node->Next;
    }
    return num;
}

// TZListGetHeader      
TZListNode* TZListGetHeader(intptr_t list) {
    if (list == 0) {
        return NULL;
    }

    tRoot* root = (tRoot*)list;
    return root->header;
}

// TZListGetTail      
TZListNode* TZListGetTail(intptr_t list) {
    if (list == 0) {
        return NULL;
    }

    tRoot* root = (tRoot*)list;
    return root->tail;
}
    テストファイルのtest_tzlist.
    #include "test_tzstatistics.h"
#include "tzstatistics.h"
#include "tzmalloc.h"

// tzmalloc       
#define TZMALLOC_USER_NUM_MAX 10

static void case1(void);

void TestTZStatistics(void) {
    printf("-------------------->test tzstatistics
    "    );
    TZMallocLoad(TZMALLOC_USER_NUM_MAX, 100 * 1024);
    TZStatisticsLoad(10);
    case1();
}

static void case1(void) {
    int itemId1 = TZStatisticsRegister("item1");
    TZStatisticsAdd(itemId1);
    TZStatisticsAdd(itemId1);
    TZStatisticsAdd(itemId1);

    TZStatisticsItem* item = TZStatisticsGetItem(itemId1);
    printf("%s:%d
    "    , item->Name, item->Value);

    int itemId2 = TZStatisticsRegister("item2");
    TZStatisticsAdd(itemId2);
    TZStatisticsAdd(itemId2);
    TZStatisticsClear(itemId2);

    char out[1024];
    TZStatisticsOutput(out, 1024);
    printf("out:
    %s
    "    , out);

    TZStatisticsClear(itemId2);
    TZStatisticsOutput(out, 1024);
    printf("out:
    %s
    "    , out);

    TZStatisticsClearAll();
    TZStatisticsOutput(out, 1024);
    printf("out:
    %s
    "    , out);
}
    出力:
    Hello World!
-------------------->case0:          
      :
0       0       0       0       0       0       0       0       0       0
1       1       1       1       1       1       1       1       1       1
2       2       2       2       2       2       2       2       2       2
3       3       3       3       3       3       3       3       3       3
4       4       4       4       4       4       4       4       4       4
            :
0       0       0       0       0       0       0       0       0       0
1       1       1       1       1       1       1       1       1       1
2       2       2       2       2       2       2       2       2       2
3       3       3       3       3       3       3       3       3       3
4       4       4       4       4       4       4       4       4       4
mid:0 tag:listTest total:102400 used:0 mallocNum:11 freeNum:11
-------------------->case0:    
-------------------->case1:           
      :
a = 0 b = 0
a = 1 b = 1
a = 2 b = 2
a = 3 b = 3
a = 4 b = 4
            :
a = 4 b = 4
a = 3 b = 3
a = 2 b = 2
a = 1 b = 1
a = 0 b = 0
mid:0 tag:listTest total:102400 used:0 mallocNum:22 freeNum:22
-------------------->case1:    
-------------------->case2:        
    :
0       0       0       0       0       0       0       0       0       0
1       1       1       1       1       1       1       1       1       1
2       2       2       2       2       2       2       2       2       2
3       3       3       3       3       3       3       3       3       3
4       4       4       4       4       4       4       4       4       4
         :
0       0       0       0       0       0       0       0       0       0
1       1       1       1       1       1       1       1       1       1
2       2       2       2       2       2       2       2       2       2
3       3       3       3       3       3       3       3       3       3
4       4       4       4       4       4       4       4       4       4
         :
4       4       4       4       4       4       4       4       4       4
3       3       3       3       3       3       3       3       3       3
2       2       2       2       2       2       2       2       2       2
1       1       1       1       1       1       1       1       1       1
0       0       0       0       0       0       0       0       0       0
mid:0 tag:listTest total:102400 used:0 mallocNum:33 freeNum:33
-------------------->case2:    
-------------------->case3:1000000             
mid:0 tag:listTest total:102400 used:0 mallocNum:10000034 freeNum:10000034
-------------------->case3:    
-------------------->case4:1000000             
mid:0 tag:listTest total:102400 used:0 mallocNum:21000034 freeNum:21000034
-------------------->case4:
    【転】Js配列(Arayオブジェクトの属性と方法)-JavaScript参照マニュアル