《数据结构》双向链表的创建

双向链表的创建

双向链表的创建同样像单链表一样可以有两种方法：头插法和尾插法。

使用尾插法创建双向链表：

算法思想：

先定义一个指针q指向头结点

1.新结点p的前驱指向头结点L;

2.新结点的next指针域置空；

3.头结点的next指向p；

4.q指向p.

void CreateList1(DuLinkList &L,int n){
	L=new DuLNode;
	L->next=NULL;
	L->prior=NULL;
	struct DuLNode *q;
	q=L;
	printf("请输入链表元素:n");
	for(int i=0;i<n;i++){
		printf("请输入第%d个元素的值:",i+1);
		struct DuLNode *p;
		p=new DuLNode;
		scanf("%d",&p->data);
		p->prior=q;
		p->next=NULL;
		
		q->next=p;
		q=p;
	}
}

使用头插法创建双向链表时，一定要判断链表是否为空是否为空，因为链表为空时，L->next_prior是不存在的，这是y8ge空指针。

//头插法创建单链表 
void CreateList(DuLinkList &L,int n){
	L=new DuLNode;
	L->next=NULL;
	L->prior=NULL;
	printf("请输入链表元素:n");
	struct DuLNode *p;
	for(int i=n;i>0;--i){
		printf("请输入第%d个元素值:",i);
		struct DuLNode *s;
		s=new DuLNode;
		scanf("%d",&s->data);
		s->next=L->next; 
		if(L->next!=NULL)//不加这一条if语句就错！！
		//原因：当链表为空时，即只有一个头结点，则L->next为空，也就不存在后继；
		//所以，下面的语句不能执行。 
		L->next->prior=s;
		L->next=s;
		s->prior=L;
	}
}

//一般的双向链表
 
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100

//定义双向链表
typedef struct DuLNode{
	int data;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode,*DuLinkList;

//初始化双向链表
int InitList(DuLinkList &L){
	L=new DuLNode;
	L->prior=NULL;
	L->next=NULL;
	return 1;
}

int ListEmpty(DuLinkList L){
	if(L->next){
		return 0;//非空 
	}else{
		return 1;//空 
	}
}

int ListLength(DuLinkList L){
	int length=0;
	struct DuLNode *p;
	p=L->next;
	while(p){
		p=p->next;
		++length;
	}
	return length;
}

void TraveList(DuLinkList L){
	struct DuLNode *p;
	p=L->next;
	while(p){
		printf("%d ",p->data);
		p=p->next;
	}
}
//头插法创建单链表 
void CreateList(DuLinkList &L,&s->data);
		s->next=L->next; 
		if(L->next!=NULL)//不加这一条if语句就错！！
		//原因：当链表为空时，即只有一个头结点，则L->next为空，也就不存在后继；
		//所以，下面的语句不能执行。 
		L->next->prior=s;
		L->next=s;
		s->prior=L;
	}
}
//尾差法创建双向链表 
void CreateList1(DuLinkList &L,&p->data);
		p->prior=q;
		p->next=NULL;
		
		q->next=p;
		q=p;
	}
}
int main(){
	DuLinkList L;
	
	if(InitList(L)){
		printf("双向链表初始化成功!n");
	}else{
		printf("双向链表初始化失败!n");
	}
	
	if(ListEmpty(L)){
		printf("当前链表为空!n");
	}else{
		printf("当前链表非空!n");
	}
	
	printf("请输入链表的长度:");
	int n;
	scanf("%d",&n);
	CreateList(L,n);
	//CreateList1(L,n);
	printf("遍历链表如下:n");
	TraveList(L);
} 

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!