数据结构教程（第五版 李春葆 上机实验题2 前七题）

一、实现顺序表的基本运算的算法

#include
#include
#define MaxSize 50

typedef struct{
	char data[MaxSize];
	int length;	
}SqList;

//1初始化顺序表 
void InitList(SqList *&L){
	L=(SqList *)malloc(sizeof(SqList));
	L->length=0;
}

//2向顺序表中依次插入元素
void CreateList(SqList *&L,char a[],int n){
	int i=0,k=0;
	L=(SqList *)malloc(sizeof(SqList));
	while(i<n){
		L->data[k]=a[i];
		k++;i++;
	}
	L->length=k;
	
} 

//3、9、11输出顺序表L
void DispList(SqList *L){
	for(int i=0;i<L->length;i++){
		printf("%c \t",L->data[i]);
	}
	printf("\n");
} 

//4输出顺序表的长度
int ListLength(SqList *L){
	return(L->length);
}

//5判断表空
bool ListEmpty(SqList *L){
	return(L->length==0);
} 

//6输出顺序表的第三个元素
bool GetElem(SqList *L,int i,char &e){
	if(i<1||i>L->length) return false;
	e=L->data[i-1];
	return true;
} 

//7输出元素a的位置
int LocateElem(SqList *L,char e){
	int i=0;
	while(i<L->length && L->data[i]!=e)
		i++;
	if(i>L->length)
		return 0;
	else
		return i+1;
} 
 
//8在第四个元素位置上插入元素f
bool ListInsert(SqList *&L,int i,char e){
	int j;
	if(i<1||i>L->length||L->length==MaxSize)
		return false;
	i--;
	for(j=L->length;j>i;j--)
		L->data[j]=L->data[j-1];
	L->data[i]=e;
	L->length++;
	return true;
}

//10删除顺序表L的第三个元素
bool ListDelete(SqList *&L,int i,char &e){
	int j;
	if(i<1||i>L->length)
		return false;
	i--;//使顺序表的物理序号与逻辑序号相一致 
	e=L->data[i];
	for(j=i;j<L->length-1;j++)	//依次向前移动元素 
		L->data[j]=L->data[j+1];
	L->length--;
	return true;
} 

//12销毁顺序表 
void DestroyList(SqList *&L){
	free(L);
} 

int main(){
	SqList *L;
	//1初始化顺序表L
	printf(" 1初始化顺序表L\n");
	InitList(L);
	//2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建顺序串）
	printf("\n 2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建顺序串）\n");
	char a[5]={'a','b','c','d','e'};
	CreateList(L,a,5);
	//3输出顺序表L
	printf("\n 3输出顺序表L:");
	DispList(L);
	//4输出顺序表L的长度
	printf("\n 4输出顺序表L的长度:");
	ListLength(L);
	printf("长度为：%d \n",ListLength(L));
	//5判断L是否为空
	printf("\n 5判断L是否为空:");
	ListEmpty(L);
	if(ListEmpty(L))
		printf("表为空\n");
	else
		printf("表非空\n"); 
	//6输出顺序表L的第三个元素
	printf("\n 6输出顺序表L的第三个元素:");
	char e;
	GetElem(L,3,e);
	printf("顺序表L的第三个元素为:%c \n",e); 
	//7输出元素a的位置
	printf("\n 7输出元素a的位置:");
	LocateElem(L,'a');
	printf("%d\n",LocateElem(L,'a'));
	//8在第四个元素的位置上插入元素f
	printf("\n 8在第四个元素的位置上插入元素f\n");
	ListInsert(L,4,'f');
	//9输出顺序表L
	printf("\n 9输出顺序表L:");
	DispList(L);
	//10删除顺序表第三个元素
	printf("\n 10删除顺序表第三个元素:");
	ListDelete(L,3,e);
	printf("%c 被删除\n",e);
	//11输出顺序表!
	printf("\n 11输出顺序表L:");
	DispList(L);
	//12释放顺序表
	printf("\n 12释放顺序表"); 
	DestroyList(L); 
	return(0);
} 

结果：

二、实现单链表的各种基本运算的算法

#include
#include

typedef struct LNode{
	char data;
	struct LNode *next;
}LinkNode; 

//1初始化链表 
void InitList(LinkNode *&H){
	H=(LinkNode *)malloc(sizeof(LinkNode));
	H->next=NULL; 
}

//2依次采用尾插法插入字符（即创建链表）
void CreateList(LinkNode *&H,char a[],int n){
	LinkNode *s,*r;
	H=(LinkNode *)malloc(sizeof(LinkNode));
	r=H; 
	for(int i=0;i<n;i++){
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL; 
} 

//3输出单链表L 
void DispList(LinkNode *H){
	LinkNode *p=H->next;
	while(p!=NULL){
		printf("%c\t",p->data);
		p=p->next;
	}
	printf("\n");
} 

//4输出单链表的长度
int ListLength(LinkNode *H){
	int n=0;
	LinkNode *p=H;
	while(p->next!=NULL){
		n++;
		p=p->next;
	}
	return n;
} 

//5判断单链表h是否为空
bool ListEmpty(LinkNode *H){
	return(H->next==NULL);
} 

//6输出单链表h的第三个元素
bool GetElem(LinkNode *H,int i,char &e){
	int j=0;
	if(i<1) return false;
	LinkNode *p=H;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL) return false;
	else{
		e=p->data;
		return true;
	}
} 

//7输出元素a的位置
int LocateElem(LinkNode *L,char a){
	int i=1;
	LinkNode *p=L->next;
	while(p->data!='a' && p!=NULL){
		p=p->next;
		i++;
	}
	if(p==NULL) return(0);
	else return(i);
} 

//8在第四个元素的位置上插入元素f
bool ListInsert(LinkNode *&H,int i,char e){
	int j=0;
	LinkNode *p=H,*s;
	if(i<1) return false;
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
} 

//9输出单链表h（直接与三同理）

//10删除单链表h的第三个元素
bool ListDelete(LinkNode *&H,int i,char &e){
	int j=0;
	LinkNode *p=H,*q;
	if(i<1) return false;
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		q=p->next;
		if(q==NULL)
			return false;
		e=q->data;
		p->next=q->next;
		free(q);
		return true;
	}
} 

//11输出单链表h（直接与三同理）

//12释放单链表h
void DestroyList(LinkNode *&H){
	LinkNode *pre=H,*p=p->next;
	while(p!=NULL){
		free(pre);
		pre=p;
		p=p->next;
	}
	free(pre);
} 



int main(){
	LinkNode *H;
	//1初始化链表H 
	printf(" 1初始化链表H\n");
	InitList(H);
	//2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建顺序串）
	printf("\n 2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建链表）\n");
	char a[5]={'a','b','c','d','e'};
	CreateList(H,a,5);
	//3输出链表H
	printf("\n 3输出链表H:");
	DispList(H);
	//4输出链表H的长度
	printf("\n 4输出顺序表H的长度:");
	ListLength(H);
	printf("长度为：%d \n",ListLength(H));
	//5判断H是否为空
	printf("\n 5判断H是否为空:");
	ListEmpty(H);
	if(ListEmpty(H))
		printf("表为空\n");
	else
		printf("表非空\n"); 
	//6输出链表H的第三个元素
	printf("\n 6输出链表H的第三个元素:");
	char e;
	GetElem(H,3,e);
	printf("链表H的第三个元素为:%c \n",e); 
	//7输出元素a的位置
	printf("\n 7输出元素a的位置:");
	LocateElem(H,'a');
	printf("%d\n",LocateElem(H,'a'));
	//8在第四个元素的位置上插入元素f
	printf("\n 8在第四个元素的位置上插入元素f\n");
	ListInsert(H,4,'f');
	//9输出链表H
	printf("\n 9输出链表H:");
	DispList(H);
	//10删除链表H第三个元素
	printf("\n 10删除链表H第三个元素:");
	ListDelete(H,3,e);
	printf("%c 被删除\n",e);
	//11输出链表H
	printf("\n 11输出链表H:");
	DispList(H);
	//12释放链表H
	printf("\n 12释放链表H"); 
	DestroyList(H); 
	return(0);
}

结果：

三、实现双链表的各种运算的算法

#include
#include

typedef struct DNode{
	char data;
	struct DNode *next;
	struct DNode *prior;
}DLinkNode; 

//1初始化双链表 
void InitList(DLinkNode *&H){
	H=(DLinkNode *)malloc(sizeof(DLinkNode));
	H->next=NULL,H->prior=NULL; 
}

//2依次采用尾插法插入字符（即创建链表）
void CreateListR(DLinkNode *&H,char a[],int n){
	DLinkNode *s,*r;
	H=(DLinkNode *)malloc(sizeof(DLinkNode));
	r=H; 
	for(int i=0;i<n;i++){
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=a[i];
		r->next=s;
		s->prior=r;
		r=s;
	}
	r->next=NULL; 
} 

//3输出双链表L 
void DispList(DLinkNode *H){
	DLinkNode *p=H->next;
	while(p!=NULL){
		printf("%c\t",p->data);
		p=p->next;
	}
	printf("\n");
} 

//4输出双链表的长度
int ListLength(DLinkNode *H){
	int n=0;
	DLinkNode *p=H;
	while(p->next!=NULL){
		n++;
		p=p->next;
	}
	return n;
} 

//5判断双链表h是否为空
bool ListEmpty(DLinkNode *H){
	return(H->next==NULL);
} 

//6输出双链表h的第三个元素
bool GetElem(DLinkNode *H,int i,char &e){
	int j=0;
	if(i<1) return false;
	DLinkNode *p=H;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL) return false;
	else{
		e=p->data;
		return true;
	}
} 

//7输出元素a的位置
int LocateElem(DLinkNode *L,char a){
	int i=1;
	DLinkNode *p=L->next;
	while(p->data!='a' && p!=NULL){
		p=p->next;
		i++;
	}
	if(p==NULL) return(0);
	else return(i);
} 

//8在第四个元素的位置上插入元素f
bool ListInsert(DLinkNode *&H,int i,char e){
	int j=0;
	DLinkNode *p=H,*s;
	if(i<1) return false;
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=e;
		s->next=p->next;
		if(p->next!=NULL)
			p->next->prior=s; 
		s->prior=p; 
		p->next=s;
		return true;
	}
} 

//9输出双链表h（直接与三同理）

//10删除双链表h的第三个元素
bool ListDelete(DLinkNode *&H,int i,char &e){
	int j=0;
	DLinkNode *p=H,*q;
	if(i<1) return false;
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		q=p->next;
		if(q==NULL)
			return false;
		e=q->data;
		p->next=q->next;
		if(q->next!=NULL)
			q->next->prior=p; 
		free(q);
		return true;
	}
} 

//11输出单链表h（直接与三同理）

//12释放单链表h
void DestroyList(DLinkNode *&H){
	DLinkNode *pre=H,*p=p->next;
	while(p!=NULL){
		free(pre);
		pre=p;
		p=p->next;
	}
	free(pre);
} 



int main(){
	DLinkNode *H;
	//1初始化链表H 
	printf(" 1初始化链表H\n");
	InitList(H);
	//2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建顺序串）
	printf("\n 2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建链表）\n");
	char a[5]={'a','b','c','d','e'};
	CreateListR(H,a,5);
	//3输出链表H
	printf("\n 3输出链表H:");
	DispList(H);
	//4输出链表H的长度
	printf("\n 4输出顺序表H的长度:");
	ListLength(H);
	printf("长度为：%d \n",ListLength(H));
	//5判断H是否为空
	printf("\n 5判断H是否为空:");
	ListEmpty(H);
	if(ListEmpty(H))
		printf("表为空\n");
	else
		printf("表非空\n"); 
	//6输出链表H的第三个元素
	printf("\n 6输出链表H的第三个元素:");
	char e;
	GetElem(H,3,e);
	printf("链表H的第三个元素为:%c \n",e); 
	//7输出元素a的位置
	printf("\n 7输出元素a的位置:");
	LocateElem(H,'a');
	printf("%d\n",LocateElem(H,'a'));
	//8在第四个元素的位置上插入元素f
	printf("\n 8在第四个元素的位置上插入元素f\n");
	ListInsert(H,4,'f');
	//9输出链表H
	printf("\n 9输出链表H:");
	DispList(H);
	//10删除链表H第三个元素
	printf("\n 10删除链表H第三个元素:");
	ListDelete(H,3,e);
	printf("%c 被删除\n",e);
	//11输出链表H
	printf("\n 11输出链表H:");
	DispList(H);
	//12释放链表H
	printf("\n 12释放链表H"); 
	DestroyList(H); 
	return(0);
}

结果：

四、实现循环单链表的各种基本运算的算法

#include
#include

typedef struct DNode{
	char data;
	struct DNode *next;
}DLinkNode; 

//1初始化双链表 
void InitList(DLinkNode *&H){
	H=(DLinkNode *)malloc(sizeof(DLinkNode));
	H->next=H; 
}

//2依次采用尾插法插入字符（即创建链表）
void CreateListR(DLinkNode *&H,char a[],int n){
	DLinkNode *s,*r;
	H=(DLinkNode *)malloc(sizeof(DLinkNode));
	r=H; 
	for(int i=0;i<n;i++){
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=H; 
} 

//3输出双链表L 
void DispList(DLinkNode *H){
	DLinkNode *p=H->next;
	while(p!=H){
		printf("%c\t",p->data);
		p=p->next;
	}
	printf("\n");
} 

//4输出双链表的长度
int ListLength(DLinkNode *H){
	int n=0;
	DLinkNode *p=H;
	while(p->next!=H){
		n++;
		p=p->next;
	}
	return n;
} 

//5判断双链表h是否为空
bool ListEmpty(DLinkNode *H){
	return(H->next==H);
} 

//6输出双链表h的第三个元素
bool GetElem(DLinkNode *H,int i,char &e){
	int j=1;
	if(i<1) return false;
	DLinkNode *p=H->next;
	while(j<i && p!=H){
		j++;
		p=p->next;
	}
	if(p==H) return false;
	else{
		e=p->data;
		return true;
	}
} 

//7输出元素a的位置
int LocateElem(DLinkNode *L,char a){
	int i=1;
	DLinkNode *p=L->next;
	while(p->data!='a' && p!=L){
		p=p->next;
		i++;
	}
	if(p==L) return(0);
	else return(i);
} 

//8在第四个元素的位置上插入元素f
bool ListInsert(DLinkNode *&H,int i,char e){
	int j=1;
	DLinkNode *pre=H,*p=H->next,*s;
	if(i<1) return false;
	while(j<i && p!=H){
		j++;
		pre=p;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=e;
		s->next=p;
		pre->next=s;
		return true;
	}
} 

//9输出双链表h（直接与三同理）

//10删除双链表h的第三个元素
bool ListDelete(DLinkNode *&H,int i,char &e){
	int j=1;
	DLinkNode *pre=H,*p=H->next;
	if(i<1) return false;
	while(j<i && p!=H){
		j++;
		pre=p;
		p=p->next;
	}
	if(p==H)return false;
	else{
		e=p->data;
		pre->next=p->next;
		return true;
	}
} 

//11输出双链表h（直接与三同理）

//12释放双链表h
void DestroyList(DLinkNode *&H){
	DLinkNode *pre=H,*p=p->next;
	while(p!=H){
		free(pre);
		pre=p;
		p=p->next;
	}
	free(pre);
} 



int main(){
	DLinkNode *H;
	//1初始化链表H 
	printf(" 1初始化链表H\n");
	InitList(H);
	//2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建顺序串）
	printf("\n 2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建链表）\n");
	char a[5]={'a','b','c','d','e'};
	CreateListR(H,a,5);
	//3输出链表H
	printf("\n 3输出链表H:");
	DispList(H);
	//4输出链表H的长度
	printf("\n 4输出链表H的长度:");
	ListLength(H);
	printf("长度为：%d \n",ListLength(H));
	//5判断H是否为空
	printf("\n 5判断H是否为空:");
	ListEmpty(H);
	if(ListEmpty(H))
		printf("表为空\n");
	else
		printf("表非空\n"); 
	//6输出链表H的第三个元素
	printf("\n 6输出链表H的第三个元素:");
	char e;
	GetElem(H,3,e);
	printf("链表H的第三个元素为:%c \n",e); 
	//7输出元素a的位置
	printf("\n 7输出元素a的位置:");
	LocateElem(H,'a');
	printf("%d\n",LocateElem(H,'a'));
	//8在第四个元素的位置上插入元素f
	printf("\n 8在第四个元素的位置上插入元素f\n");
	ListInsert(H,4,'f');
	//9输出链表H
	printf("\n 9输出链表H:");
	DispList(H);
	//10删除链表H第三个元素
	printf("\n 10删除链表H第三个元素:");
	ListDelete(H,3,e);
	printf("%c 被删除\n",e);
	//11输出链表H
	printf("\n 11输出链表H:");
	DispList(H);
	//12释放链表H
	printf("\n 12释放链表H"); 
	DestroyList(H); 
	return(0);
}

五、实现循环双链表的各种基本运算的算法

#include
#include

typedef struct DNode{
	char data;
	struct DNode *next;
	struct DNode *prior;
}DLinkNode; 

//1初始化双链表 
void InitList(DLinkNode *&H){
	H=(DLinkNode *)malloc(sizeof(DLinkNode));
	H->next=H,H->prior=H; 
}

//2依次采用尾插法插入字符（即创建链表）
void CreateListR(DLinkNode *&H,char a[],int n){
	DLinkNode *s,*r;
	H=(DLinkNode *)malloc(sizeof(DLinkNode));
	r=H; 
	for(int i=0;i<n;i++){
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=a[i];
		r->next=s;
		s->prior=r;
		r=s;
	}
	r->next=H; 
	H->prior=r;
} 

//3输出双链表L 
void DispList(DLinkNode *H){
	DLinkNode *p=H->next;
	while(p!=H){
		printf("%c\t",p->data);
		p=p->next;
	}
	printf("\n");
} 

//4输出双链表的长度
int ListLength(DLinkNode *H){
	int n=0;
	DLinkNode *p=H;
	while(p->next!=H){
		n++;
		p=p->next;
	}
	return n;
} 

//5判断双链表h是否为空
bool ListEmpty(DLinkNode *H){
	return(H->next==H);
} 

//6输出双链表h的第三个元素
bool GetElem(DLinkNode *H,int i,char &e){
	int j=1;
	if(i<1) return false;
	DLinkNode *p=H->next;
	while(j<i && p!=H){
		j++;
		p=p->next;
	}
	if(p==H) return false;
	else{
		e=p->data;
		return true;
	}
} 

//7输出元素a的位置
int LocateElem(DLinkNode *L,char a){
	int i=1;
	DLinkNode *p=L->next;
	while(p->data!='a' && p!=L){
		p=p->next;
		i++;
	}
	if(p==L) return(0);
	else return(i);
} 

//8在第四个元素的位置上插入元素f
bool ListInsert(DLinkNode *&H,int i,char e){
	int j=1;
	DLinkNode *p=H->next,*s;
	if(i<1) return false;
	while(j<i && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL)return false;
	else{
		s=(DLinkNode *)malloc(sizeof(DLinkNode));
		s->data=e;
		s->next=p;
		p->prior->next=s; 
		s->prior=p->prior; 
		p->prior=s;
		return true;
	}
} 

//9输出双链表h（直接与三同理）

//10删除双链表h的第三个元素
bool ListDelete(DLinkNode *&H,int i,char &e){
	int j=1;
	DLinkNode *p=H->next,*q;
	if(i<1) return false;
	while(j<i && p!=H){
		j++;
		p=p->next;
	}
	if(p==H)return false;
	else{
		p->next->prior=p->prior;
		p->prior->next=p->next;
		return true;
	}
} 

//11输出双链表h（直接与三同理）

//12释放双链表h
void DestroyList(DLinkNode *&H){
	DLinkNode *pre=H,*p=p->next;
	while(p!=H){
		free(pre);
		pre=p;
		p=p->next;
	}
	free(pre);
} 

int main(){
	DLinkNode *H;
	//1初始化链表H 
	printf(" 1初始化链表H\n");
	InitList(H);
	//2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建顺序串）
	printf("\n 2依次插入元素a,b,c,d,e元素（可以理解为用字符数组创建链表）\n");
	char a[5]={'a','b','c','d','e'};
	CreateListR(H,a,5);
	//3输出链表H
	printf("\n 3输出链表H:");
	DispList(H);
	//4输出链表H的长度
	printf("\n 4输出链表H的长度:");
	ListLength(H);
	printf("长度为：%d \n",ListLength(H));
	//5判断H是否为空
	printf("\n 5判断H是否为空:");
	ListEmpty(H);
	if(ListEmpty(H))
		printf("表为空\n");
	else
		printf("表非空\n"); 
	//6输出链表H的第三个元素
	printf("\n 6输出链表H的第三个元素:");
	char e;
	GetElem(H,3,e);
	printf("链表H的第三个元素为:%c \n",e); 
	//7输出元素a的位置
	printf("\n 7输出元素a的位置:");
	LocateElem(H,'a');
	printf("%d\n",LocateElem(H,'a'));
	//8在第四个元素的位置上插入元素f
	printf("\n 8在第四个元素的位置上插入元素f\n");
	ListInsert(H,4,'f');
	//9输出链表H
	printf("\n 9输出链表H:");
	DispList(H);
	//10删除链表H第三个元素
	printf("\n 10删除链表H第三个元素:");
	ListDelete(H,3,e);
	printf("%c 被删除\n",e);
	//11输出链表H
	printf("\n 11输出链表H:");
	DispList(H);
	//12释放链表H
	printf("\n 12释放链表H"); 
	DestroyList(H); 
	return(0);
}

(原理皆与单链表的基本运算算法一致)

六、将单链表按基准划分

#include
#include

typedef struct LNode{
	int data;
	struct LNode *next;
}LinkNode;

//创建单链表
void CreateListR(LinkNode *&L,int 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->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;	
}
 
//打印链表
void DispList(LinkNode *L){
	LinkNode *p=L->next;
	while(p!=NULL){
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
} 


//元素依次与第一个元素做比较，不小于的插入到x的后面，小于的插入到头结点的后面 
void partition(LinkNode *&L){
	LinkNode *p1,*p2,*q;
	p2=L->next->next;			//p2始终指向要插入比较的元素 
	p1=L->next;					//p1指向第一个元素 						
	p1->next=NULL;
	while(p2!=NULL){
		q=p2->next;
		if(p2->data>=p1->data){	//比较元素不小于x，将其插入到x的后面 
			p2->next=p1->next;
			p1->next=p2;	
		}else{	//比较元素小于x 将其插入到L的后面 
			p2->next=L->next;
			L->next=p2;
		}
		p2=q; 		
	}
}

int main(){
	int a[7]={4,5,12,1,4,56,3};
	LinkNode *L;
	CreateListR(L,a,7);
	printf("排列前的链表：\n"); 
	DispList(L);
	partition(L);
	printf("排列后的链表：\n"); 
	DispList(L);
	return 0;	
}

结果：

七、将两个单链表合并成一个单链表

思路：用指针L3指向L1的头结点，依次用指针指向L1,L2中的结点

#include
#include

typedef struct LNode{
	int data;
	struct LNode *next;
}LinkNode;

//创建单链表
void CreateListR(LinkNode *&L,int 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->data=a[i];
		r->next=s;
		r=s;
	}
	r->next=NULL;	
}
 
//打印链表
void DispList(LinkNode *L){
	LinkNode *p=L->next;
	while(p!=NULL){
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
} 


//元素依次与第一个元素做比较，不小于的插入到x的后面，小于的插入到头结点的后面 
void unionlist(LinkNode *L1,LinkNode *L2,LinkNode *&L3){
	LinkNode *p=L1->next,*q=L2->next,*r,*m;
	L3=L1;
	r=L3;
	L3->next=NULL;
	while(p!=NULL && q!=NULL){
		r->next=p;
		p=p->next;		
		r->next->next=q;
		q=q->next;
		r=r->next->next; 
	}
	while(q!=NULL){
			r->next=q;
			q=q->next;
			r=r->next;			
		}
	while(p!=NULL){
			r->next=p;
			p=p->next;
			r=r->next;			
		}
	r->next=NULL;

}

int main(){
	int a1[7]={4,5,12,1,4,56,3};
	int a2[10]={4,5,12,1,4,56,3,45,88,99};
	LinkNode *L1,*L2,*L3;
	CreateListR(L1,a1,7);
	CreateListR(L2,a2,10);
	printf("排列前的链表：\n"); 
	DispList(L1);
	printf("\n");
	DispList(L2);
	unionlist(L1,L2,L3);
	printf("合并后的链表：\n"); 
	DispList(L3);
	return 0;	
}

结果：