C语言实现链表及常用的维护方法
本文最后更新于 408 天前,其中的信息可能已经有所发展或是发生改变。

用C语言实现了链表,还有比较常用的22个常用维护方法。

下面的文章会比较详细的写一些功能的实现方法。这里就直接贴代码了。

/* 1.初始化线性表,置链表的表头指针为空 */ //initNode
/* 2.创建线性表 */ //create
/* 3.打印链表*/ //show
/* 4.清除线性表中的所有元素,即释放链表中所有的结点,使之成为一个空表 */ //clear
/* 5.返回链表的长度 */ //getLength
/* 6.检查链表是否为空,若为空则返回1,否则返回0 */ //isEmpty
/* 7.返回链表中第pos个结点中的元素,若超出范围返回0 */ //get
/* 8.从链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回NULL */ //find
/* 9.把链表中第pos个结点的值修改为x的值 */ //change
/* 10.向链表的表头插入一个元素 */ //insertHead
/* 11.向链表的末尾添加一个元素 */ //insertTail
/* 12.向链表中第pos个结点位置插入元素为x的结点 */ //insert
/* 13.向有序链表中插入元素x结点,使得插入后仍然有序 */ //insertByRange
/* 14.从链表中删除表头结点 */ //deleteHead
/* 15.从链表中删除表尾结点并返回它的值 */ //pop
/* 16.从链表中删除第pos个结点 */ //delete
/* 17.从链表中删除值为x的第一个结点,若删除成功则返回1,否则返回0 */ //removeOne
/* 18.交换2个元素的位置 */ //swapTwo
/* 19.对线性表进行快速排序 */ //sort
/* 20.将当前线性表逆序 */ //reverse
/* 21.从链表中删除值为x的所有节点 */ //removeAll
/* 22.从链表中获取一个数组 */ //toArray

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

#define len(array) (sizeof(array) / sizeof(array[0]))
#define max(a, b) (a >= b ? a : b)

#define true 1
#define false 0

struct node{
    int data;
    struct node* next;
};

typedef struct node node;

node* initNode(void){
    node* headNode;
    headNode = (node *)malloc(sizeof(node));
    headNode -> next = NULL;
    return headNode;
}

node* create(int* array, int length){
    node* newNode;
    node* lastNode;
    node* headNode = initNode();
    newNode = (node *)malloc(sizeof(node));
    headNode -> data = array[0];
    int arrayLength = 1;
    int hasSetHead = false;
    while(arrayLength < length){
        if (! hasSetHead){
            lastNode = headNode;
            hasSetHead = true;
        }
        memset(newNode, 0, sizeof(node));
        newNode -> data = array[arrayLength];
        newNode -> next = NULL;
        lastNode -> next = newNode;
        lastNode = newNode;
        newNode = malloc(sizeof(node));
        if (newNode == NULL) exit(0);
        arrayLength++;
    }
    return headNode;
}

void show(node* headNode){
    if (headNode == NULL) return;
    while(headNode != NULL){
        printf("%d ", headNode -> data);
        headNode = headNode -> next;
    }
    putchar('\n');
}

int getLength(node* headNode){
    if (headNode == NULL) return false;
    int length = 0;
    while (headNode != NULL){
        length++;
        headNode = headNode -> next;
    }
    return length;
}

void clear(node** headNode){
    if (headNode == NULL) return;
    node* nextNode;
    while (*headNode != NULL){
        nextNode = (*headNode) -> next;
        free(*headNode);
        *headNode = nextNode;
    }
    *headNode = NULL;
}

void deleteHead(node** headNode){
    if (*headNode == NULL) return;
    node* newHeadNode;
    node* previousNode;
    newHeadNode = (*headNode) -> next;
    previousNode = (*headNode);
    *headNode = newHeadNode;
    free(previousNode);
}

void deleteTail(node** headNode){
    if (*headNode == NULL) return;
    node* previousNode;
    node* currentNode;
    previousNode = *headNode;
    currentNode = (*headNode) -> next;
    while ((currentNode -> next) != NULL){
        previousNode = currentNode;
        currentNode = currentNode -> next;
    }
    previousNode -> next = NULL;
    free(currentNode);
}

void delete(node** headNode, int remoth){
    if (*headNode == NULL) return;
    int length = getLength(*headNode);
    if (remoth > length - 1 || remoth < 0) return;
    if (remoth == 0){
        deleteHead(headNode);
        return;
    }
    if (remoth == length - 1){
        deleteTail(headNode);
        return;
    }
    node* previousNode;
    node* nextNode;
    node* currentNode;
    previousNode = *headNode;
    currentNode = previousNode -> next;
    nextNode = currentNode -> next;
    int locate = 0;
    while (locate < remoth - 1){
        previousNode = previousNode -> next;
        currentNode = previousNode -> next;
        nextNode = currentNode -> next;
        locate++;
    }
    free(currentNode);
    previousNode -> next = nextNode;
}

int pop(node** headNode){
    if (*headNode == NULL) return false;
    int data = (*headNode) -> data;
    deleteHead(headNode);
    return data;
}

int isEmpty(node* headNode){
    if (headNode == NULL) return false;
    return true;
}

int get(node* headNode, int position){
    if (headNode == NULL) return false;
    int length = getLength(headNode);
    if (position > length) return false;
    int current = 0, data;
    while (current < position){
        headNode = headNode -> next;
        current++;
    }
    data = headNode -> data;
    return data;
}

int* find(node* headNode, int target){
    if (headNode == NULL) return false;
    while (true){
        if ((headNode -> data) == target){
            return (&(headNode -> data));
        }
        headNode = headNode -> next;
    }
    return NULL;
}

void change(node* headNode, int position, int changed){
    if (headNode == NULL) return;
    int length = getLength(headNode);
    if (position > length) return;
    int current = 0;
    while (current < position){
        headNode = headNode -> next;
        current++;
    }
    headNode -> data = changed;
}

void insertHead(node** headNode, int data){
    if (*headNode == NULL) return;
    node* newHeadNode;
    newHeadNode = initNode();
    newHeadNode -> data = data;
    newHeadNode -> next = *headNode;
    *headNode = newHeadNode;
}

void insertTail(node** headNode, int data){
    if (*headNode == NULL) return;
    node* newTailNode = initNode();
    newTailNode -> data = data;
    node* currentNode = *headNode;
    while (currentNode -> next != NULL){
        currentNode = currentNode -> next;
    }
    currentNode -> next = newTailNode;
}

void insert(node** headNode, int inserth, int data){
    if (*headNode == NULL) return;
    int length = getLength(*headNode);
    if (inserth > length - 1 || inserth < 0) return;
    if (inserth == 0){
        insertHead(headNode, data);
        return;
    }if (inserth == length - 1){
        insertTail(headNode, data);
        return;
    }
    node* newNode = initNode();
    newNode -> data = data;
    node* previousNode;
    node* nextNode;
    previousNode = *headNode;
    int current = 0;
    while(current < inserth - 1){
        previousNode = previousNode -> next;
        nextNode = previousNode -> next;
        current++;
    }
    newNode -> next = previousNode -> next;
    previousNode -> next = newNode;
}

void insertByRange(node** headNode, int data){
    if (*headNode == NULL) return;
    node* currentNode = *headNode;
    int index = 0;
    while (currentNode -> data < data){
        currentNode = currentNode -> next;
        index++;
    }
    insert(headNode, index, data);
}

int removeOne(node** headNode, int data){
    if (*headNode == NULL) return false;
    node* currentNode = *headNode;
    int index = 0;
    while ((currentNode -> next) != NULL){
        if ((currentNode -> data) == data){
            delete(headNode, index);
            return true;
        }
        currentNode = currentNode -> next;
        index++;
    }
    return false;
}

void removeAll(node** headNode, int data){
    if (*headNode == NULL) return;
    node* currentNode = *headNode;
    int index = 0;
    while ((currentNode -> next) != NULL){
        if ((currentNode -> data) == data){
            delete(headNode, index);
        }
        currentNode = currentNode -> next;
        index++;
    }
}

void swapTwo(node** headNode, int fIndex, int sIndex){
    if (*headNode == NULL) return;
    if (fIndex == sIndex) return;
    int maxIndex = max(fIndex, sIndex);
    int minIndex = ((maxIndex == fIndex) ? sIndex : fIndex);
    int length = getLength(*headNode);
    if (maxIndex >= length || minIndex < 0) return;
    node* currentNode = *headNode;
    node* minNode;
    node* maxNode;
    int currentIndex = 0;
    while (currentIndex < minIndex){
        currentNode = currentNode -> next;
        currentIndex++;
    }
    int minIndexValue = currentNode -> data;
    minNode = currentNode;
    while (currentIndex < maxIndex){
        currentNode = currentNode -> next;
        currentIndex++;
    }
    int maxIndexValue = currentNode -> data;
    maxNode = currentNode;
    minNode -> data = maxIndexValue;
    maxNode -> data = minIndexValue;
}

void reverse(node** headNode){
    if (*headNode == NULL) return;
    if ((*headNode) -> next == NULL) return;
    node* previousNode;
    node* currentNode;
    node* nextNode;
    previousNode = *headNode;
    currentNode = previousNode -> next;
    nextNode = currentNode -> next;
    (*headNode) -> next = NULL;
    while (true){
        currentNode -> next = previousNode;
        previousNode = currentNode;
        currentNode = nextNode;
        nextNode = nextNode -> next;
        if (nextNode == NULL) break;
    }
    currentNode -> next = previousNode;
    *headNode = currentNode;
}

void _swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}

int _partition(int *array, int low, int high){
    int pivot = array[high];
    int i = low - 1, j;
    for (j = low; j <= high - 1; j++){
        if (array[j] <= pivot){
            i++;
            _swap(&array[i], &array[j]);
        }
    }
    _swap(&array[high], &array[i + 1]);
    return (i + 1);
}

void _quick(int *array, int low, int high){
    if (low >= high) return;
    int pivot = _partition(array, low, high);
    _quick(array, low, pivot - 1);
    _quick(array, pivot + 1, high);
}

void toArray(node* headNode, int* array, int length){
    int currentIndex = 0, data;
    while (headNode != NULL || currentIndex < length){
        data = headNode -> data;
        headNode = headNode -> next;
        array[currentIndex] = data;
        currentIndex++;
    }
}

void sort(node** headNode){
    int length = getLength(*headNode);
    int eleArray[length];
    toArray(*headNode, eleArray, length);
    _quick(eleArray, 0, length);
    *headNode = create(eleArray, length);
}

int main(void){
    return true;
}

所有的方法在顶部的注释有解释,我自己试了试,还蛮好用的
开心o(* ̄▽ ̄*)ブ

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇