数据结构与算法_C语言描述_单链表

妖狐艹你老母 2022-12-21 06:25 154阅读 0赞

## 数据结构与算法\_C语言描述\_单链表 ##

入职四个月，在用c语言开发，正好练习一下c语言。希望每周实现一个数据结构：链表，栈，队列，二叉树… … 最终希望实现红黑树（毕竟面试经常问到）。同时每周也会分享linux相关知识。  
leetcode ： [leetcode官网][leetcode] 的explore栏目有各个数据结构的实现题目，使用起来非常方便。如下便是链表的题目：

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
    
    在链表类中实现这些功能：
    
    get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
    addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
    addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
    deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
     
    
    示例：
    
    MyLinkedList linkedList = new MyLinkedList();
    linkedList.addAtHead(1);
    linkedList.addAtTail(3);
    linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
    linkedList.get(1);            //返回2
    linkedList.deleteAtIndex(1);  //现在链表是1-> 3
    linkedList.get(1);            //返回3
     
    
    提示：
    
    所有val值都在 [1, 1000] 之内。
    操作次数将在  [1, 1000] 之内。
    请不要使用内置的 LinkedList 库。
    
    作者：力扣 (LeetCode)
    链接：https://leetcode-cn.com/leetbook/read/linked-list/jy291/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我自己的解法如下，其中printList用于调试：

typedef struct Node{
        
        int val;
        struct Node * next;
    }Node;
    
    typedef struct {
        
        int length;
        Node * head;
    } MyLinkedList;
    
    
    /** Initialize your data structure here. */
    
    MyLinkedList* myLinkedListCreate() {
        
        MyLinkedList * list = malloc(sizeof(MyLinkedList));
        list -> length = 0;
        list -> head = NULL;
        return list;
    }
    
    void printList(MyLinkedList* obj)
    {
        
        Node * t = obj -> head;
        while(t!=NULL)
        {
        
            printf("%d,",t->val);
            t=t->next;
        }
        printf("\n");
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int myLinkedListGet(MyLinkedList* obj, int index) {
        
        if(index < 0 || index >= (obj -> length))
            return -1;
        int ret = 0;
        Node * t;
        t=obj -> head;
        for(int i=0;i<=index;i++)
        {
        
            ret = t -> val;
            t=t -> next;
        }
        //printList(obj);
        return ret;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
        
        if(obj -> head == NULL)
        {
        
            Node * t = malloc(sizeof(Node));
            t -> val = val;
            t -> next = NULL;
            obj -> head = t;
        }
        else
        {
        
            Node * t = malloc(sizeof(Node));
            t -> val = val;
            t -> next = obj -> head;
            obj -> head = t;
        }
        obj -> length++;
        //printList(obj);
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
        
        if(obj -> head == NULL)
        {
        
            Node * t = malloc(sizeof(Node));
            t -> val = val;
            t -> next = NULL;
            obj -> head = t;
        }
        else
        {
        
            Node * t ;
            t = obj -> head;
            while(t-> next != NULL)
            {
        
                t = t -> next;
            }
            Node * last = malloc(sizeof(Node));
            last -> val = val;
            last -> next = NULL;
            t -> next = last;
        }
        obj -> length++;
        //printList(obj);
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
        
        if(index > obj -> length)
            return;
        if(index == obj -> length)
            {
        
            myLinkedListAddAtTail(obj, val);
            return;
            }
        if(index < 1){
        
            myLinkedListAddAtHead(obj, val);
            return;
        }
        obj -> length++;
        int t = index;
        Node * h ;
        h = obj -> head;
        Node * insert = malloc(sizeof(Node));
        insert -> val = val;
        insert -> next = NULL;
        int i = 0;
        for(i=0;i<t-1;i++)
        {
        
            h = h->next;
        }
        Node * hh = h->next;
        insert -> next = hh;
        h-> next = insert;
        //printList(obj);
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
        
        if(index >= obj -> length || index <0)
            return;
        int t = index;
        Node * del = obj -> head;
        if(obj -> length == 1)
        {
        
            free(del);
            obj -> length --;
        }
        else{
        
            if(t == 0)
            {
        
                obj -> head = del ->next;
                free(del);
                obj->length--;
            }
            else{
        
                int i = 0;
                for(i=0;i<t-1;i++)
                {
        
                    del =del -> next;
                }
                if(t==obj->length)
                {
        
                    free(del->next);
                    del -> next = NULL;
                }
                else{
        
                    Node * nextn = del ->next;
                    del -> next = nextn ->next;
                    free(nextn);
                }
                obj -> length --;
            }
        }
        //printList(obj);
    }
    
    void myLinkedListFree(MyLinkedList* obj) {
        
        //Node * t = obj -> head;
        int t = obj -> length;
        while(t>0)
        {
        
            myLinkedListDeleteAtIndex(obj, 0);
            t--;
        }
        free(obj);
        return;
    }
    
    /**
     * Your MyLinkedList struct will be instantiated and called as such:
     * MyLinkedList* obj = myLinkedListCreate();
     * int param_1 = myLinkedListGet(obj, index);
     
     * myLinkedListAddAtHead(obj, val);
     
     * myLinkedListAddAtTail(obj, val);
     
     * myLinkedListAddAtIndex(obj, index, val);
     
     * myLinkedListDeleteAtIndex(obj, index);
     
     * myLinkedListFree(obj);
    */

这个实现里面有两个问题：  
1.何时使用或者何时不使用malloc来获取一个新的单元。当然insert时候需要使用malloc，但是只是沿着链表进行遍历的话，则不需要使用malloc。  
2.删除链表（myLinkedListFree）的实现。原则当然是malloc一次，free一次，我的函数里面第二个参数是0或者1，都能pass全部测试用例，但是显然为1的话，最后一个头节点没有free，系统也没有检测出来，也算是内存泄漏的一个问题。

myLinkedListDeleteAtIndex(obj, 0);

下一周我会使用《数据结构与算法分析-c语言描述》这本书再实现一个版本，主要变化是：  
1.函数更多（如判断一个元素在不在链表里）  
2.模块化程度更高  
另外，终于知道编译开关的重要作用了，最起码调试起来非常方便。

[leetcode]: https://leetcode-cn.com/