亲宝软件园·资讯

展开

C语言单向链表

胡安民 人气:0

链表

链表实现了,内存零碎数据的有效组织。比如,当我们用 malloc 来进行内存申请的时候,当内存足够,但是由于碎片太多,没有连续内存时,只能以申请失败而告终,而用链表这种数据结构来组织数据,就可以解决上类问题。

静态链表

#include <stdio.h>
// 1.定义链表节点
typedef struct node{
    int data;
    struct node *next;
}Node;
int main(int argc, char *argv[]) {
    // 2.创建链表节点
    Node a;
    Node b;
    Node c;

    // 3.初始化节点数据
    a.data = 1;
    b.data = 3;
    c.data = 5;

    // 4.链接节点
    a.next = &b;
    b.next = &c;
    c.next = NULL;

    // 5.创建链表头
    Node *head = &a;

    // 6.使用链表
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;//指向下一个节点
    }

    return 0;
}

动态链表

静态链表的意义不是很大,主要原因,数据存储在栈上,栈的存储空间有限,不能动态分配。所以链表要实现存储的自由,要动态的申请堆里的空间。

有头链表

无头链表

单向链表有有头节点和无头节点两种列表, 有头节点在列表的删除,反转,插入等操作会比无头节点简单,但是不好之处就是多占用些空间,而且在多个链表结合处理的时候有头链表每次都需要过滤头节点,而无头链表直接完美融合 ,而且很多高级语言都是无头链表的便于日后的扩展 ,下面都是依据无头节点进行演示

定义链表节点

// 1.定义链表节点
typedef struct node {
    void *data;
    struct node *next;
} Node;

创建链表

/**
 * 创建链表
 */
Node *createList() {

    // 1.创建头节点
    Node *root = (Node *) malloc(sizeof(Node));
    root->data = NULL;
    root->next = NULL;
    //返回头节点
    return root;
}

创建一个空节点

/**
 * 创建一个空节点
 */
Node *createNode() {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = NULL;
    node->next = NULL;
    return  node;
}

尾插法

/**
 * @brief insertEndNode 尾插法插入节点
 * @param head 需要插入的头指针
 * @param data 需要插入的数据
 */
void insertEndNode(Node *node, void *data) {
    Node *head = node;
    //找到数据为空的节点,没有节点那么就扩展
    while (head->data != NULL) {
        //扩容
        if(head->next == NULL) {
            Node *pNode = createNode();
            head->next = pNode;
            head = pNode;
            break;
        }
        head = head->next;
    }
    //插入数据
    head->data = data;
}

头插法

/**
 * @brief insertHeadNode 头插法插入节点
 * @param head 需要插入的头指针
 * @param data 需要插入的数据
 */
void insertHeadNode(Node **node, void *data) {
    Node *pNode = createNode();
    pNode->data = data;
    pNode->next = *node;
    *node = pNode;
}

指定位置插入一个结点

简单来说就是先找到需要插入的位置,然后将当前位置节点和他前一个节点连接到需要插入的节点就行了

/**
 * @brief insertNOde 将数据节点插入到指定数据位置节点,指定数据节点向后移动,  如果没有找到插入的位置,那么就插入到最后
 * @param insertionPoint 指定的数据节点
 * @param data 需要插入的数据
 */
void insertNode(Node *node ,void *insertionPoint,void *data){
    Node *pNode = node;
    Node *pre = pNode;//父节点
    while (pNode!=NULL){
        if(pNode->data == insertionPoint){
            break;
        }
        pre=pNode; //保留当前节点
        pNode=pNode->next;
    }
    //如果没有找到那么就插入到最后
    if(pNode==NULL){
        insertEndNode(node,data);
        return;
    }
    Node *dataNode = createNode();
    dataNode->data= data;
    pre->next = dataNode;
    dataNode->next = pNode;
}

遍历链表

因为我们值存储是使用无类型的指针,所以需要转换为插入时候的类型才行

/**
 * @brief printNodeListDouble 遍历链表
 * @param node 链表指针头
 */
void printNodeListDouble(Node *node) {
    Node *head = node;
    while (head!=NULL&&head->data!=NULL){
        double *currentData = head->data;
        printf("currentData = %f\n", *currentData);
        head = head->next;
    }
}

获取链表长度

/**
 * @brief listLength 计算链表长度
 * @param head 链表头指针
 * @return 链表长度
 */
int listLength(Node *head){
    int count = 0;
    head = head;
    while(head){
        count++;
        head = head->next;
    }
    return count;
}

链表搜索

/**
 * @brief searchList 查找指定节点
 * @param head 链表头指针
 * @param key 需要查找的值
 * @return
 */
Node *searchList(Node *head, void *key){
    head = head;
    while(head){
        if(head->data == key){
            break;
        }else{
            head = head->next;
        }
    }
    return head;
}

链表数据排序

因为我们存储数据类型是使用无类型的指针,那么在排序的时候需要转换为指定类型才行

/**
 * @brief bubbleSort 对链表值进行排序  小到大
 * @param head 链表头指针
 */
void sortDouble(Node *head){
    // 1.计算链表长度
    int len = listLength(head);
    // 2.定义变量记录前后节点
    Node *cur = head;
    while (cur!=NULL){
        Node *cur1=cur->next;
        while (cur1!=NULL){
            //比较大小 ,然后交换数据
            if(*((double *)cur->data) > *((double *)cur1->data)){
                double *temp = (double *)cur->data;
                cur->data = cur1->data;
                cur1->data = temp;
            }
            cur1 = cur1->next;
        }
        cur= cur->next;
    }
}

反转链表

断开链表头,然后以头插法的方式将原链表的数据添加链表。

/**
 * @brief reverseList 反转链表
 * @param head 链表头指针
 */
void reverseList(Node **root){
    Node *head = *root;
    Node *pre=head, *cur=head->next;
    pre->next = NULL;
    while (cur!=NULL){
        Node *node = cur->next;
        cur->next = pre;
        pre = cur;
        cur=node;
    }
    *root=pre;
}

删除节点数据

先找到需要删除的节点,之后将后一个结点赋值给前一个结点的next,然后将删除位置的结点释放即可

/**
 * @brief delNode 删除指定节点
 */
void delNode(Node **root, void *key){
    Node *head = *root;
    //根节点单独处理
    if(head->data == key&&head->next != NULL){
        *root = head->next;
        free(head->data);
        free(head);
        return;
    }

    Node *head1 = head->next;
    Node *pre = head;//根节点
    while (head1!=NULL){
        if(head1->data == key){
            pre->next = head1->next;
            free(head1->data);
            free(head1);
            break;
        }
        pre = head1;//当前节点
        head1 = head1->next; //下一个节点
    }
}

销毁链表

/**
 * @brief destroyList 销毁链表
 * @param head 链表头指针
 */
void destroyList(Node *head){
    Node *cur = head;
    while(head != NULL){
        cur = head->next;
        free(head->data);//清除当前节点数据内存
        free(head);//清除当前节点内存
        head = cur;
    }
}

测试

int main(int argc, char *argv[]) {


    //创建链表
    Node *head = createList();

    //插入数据
    printf("insert ====================\n");
    double *f = (double *)malloc(sizeof(double));
    *f=2.1;
    insertEndNode(head, f);
    double *f1 = (double *)malloc(sizeof(double));
    *f1=1.1;
    insertEndNode(head, f1);
    double *f2= (double *)malloc(sizeof(double));
    *f2=0.1;
    insertEndNode(head, f2);

    double *f3= (double *)malloc(sizeof(double));
    *f3=3.1;
    insertHeadNode(&head, f3);


    double *se = (double *)malloc(sizeof(double));
    *se=111.1;
    double *f4= (double *)malloc(sizeof(double));
    *f4=7.1;
    insertNode(head,se, f4);
    free(se);
    printNodeListDouble(head);

    //获取长度
    printf("listLength ====================\n");
    int i = listLength(head);
    printf("listLength = %d\n", i);

    //搜索
    printf("searchList ====================\n");
    Node *pNode = searchList(head, f1);
    printf("currentData = %f\n", *((double *)pNode->data));

    //排序
    printf("sortDouble ====================\n");
    sortDouble(head);
    printNodeListDouble(head);

    //反转
    printf("reverseList ====================\n");
    reverseList(&head);
    printNodeListDouble(head);

    //删除节点
    printf("delNode ====================\n");
    delNode(&head, f1);
    printNodeListDouble(head);

    //销毁
    destroyList(head);


    return 0;
}

加载全部内容

相关教程
猜你喜欢
用户评论