「C與指針心得」21.鏈表-雙向鏈表

上一節講了鏈表的基本概念以及單項鍊表的使用方法,這一節主要講解雙向鏈表的使用方法。

雙向鏈表

含義:

雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個數據結點中都有兩個指針,分別指向直接後繼和直接前驅。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和後繼結點。

特點:

1)在數據結構中具有雙向指針
2)插入、刪除數據的時候需要考慮前後的方向的操作

用法:


typedef struct NODE{
struct NODE *prev;
struct NODE *next;
int data;
}Node;



1.初始化鏈表:

int InitNodeList(Node **node)
{
*node=(Node*)malloc(sizeof(Node));//鏈表分配內存空間
if(!*node)
{
return 0;
}
(*node)->prev=NULL;
(*node)->next=NULL;
return 1;
}

2.插入數據:

int InsertNodeList(register Node *root,int data)
{
register Node *this;
register Node *next;
register Node *newnode;
for(this = root;(next = this->next)!= NULL; this =next)
{
if(next->data == data)
{
return 0;
}
if(next->data > data)
{
break;
}
}
/*新節點分配內存空間*/
newnode = (Node *)malloc(sizeof(Node));
if(newnode == NULL)
{
return -1;
}


/*新節點插入鏈表*/
newnode->data = data;

/*插入新節點*/
newnode->next = next;
this->next = newnode;

if(this != root)
{
newnode->prev = this;
}
else
{
newnode->prev = NULL;
}

if(next != NULL)
{
next->prev = newnode;
}
else
{
root->prev = newnode;
}
return 1;
}

3.獲取鏈表長度

int LengthNodeList(Node *root)
{
int i = 0;
Node *previous;
previous=root->next;/*p指向鏈表的第一個結點。*/
/*循環鏈表,直到節點為空*/
while(previous)
{
i++;
previous=previous->next;
}
return i;
}

4.刪除節點:

void DestroyNodeList(Node *root)
{
Node *current,*next;

if(root == NULL)
{
return;
}

current=root;/*current 指向鏈表的根結點*/
/*當節點指向為空,即到了鏈表末尾,跳出*/
while(current)
{
next = current->next;/*指向當前結點的下一個結點。*/
free(current);/*釋放當前結點*/
current = next;/*指向下一個結點*/
}
}

5.調用:

int main(void)
{
Node *root;
int node_length = 0;
InitNodeList(&root); /*初始化鏈表,得到一個跟節點*/
InsertNodeList(root,10); /*向鏈表中插入一個數據*/
InsertNodeList(root,20); /*向鏈表中插入一個數據*/
node_length = LengthNodeList(root); /*獲取鏈表長度*/
printf("%d\n",node_length);
DestroyNodeList(root); /*銷燬鏈表*/
return 0;
}