#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node* next;
}Node;
Node* initList(){
Node* list = (Node*)malloc(sizeof(Node));
list -> data=0;
list -> next=NULL;
return list;
}
void headInsert(Node* list,int data){
Node* node=(Node*)malloc(sizeof(Node));
node->data=data;
node->next=list->next;
list->next=node;
list->data++;
}
void tailInsert(Node* list,int data){
Node* head=list;
Node* node=(Node*)malloc(sizeof(Node));
node->data=data;
node->next=NULL;
list=list->next;
while(list->next){
list=list->next;
}
list->next=node;
head->data++;
}
void delete(Node* list,int data){
Node* pre = list;
Node* current = list->next;
while(current){
if(current->data == data){
pre -> next = current -> next;
free(current);
break;//
}
pre = current;
current = current -> next;
}
list -> data--;
}
void loop(Node* list){
list=list->next;
while(list){
printf("%d",list->data);
list=list->next;
}
printf("\n");
}
int search(Node* list,int data){
int temp=0;
int single=0;
Node* current = list->next;
while(current){
temp++;
if(current->data==data){
printf("%d",temp);
single=1;
break;//????
}
}
}
void ascend(Node* list){
Node* pre=list;
Node* current=list->next;
Node* last=current->next;
int flag=0;
int count=0;
while(current){
count++;
current=current->next;
}
for(int i=0;i<count;i++){
flag=0;
while(list->next){
if(current->data>last->data){
pre->next=current->next;
last->next=pre->next;
current->next=last->next;
flag=1;
}
else{
pre=current;
current=current->next;
}
}
if(flag==0)break;
}
}
int main()
{
Node* list = initList();
headInsert(list,1);
headInsert(list,2);
headInsert(list,3);
tailInsert(list,4);
loop(list);
//delete(list,2);
//loop(list);
//int i=search(list,3);
ascend(list);
loop(list);
return 0;
}
【以下回答由 GPT 生成】
这段代码中没有实现链表的排序算法。如果要对单链表进行排序，可以使用冒泡排序或者快速排序。下面是对单链表进行冒泡排序的改进算法示例：
void bubbleSort(Node* list) {
if (list == NULL || list->next == NULL) {
return;
}
int swapped;
Node* ptr1;
Node* lptr = NULL;
do {
swapped = 0;
ptr1 = list;
while (ptr1->next != lptr) {
if (ptr1->data > ptr1->next->data) {
int temp = ptr1->data;
ptr1->data = ptr1->next->data;
ptr1->next->data = temp;
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while (swapped);
}
这是一个冒泡排序的改进版本。它通过设置lptr来记录上一次交换的位置，避免了对已经排好序的元素进行不必要的比较。排序的时间复杂度为O(n^2)。
如果要实现快速排序，可以使用递归的方式来处理链表。下面是对单链表进行快速排序的改进算法示例：
Node* getTail(Node* cur) {
while (cur != NULL && cur->next != NULL) {
cur = cur->next;
}
return cur;
}
Node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {
Node* pivot = end;
Node* prev = NULL, *cur = head, *tail = pivot;
while (cur != pivot) {
if (cur->data < pivot->data) {
if (*newHead == NULL)
*newHead = cur;
prev = cur;
cur = cur->next;
}
else {
if (prev) {
prev->next = cur->next;
}
Node* tmp = cur->next;
cur->next = NULL;
tail->next = cur;
tail = cur;
cur = tmp;
}
}
if (*newHead == NULL) {
*newHead = pivot;
}
*newEnd = tail;
return pivot;
}
Node* quickSortRecur(Node* head, Node* end) {
if (!head || head == end) {
return head;
}
Node* newHead = NULL, *newEnd = NULL;
Node* pivot = partition(head, end, &newHead, &newEnd);
if (newHead != pivot) {
Node* tmp = newHead;
while (tmp->next != pivot) {
tmp = tmp->next;
}
tmp->next = NULL;
newHead = quickSortRecur(newHead, tmp);
tmp = getTail(newHead);
tmp->next = pivot;
}
pivot->next = quickSortRecur(pivot->next, newEnd);
return newHead;
}
void quickSort(Node** headRef) {
*headRef = quickSortRecur(*headRef, getTail(*headRef));
}
这个算法使用了快速排序的思想来对链表进行排序。它首先找到尾节点，然后通过partition函数找到一个枢轴点，将链表分成两部分。再对左右两部分递归进行快速排序。排序的时间复杂度为O(nlogn)。
这些是改进后的排序算法示例，你可以根据自己的需要选择其中的一种来对单链表进行排序。
【相关推荐】