双向链表的实现与操作(C语言实现)

双向链表也叫双链表，是链表的一种，它的每一个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的随意一个结点開始，都能够非常方便地訪问它的前驱结点和后继结点。

单链表的局限

1。单链表的结点都仅仅有一个指向下一个结点的指针

2，单链表的数据元素无法直接訪问其前驱元素

3。逆序訪问单链表中的元素是极其耗时的操作

双向链表的操作

双向链表的新操作

1,获取当前游标指向的数据元素

2,将游标重置指向链表中的第一个数据元素

3,将游标移动指向到链表中的下一个数据元素

4,将游标移动指向到链表中的上一个数据元素

5,直接指定删除链表中的某个数据元素

DLinkListNode*DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode*DLinkList_Reset(DLinkList* list);

DLinkListNode*DLinkList_Current(DLinkList* list);

DLinkListNode*DLinkList_Next(DLinkList* list);

DLinkListNode*DLinkList_Pre(DLinkList* list);

头文件：

#ifndef _DDLinkList_H_

#define _DDLinkList_H_

typedef void DLinkList;

typedef struct DLinkListNode   //声明指针域

{

	DLinkListNode * pre;

	DLinkListNode * next;

}DLinkListNode;

DLinkList * DLinkList_Create();

void DLinkList_DesTroy(DLinkList * list);

void DLinkList_Clear(DLinkList* list);

int DLinkList_Length(DLinkList* list);

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

#endif

源文件：

// 双向链表.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include "DLinkList.h"

#include <stdlib.h>

#include <malloc.h>

typedef struct

{

	DLinkListNode header;

	DLinkListNode * slider; //游标

	int len;

}TDLinkList;

struct Value

{

    DLinkListNode header; //指针域

    int v; //数据域

};

int _tmain(int argc, _TCHAR* argv[])

{

	 int i = 0;

    DLinkList* list = DLinkList_Create();//创建链表

    struct Value* pv = NULL;

    struct Value v1;

    struct Value v2;

    struct Value v3;

    struct Value v4;

    struct Value v5;

    v1.v = 1;

    v2.v = 2;

    v3.v = 3;

    v4.v = 4;

    v5.v = 5;

    //插入5个数

    DLinkList_Insert(list, (DLinkListNode*)&v1, DLinkList_Length(list));

    DLinkList_Insert(list, (DLinkListNode*)&v2, DLinkList_Length(list));

    DLinkList_Insert(list, (DLinkListNode*)&v3, DLinkList_Length(list));

    DLinkList_Insert(list, (DLinkListNode*)&v4, DLinkList_Length(list));

    DLinkList_Insert(list, (DLinkListNode*)&v5, DLinkList_Length(list));

    for(i=0; i<DLinkList_Length(list); i++)

    {

        pv = (struct Value*)DLinkList_Get(list, i);

        printf("插入了：%d\n", pv->v);

    }

    printf("\n");

    //删除头尾

    DLinkList_Delete(list, DLinkList_Length(list)-1);

    DLinkList_Delete(list, 0);

    printf("删除头尾结点后：\n");

    for(i=0; i<DLinkList_Length(list); i++)

    {

		pv = (struct Value*)DLinkList_Next(list);

        printf("%d\n", pv->v);

    }

    printf("\n");

    DLinkList_Reset(list);//游标指向第一个结点   2

    DLinkList_Next(list);//游标指向第二个结点    3 

    pv = (struct Value*)DLinkList_Current(list);

    printf("游标移到第二个结点后的值： %d\n", pv->v);

    DLinkList_DeleteNode(list, (DLinkListNode*)pv);//删除第二个结点

    pv = (struct Value*)DLinkList_Current(list);

    printf("游标删除第二个结点后的值： %d\n", pv->v);

    DLinkList_Pre(list); //将游标向前移动一位

    pv = (struct Value*)DLinkList_Current(list);

    printf("游标向前移了一位后的值：%d\n", pv->v);

    printf("Length: %d\n", DLinkList_Length(list));

    DLinkList_DesTroy(list);

	system("pause");

	return 0;

}

//创建

DLinkList * DLinkList_Create()

{

	TDLinkList* list = NULL;

	list = (TDLinkList*)malloc(sizeof(TDLinkList));

	if(NULL != list)

	{

		list->len = 0;

		list->header.next = NULL;

		list->header.pre = NULL;

		list->slider = NULL;

	}

	return list;

}

//销毁

void DLinkList_DesTroy(DLinkList * list)

{

	free(list);

}

//清空

void DLinkList_Clear(DLinkList* list)

{

	TDLinkList* sList = (TDLinkList*)list;

	if(NULL != sList)

	{

		sList->len = 0;

		sList->header.next = NULL;

		sList->header.pre = NULL;

		sList->slider = NULL;

	}

}

//获得长度

int DLinkList_Length(DLinkList* list)

{

	TDLinkList* sList = (TDLinkList*)list;

	int len = -1;

	if(NULL != sList)

	{

		len = sList->len;

	}

	return len;

}

//插入

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)

{

	TDLinkList* sList = (TDLinkList*)list;

	int i = 0;

	int ret = 0;

	if((NULL != sList) && (pos >= 0) && (NULL != node))

	{

		DLinkListNode* current = (DLinkListNode*)sList;

		DLinkListNode* next = NULL;

		for( i=0; (i<pos) && (current->next != NULL); i++)

		{

			current = current->next;

		}

		next = current->next;

		current->next = node;

		node->next = next;

		if(NULL != next)

		{

			next->pre = node;

		}

		node->pre = current;

		if(sList->len == 0)

		{

			node->pre = NULL;

			sList->slider = node;

		}

		sList->len++;

		ret = 1;

	}

	return ret;

}

//获得结点

DLinkListNode* DLinkList_Get(DLinkList* list, int pos)

{

	TDLinkList* sList = (TDLinkList*)list;

	int i = 0;

	DLinkListNode * resnode  = NULL;

	if((pos >= 0) && (pos < sList->len) && (NULL != sList))

	{

		DLinkListNode * current = (DLinkListNode*)sList;

		for ( i=0; i<pos; i++)

		{

			current = current->next;

		}

		resnode = current->next;

	}

	return resnode;

}

//删除

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)

{

	TDLinkList* sList = (TDLinkList*)list;

	int i = 0;

	DLinkListNode* ret = NULL;

	if((NULL != sList) && (pos >= 0) && (pos < sList->len))

	{

		DLinkListNode* current = (DLinkListNode*)sList;

		DLinkListNode* next = NULL;

		for ( i=0; i<pos; i++)

		{

			current = current->next;

		}

		ret = current->next;

		next = ret->next;

		current->next = next;

		if(NULL != next)

		{

			next->pre = current;

			//当删除的结点是第一个结点的时候

			if(current == (DLinkListNode*)sList)

			{

				//前驱指针为空

				next->pre = NULL;

			}

		}

		if(sList->slider == ret)

		{

			sList->slider = next;

		}

		sList->len--;

	}

	return ret;

}

//通过指定结点删除

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)

{

	TDLinkList* sList = (TDLinkList*)list;

	DLinkListNode* ret = NULL;

	int i = 0;

	if((NULL != sList) && (NULL != node))

	{

		DLinkListNode* current = (DLinkListNode*)sList;

		for ( i=0; i<sList->len; i++)

		{

			if(current->next == node)

			{

				ret = current->next;

				break;

			}

			current = current->next;

		}

		if( ret != NULL )

        {

            DLinkList_Delete(sList, i);

        }

	}

	return ret;

}

//重置游标，使其到第一个结点处

DLinkListNode* DLinkList_Reset(DLinkList* list)

{

	TDLinkList* sList = (TDLinkList*)list;

	DLinkListNode* ret = NULL;

	if((NULL != sList))

	{

		sList->slider = sList->header.next;

		ret = sList->slider;

	}

	return ret;

}

//将游标移至当前结点处

DLinkListNode* DLinkList_Current(DLinkList* list)

{

	TDLinkList* sList = (TDLinkList*)list;

	DLinkListNode* ret = NULL;

	if(NULL != sList)

	{

		ret = sList->slider;

	}

	return ret;

}

//

DLinkListNode* DLinkList_Next(DLinkList* list)

{

	TDLinkList* sList = (TDLinkList*)list;

	DLinkListNode* ret = NULL;

	if((NULL != sList) && (NULL != sList->slider ))

	{

		ret = sList->slider;

		sList->slider = ret->next;

	}

	return ret;

}

DLinkListNode* DLinkList_Pre(DLinkList* list)

{

	TDLinkList* sList = (TDLinkList*)list;

	DLinkListNode* ret = NULL;

	if((NULL != sList) && (NULL != sList->slider ))

	{

		ret = sList->slider;

		sList->slider = ret->pre;

	}

	return ret;

}

执行结果：

插入了：1

插入了：2

插入了：3

插入了：4

插入了：5

删除头尾结点后：

2

3

4

游标移到第二个结点后的值： 3

游标删除第二个结点后的值： 4

游标向前移了一位后的值：2

Length: 2

请按随意键继续. . .

如有错误，望不吝指出。

巴特西

双向链表的实现与操作(C语言实现)

最新文章

热门文章