4.リニアテーブルの静的チェーンテーブル(ポインタを外したシングルチェーンテーブル)

8465 ワード

3.12静的チェーンテーブル、単一チェーンテーブルとの違いはポインタを外すだけです
一般的にcc++プログラムは使用されませんが、コードアルゴリズムの考え方は見識する必要があります.
//            
//          1000
#define MAXSIZE 1000
typedef struct 
{
    ElemType data;
    //  (Cursor), 0      
    int cur;
} Component,
    /*       struct       ,          data cur   */
  StaticLinkList[MAXSIZE];

//       (StaticLinkList)                  ,    。     
//               。        ,    0    cur                ;
//           cur              ,            ,        ,  0

//     
//     space           ,space[0].cur    ,"0"     
Status InitList(StaticLinkList space)
{
    int i;
    for(i = 0; i < MAXSIZE-1; i++)
        space[i].cur = i+1;
    //        ,       cur 0
    space[MAXSIZE-1].cur=0;
    return OK;
}

//ListLength
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while (i)       //     ...  x 
    {
        i=L[i].cur;
        j++;
    }
    return j;
}

//         :                     ,     ,     
//                  malloc() free()       ,            ,
// ,
//// , , 0 int Malloc_SLL(StaticLinkList space) { // cur , int i = space[0].cur; // if(space[0].cur) space[0].cur=space[i].cur; return i; } // L i e Status ListInsert(StaticLinkList L, int i, ElemType e) { int j,k,l; // k k= MAXSIZE -1; if (i < 1 || i > ListLength(L)+1) return ERROR; // j = Malloc_SLL(L); if (j) { // data L[j].data=e; // i for(l=1; l<=i-1; l++) k=L[k].cur; // : k MAXSIZE -1;cur // i cur cur L[j].cur=L[k].cur; // i cur L[k].cur=j; return OK; } return ERROR; } // k void Free_SSL(StaticLinkList space, int k) { // cur cur space[k].cur=space[0].cur; space[0].cur=k; } // L i e Status ListDelete(StaticLinkList L, int i) { int j,k; if(i < 1 || i > ListLength(L)) return ERROR; k = MAXSIZE-1; for(j=1; j<=i-1;j++) k=L[k].cur; j = L[k].cur; L[k].cur=L[j].cur; Free_SSL(L, j); return OK; }

//スタティックチェーンテーブルのメリットとデメリット
利点:カーソルを変更するだけで、エレメントを移動する必要がなくなり、シーケンスストレージ構造での挿入と削除操作で多くのエレメントを移動する必要があるという欠点が改善されました.
欠点:連続ストレージ割り当てによるテーブル長の確定が困難な問題を解決していない.シーケンスストレージ構造のランダムアクセスの特性が失われました