shuju.cpp

对严蔚敏版数据结构（C版）的双向顺序表的部分源码

#include"shuju.h"
Status InitDuList(DuLinkList &L){
	//初始化 双向链表 L
	L=(DuLinkList)malloc(sizeof(DuLNode));
	if(!L)exit(OVERFLOW);//初始化失败
	//L->next=NULL;

	L->next=L->prior=L;
	//L->next->prior=L;
	return OK;
}//InitDuList
/*Status CreateDuList(DuLinkList &L){ //双向 非 循环链表 尾插入法
	DuLinkList p=L,q;
	ElemType x=1,e,i;
	while(p){
		q=p;
		p=p->next;
	}
	printf("Please input the number of the List x(x>=1):");
	scanf("%d",&x);
	for(i=1;i<=x;i++){
		printf("Please input the NO.%d number:",i);
		scanf("%d",&e);
		DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));
		s->data=e;
		s->next=q->next;
		q->next=s;
		s->prior=q;

		q=s;
		q->prior=s->prior;
		q->next=s->next;
	}
	return OK;
}//CreateDuList*/
Status CreateDuList(DuLinkList &L){ //双向 循环链表 尾插入法
	DuLinkList q=L->prior;
	ElemType x=1,e,i;
	printf("Please input the number of the List x(x>=1):");
	scanf("%d",&x);
	for(i=1;i<=x;i++){
		printf("Please input the NO.%d number:",i);
		scanf("%d",&e);
		DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));
		s->data=e;
		s->next=q;
		s->prior=q->prior;
		q->prior->next=s;
		q->prior=s;
	}
	return OK;
}//CreateDuList
Status DuListInsert(DuLinkList &L,int i,ElemType e){
	//在带头节点的双向链表 L中第i个位置之前插入元素e。
	//L的合法值为1<<i<<表长+1
	DuLinkList p=L,s;
	ElemType x=1,j=0;
	while(j<i){
		p=p->next;
		++j;
	}
	if(p==L||(j>i))return ERROR;
	if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))return ERROR;
	s->data=e;
	s->prior=p->prior;
	p->prior->next=s;
	s->next=p;
	p->prior=s;
	return OK;
}//DuListInsert
Status DuListDelete(DuLinkList &L,int i,ElemType &e){
	//删除带头结点的双向链表L 的第i个元素，i的合法值为1<<i<<表长
	DuLinkList p=L;
	ElemType j=0;
	while(j<i){
		p=p->next;
		++j;
	}
	if(p==L||(j>i))return ERROR;
	e=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);
	return OK;
}//DuListDelete
Status InsertDuList(DuLinkList &L,ElemType e){
	//在非递减链表中插入一个元素，使链表仍为非递减链表
	DuLinkList p;
	DuLinkList s=(DuLinkList)malloc(sizeof(DuLNode));
	if(!s)return ERROR;
	s->data=e;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           
	p=L->next;
	while(p!=L&&(p->data)<(s->data))
		p=p->next;
	s->next=p;	
	s->prior=p->prior;			
	p->prior=p->prior->next=s;
	return OK;
}//InsertDuList
Status OrderDuList(DuLinkList &L){
	//建立非递减链表
	DuLinkList p=L->next;
	ElemType i,x,e;
	printf("Please input the number of the List x(x>=1):");
	scanf("%d",&x);
	for(i=1;i<=x;i++){
		printf("Please input the NO.%d number:",i);
		scanf("%d",&e);
		InsertDuList(L,e);
	}
	return OK;
}//OrderDuList
int Symmetric(DuLinkList L){
	DuLinkList p=L->next,q=L->prior;
	while(p!=q&&q->next!=p)
		if(p->data==q->data){
			p=p->next;
			q=q->prior;
		}
		else return 0;
	return 1;
}
/*void SerparateList(DuLinkList &L){
	DuLinkList p=L->next,q=L->prior,m;
	while(q->next!=p)
		if(p->data%2)p=p->next;
	else {
		m=p->next;
		
		m->prior=p->prior;
		p->prior->next=m;
		p->next=L;	
		p->prior=L->prior;			
		L->prior=L->prior->next=p;
		p=m;
	}
}*/
void SerparateList(DuLinkList &L){
	DuLinkList p=L->next,q=L->prior;
	while(p!=q){
		while(p!=q&&p->data%2)p=p->next;
		while(p!=q&&q->data%2==0) q=q->prior;
		L->data=p->data;
		p->data=q->data;
		q->data=L->data;
	}
}
void Printf(DuLinkList &L){
		DuLinkList p=L->next;
		while(p!=L){
			printf(" %d  ",p->data);
			p=p->next;
		}
		printf("\n");
}//Printf
Status ClearList(DuLinkList &L){
	DuLinkList p=L->next,q;
	while(p!=L){
		q=p;
		p=p->next;
		free(q);
	}
	L->next=L->prior=L;
	return OK;
}
void DestoryDuList(DuLinkList &L){
	DuLinkList p=L->next,q;
	while(p!=L){
		q=p;
		p=p->next;
		free(q);
	}
	free(L);
}