学步园

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;



typedef struct node
{
	int id;
	struct node* prev;
	struct node* next;
}Node,*pNode;

typedef struct list
{
	pNode nil; //带哨兵的链表结构
}List,*pList;

pList listInit(void)
{
	pList p = (pList)malloc(sizeof(List));
	p->nil = (pNode)malloc(sizeof(Node));
	p->nil->prev = p->nil;
	p->nil->next = p->nil;
	return p;
}

//有0或者1个元素list->nil->next = list->nil->prev
int isEmpty(pList list)
{
	//if(list->nil->next != list->nil->prev)//错误方式
	if(list->nil != list->nil->next)
		return 0;
	else
		return 1;
}
// 插入循环链表哨兵头部

int insertList(pList plist,pNode pnode)// nil - a - b 先处理ab之间的链接（先next后pre），在处理nil和a之间链接（先next后pre）
{
	if(pnode != NULL)
	{
		pnode->next = plist->nil->next;
		plist->nil->next->prev = pnode;
		pnode->prev = plist->nil;
		plist->nil->next = pnode;
		return 0;
	}
	else
	{
		printf("node doesnt exsit\n");
		return -1;
	}
}

// 找到id的节点并返回,没找到返回NULL
pNode seachList(pList list,int id)
{
	pNode tmp = list->nil->next;
	while(tmp!=list->nil && tmp->id != id)
	{
		tmp = tmp->next;
	}
	if(tmp != list->nil)
	{
		printf("search id = %d\n",tmp->id);
		return tmp;
	}
	else
	{
		printf("cant find id = %d\n",id);
		return NULL;
	}
	
}


//删除节点时注意释放内存空间,根据id删除节点，没有编写根据pnode删除对应节点
int deleteNode(pList list,int id)
{
	pNode tmp = NULL;
	if(!isEmpty(list))
	{
		if( (tmp=seachList(list,id)) != NULL)
		{
			tmp->next->prev = tmp->prev;
			tmp->prev->next = tmp->next;
			free(tmp);
			return 0;
		}
		else
		{
			printf("cant delet id = %d\n",tmp->id);
			return -1;
		}
	}
	else
	{
		printf("the list is empty cant delete\n");
		return -1;
	}
}

int deletefromhead(pList list)
{
	if(!isEmpty(list))
	{
		list->nil->next->next->prev = list->nil;
		list->nil->next = list->nil->next->next;
		return 0;
	}
	else
	{
		printf("list is empty cant delete form head\n");
		return -1;
	}
}


int destroyList(pList list)
{
	pNode pre = list->nil->next;
	pNode p;
	while(pre!=list->nil)
	{
		p = pre->next;
		free(pre);
		pre = p;
	}
	free(list->nil);
	free(list);
	return 0;
}


void printList(const char* s,pList list)
{
	pNode p = list->nil->next;
	printf("\n");
	printf("--------%s-------\n",s);
	if(isEmpty(list))
		printf("list is empty\n");
	else
	{
		while(p!=list->nil)
		{
			printf("id = %d\n",p->id);
			p = p->next;
		}
	}
}

int main(void)
{
	pNode node1,node2,node3;
	pNode tmp;
	pList mylist = listInit();
	
	node1 = (pNode)malloc(sizeof(Node));
	node2 = (pNode)malloc(sizeof(Node));
	node3 = (pNode)malloc(sizeof(Node));
	node1->id = 1;
	node2->id = 2;
	node3->id = 3;

	//insert to the list  
	insertList(mylist,node1);		
	insertList(mylist,node2);
	insertList(mylist,node3);
	printList("0:test insert",mylist);//3->2->1

	deletefromhead(mylist);
	printList("1:test delefromhead",mylist);//2->1

	tmp = seachList(mylist,5);
	printList("2:after search",mylist);//2->1
	tmp = seachList(mylist,2);
	printList("3:after search",mylist);//2->1

	deleteNode(mylist,1);
	printList("4:after deleteNode",mylist);// 2

	deleteNode(mylist,2);
	printList("5:after deleteNode",mylist);// null

	deletefromhead(mylist); // null
	printList("6:after deletefromhead",mylist);

	//清理内存
	destroyList(mylist);
	return 0;
}

自己写的代码，欢迎指正和提问，该算法源自算法导论。打印部分不是很美观，测试正常。