数据结构（C语言）：双向链表的创建、插入、修改、删除、查找、修改等操作

.h文件

#ifndef DOUBLELINK_H_
#define DOUBLELINK_H_

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

/*数据域数据类型*/
typedef struct student
{
	int id;
	char name[32];
	int score;
}DataType;

/*结点数据类型*/
typedef struct node
{
	DataType data;//数据域
	struct node *pPre;//指向前驱结点
	struct node *pNext;//指向后继结点
}DouNode;

/*标签数据类型*/
typedef struct list
{
	DouNode *pHead;
	int cLen;
}DouList;

#endif

.c文件

#include "doublelink.h"

/*创建双向链表*/
DouList *createDouLink()
{
	DouList *pList = malloc(sizeof(DouList));
	if(NULL == pList)
	{
		perror("createDouLink malloc error!\n");
		return NULL;
	}

	pList->pHead = NULL;
	pList->cLen = 0;

	return pList;
}

/*判断链表是否为空*/
int isEmptyLinkList(DouList *pList)
{
	return pList->cLen == 0;
}

/*遍历打印双向链表*/
void showDouLink(DouList *pList,int dir)
{
	DouNode *pTmpNode = pList->pHead;
	if(0 == dir)//从头到尾遍历
	{
		while (pTmpNode != NULL)
		{
			printf("%d  %s  %d\n",pTmpNode->data.id,pTmpNode->data.name,pTmpNode->data.score);
			pTmpNode = pTmpNode->pNext;
		}
	}
	else if(1 == dir)//从尾到头遍历
	{
		while(pTmpNode->pNext != NULL)
		{
			pTmpNode = pTmpNode->pNext;
		}
		while(pTmpNode != NULL)
		{
			printf("%d  %s  %d\n",pTmpNode->data.id,pTmpNode->data.name,pTmpNode->data.score);
			pTmpNode = pTmpNode->pPre;
		}
	}
}

/*双向链表头插法*/
int insertHeadDouLink(DouList *pList,DataType *pdata)
{
	DouNode * pInsertNode = malloc(sizeof(DouNode));
	if(NULL == pInsertNode)
	{
		perror("insertHeadDouLink malloc error!\n");
		return -1;
	}
	memcpy(&(pInsertNode->data),pdata,sizeof(DataType));

	pInsertNode->pPre = NULL;
	pInsertNode->pNext = NULL;
	pInsertNode->pNext = pList->pHead;

	if(pList->pHead != NULL)
	{
		pList->pHead->pPre = pInsertNode;
	}
	pList->pHead = pInsertNode;
	pList->cLen++;

	return 0;
}

/*双向链表尾插法*/
int insertTailDouLink(DouList *pList,DataType *pdata)
{
	if(isEmptyLinkList(pList))//如果是空链表则用头插法
	{
		insertHeadDouLink(pList,pdata);
	}
	else
	{
		DouNode *pInsertNode = malloc(sizeof(DouNode));
		if(NULL == pInsertNode)
		{
			perror("insertTailDouLink malloc error!\n");
			return -1;
		}

		memcpy(&(pInsertNode->data),pdata,sizeof(DataType));
		pInsertNode->pPre =NULL;
		pInsertNode->pNext = NULL;

		DouNode *pTmpNode = pList->pHead;
		while(pTmpNode->pNext != NULL)
		{
			pTmpNode = pTmpNode->pNext;
		}
		pTmpNode->pNext = pInsertNode;
		pInsertNode->pPre = pTmpNode;
		pList->cLen++;
	}
	return 0;
}

/*双向链表头删法*/
int deleteHeadDouLink(DouList *pList)
{
	if(isEmptyLinkList(pList))
	{
		return 0;
	}

	DouNode *pTmpNode = pList->pHead;
	pList->pHead = pTmpNode->pNext;
	if(pList->pHead != NULL)
	{
		pList->pHead->pPre = NULL;
	}
	free(pTmpNode);
	pList->cLen--;

	return 0;
}

/*双向链表尾删法*/
int deleteTailDouLink(DouList *pList)
{
	if(isEmptyLinkList(pList))
	{
		return 0;
	}
	else if(1 == pList->cLen)
	{
		deleteHeadDouLink(pList);
	}
	else
	{
		DouNode *pTmpNode = pList->pHead;
		while(pTmpNode->pNext != NULL)
		{
			pTmpNode = pTmpNode->pNext;
		}
		pTmpNode->pPre->pNext = NULL;
		free(pTmpNode);
		pList->cLen--;
	}
	return 0;
}

/*双向链表的查找*/
DouNode *findDouList(DouList *pList,int score)
{
	DouNode *pTmpNode = pList->pHead;
	while(pTmpNode != NULL)
	{
		 if(score == pTmpNode->data.score)
		 {
		 	return pTmpNode;
		 }
		 pTmpNode = pTmpNode->pNext;
	}
	
	return NULL;
}

/*修改双链表指定结点*/
int changeDouLink(DouList *pList,int oldScore,int newScore)
{
	DouNode *pTmpNode = NULL;
	if((pTmpNode = findDouList(pList,oldScore)) != NULL)
	{
		pTmpNode->data.score = newScore;
	}
	return 0;
}

/*双向链表的销毁*/
void destroyDouLink(DouList **ppList)
{
	while((*ppList)->pHead != NULL)
	{
		deleteHeadDouLink(*ppList);
	}
	free(*ppList);
	*ppList =NULL;
}

/*删除双向链表指定结点*/
int deletePointNode(DouList *pList,int id)
{
	if(isEmptyLinkList(pList))
	{
		return 0;
	}
	DouNode *pTmpNode = pList->pHead;
	DouNode *pTmp = NULL;
	while(pTmpNode != NULL)
	{
		if(id == pTmpNode->data.id)
		{
			if(NULL == pTmpNode->pPre)
			{
				deleteHeadDouLink(pList);
				pTmpNode = pList->pHead;
			}
			else if(NULL == pTmpNode ->pNext)
			{
				deleteTailDouLink(pList);
				pTmpNode = NULL;
			}
			else
			{
				pTmpNode->pPre->pNext = pTmpNode->pNext;
				pTmpNode->pNext->pPre = pTmpNode->pPre;
				pTmp = pTmpNode->pNext;
				free(pTmpNode);
				pTmpNode = pTmp;
				pList->cLen--;
			}	
		}
		else
		{
			pTmpNode = pTmpNode->pNext;
		}
	}
	return 0;
}

/*创建双向环形链表*/
DouList *createLoopDouList(DouList *pList)
{
	DouNode *pTmpNode = pList->pHead;
	while(pTmpNode->pNext != NULL)
	{
		pTmpNode = pTmpNode->pNext;
	}
	pTmpNode->pNext = pList->pHead;
	pList->pHead->pPre = pTmpNode;
	 
	return pList;
}

/*判断链表是否有环*/
int isLoopDouList(DouList *pList)
{
	DouNode *pFast = pList->pHead;
	DouNode *pSlow = pList->pHead;
	while(1)
	{
		pFast = pFast->pNext;
		if(NULL == pFast)
		{
			return 0;//无环
		}
		if(pFast->data.id == pSlow->data.id)
		{
			return 1;//有环
		}

		pFast = pFast->pNext;
		if(NULL == pFast)
		{
			return 0;//无环
		}

		pSlow = pSlow->pNext;
		if(pFast->data.id == pSlow->data.id)
		{
			return 1;//有环
		}
	}
}
/*约瑟夫环*/
DouNode *Joseph(DouList *pList)
{
	DouNode *pFreeNode = pList->pHead;
	DouNode *pTmpNode = NULL;

	while(pList->cLen > 1)
	{
		pFreeNode = pFreeNode->pNext->pNext;
		pFreeNode->pPre->pNext = pFreeNode->pNext;
		pFreeNode->pNext->pPre = pFreeNode->pPre;
		pTmpNode = pFreeNode->pNext;
		free(pFreeNode);
		pList->cLen--;
		pFreeNode = pTmpNode;
	}
	return pFreeNode;
}

int main(int argc, const char *argv[])
{
	DouList *pList = NULL;
	pList = createDouLink();
//	DouNode *pTmpNode = NULL;

	DataType stu[] = {
		{1,"zhangsan",90},
		{2,"lisi",80},
		{3,"wangwu",70},
		{3,"liubei",60},
		{3,"guanyu",50},
		{6,"guanyu",50},
		{7,"guanyu",50},
		{8,"guanyu",50},
		{3,"guanyu",50}
	};
	int i = 0;
	for(i = 0;i < 9;i++)
	{
		//insertHeadDouLink(pList,&stu[i]);
		insertTailDouLink(pList,&stu[i]);
	}

//	showDouLink(pList,0);
/*
	pTmpNode = findDouList(pList,70);
	printf("%d,%s,%d\n",pTmpNode->data.id,pTmpNode->data.name,pTmpNode->data.score);
	
	changeDouLink(pList,70,75);
	printf("%d,%s,%d\n",pTmpNode->data.id,pTmpNode->data.name,pTmpNode->data.score);
*/	
	deletePointNode(pList,3);
	
	showDouLink(pList,0);
	
//	createLoopDouList(pList);
//	printf("%d\n",isLoopDouList(pList));
//	printf("%d\n",Joseph(pList)->data.id);	
	destroyDouLink(&pList);
	return 0;
}