0%

链表参考实现

链表参考实现代码

处理了传入非法参数等大部分特殊情况.

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

struct N{
    int value;
    struct N *next;
};
typedef struct N * nodePtr;
typedef struct N node;

/**
 * 根据数组创建长度为n的链表
 * @param value
 * @param n
 * @return
 */
nodePtr buildByArray(int value[], int n){
    nodePtr head = (nodePtr)malloc(sizeof(node));
    nodePtr tail = head;
    nodePtr t = NULL;
    int i = 1;
    head->next = NULL;
    head->value = value[0];
    tail = head;
    for(i = 1; i < n; ++ i){
        t = (nodePtr)malloc(sizeof(node));
        t->value = value[i];
        t->next = NULL;
        tail->next = t;
        tail = t;
    }
    return head;
}

/**
 * 构建一个值全部为0的长度为n的链表
 * @param n
 * @return
 */
nodePtr buildByZeros(int n){
    nodePtr head = (nodePtr)malloc(sizeof(node));
    nodePtr tail = head;
    nodePtr t = NULL;
    int i = 1;
    head->next = NULL;
    head->value = 0;
    tail = head;
    for(i = 1; i < n; ++ i){
        t = (nodePtr)malloc(sizeof(node));
        t->value = 0;
        t->next = NULL;
        tail->next = t;
        tail = t;
    }
    return head;
}

/**
 * 在链表头部添加一个节点
 * @param head
 * @param value
 * @return nodePtr
 */
nodePtr insertAsHead(nodePtr head, int value){
    nodePtr p = (nodePtr)malloc(sizeof(node));
    p->value = value;
    p->next = head;
    return p;
}

/**
 * 在链表尾部添加一个新节点
 * @param head
 * @param value
 * @return
 */
nodePtr insertAsTail(nodePtr head, int value){
    nodePtr h = head;
    nodePtr p;
    while(head->next != NULL){
        head = head->next;
    }
    p = (nodePtr)malloc(sizeof(node));
    p->value = value;
    p->next = NULL;
    head->next = p;
    return h;
}

/**
 * 在指定节点后面插入一个新节点
 * @param after
 * @param value
 * @return
 */
nodePtr insertAfter(nodePtr after, int value){
    nodePtr tmp;
    if(after == NULL){
        return NULL;
    }
    tmp = (nodePtr)malloc(sizeof(node));
    tmp->value = value;
    tmp->next = after->next;
    after->next = tmp;
    return tmp;
}

/**
 * 返回第一个指定值的value
 * @param head
 * @param value
 * @return
 */
nodePtr findByValue(nodePtr head, int value){
    nodePtr p = head;
    while(p != NULL){
        if(value == p->value){
            return p;
        }
        p++;
    }
    return NULL;
}


/**
 * 返回链表中的第ID个节点
 * @param head
 * @param id
 * @return
 */
nodePtr findByIndex(nodePtr head, int id){
    nodePtr p = head;
    if(id < 0) return NULL;
    while(id--){
        if(p == NULL) break;
        p = p->next;
    }
    return p;
}

/**
 * 删除链表中第一个指定值的节点
 * @param head
 * @param value
 * @return
 */
nodePtr delByValue(nodePtr head, int value){
    nodePtr p = head;
    nodePtr t;
    if(head == NULL){
        return NULL;
    }
    if(head->value == value){
        p = head->next;
        free(head);
        return p;
    }
    while(p->next != NULL){
        if(value == p->next->value){
            t = p->next;
            p->next = t->next;
            free(t);
            return head;
        }
        p++;
    }
    return head;
}

/**
 * 删除链表中第ID个节点
 * @param head
 * @param id
 * @return
 */
nodePtr delByIndex(nodePtr head, int id){
    nodePtr t = NULL;
    nodePtr p;
    if(head == NULL){
        return NULL;
    }
    p = NULL;
    if(id == 0){
        p = head->next;
        free(head);
        return p;
    }
    p = findByIndex(head, id-1);
    if(p == NULL){
        return head;
    }
    t = p->next;
    p->next = t->next;
    free(t);
    return head;
}

/**
 * 打印链表
 * @param head
 */
void printList(nodePtr head){
    while(head != NULL){
        printf("%d ", head->value);
        head = head->next;
    }
    printf("\n");
}

/**
 * 删除链表, 释放空间
 * @param head
 */
void freeList(nodePtr head){
    nodePtr p = head;
    while(p != NULL){
        free(head);
        head = p->next;
        p = p->next;
    }
}

int main(){
    nodePtr head = NULL;
    int values[] = {0,1,2,3,4,5,6,7,8,9,0};
    head = buildByArray(values,11);
    printList(head);
    insertAfter(head->next->next->next,5);
    printList(head);
    head = delByIndex(head,0);
    printList(head);
    head = delByValue(head,1);
    printList(head);
    printList(findByValue(head, 8));
    freeList(head);
    return 0;
}

欢迎关注我的其它发布渠道