欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序表归并,链表归并,顺序表划分

程序员文章站 2022-07-07 12:27:16
...

将两个升序数组归并为一个大的升序数组:
 

#include <stdio.h>
#include <stdlib.h>
//顺序表归并
void mergearray(int a[],int lengtha,int b[],int lengthb,int c[]){
	int k=0;
	int i=0,j=0;
	while(i<lengtha&&j<lengthb){
		if(a[i]<b[j]){
			c[k++]=a[i++];
		}else{
			c[k++]=b[j++];
		}
	}
	while(i<lengtha){
		c[k++]=a[i++];
	}
	while(j<lengthb){
		c[k++]=b[j++];
	}
} 
void PrintArray(int c[],int length){
	for(int i=0;i<length;i++){
		printf("%d  ",c[i]);
	}
}
int main(){
	int a[]={1,3,5,7,9};
	int b[]={2,4,6,8};
	int c[9];
	mergearray(a,5,b,4,c);
	PrintArray(c,9);
	
}

 

代码运行效果图:

顺序表归并,链表归并,顺序表划分

 

将两个升序链表归并为一个升序链表:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
typedef struct LNode{
	int data;
	struct LNode *next; 
}LNode,*LinkList;
//尾插法建立单链表
LinkList List_TailInsert(LinkList &L){
	//从表头到表尾正向建立单链表,每次均在表尾插入元素
	int x;
	L=(LNode *)malloc(sizeof(LNode)); 
	LNode *s;
	
	LNode *r=L;//r为表尾指针 
	scanf("%d",&x);//输入结点的值 
	
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;
		r=s; 
	    scanf("%d",&x);//只要输入不结束,就继续创建新节点 
	  
	} 
	r->next=NULL;//尾指针置空 
	return L;
	 
} 
//输出表
int PrintList(LinkList L){
	LNode *p=L;
	//printf("%d->",p->data);
	while(p->next!=NULL){
		 p=p->next;
		 printf("%d->",p->data);
	}   
	printf("\n");
	return 0;
} 

void MergeList(LinkList l1,LinkList l2,LinkList &l3){
	LinkList p =l1->next;
	LinkList q=l2->next;
	l3=l1;
    l3->next=NULL;
    LinkList r=l3;
	while(p!=NULL&&q!=NULL){
		if(p->data<q->data){
			r->next=p;
			p=p->next;
			
		}else{
			r->next=q;
			q=q->next;
		}
		r=r->next;
	}
    if(p!=NULL){
    	r->next=p;	
	}	
	if(q!=NULL){
		r->next=q;
	}
	
} 
int main(){
	LinkList l1;
	printf("建立单链表1,请输入一组升序数据,输入9999结束输入\n");
	List_TailInsert(l1);//头插法  
	PrintList(l1);//输出表
	
	LinkList l2;
	printf("建立单链表2,请输入一组升序数据,输入9999结束输入\n");
	List_TailInsert(l2);//头插法  
	PrintList(l2);//输出表
	LinkList l3;
	MergeList(l1,l2,l3);
	PrintList(l3); 
	
}

运行效果图:

顺序表归并,链表归并,顺序表划分

划分数组:在一个数组中选一个枢轴元素,比枢轴元素大的放在枢轴元素左面,比枢轴元素小的放在枢轴元素右面

实现代码:

#include<stdio.h>
void partition(int a[],int n){
	int i=0;
	int temp=a[i];
	int j=n-1;
	while(i<j){
		while(i<j&&a[j]>temp) j--;
		if(i<j){
			a[i]=a[j];
			i++;
		}
		
		while(i<j&&a[i]<temp) i++;
		if(i<j){
			a[j]=a[i];
			j--;
		}
		 
	}
	a[i]=temp;
	
}
void PrintArray(int c[],int length){
	for(int i=0;i<length;i++){
		printf("%d  ",c[i]);
	}
}
int main(){
	int a[]={2,1,3,-2,-4,5,9,10};
	partition(a,8);
	PrintArray(a,8);
}

运行代码截图:

顺序表归并,链表归并,顺序表划分

 

相关标签: 数据结构 划分