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、删除連結清單重複元素