[C++知识库]1.4 附

例题一：

#include<stdio.h>
#include"1.h"
int main(){
	LinkNode *L;
	InitList(L);
	ElemType a[]={1,2,3,4,5};
	CreateListR(L,a,5);
	Reverse(L);
	DispList(L);
}

例题二：

#include<stdio.h>
#include"1.h"
int main(){
	LinkNode *L,*L1,*L2;
	InitList(L);
	InitList(L1);
	InitList(L2);
	ElemType a[]={1,2,3,4,5,6};
	CreateListR(L,a,6);
	Split(L,L1,L2);
	DispList(L1);
	DispList(L2);
}

例题三：

#include<stdio.h>
#include"1.h"
int main(){
	LinkNode *L;
	InitList(L);
	ElemType a[]={1,6,10,5,2,0};
	CreateListR(L,a,6);
	DeleteMax(L); 
	DispList(L);
}

.h文件

#include<stdio.h>
#include<malloc.h>
typedef int ElemType;

struct LinkNode{
	ElemType Elem;
	LinkNode *Next;
}; 


//初始化 
void InitList(LinkNode *&L){
	L=(LinkNode*)malloc(sizeof(LinkNode));
	L->Next=NULL; 
}

//销毁
void DestroyList(LinkNode *&L){
	LinkNode *pre=L,*p=L->Next;
	while(p!=NULL){
		free(pre);
		pre=p;
		p=pre->Next;
	}
	free(pre);
} 

//判断是否为空
bool EmptyList(LinkNode *L){
	return (L->Next==NULL);
} 


//求长度
int ListLength(LinkNode *L){
	int n=0;
	LinkNode *p=L;
	while(p->Next!=NULL){
		n++;
		p=p->Next;
	}
	return (n);
} 

//输出
void DispList(LinkNode *L){
	LinkNode *p=L->Next;
	while(p!=NULL){
		printf("%d ",p->Elem);
		p=p->Next;
	}	
	printf("\n");
} 

//求数据元素值 
bool GetElem(LinkNode *L,ElemType i,ElemType &e){
	int j;
	LinkNode *p=L;
	for(j=0;j<i;j++){
		p=p->Next;
		e=p->Elem;
	}
	if(p==NULL)
	return false;
	else
	return e;
}


//按值查找元素 
int LocateElem(LinkNode *L,ElemType e){
	int n=0;
	LinkNode *p=L;
	while(p->Elem!=e&&p!=NULL){
		n++;
		p=p->Next;
	}
	if(p==NULL)
	return 0;
	else 
	return (n);
}


//头插法
void CreateListF(LinkNode *&L,ElemType a[],int n){
	LinkNode *s;
	L=(LinkNode *)malloc(sizeof(LinkNode));
	L->Next=NULL;
	for(int i=0;i<n;i++){
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->Elem=a[i];
		s->Next=L->Next;
		L->Next=s;
	}
} 


//尾插法
void CreateListR(LinkNode *&L,ElemType a[],int n){
	LinkNode *s,*r;
	L=(LinkNode *)malloc(sizeof(LinkNode));
	r=L;
	for(int i=0;i<n;i++){
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->Elem=a[i];
		r->Next=s;
		r=s;
	}
	r->Next=NULL;
} 

 
//删除
int ListDeleteNode(LinkNode *&L,int i){
 	LinkNode *p=L,*q;
 	int j=0;
 		for(int j=0;j<i-1;j++){
 			p=p->Next;
		 }
		 if(!(p->Next)||(j>i-1))
		 return 0;
 		q=p->Next;
 		p->Next=q->Next;
 		free(q);
 		return 1;
 } 

//插入 
bool ListInsert(LinkNode *&L,int i,ElemType e){
	int j=1;
	LinkNode *p=L->Next,*s;
	while(j<i-1&&p!=NULL){
		p=p->Next;
		j++;
	}
	if(p==NULL)
	return false;
	else{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->Elem=e;
		s->Next=p->Next;
		p->Next=s;
		return true;
	}
}

//逆置 
void Reverse(LinkNode *&L){
	LinkNode *p=L->Next,*q;
	L->Next=NULL;
	while(p!=NULL)
	{
		q=p->Next;
		p->Next=L->Next;
		L->Next=p;
		p=q;
		}	
}

//拆分单链表
void Split(LinkNode *&L,LinkNode *&L1,LinkNode *&L2){
	LinkNode *p=L->Next,*q,*r1;
	L1=L;
	r1=L1;
	L2=(LinkNode *)malloc(sizeof(LinkNode));
	L2->Next=NULL;
	while(p!=NULL){
		r1->Next=p;
		r1=p;
		p=p->Next;
		q=p->Next;
		p->Next=L2->Next;
		L2->Next=p;
		p=q;
	}	
	r1->Next=NULL;
} 

// 删除单链表中最大的数
void DeleteMax(LinkNode *&L){
	LinkNode *p=L->Next,*pre=L,*maxp,*maxpre;
	maxp=p;
	maxpre=pre;
	while(p!=NULL){
		if(p->Elem>maxp->Elem){
			maxp=p;
			maxpre=pre;
		}
		else{
			pre=p;
			p=p->Next;
		}
	}
	maxpre->Next=maxp->Next;
	free(maxp);
}