插入排序的流程图
void InsertionSort(Node *head)//插入排序
{
Node *p, *q, *r, *l;
p = head->next;//将原链表拆分为两个链表,一个head带一个结点,一个q带剩余结点
q = p->next;//指向原链表
p->next = NULL;//链表置位空,等待插入有序节点
while (q != NULL)
{
p = head;
r = q->next;
while (p->next != NULL)
{//找到要插入的位置
if (p->next->data.Price < q->data.Price) {
p = p->next;
} else {
break;
}
}
q->next = p->next;//插入结点
p->next = q;//保留原来指针的信息
q = r;//恢复位置,完成插入过程
l = head;
int i = 0;
while (l != NULL) {
l = l->next;
}
}
}
回答:链表的插入排序哈,这里变量名没有取得很好,不方便阅读与理解,流程图如下:
# include <stdio.h>
# include <stdlib.h>
struct data
{
int Price;
};
struct Node
{
Node* next;
data data;
};
void InsertionSort(Node* head)//插入排序
{
Node* p, * q, * r, * l;
p = head->next;//将原链表拆分为两个链表,一个head带一个结点,一个q带剩余结点
q = p->next;//指向原链表
p->next = NULL;//链表置位空,等待插入有序节点
while (q != NULL)
{
p = head;
r = q->next;
while (p->next != NULL)
{//找到要插入的位置
if (p->next->data.Price < q->data.Price) {
p = p->next;
}
else {
break;
}
}
q->next = p->next;//插入结点
p->next = q;//保留原来指针的信息
q = r;//恢复位置,完成插入过程
l = head;
while (l != NULL) {
l = l->next;
}
}
}
void init(Node* head, int arr[], int n)
{
Node* cur = head;
for (int i = 0; i < n; i++)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data.Price = arr[i];
newNode->next = NULL;
cur->next = newNode;
cur = cur->next;
}
}
void print(Node* head)
{
Node* cur = head->next;
while (cur)
{
printf("%d ", cur->data.Price);
cur = cur->next;
}
printf("\n");
}
int main()
{
Node* head = (Node*)malloc(sizeof(Node));
int arr[10] = { 1,3,5,7,9,2,4,6,8,10 };
init(head, arr, 10);
print(head);
InsertionSort(head);
print(head);
}