顺序表归并,链表归并,顺序表划分
程序员文章站
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);
}
运行代码截图: