选取一个合适的数据结构存储一批数据,能对数据进行插入、删除和显示操作,还能分别用二分法插入排序、直接选择排序、直接插入排序算法对这些数据进行排序,用C语言表示
时间: 2024-02-12 10:10:04 浏览: 42
一个合适的数据结构是链表,可以通过指针实现节点间的链接,可以进行插入和删除操作。下面是一个简单的链表结构体的定义:
```c
typedef struct node {
int data;
struct node* next;
} Node;
```
其中,`data` 存储节点的数据,`next` 存储下一个节点的地址。
插入操作可以通过在指定位置处插入节点实现,例如:
```c
void insert(Node* head, int position, int data) {
Node* p = head;
for (int i = 0; i < position && p->next; ++i) {
p = p->next;
}
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = p->next;
p->next = node;
}
```
删除操作可以通过找到要删除的节点,然后修改前一个节点的 `next` 指针实现,例如:
```c
void remove(Node* head, int position) {
Node* p = head;
for (int i = 0; i < position && p->next; ++i) {
p = p->next;
}
Node* tmp = p->next;
p->next = tmp->next;
free(tmp);
}
```
显示操作可以通过遍历链表,依次输出每个节点的 `data` 值实现,例如:
```c
void display(Node* head) {
Node* p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```
二分法插入排序可以通过遍历链表,然后将每个节点插入到已排好序的节点中的合适位置实现,例如:
```c
void binary_insert_sort(Node* head) {
Node* p = head->next;
head->next = NULL;
while (p) {
Node* q = head;
Node* pre = NULL;
while (q && q->data < p->data) {
pre = q;
q = q->next;
}
Node* tmp = p->next;
if (pre) {
p->next = pre->next;
pre->next = p;
} else {
p->next = head->next;
head->next = p;
}
p = tmp;
}
}
```
直接选择排序可以通过遍历链表,找到未排序部分的最小值,然后将其插入到已排好序的节点的尾部实现,例如:
```c
void selection_sort(Node* head) {
Node* p = head->next;
head->next = NULL;
while (p) {
Node* min = p;
Node* q = p->next;
while (q) {
if (q->data < min->data) {
min = q;
}
q = q->next;
}
Node* tmp = min->next;
min->next = NULL;
if (head->next) {
Node* last = head->next;
while (last->next) {
last = last->next;
}
last->next = min;
} else {
head->next = min;
}
p = tmp;
}
}
```
直接插入排序可以通过将节点依次插入到已排好序的节点中的合适位置实现,例如:
```c
void insertion_sort(Node* head) {
Node* p = head->next;
head->next = NULL;
while (p) {
Node* q = head;
Node* pre = NULL;
while (q && q->data < p->data) {
pre = q;
q = q->next;
}
Node* tmp = p->next;
if (pre) {
p->next = pre->next;
pre->next = p;
} else {
p->next = head->next;
head->next = p;
}
p = tmp;
}
}
```
注意,这里的排序算法都是针对单向链表的,对于双向链表或其他数据结构的排序实现可能会有所不同。