站点图标

C链表实现重制版

2018-12-26折腾记录算法 / C
本文最后更新于 410 天前,文中所描述的信息可能已发生改变

重写了 C 链表的算法,将原本多个函数整合成一个函数,并且保留原本功能的函数,只不过现在是通过调用父函数实现,也就是子函数通过调用一个集成了多种功能的父函数实现部分父函数功能,减少了大量的代码,另外目前新算法是在之前写的 Java 链表的基础上写的,并且改进了部分代码,重新看了一遍自己写的 Java 链表才发现还有许多不足,不久后将会在这个算法上修改自己写的 Java 链表,( ̄ ▽  ̄)”

Coding 了两个小时终于将排序部分弄完了,这次加入了快速排序,链表的排序不再缓慢,这是不可能的,其实快速排序在某些情况下的速度会降到 O(N^2),正常情况下的时间复杂度是 O(NlogN),还加入了两个获取数据的函数


_276
#include <stdio.h>
_276
#include <malloc.h>
_276
#include <time.h>
_276
//数据块
_276
typedef struct Data
_276
{
_276
int intData;
_276
char charData;
_276
} Data,*pData;
_276
_276
//链表结构
_276
typedef struct Node
_276
{
_276
// 指向上一个节点的指针
_276
struct Node *prev;
_276
// 数据域
_276
struct Data *data;
_276
// 指向下一个节点的指针
_276
struct Node *next;
_276
} Node,*pNode;
_276
_276
// 头节点
_276
pNode head = NULL;
_276
// 尾节点
_276
pNode end = NULL;
_276
// 链表长度
_276
int len = 0;
_276
_276
//添加节点函数,传入一个链表
_276
void 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
_276
void AddFirst(pData data) {
_276
Add(0, data, NULL);
_276
}
_276
_276
void AddLast(pData data) {
_276
Add(-1, data, NULL);
_276
}
_276
_276
void Insert(int i, pNode havaNode) {
_276
Add(i, NULL, havaNode);
_276
}
_276
_276
void 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
_276
void Clear() {
_276
len = 0;
_276
free(head);
_276
head = NULL;
_276
end = NULL;
_276
}
_276
_276
void 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
_276
pData 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
_276
pNode 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
//链表排序-从小到大
_276
void 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
//快速排序函数
_276
void 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
_276
int 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
  • 许可协议

    BY-NC-SA

  • 发布于

    2018-12-26

  • 本文作者

    Otstar Lin

转载或引用本文时请遵守许可协议,注明出处、不得用于商业用途!

Windows IP变化自动发送邮件C 结构体的定义和使用