資料結構線性表雙向連結清單

雙向連結清單的實作

雙向連結清單與之前的連結清單之間的差別是雙向連結清單的每個節點既有指向後面節點的指針,又有指向前面節點的指針.

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1
typedef int ElemType;

/*
待完成任務:實作雙向連結清單定義,雙向連結清單的插入及删除 
在雙向連結清單的結構體定義時,使用typedef定義*DuLinkList 是為了更友善的調用結構體内的變量,
并且在調用函數時隻需要輸入通過*DuLinkList定義的結構體即可直接傳入位址進入函數,進而使題目簡化. 
*/

typedef struct DuLNode{
	ElemType data;
	struct DuLNode *Prior;
	struct DuLNode *Next;
}DuLNode,*DuLinkList;

//雙向連結清單的初始化 
int InitDuList(DuLinkList &L){
	L=(DuLinkList)malloc(sizeof(DuLinkList));
	L->Prior=L;
	L->Next=L;
	if(L)
	{
		return OK;
	}
	else
	{
		return ERROR;
	}
}

//雙向連結清單的尾插法 
void TailCreatDuList(DuLinkList &L){
	int i,n;
	DuLinkList Head=L,Tail=L;
	printf("請輸入需要插入的元素的數量:");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		int a;
		DuLinkList Insert =(DuLinkList)malloc(sizeof(DuLinkList));
		scanf("%d",&a);
		Insert->data=a;
		Insert->Prior=Tail;
		Tail->Next=Insert;
		Insert->Next=Head;
		Head->Prior=Insert;
		Tail=Insert;
	}
}

//雙向連結清單的周遊
void TravelList(DuLinkList L)
{
	int i=1;
	DuLinkList Head=L,Travel=L->Next;
	do
	{
		printf("第%d個元素的值為:%d\n",i,Travel->data);
		i++;
		Travel=Travel->Next;
	}while(Travel!=Head);
}

//雙向連結清單的删除
void DeleteList(DuLinkList &L)
{
	int i;
	DuLinkList Move=L;
	printf("輸入删除元素的位置");
	scanf("%d",&i);
	//通過for循環将Move節點移動到需要删除的節點位置 
	for(;i>0;i--)
	{
		Move=Move->Next;
	}
	/*
	先将move前面節點的next指向move後面的節點
	再将move節點的next的prior指向move前面的節點
	以此來完成節點的删除
	*/
	Move->Prior->Next=Move->Next;
	Move->Next->Prior=Move->Prior;
	//删除Move節點 
	delete Move;
}

int main()
{
	DuLinkList A;
	InitDuList(A);
	TailCreatDuList(A);
	TravelList(A);
	
	DeleteList(A);
	TravelList(A)
	
	return 0;
}
           

[參考文獻]

資料結構c語言版