doublelinklist.c

数据结构线性表源代码

/*双向链表 ,但不是双向循环链表 , 此结构没有头节点*/
#include <stdio.h>

/*定义双向链表的结构类型*/
typedef int ElemType;
struct DNode
{
	ElemType data;
	struct DNode *left, *right;

};

/*初始化双向链表*/
void InitDList( struct DNode **hl)
{
	*hl = NULL;
	
	
}

/*在表头插入双向链表*/
int InsertFirstList(struct DNode **hl, ElemType e)
{
	struct DNode *newp;

	/*分配一个新的节点*/
	newp = malloc(sizeof(struct DNode));
	if( newp == NULL)
	{
		printf("InsertFirstList Error: malloc error\n");
		return -1;

	}

	/*给新节点赋值*/
	newp->data = e;
	newp->left = newp->right = NULL;

    /*如果一开始表为空*/
	if( *hl == NULL)
	{
		*hl = newp;
		return 0;

	}

	/*如果一开始的双向链表不为空*/
	if(*hl != NULL)
	{
		newp->right = *hl;
		(*hl)->left = newp;
		*hl = newp;
	}
	return 0;

}

/*向表尾插入双向链表节点*/
int InsertLastList( struct DNode **hl, ElemType e)
{
	struct DNode *newp, *p;
		
		p = *hl;

	/*分配一个新的节点*/
	newp = malloc(sizeof(struct DNode));
	if( newp == NULL)
	{
		printf("InsertFirstList Error: malloc error\n");
		return -1;
		
	}
	
	/*给新节点赋值*/
	newp->data = e;
	newp->left = newp->right = NULL;

	/*如果一开始表为空*/
	if( *hl == NULL)
	{
		*hl = newp;
		return 0;
		
	}

	/*如果一开始的双向链表不为空, 让p指向双链表的最后一个节点*/
	while (p->right != NULL)
	{
		p = p->right; 
	}
	p->right = newp;
	newp->left = p;
}

/*在双向链表的第pos 个位置插入元素值为e的节点*/
int InsertPosList( struct DNode **hl, int pos, ElemType e)
{
	struct DNode *newp, *p,*ppre;
	int count = 1;
	/*分配一个新的节点*/
	newp = malloc(sizeof(struct DNode));
	if( newp == NULL)
	{
		printf("InsertFirstList Error: malloc error\n");
		return -1;
		
	}
	
	/*给新节点赋值*/
	newp->data = e;
	newp->left = newp->right = NULL;

	/*检验pos 位置是否合法*/
	if(pos <1)
	{
		printf("The pos is not right.");
		return -1;
	}

	/*一开始双向链表为空*/
	if(*hl == NULL)
	{
		*hl = newp;
		
		return 0;
	}

	p = *hl;
	ppre = p ;
	
	/*
	if(pos == 1 && (*hl) != NULL)
		{
			newp->right = p;
			p->left = newp;
			*hl = newp;
	
			return 0;
	
		}*/
	
	
	/*查找pos 之前的一节点*/
	while(p->right!= NULL && count < pos)
	{
		count++;
		ppre = p;
		p = p->right;
	}

     /*插入节点 插入到ppre 之后*/
	newp->right = ppre->right;
	ppre->right = newp;
	newp->left = ppre;


}

/*删除双链表第pos 个节点*/
int DeletePosList( struct DNode **hl, int pos)
{
	/*分为两个大的类型，一个是 pos 为1， 一个是 pos 不为1 */

	if(*hl == NULL)
	{
		printf("Error: the list is empty.");
		return -1;
	}
	if( pos == 1)
	{
		/*分为两种类型，双链表只有一个节点,当双链表不只一个结点时,*/


	}
	else
	{
		/*分为两种类型，双链表只有一个节点,当双链表不只一个结点时,*/

	}
}

/*打印双向链表*/
int PrintDlist( struct DNode **hl)
{
	struct DNode *p;
	p = *hl;
	printf("Print the List\n");
	while ( p != NULL)
	{
		printf("%5d", p->data);
		p = p->right;
	
	}
	printf("\n");
	return 0;

}

int main()
{
	int flag;
	int i;
	int aFirst[10] ={15,2,25,33,8,99,5,23,46,12};
	int bLast[6] ={111,125,101,123,180,122};
	int c[6] = {1001, 1005, 2001, 1056, 3355, 8821};
	
	struct DNode *pdhead;/*定义双向链表结构*/

	InitDList(&pdhead);	

	/*插入双向链表表头插入*/
	for(i = 0; i<10; i++)
	{
		flag = InsertFirstList( &pdhead, aFirst[i]);
		if(flag == -1)
		{
			printf("InsertFirstList Error:\n");
			return -1;
		}

	}

	/*打印双向链表*/
	PrintDlist(&pdhead);

	/*插入双向链表表尾插入*/
	for(i = 0; i<6; i++)
	{
		flag = InsertLastList( &pdhead, bLast[i]);
		if(flag == -1)
		{
			printf("InsertFirstList Error:\n");
			return -1;
		}
		
	}
	
	/*打印双向链表*/
	PrintDlist(&pdhead);


	/*插入双向链表 pos*/
	for(i = 0; i<6; i++)
	{
		flag = InsertPosList( &pdhead, i+5, c[i]);
		if(flag == -1)
		{
			printf("InsertFirstList Error:\n");
			return -1;
		}
		
	}

	/*打印双向链表*/
	PrintDlist(&pdhead);

	
}