天天看點

連結清單(1)----單連結清單基本操作

1、單連結清單定義

單連結清單元素定義:

typedef  struct ListElement_t_{
    void  *data;
    struct ListElement_t_  *next;
} ListElement_t;
           

單連結清單定義:

typedef struct List_t_{
    int  size;
    int  (*match)(const void  *key1, const void  *key2);
    int  (*destroy)(void  *data);
    ListElement_t  *head;
    ListElement_t  *tail;
}  List_t;
           

2、單連結清單初始化:

int  list_init( List_t *list, int (*match)(const void *key1, const void *key2), int (*destroy)(void *data)){
    list->size = 0;
    list->match = match;
    list->destroy = destroy;
    list->head = NULL;
    list->tail = NULL;
    return 0;
}
           

3、插入

給定連結清單元素element, 在element之後插入資料data,需要開辟空間;

異常情況考慮:

(1)是否超過連結清單的最大容量

            if (list_is_full( list )

                    return OVERFLOW;

(2)申請節點空間是否成功

           if( (new_element = (ListElement_t *)malloc( sizeof( ListElement_t))) == NULL )

                          return  ALLOCA_ERROR;

需要考慮的情況:

(1)若element為NULL,則在頭結點插入;

    new_element->next = list->head;

    list->head = new_element;

        同時需要考慮是不是為空連結清單,如果是則需要維護尾指針;

    if(list_is_empty( list))

        list->tail = new_element;

(2)若element不為NULL,則在頭結點之後的某個節點後面插入,需要考慮element為尾節點

new_element->next = element->next;

        element->next = new_element;

        if( list_is_tail( list, element ))

            list->tail = element;

int list_insert_next( List_t *list, ListElement_t *element, const void *data ){
    ListElement_t  *new_element = NULL;
    if( ( new_element = (ListElement_t *)malloc( sizeof( ListElement_t ))) == NULL )
        return ALLOCA_ERROR;
  
    new_element->data = data;
    new_element->next =NULL;
 
    if( element == NULL ){
        if( list_is_empty( list) )
            list->tail = new_element;

        new_element->next = list->head;
        list->head = new_element;
    } else {
        if( list_is_tail( element ))
                list->tail = new_element;    
   
        new_element->next = element->next;
        element->next = new_element;
   }

   list->size++;
   return 0;
}
           

4、删除

删除指定元素element之後的元素。

異常情況:

(1)連結清單為空

          if( list_is_empty ( list) )

                   return -1;

(2)待删除節點為空,或者說删除尾節點之後的節點

          if( list_is_tail ( element ))

                   return -2;

需要考慮的情況為:

(1)如果element為NULL,則删除頭結點。

          *data = list->head->data;

          del_element = list->head;

          list->head = list->head->next;

          需要注意,是否删除的節點為最後一個:

          if( list_size( list ) == 1 )

                  list->tail = NULL;

(2)如果是其他節點,則删除element後面的節點

          *data = element->next->data;

          del_element = element->next;

          element->next = element->next->next;

          需要注意的是如果删除的是尾節點

          if( list_is_tail( list, del_element))

                  list->tail = element;

int list_remove_next( List_t *list, ListElement_t *element, void **data ){
    if( list_is_empty( list ) || list_is_tail(list, element))
        return -1;
    ListElement_t *del_element = NULL;
    if(element == NULL ){
        *data = list->head->data;
        del_element = list->head;
        list->head = list->head->next;
        if( list_size( list ) == 1 )
            list->tail = NULL;
    } else {
        *data = element->next->data;
        del_element = element->next;
        if ( list_is_tail( list, element->next) )
            list->tail = element;
    }
    free(del_element);
    del_element = NULL;
    list->size--;
    return 0;
}
           

5、銷毀連結清單

int list_destroy( List_t *list){
    void *data;
    while( list_size( list ) > 0 ){
        if( (list_remove_next( list, NULL, (void **)&data) == 0) && 
               ( list->destory != NULL ) )
            list->destory( data );
    }
    return 0;
}
           

6、其他函數

inline int  list_is_empty( List_t *list)
{
    return (list->size == 0 ? 1 : 0 );
}

inline int list_is_head( List_t *list, ListElement_t *element)
{
    return ( element == list->head ? 1:0);
}

inline int list_is_tail(List_t *list, ListElement_t *element)
{
    return ( element == list->tail ? 1:0);
}

inline int list_size( List_t *list)
{
    return list->size;
}
           

7、通過周遊求連結清單長度

int list_size( List_t *list ){
    if( list == NULL )
        return ERROR;

    ListElement_t *pNode = list->head;
    int len = 0;
    while( pNode != NULL ){
        ++len;
        pNode = pNode->next;
    }

    return len;
}
           

int list_size( List_t *list ){

    if( list == NULL )

        return ERROR;

    ListElement_t *pNode = list->head;

    int len = 0;

    while( pNode != NULL ){

        ++len;

        pNode = pNode->next;

    }

    return len;

}

其他相關題目下面以超連結形式給出:

連結清單面試題合集

1、單連結清單基本操作

2、雙連結清單基本操作

3、循環單連結清單基本操作

4、反轉單連結清單

5、查找單連結清單倒數第K個節點

6、倒序列印連結清單

7、查找連結清單中間節點

8、删除連結清單第K個節點,平均時間複雜度為O(1)

9、判斷連結清單是否有環

10、判斷兩個單連結清單是否相交

11、求相交連結清單的第一個相交節點

12、判斷是否有環,并判定是6型環還是0型環

13、判斷連結清單是否有環,并求環入口節點

14、合并兩個有序單連結清單

15、給定連結清單中間某節點,不周遊連結清單,将帶插入節點插入給定節點之前

16、删除連結清單重複元素