關(guān)于雙向鏈表和循環(huán)鏈表，維基上的解釋是：

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。

循環(huán)鏈表是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的最后一個(gè)結(jié)點(diǎn)指向頭結(jié)點(diǎn)，形成一個(gè)環(huán)。因此，從循環(huán)鏈表中的任何一個(gè)結(jié)點(diǎn)出發(fā)都能找到任何其他結(jié)點(diǎn)。循環(huán)鏈表的操作和單鏈表的操作基本一致，差別僅僅在于算法中的循環(huán)條件有所不同。


#include
#include
//定義鏈接節(jié)點(diǎn)結(jié)構(gòu) 包含了節(jié)點(diǎn)的數(shù)據(jù)域、前后指針域
typedef struct node {
char *data;
struct node *next;
struct node *prior;
} node;
//定義鏈表結(jié)構(gòu) 包含鏈表頭節(jié)點(diǎn)指針、鏈表長(zhǎng)度
typedef struct {
node *head;
int len;
}LinkedList;
//初始化雙向鏈表 包括生成表頭，初始化表長(zhǎng)度
LinkedList * init() {
LinkedList *L = NULL;
L = (LinkedList *)malloc(sizeof(LinkedList));
node *head = (node *)malloc(sizeof(node));
head->next = head;
head->prior= head;
L->head = head;
L->len = 0;
return L;
}
//向鏈表頭部插入數(shù)據(jù)
void add_to_head(LinkedList *L, char *data) {
node *dnode = (node *)malloc(sizeof(node));
dnode->data = data;
dnode->next = L->head->next;
dnode->prior= L->head;
L->head->next->prior = dnode;
L->head->next = dnode;
L->len++;
}
//向鏈表尾部插入數(shù)據(jù)
void add_to_tail(LinkedList *L, char *data) {
node *dnode = (node *)malloc(sizeof(node));
dnode->data = data;
dnode->next = L->head;
dnode->prior= L->head->prior;
dnode->prior->next = dnode;
L->head->prior = dnode;
L->len++;
}
//從鏈表中刪除下標(biāo)為index的節(jié)點(diǎn)，index從0開(kāi)始。
//index在鏈表前半段時(shí)從頭部遍歷 index在鏈表后半段時(shí)從頭部逆向遍歷
void del_data(LinkedList *L, int index) {
if(index > L->len) {
printf("index error");
return;
}
node * node_tmp = NULL;
int i=0;
if(index < L->len/2) {
node_tmp = L->head->next;
for(i=0; inext;
}
} else {
node_tmp = L->head->prior;
for(i=0; ilen-index; i++) {
node_tmp = node_tmp->prior;
}
}
node_tmp->prior->next = node_tmp->next;
node_tmp->next->prior = node_tmp->prior;
free(node_tmp);
L->len--;
}
//遍歷并打印鏈表（正向）
void foreach(LinkedList *L) {
node *n = L->head->next;
while(n != L->head) {
printf("%s\n", n->data);
n = n->next;
}
}
//遍歷并打印鏈表（逆向）
void rforeach(LinkedList *L) {
node *n = L->head->prior;
while(n != L->head) {
printf("%s\n", n->data);
n = n->prior;
}
}
int main() {
LinkedList *L;
L = init();
add_to_tail(L, "C");
add_to_tail(L, "C++");
add_to_tail(L, "C#");
add_to_tail(L, "java");
add_to_tail(L, "php");
add_to_tail(L, "python");
add_to_tail(L, "ruby");
add_to_tail(L, "object-c");
printf("打印鏈表\n");
foreach(L);
printf("刪除index=2的元素 打印鏈表\n");
del_data(L, 2);
foreach(L);
printf("逆向打印鏈表\n");
rforeach(L);
return;
}

以上代碼的運(yùn)行結(jié)果：