数据结构与算法(二)-双向链表

大话数据结构笔记， 双向链表

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <string.h>

//双向链表的节点结构
typedef struct LinkListNode
{
	int data;
	struct LinkListNode *prev, *next;
} DLinkList;

DLinkList *DLinkList_p;

//初始化双向链表
DLinkList_p InitDLinkList(int size){

	DLinkList_p p, pHead;
	//生成头节点
	p = (DLinkList_p)malloc(sizeof(DLinkList));
	if(NULL == p) {
		printf("分配内存失败\n");
		exit(0);
	}
	p->prev = NULL;
	p->next = NULL;
	p->data = -1;
	
	pHead = p;
	int i;
	for(i=1; i<size; i++) {//头结点， 然后才是第一个节点，所以 i 从 1， 开始循环
		//新建一个链表的节点
		DLinkList_p new_q = (DLinkList_p)malloc(sizeof(DLinkList));
		if(NULL == new_q) {
			printf("分配内存失败\n");
			exit(0);
		}
		new_q->next = NULL;	//新节点和下一个节点的关系, 下一个节点没有，就用NULL代替
		new_q->prev = p;	//新节点和前一个节点关系. 指向前一个节点
		new_q->data = -1; 	//给新节点填充数据, 我这里给填充为 -1
		
		p->next = new_q;	//上一个节点 和 下一个节点的关系 next 指针
		p = new_q;		//然后移动指针 p 到下一个节点，继续循环
	}	

	return pHead;
}

//打印链表-只需要一个指针就可以打印元素了
void PrintDLinlList(DLinkList_p L){

	DLinkList_p p = L->next;
	while(!p) {
		printf("val=%d \n", p->data);
		p = p->next;
	}
}

//向双向链表的第i个位置插入元素 elem, 其实和单链表插入差不多，多一步把指针指向前一个节点
int InsertDLinkList(DLinkList_p L, int i, int elem){

	DLinkList_p p, new_q;
	p = L->next;
	int j;
	while(!p || j < i) {
		p = p->next;
		++j;
	}

	if(!p || j < i) {
		printf("没有找到位置\n");
		exit(0);
	}
	
	//生成一个新节点
	new_q = (DLinkList_p)malloc(sizeof(DLinkList));
	if(NULL == new_q) {
		printf("分配内存shi\n");
		exit(0);
	}
	new_q->data = elem;
	new_q->pre = p;
	new_q->next = p->next;
	if(NULL != p->next) {//新节点的下一个节点的 perv是否为NULL
		p->next->prev = new_q;
	}

	p->next = new_q;
	return 1;
}