C链表实现重制版
重写了 C 链表的算法,将原本多个函数整合成一个函数,并且保留原本功能的函数,只不过现在是通过调用父函数实现,也就是子函数通过调用一个集成了多种功能的父函数实现部分父函数功能,减少了大量的代码,另外目前新算法是在之前写的 Java 链表的基础上写的,并且改进了部分代码,重新看了一遍自己写的 Java 链表才发现还有许多不足,不久后将会在这个算法上修改自己写的 Java 链表,( ̄ ▽  ̄)”
Coding 了两个小时终于将排序部分弄完了,这次加入了快速排序,链表的排序不再缓慢,这是不可能的,其实快速排序在某些情况下的速度会降到 O(N^2),正常情况下的时间复杂度是 O(NlogN),还加入了两个获取数据的函数
_276#include <stdio.h>_276#include <malloc.h>_276#include <time.h>_276//数据块_276typedef struct Data_276{_276 int intData;_276 char charData;_276} Data,*pData;_276_276//链表结构_276typedef struct Node_276{_276 // 指向上一个节点的指针_276 struct Node *prev;_276 // 数据域_276 struct Data *data;_276 // 指向下一个节点的指针_276 struct Node *next;_276} Node,*pNode;_276_276// 头节点_276pNode head = NULL;_276// 尾节点_276pNode end = NULL;_276// 链表长度_276int len = 0;_276_276//添加节点函数,传入一个链表_276void Add(int i/*插入的位置,若为 -1 则代表从尾插入*/, pData data/*传入数据域*/, pNode havaNode) {_276 len++;_276 // 定位_276 int j;_276 // 定义新节点_276 pNode newNode = NULL;_276 if(havaNode == NULL) { // 判断是创建新节点还是,已有节点_276 // 创建新节点_276 newNode = (pNode)malloc(sizeof(Node));_276 // 将新节点的数据域指向传入的数据域_276 newNode->data = data;_276 } else { // 若为已有节点就将已有节点定义为newNode_276 newNode = havaNode;_276 }_276 // 设置新节点的指针域,防止形成野指针_276 newNode->prev = NULL;_276 newNode->next = NULL;_276 // 创建定位节点,指向链表头节点_276 pNode indexNode = head;_276_276 if(head == NULL) { // 判断链表是否为空,若为空只需将新节点设为头节点和尾节点即可_276 // 设置新节点为头节点和尾节点_276 head = newNode;_276 end = newNode;_276 return;_276 }_276_276 if(i == 0) { // 判断是否是插入到第一个 节点_276 // 将新节点添加至头节点前_276 newNode->next = head;_276 head->prev = newNode;_276 // 设置新节点为头节点_276 head = newNode;_276 return;_276 } else if(i == -1) { // 判断是否添加至最后一个节点_276 // 定位到尾节点_276 while(indexNode->next != NULL) {_276 indexNode = indexNode->next;_276 }_276 }_276_276 // 若在中间插入,则将定位节点定位到该节点的上一个节点_276 for(j = 0; j < i-1 && indexNode != NULL; j++) {_276 indexNode = indexNode->next;_276 }_276_276 // 判断目前的节点是否是最后一个节点,也就是插入节点是否是插在尾部,i=-1 的插入操作也是在这完成的_276 if(indexNode->next == NULL) {_276 // 插入新节点到链表尾部_276 indexNode->next = newNode;_276 newNode->prev = indexNode;_276 // 重新设置end节点_276 end = newNode;_276 return;_276 }_276_276 // 下方是新节点插入中间的情况_276 // 创建临时节点,指向定位节点的下一个节点,结构和步骤和Java链表相同,这里就不写注释了_276 pNode tempNode = indexNode->next;_276 indexNode->next = newNode;_276 newNode->next = tempNode;_276 newNode->prev = indexNode;_276 tempNode->prev = newNode;_276 return;_276}_276_276void AddFirst(pData data) {_276 Add(0, data, NULL);_276}_276_276void AddLast(pData data) {_276 Add(-1, data, NULL);_276}_276_276void Insert(int i, pNode havaNode) {_276 Add(i, NULL, havaNode);_276}_276_276void Delete(int i/*删除的位置*/) {_276 len--;_276 // 判断是否是删除第一个节点_276 if (i == 0) {_276 // 将头节点指向第二个节点,然后将头节点的prev设置为NULL,这样就屏蔽掉了第一个节点_276 head = head->next;_276 head->prev = NULL;_276 return;_276 }_276 // 若是删除最后一个节点,那只需将尾节点移到倒数第二个节点即可_276 else if (i == -1) {_276 end = end->prev;_276 end->next = NULL;_276 return;_276 }_276_276 // 递增定位_276 int j;_276 // 创建定位节点,将其指向头节点_276 pNode indexNode = head;_276 // 将定位节点移至要删除节点的上一个节点_276 for (j = 0; j < i - 1 && indexNode != NULL; j++) {_276 indexNode = indexNode->next;_276 }_276 // 判断要删除节点是否是最后一个节点_276 if (indexNode->next->next == NULL) {_276 // 操作方式同删除头节点与_276 end = end->prev;_276 end->next = NULL;_276 return;_276 }_276 // 要删除节点的下一个节点prev设置为要删除节点的上一个节点_276 indexNode->next->next->prev = indexNode;_276 // 将要删除节点的上一个节点的next设置为要删除节点的下一个节点_276 indexNode->next = indexNode->next->next;_276}_276_276void Clear() {_276 len = 0;_276 free(head);_276 head = NULL;_276 end = NULL;_276}_276_276void Resever() {_276 // 创建临时节点用来临时存储指向数据_276 pNode tempNode = NULL;_276 // 将头节点与尾节点交换_276 tempNode = head;_276 head = end;_276 end = tempNode;_276 // 创建定位节点_276 pNode indexNode = head;_276 // 循环交换next和prev数据_276 while (indexNode->prev != NULL && (indexNode->next != NULL || indexNode == head)) {_276 tempNode = indexNode->next;_276 indexNode->next = indexNode->prev;_276 indexNode->prev = tempNode;_276 indexNode = indexNode->next;_276 }_276 // 设置最后一个节点的next为null_276 end->next = NULL;_276 // 设置最后一个节点的prev数据_276 end->prev = tempNode->next;_276}_276_276pData GetData(int i) {_276 if(i < len/2) {_276 pNode indexNode = head;_276 for(int j = 0; j < i && indexNode != NULL; j++) {_276 indexNode = indexNode->next;_276 }_276 return indexNode->data;_276 } else {_276 pNode indexNode = end;_276 for(int j = len - 2; j >= i && indexNode != NULL; j--) {_276 indexNode = indexNode->prev;_276 }_276 return indexNode->data;_276 }_276}_276_276pNode GetNode(int i) {_276 if(i < len/2) {_276 pNode indexNode = head;_276 for(int j = 0; j < i && indexNode != NULL; j++) {_276 indexNode = indexNode->next;_276 }_276 return indexNode;_276 } else {_276 pNode indexNode = end;_276 for(int j = len - 2; j >= i && indexNode != NULL; j--) {_276 indexNode = indexNode->prev;_276 }_276 return indexNode;_276 }_276}_276_276//链表排序-从小到大_276void Bubble_Sort()_276{_276 //定义排序个数和下标的变量_276 int i, j, k;_276 //定义判断链表个数的链表和用来判断大小的链表_276 pNode p = head, temp;_276 //外层循环控制循环轮数_276 for(i = 0; i < len - 1; i++)_276 {_276 //内层循环控制每轮比较次数_276 for(j = 0; j < len - i - 1; j++)_276 {_276 temp = GetNode(j);_276 if(temp->data->intData > temp->next->data->intData)_276 {_276 //交换的方式是先删除大数据的节点,然后在添加回链表_276 //删除大数据的节点_276 Delete(j);_276 //将删除后的节点添加会链表的下一个节点_276 Insert(j+1,temp);_276 }_276 }_276 }_276}_276_276//快速排序函数_276void Quick_Sort(pNode left, pNode pivot, int l, int p)_276{_276 int r = p - 1;_276 pNode right = pivot->prev;_276 int l_temp = l;_276 pNode left_temp = left;_276 pData tempData;_276 while(l < r) {_276 while(left->data->intData < pivot->data->intData) {_276 l++;_276 left = left->next;_276 if(l > r) break;_276 }_276 while(right->data->intData > pivot->data->intData) {_276 r--;_276 right = right->prev;_276 if(l > r) break;_276 }_276 if(l >= r) break;_276 tempData = left->data;_276 left->data = right->data;_276 right->data = tempData;_276 }_276 if(left->data->intData >= pivot->data->intData) {_276 tempData = left->data;_276 left->data = pivot->data;_276 pivot->data = tempData;_276 }_276 if(l_temp < l - 1) Quick_Sort(left_temp, left->prev, l_temp, l - 1);_276 if(l + 1 < p) Quick_Sort(left->next, pivot, l + 1, p);_276}_276_276int main() {_276 for(int i = 0;i <= 5;i++) {_276 pData data = (pData)malloc(sizeof(Data));_276 scanf("%d",&data->intData);_276 AddFirst(data);_276 }_276 // Resever();_276 // Bubble_Sort();_276 Quick_Sort(head, end, 0, len - 1);_276 // pNode node2 = GetNode(3);_276 return 0;_276}
C链表实现重制版
https://blog.ixk.me/post/c-linked-list-implementation-new许可协议
发布于
2018-12-26
本文作者
Otstar Lin
转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!