1、用数据结构C++写顺序表和链表实现基准划分。以x为基准,将所有小于x的数都放到大于等于x的数前面。
时间: 2024-05-05 21:17:44 浏览: 137
顺序表实现基准划分:
```c
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int length;
} SqList;
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void partition(SqList *L, int x) {
int i = 0, j = L->length - 1;
while (i < j) {
while (i < j && L->data[i] < x) i++;
while (i < j && L->data[j] >= x) j--;
if (i < j) {
swap(&L->data[i], &L->data[j]);
}
}
}
int main() {
SqList L = {{1, 3, 2, 5, 4, 6}, 6};
int x = 4;
partition(&L, x);
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
return 0;
}
```
链表实现基准划分:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkedList;
void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void partition(LinkedList *L, int x) {
LinkedList small = (LinkedList)malloc(sizeof(Node));
LinkedList big = (LinkedList)malloc(sizeof(Node));
LinkedList p = *L, pSmall = small, pBig = big;
while (p != NULL) {
if (p->data < x) {
pSmall->next = p;
pSmall = pSmall->next;
} else {
pBig->next = p;
pBig = pBig->next;
}
p = p->next;
}
pSmall->next = big->next;
pBig->next = NULL;
*L = small->next;
free(small);
free(big);
}
int main() {
LinkedList L = (LinkedList)malloc(sizeof(Node));
L->data = 1;
L->next = (LinkedList)malloc(sizeof(Node));
L->next->data = 3;
L->next->next = (LinkedList)malloc(sizeof(Node));
L->next->next->data = 2;
L->next->next->next = (LinkedList)malloc(sizeof(Node));
L->next->next->next->data = 5;
L->next->next->next->next = (LinkedList)malloc(sizeof(Node));
L->next->next->next->next->data = 4;
L->next->next->next->next->next = (LinkedList)malloc(sizeof(Node));
L->next->next->next->next->next->data = 6;
L->next->next->next->next->next->next = NULL;
int x = 4;
partition(&L, x);
while (L != NULL) {
printf("%d ", L->data);
L = L->next;
}
return 0;
}
```