數據結構：C語言實現----帶頭雙向鏈表總結

雙向鏈表結構體宣告

typedef struct DNode
{
	int data;
	struct DNode *prior;
	struct DNode *next;
} DNode, *DLinkList;

（1)初始化

void InitDulList(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	plist->prior=plist->next=NULL;
}

（2）靜態函數：申請節點記憶體

static DLinkList ApplyNode(DLinkList next, DLinkList prior, int val)
{
	DLinkList s=(DNode *) malloc (sizeof (DNode));
	assert(s != NULL);
	if(s == NULL)
		return NULL;

	s->data=val;
	s->next=next;
	s->prior=prior;

	return s;
}

（3）求鏈表長度

int Listlength(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return -1;

	int count = 0;
	DLinkList p=plist->next; //p指向頭的下一個，即第一個有效結點
	while(p != NULL)
	{
		count++;
		p=p->next;
	}
	return count;
}

（4）得到某個結點，函數返回該結點

DLinkList GetNode(DLinkList plist, int pos)
{
	assert(plist != NULL);
	if(plist == NULL)
		return NULL;

	if(pos < 0)
		return NULL;

	DLinkList p=plist;
	while(pos && p != NULL)
	{
		p=p->next;
		pos--;
	}

	return p;
}

（5）插入

void Insert(DLinkList plist, int pos, int val)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	DLinkList p = GetNode(plist, pos); //要插入其後的結點的位置
	DLinkList s = ApplyNode(p->next, p, val); //要插入的結點

	if(p->next != NULL) //尾插單獨考慮
	{
		p->next->prior=s;	
	}
	p->next = s;
}

（6）頭插

void InsertHead(DLinkList plist, int val)
{
	assert(plist != NULL);
	if(plist == NULL)
		return; 

	DLinkList s=ApplyNode(plist->next, plist, val);
	if(plist->next != NULL) //若此時鏈表內沒有有效數據，爲空鏈
	{
		plist->next->prior = s;
	}
	plist->next = s;
}

（7）尾插

void InsertTail(DLinkList plist, int val)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	Insert(plist, Listlength(plist), val);
}

（8）刪除

void Delete(DLinkList plist, int pos)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	if(pos<0 || pos>Listlength(plist))
	{
		return;
	}

	DLinkList p=GetNode(plist,pos); //要刪除的結點
	if(p == NULL || p == plist) return;

	p->prior->next=p->next; 
	if(p->next != NULL) //尾刪無next
	{
		p->next->prior=p->prior;
	}
	free(p);
}

（9）頭刪

void DeleteHead(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	Delete(plist,1);
}

（10）尾刪

void DeleteTail(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	Delete(plist,Listlength(plist));
}

（11）判空

int ListEmpty(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return -1;

	if(plist->next == NULL)
		return -1;

	return 0;
}

（12）清空鏈表 

void ClearList(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	while(!ListEmpty(plist))
	{
		DeleteHead(plist);
	}
}

（13）輸出

void Show(DLinkList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
		return;

	DLinkList p=plist->next;
	while(p != NULL)
	{
		printf("%d -->",p->data);
		p=p->next;
	}
	printf("NULL\n");
}