C言語による単一リンクテーブル(先頭ノードでない)の基本操作の実現

データ構造とアルゴリズムにおけるチェーンテーブルの重要性は言うまでもない.ここでは、チェーンテーブル(単一チェーンテーブル)の基本的な操作をCで実現します.チェーンテーブルの基本的な概念については、「データ構造とアルゴリズムのチェーンテーブル」というブログを参照してください.サンプルコードはhttps://github.com/chenyufeng1991/LinkedList .この例の単一チェーンテーブルでは、ヘッダノードはなく、ヘッダポインタが最初のノードを直接指します.先頭ノードの例は後で説明します.
(1)単一チェーンテーブルのノードタイプを定義する

typedef int elemType ;

//          
typedef struct ListNode{
    elemType element;      //   
    struct ListNode *next;   //   
}Node;

(2)リニアテーブルの初期化

// 1.      ，            
void initList(Node *pNode){

    pNode = NULL;
    printf("%s    ，     
",__FUNCTION__);
}

ヘッダノードを宣言した後、そのヘッダノードを空に設定します.すなわち、データドメインとアドレスドメインを空に設定すると、チェーンテーブルの初期化が完了します.
(3)線状テーブルの作成

// 2.     ，             
Node *creatList(Node *pHead){

    Node *p1;//    ，       
    Node *p2;//    ，             

    p1 = p2 = (Node *)malloc(sizeof(Node)); //     ,    
    if(p1 == NULL || p2 == NULL){

        printf("      
");
        exit(0);
    }
    memset(p1,0,sizeof(Node));

    scanf("%d",&p1->element);    //       
    p1->next = NULL;         //         
    while(p1->element > 0){        //      0   ，        
        if(pHead == NULL){       //  ，    
            pHead = p1;          //   p1     ，       pHead     p1
        }else{
            p2->next = p1;       //   ，    
        }
        p2 = p1;                //p1   ，p1     ，  p2      
        p1 = (Node *)malloc(sizeof(Node));    //        
        if(p1 == NULL || p2 == NULL){

            printf("      
");
            exit(0);
        }
        memset(p1,0,sizeof(Node));
        scanf("%d",&p1->element);
        p1->next = NULL;
    }
    printf("%s    ，      
",__FUNCTION__);
    return pHead;           //        
}

ここでは、0または負数が止まるまで手動で要素を入力します.
(4)チェーンテーブルの印刷

// 3.    ，     
void printList(Node *pHead){
    if(NULL == pHead){   //    
        printf("%s    ，    
",__FUNCTION__);
    }else{
        while(NULL != pHead){
            
            printf("%d ",pHead->element);
            pHead = pHead->next;
        }
        printf("
");
    }
}

アドレスフィールド順で印刷すればいいです.
(5)チェーンテーブルのクリア

// 4.     L      ，      L      ，        
void clearList(Node *pHead){

    Node *pNext;            //     pHead    ,             
    if(pHead == NULL){
        printf("%s    ，    
",__FUNCTION__);
    }
    while(pHead->next != NULL){

        pNext = pHead->next;//         
        free(pHead);   //      
        pHead = pNext;      //       
    }
    printf("%s    ，      
",__FUNCTION__);
}

クリアに成功したかどうかを確認するには、(4)のチェーンテーブルを使用してチェックを印刷すればよい.
(6)チェーンテーブル長の計算

// 5.        
int sizeList(Node *pHead){

    int size = 0;
    while(pHead != NULL){

        size++;
        pHead = pHead->next;
    }
    printf("%s    ，     %d 
",__FUNCTION__,size);
    return size;    //       
}

つまり、ノードが何個あるかを計算します.
(7)チェーンテーブルが空であるか否かを判断する

// 6.         ，      １，    ０
int isEmptyList(Node *pHead){
    if(pHead == NULL){

        printf("%s    ，    
",__FUNCTION__);
        return 1;
    }
    printf("%s    ，    
",__FUNCTION__);

    return 0;
}

(8)チェーンテーブルの位置要素の検索

// 7.       pos       ， pos    ，       
void getElement(Node *pHead, int pos){

    int i = 0;
    if(pos < 1){
        printf("%s    ，pos   
",__FUNCTION__);
    }

    if(pHead == NULL){
        printf("%s    ，    
",__FUNCTION__);
    }

    while(pHead != NULL){

        i++;
        if(i == pos){
            break;
        }
        pHead = pHead->next;    //      
    }
    if(i < pos){                  //pos       
        printf("%s    ，pos       
",__FUNCTION__);
    }

    printf("%s    ，   %d       %d
",__FUNCTION__,pos,pHead->element);
}

(9)ある要素値のチェーンテーブル内のメモリアドレスを返す

// 8.            x      ，           data      ，    NULL
elemType* getElemAddr(Node *pHead, elemType x){
    if(NULL == pHead){

        printf("%s    ，    
",__FUNCTION__);
        return NULL;
    }

    while((pHead->element != x) && (NULL != pHead->next)) {//         ，            
        pHead = pHead->next;
    }

    if((pHead->element != x) && (pHead != NULL)){
        //         
        printf("%s    ，       x 
",__FUNCTION__);
        return NULL;
    }

    if(pHead->element == x){
        printf("%s    ，   %d      0x%x
",__FUNCTION__,x,&(pHead->element));
    }

    return &(pHead->element);//       
}

(10)あるノードの値を修正する

// 9.      pos        x  ，       １，    ０
int modifyElem(Node *pNode,int pos,elemType x){

    int i = 0;
    if(NULL == pNode){
        printf("%s    ，    
",__FUNCTION__);
        return 0;
    }

    if(pos < 1){

        printf("%s    ，pos   
",__FUNCTION__);
        return 0;
    }

    while(pNode != NULL){

        i++;
        if(i == pos){
            break;
        }
        pNode = pNode->next; //      
    }

    if(i < pos) {                 //pos       

        printf("%s    ，pos       
",__FUNCTION__);
        return 0;
    }
    pNode->element = x;
    printf("%s    
",__FUNCTION__);

    return 1;
}

(11)ヘッダにノードを挿入する

// 10.             
int insertHeadList(Node **pNode,elemType insertElem){

    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert,0,sizeof(Node));
    pInsert->element = insertElem;
    pInsert->next = *pNode;
    *pNode = pInsert;          //   *pNode        ，             ；
    printf("%s    ，         
",__FUNCTION__);

    return 1;
}

(12)テーブルの末尾にノードを挿入する

// 11.             
int insertLastList(Node **pNode,elemType insertElem){

    Node *pInsert;
    Node *pHead;

    pHead = *pNode;
    pInsert = (Node *)malloc(sizeof(Node)); //       
    memset(pInsert,0,sizeof(Node));
    pInsert->element = insertElem;

    while(pHead->next != NULL){
        pHead = pHead->next;
    }
    pHead->next = pInsert;   //                    

    printf("%s    ，         
",__FUNCTION__);
    
    return 1;
}

(13)テスト関数

int main(int argc, const char * argv[]) {

    Node *pList;            //     

    initList(pList);       //     
    printList(pList);       //    ，    

    pList = creatList(pList); //    
    printList(pList);

    sizeList(pList);        //     
    printList(pList);

    isEmptyList(pList);     //          

    getElement(pList,3);  //       ，      3 ，   0
    printList(pList);

    getElemAddr(pList,5);   //    5     

    modifyElem(pList,4,1);  //      4       1
    printList(pList);

    insertHeadList(&pList,5);   //      5
    printList(pList);

    insertLastList(&pList,10);  //      10
    printList(pList);

    clearList(pList);       //    
    printList(pList);

    return 0;
}

参考資料:http://www.cnblogs.com/renyuan/archive/2013/05/21/3091506.html