内功修繕のデータ構造---チェーン表

13037 ワード
データ構造 チェーン？メーター
前の配列に続き、このページでは主にチェーンを学習し、所与の位置の値を作成、遍歴、検索、挿入を実現しました.他の操作は書きません.基本的に似ています.コードを見て、詳しい注釈があります.

  
  
  
  
    
   
   
   
   
  1. #include <stdio.h> 
    2. 
   
   
   
   
  2. #include <malloc.h> 
    3. 
   
   
   
   
  3. #include <stdlib.h> 
    4. 
   
   
   
   
  4. /* 
    5. 
   
   
   
   
  5. *             
    6. 
   
   
   
   
  6. * 
    7. 
   
   
   
   
  7. */ 
    8. 
   
   
   
   
  8. typedef struct Node 
    9. 
   
   
   
   
  9. { 
    10. 
   
   
   
   
  10.     int data;//    
    11. 
   
   
   
   
  11.     struct Node * pNext;//    
    12. 
   
   
   
   
  12. }NODE,*PNODE; 
    13. 
   
   
   
   
  13.  
    14. 
   
   
   
   
  14.  
    15. 
   
   
   
   
  15. /** 
    16. 
   
   
   
   
  16. *      
    17. 
   
   
   
   
  17. * @return PNODE  
    18. 
   
   
   
   
  18. * 
    19. 
   
   
   
   
  19. */ 
    20. 
   
   
   
   
  20. PNODE create(){ 
    21. 
   
   
   
   
  21.     int length;//     
    22. 
   
   
   
   
  22.     printf("              length = "); 
    23. 
   
   
   
   
  23.     scanf("%d",&length); 
    24. 
   
   
   
   
  24.     //          
    25. 
   
   
   
   
  25.     PNODE pHead = (PNODE)malloc(sizeof(NODE)); 
    26. 
   
   
   
   
  26.     if(NULL == pHead){ 
    27. 
   
   
   
   
  27.         printf("       ");   
    28. 
   
   
   
   
  28.         exit(-1); 
    29. 
   
   
   
   
  29.     } 
    30. 
   
   
   
   
  30.     //      
    31. 
   
   
   
   
  31.     PNODE pTail = pHead;//                 
    32. 
   
   
   
   
  32.     pTail->pNext = NULL; 
    33. 
   
   
   
   
  33.     //              
    34. 
   
   
   
   
  34.     int data; 
    35. 
   
   
   
   
  35.     for(int i=1;i<=length;i++){ 
    36. 
   
   
   
   
  36.         //    length    
    37. 
   
   
   
   
  37.         PNODE pNode = (PNODE)malloc(sizeof(NODE)); 
    38. 
   
   
   
   
  38.         if(NULL == pNode){ 
    39. 
   
   
   
   
  39.             printf(" %d       ",i); 
    40. 
   
   
   
   
  40.             exit(-1); 
    41. 
   
   
   
   
  41.         } 
    42. 
   
   
   
   
  42.         printf("    %d     :",i); 
    43. 
   
   
   
   
  43.         scanf("%d",&data); 
    44. 
   
   
   
   
  44.         pNode->data = data; 
    45. 
   
   
   
   
  45.         pNode->pNext = NULL; 
    46. 
   
   
   
   
  46.         pTail->pNext = pNode;//          ，                  
    47. 
   
   
   
   
  47.         pTail = pNode;//               
    48. 
   
   
   
   
  48.     } 
    49. 
   
   
   
   
  49.     return pHead; 
    50. 
   
   
   
   
  50. } 
    51. 
   
   
   
   
  51.  
    52. 
   
   
   
   
  52.  
    53. 
   
   
   
   
  53. /** 
    54. 
   
   
   
   
  54. *        
    55. 
   
   
   
   
  55. * @param PNODE pHead 
    56. 
   
   
   
   
  56. */ 
    57. 
   
   
   
   
  57. void traverse(PNODE pHead){ 
    58. 
   
   
   
   
  58.     if(NULL == pHead->pNext){ 
    59. 
   
   
   
   
  59.         printf("    "); 
    60. 
   
   
   
   
  60.         exit(-1); 
    61. 
   
   
   
   
  61.     } 
    62. 
   
   
   
   
  62.     PNODE cNode = pHead->pNext;//            
    63. 
   
   
   
   
  63.     int i = 1;//       
    64. 
   
   
   
   
  64.     while(NULL != cNode){//          
    65. 
   
   
   
   
  65.         printf(" %d      :%d
    "    ,i,cNode->data); 
    66. 
   
   
   
   
  66.         cNode = cNode->pNext;//        
    67. 
   
   
   
   
  67.         i ++; 
    68. 
   
   
   
   
  68.     } 
    69. 
   
   
   
   
  69.     return; 
    70. 
   
   
   
   
  70. } 
    71. 
   
   
   
   
  71.  
    72. 
   
   
   
   
  72. /** 
    73. 
   
   
   
   
  73. *            
    74. 
   
   
   
   
  74. * @param PNODE pHead 
    75. 
   
   
   
   
  75. * @param int pos 
    76. 
   
   
   
   
  76. * @return int 
    77. 
   
   
   
   
  77. */ 
    78. 
   
   
   
   
  78. int get(PNODE pHead,int pos){ 
    79. 
   
   
   
   
  79.     if(NULL == pHead->pNext){ 
    80. 
   
   
   
   
  80.         printf("    "); 
    81. 
   
   
   
   
  81.         exit(-1); 
    82. 
   
   
   
   
  82.     } 
    83. 
   
   
   
   
  83.     PNODE cNode = pHead->pNext;//            
    84. 
   
   
   
   
  84.     int i = 1;//    
    85. 
   
   
   
   
  85.     while(NULL != cNode && i < pos){//   pos    
    86. 
   
   
   
   
  86.         cNode = cNode->pNext; 
    87. 
   
   
   
   
  87.         i++; 
    88. 
   
   
   
   
  88.     } 
    89. 
   
   
   
   
  89.     if(NULL == cNode || i > pos){ 
    90. 
   
   
   
   
  90.         printf("    %d   ",pos); 
    91. 
   
   
   
   
  91.         exit(-1); 
    92. 
   
   
   
   
  92.     } 
    93. 
   
   
   
   
  93.     return cNode->data; 
    94. 
   
   
   
   
  94. } 
    95. 
   
   
   
   
  95.  
    96. 
   
   
   
   
  96. /** 
    97. 
   
   
   
   
  97. *            
    98. 
   
   
   
   
  98. * @param PNODE pHead 
    99. 
   
   
   
   
  99. * @param int pos 
    100. 
   
   
   
   
  100. * @param PNODE pNode 
    101. 
   
   
   
   
  101. */ 
    102. 
   
   
   
   
  102. void insert(PNODE pHead,int pos,PNODE pNode){ 
    103. 
   
   
   
   
  103.     PNODE cNode = pHead->pNext;//            
    104. 
   
   
   
   
  104.     int i = 1;//    
    105. 
   
   
   
   
  105.     while(NULL != cNode && i < pos){//   pos    
    106. 
   
   
   
   
  106.         cNode = cNode->pNext; 
    107. 
   
   
   
   
  107.         i++; 
    108. 
   
   
   
   
  108.     } 
    109. 
   
   
   
   
  109.     if(NULL == cNode || i > pos){ 
    110. 
   
   
   
   
  110.         printf("    %d   
    "    ,pos); 
    111. 
   
   
   
   
  111.         exit(-1); 
    112. 
   
   
   
   
  112.     } 
    113. 
   
   
   
   
  113.     if(NULL == cNode->pNext){// pos         ，     
    114. 
   
   
   
   
  114.         cNode->pNext = pNode; 
    115. 
   
   
   
   
  115.         return; 
    116. 
   
   
   
   
  116.     } 
    117. 
   
   
   
   
  117.     pNode->pNext = cNode->pNext;//                       
    118. 
   
   
   
   
  118.     cNode->pNext = pNode; 
    119. 
   
   
   
   
  119.     return; 
    120. 
   
   
   
   
  120. } 
    121. 
   
   
   
   
  121.  
    122. 
   
   
   
   
  122. void main(){ 
    123. 
   
   
   
   
  123.     PNODE  pHead = NULL;//    
    124. 
   
   
   
   
  124.     pHead = create();//     
    125. 
   
   
   
   
  125.     traverse(pHead);//     
    126. 
   
   
   
   
  126.     int data = get(pHead,2);//   2      
    127. 
   
   
   
   
  127.     printf("     %d
    "    ,data); 
    128. 
   
   
   
   
  128.     //         
    129. 
   
   
   
   
  129.     NODE node; 
    130. 
   
   
   
   
  130.     node.data = 100; 
    131. 
   
   
   
   
  131.     node.pNext = NULL; 
    132. 
   
   
   
   
  132.     insert(pHead,2,&node); 
    133. 
   
   
   
   
  133.     traverse(pHead); 
    134. 
   
   
   
   
  134. } 
    135.
浙大データ構造練習問題ノート:04-樹5 Root of AVL Tree(25分)