数据结构：单向链表

亦凉 2022-05-31 00:45 232阅读 0赞

Python：

注：不带头结点

#!/usr/bin/python3.5
    # _*_coding:utf-8_*_
    class Node():
        def __init__(self, value):
            self.data = value
            self.next = None
    
    
    class LinkList():
        '''没有头结点'''
    
        def __init__(self):
            self._head = None
    
        def empty(self):
            return self._head == None
    
        def length(self):
            cur = self._head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            cur = self._head
            while cur != None:
                print(cur.data)
                cur = cur.next
    
        def insert(self, index, value):
            index -= 1
            p = Node(value)
            if index == 0:
                if self._head == None:
                    self._head = p
                    return
                p.next = self._head
                self._head = p
                return
    
            cur = self._head
            for i in range(index - 2):
                cur = cur.next
                if cur == None:
                    print('插入位置有误')
                    return
            p.next = cur.next
            cur.next = p
    
        def remove(self, index):
            if self.empty():
                print('链表是空的')
                return
            index -= 1
            if index == 0:
                n = self._head
                self._head = self._head.next
                del n
                return
    
            cur = self._head
            for i in range(index - 1):
                cur = cur.next
                if cur == None:
                    print('删除位置有误')
                    return
            n = cur.next
            del n
            cur.next = cur.next.next
    
        def appendLeft(self, value):
            n = Node(value)
            n.next = self._head
            self._head = n
    
        def appendRight(self, value):
            n = Node(value)
            if self._head == None:
                self.head = n
                return
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = n
    
        def search(self, value):
            cur = self._head
            count = 1
            while cur.next != None and cur.data != value:
                cur = cur.next
                count += 1
            if cur.next == None and cur.data != value:
                print('没有该数据')
                return
            print('value:%d,index:%d' % (value, count))
    
        def clear(self):
            cur = self._head
            while cur != None:
                n = cur
                cur = cur.next
                del n
            self._head = None
    
    
    if __name__ == '__main__':
        link = LinkList()

C语言：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        int data;
        struct node* next;
    } Node;
    
    Node* init (Node* head) {//初始化
        head = (Node*)malloc(sizeof(Node));
        head -> next = NULL;
        printf("初始化成功\n");
        return head;
    }
    
    void insert_head (Node* head, int value) {//头插
        Node* p;
        p = (Node*)malloc(sizeof(Node));
        p -> data = value;
    
        p -> next = head -> next;
        head -> next = p;
    }
    
    void insert_tail (Node* head, int value) {//尾插
        Node* cur = head;
        Node* p;
        p = (Node*)malloc(sizeof(Node));
        p -> data = value;
        p->next = NULL;
    
        while (cur -> next != NULL) {
            cur = cur -> next;
        }
        cur -> next = p;
    }
    
    int length (Node* head) {//获取长度
        int length = 0;
        Node* cur = head -> next;
        while (cur != NULL) {
            length++;
            cur = cur -> next;
        }
        return length;
    }
    
    void insert(Node* head, int index, int value) {//插入
        if (index < 0 || index > length(head) + 1) {
            printf("index error!\n");
            return;
        }
        else {
            Node* cur = head;
            for (int i=1; i < index; i++) {
                cur = cur -> next;
            }
            Node* p;
            p = (Node*)malloc(sizeof(Node));
            p -> data = value;
            p -> next = cur -> next;
            cur -> next = p;
        }
    }
    
    void delete_node (Node* head, int index) {//删除节点
        if (index < 0 || index > length(head)) {
            printf("index error!\n");
            return;
        }
        else {
            Node* cur = head;
            Node* del;
            for (int i=1; i < index; i++) {
                cur = cur -> next;
            }
            del = cur -> next;
            cur -> next = cur -> next -> next;
            free(del);
        }
    }
    
    int locate (Node* head, int value) {//元素定位
        Node* cur = head -> next;
        int site = 1;
        while (cur -> data != value) {
            cur = cur -> next;
            site++;
            if (cur == NULL) {
                printf("no value");
                return -1;
            }
        }
        return site;
    }
    
    void getElem (Node* head, int index) {//获取元素
        if (index < 0 || index > length(head)) {
            printf("index error!");
            return;
        }
        else {
            Node* cur = head -> next;
            for (int i=1; i < index; i++) {
                cur = cur -> next;
            }
            printf("%d\n", cur -> data);
        }
    }
    
    bool isEmpty (Node* head) {//判空
        if (head -> next == NULL) {
            return true;
        }
        else {
            return false;
        }
    }
    
    Node* clear (Node* head) {//清空链表
        Node* cur = head -> next;
        Node* prev;
        while (cur != NULL) {
            prev = cur;
            cur = cur -> next;
            free(prev);
        }
        head -> next = NULL;
        printf("清空成功！\n");
        return head;
    }
    
    void print (Node* head) {//打印链表
        Node* cur = head -> next;
        while (cur != NULL) {
            printf("%d ", cur -> data);
            cur = cur -> next;
        }
    }
    
    int main (int argc, char **argv) {
        Node* head;
        head = init(head);
    
        insert_head(head, 3); insert_head(head, 2); insert_head(head, 1);
        print(head); printf("\n");
    
        insert_tail(head, 4); insert_tail(head, 5); insert_tail(head, 6);
        print(head); printf("\n");
    
        insert(head, 7, 0);
        print(head); printf("\n");
    
        delete_node(head, 7); delete_node(head, 1); delete_node(head, 3); delete_node(head, 5);
        print(head); printf("\n");
    
        printf("%d\n", locate(head, 2)); printf("%d\n", locate(head, 5)); printf("%d\n", locate(head, 0));
    
        getElem(head, 3);
    
        printf("%d\n", isEmpty(head));
    
        clear(head);
        printf("%d", isEmpty(head));
        return 0;
    }