实现一个单向链表的：创建、插入、删除、排序（冒泡）、逆向、搜索中间节点
#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; typedef struct student { int data; struct student *next; } node; //创建链表 node *create() { //1. 定义变量 node *head = NULL; node *p = NULL; node *pnew = NULL; int x = 0; int cycle = 1; //2. 新建头节点 head = (node*)malloc(sizeof(node)); p = head; //3. 添加新节点 while (cycle) { printf("input data:"); scanf("%d", &x); if (x != 0) { pnew = (node*)malloc(sizeof(node)); pnew->data = x; p->next = pnew; p = pnew; } else { cycle = 0; } } //4. 释放头节点 p->next = NULL; p = head; head = head->next; free(p); p = NULL; //5. 返回链表 return head; } //计算链表长度 int length(node *head) { //1. 定义变量 node *p = NULL; int n = 0; //2. 遍历累加 p = head; while (p != NULL) { p = p->next; n++; } printf("%d ", n); //3. 返回计数 return n; } //显示 void show(node *head) { //1. 定义变量 node *p = NULL; //2. 遍历打印 p = head; while(p != NULL) { printf("data:%d ", p->data); p = p->next; } printf(" "); } //插入节点（升序） node *insert (node *head, int num) { //1. 定义变量 node *p0 = NULL; node *p1 = NULL; node *p2 = NULL; //2. 新建节点 p0 = (node*)malloc(sizeof(node)); p0->data = num; //3. 定位插入位置（升序） p1 = head; while (p0->data > p1->data && p1->next != NULL) { p2 = p1; p1 = p1->next; } //4. 插入节点 if (p0->data > p1->data) //末尾 { p1->next = p0; p0->next = NULL; } else { if (head == p1) //头 { p0->next = p1; head = p0; } else //中间 { p2->next = p0; p0->next = p1; } } //5. 返回头 return head; } //删除链表中指定节点 node *del(node *head, int num) { //1. 定义变量 node *p1 = NULL; node *p2 = NULL; //2. 定位删除位置 p1 = head; while (num != p1->data && p1->next != NULL) { p2 = p1; p1 = p1->next; } //3. 删除节点 if (num != p1->data) { printf("not found data to delete "); } else { if(p1 == head) { head = p1->next; free(p1); p1 = NULL; } else { p2->next = p1->next; free(p1); p1 = NULL; } } //4. 返回头 return head; } //链表升序排序（冒泡算法） node *sort(node *head) { //1. 定义变量 node *p = NULL; int n = 0; int temp = 0; if (head == NULL || head->next == NULL) { return head; } //2. 获取链表长度 n = length(head); //3. 排序 for (int j=1; j<n; ++j) //遍历所有节点 { p = head; for(int i=0; i<n-j; ++i) //遍历未排序好的节点 { if (p->data > p->next->data) { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next; } } //4. 返回头 return head; } //链表逆置 node *reverse(node *head) { //1. 定义变量 node *p1 = NULL; node *p2 = NULL; node *p3 = NULL; if (head == NULL || head->next == NULL) { return head; } //2. 逆置 p1 = head; p2 = p1->next; while(p2 != NULL) { p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; } //3. 调换头尾节点 head->next = NULL; //转置完后头节点成为尾节点 head = p1; //转置完后尾节点成为头节点 //4. 返回头 return head; } //搜索链表中间节点 //算法：以步长2和1单位同时遍历链表，步长2到末尾，步长1到中间 void searchmid(node *head, node *mid) { //1. 定义变量 node *p1 = NULL; node *p2 = NULL; //2. 定位中间节点 p1 = head; p2 = head; while (p2->next != NULL && p2->next->next != NULL) { p1 = p1->next; mid = p1; p2 = p2->next->next; } printf("mid:%d ", mid->data); } int main() { node *head = create(); int len = length(head); show(head); head = insert(head, 2); show(head); head = del(head, 2); show(head); head = sort(head); show(head); head = reverse(head); show(head); node *mid; searchmid(head, mid); }