首页 > > 网络编程 > 其它 >

python算法与数据结构-单链表(40)

2019-07-24 09:06:54来源：博客园阅读 ()

一、链表

　　链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

　　使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

二、单链表介绍

　　单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

　　链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢，使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。

三、单链表结构

表元素域elem用来存放具体的数据。
链接域next用来存放下一个节点的位置（python中的标识）
变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

四、单链表的常用操作图解

　　1、头插

　　2、尾插

　　3、指定为之插入

　　4、删除

五、单链表的python代码实现

# 创建节点
class Node(object):
    def __init__(self,item):
        self.element = item
        self.next = None

# 创建单链表类
class SingleLinkList(object):
    def __init__(self):
        self.header = None
        self.length = 0
    
    # 1、判断是否为空
    def is_empty(self):
        if self.header == None:
            return True
        else:
            return False
    
    # 2、头部插入
    def add(self,node):
        if self.is_empty():
            self.header = node
        else:
            node.next = self.header
            self.header = node
            # currentNode = self.header
        self.length += 1
    
    # 3、尾部插入
    def appent(self,node):
        currentNode = self.header
        if self.is_empty():
            self.add(node)
        else:
            while (currentNode.next != None):
                currentNode = currentNode.next
            currentNode.next = node
            self.length += 1
        
    # 4、指定位置插入
    def insert(self,node,index):
        currentNode = self.header
        if index>self.length+1 or index<=0:
            print("你要插入的位置不对，请重现选择位置")
            
        if index == 1:
            self.add(node)
        elif index == 2:
            node.next = self.header.next
            self.header.next = node
            self.length += 1
        else:
            for i in range(1,index-1):
                currentNode = currentNode.next
            node.next = currentNode.next
            currentNode.next = node
            self.length += 1
        
    # 5、遍历
    def travel(self):
        currentNode = self.header
        if self.length == 0:
            print("你要遍历的链表没有数据\n")
        else:
            print("你要遍历的链表里面的元素有:",end=" ")
            for i in  range(self.length):
                print("%s "%currentNode.element,end=" ")
                currentNode = currentNode.next
            print("\n")
    
    
    # 6、排序不用交换节点的位置，只需要交换节点上的数据值
    def list_sort(self):
        for i in range(0,self.length-1):
            currentNode = self.header
            for j in range(0,self.length-i-1):
                if  currentNode.element > currentNode.next.element:
                    temp = currentNode.element
                    currentNode.element = currentNode.next.element
                    currentNode.next.element = temp
                    
                currentNode = currentNode.next
            
            
    # 7、按索引删除
    def remove(self,index):
        if index<=0 or index>self.length:
            print("你输入的下标不对，请重新输入")
            return
        else:
            if index == 1:
                self.header = self.header.next
                currentNode = self.header
            elif index == 2:
                currentNode = self.header
                currentNode.next = currentNode.next.next
            else:
                currentNode = self.header
                for i in range(1,index-1):
                    currentNode = currentNode.next
                currentNode.next = currentNode.next.next
        self.length -= 1
    
    # 8、查找是否包含,并返回下标
    def isContain(self,num):
        contain = 0
        currentNode = self.header
        for i in range(self.length):
            if currentNode.element == num:
                print("%d在链表中%d处\n"%(num,i))
                contain = 1
            currentNode = currentNode.next
        
        if contain == 0:
            print("%d不在链表中\n"%num)
        
    
    
    # 9、根据下标找节点
    def searchNodeByIndex(self,index):
        currentNode = self.header
        if index<=0 or index>self.length:
            print("你输入的下标不对，请重新输入\n")
            return 0
        else:
            for i in range(index-1):
                currentNode = currentNode.next
            return currentNode
        
    # 10、根据下标修改节点的值
    def modifyByIndex(self,index,num):
        currentNode = self.header
        if index<=0 or index>self.length:
            print("你输入的下标不对，请重新输入\n")
        else:
            for i in range(index-1):
                currentNode = currentNode.next
            currentNode.element = num
            
def main():
    # 创建一个节点对象
    node1 = Node(1)
    # 创建一个单链表对象
    single_link_list = SingleLinkList()
    
    print("验证空链表的遍历")
    single_link_list.travel()
    
    print("验证头插")
    single_link_list.add(node1)
    single_link_list.travel()
    
    print("验证尾插")
    node2 = Node(2)
    single_link_list.appent(node2)
    single_link_list.travel()
    
    print("验证按位置插入")
    node3 = Node(3)
    single_link_list.insert(node3,1)
    single_link_list.travel()
    
    print("继续验证头插")
    node4 = Node(5)
    single_link_list.add(node4)
    single_link_list.travel()
    
    print("继续验证按位置插入")
    node5 = Node(4)
    single_link_list.insert(node5,4)
    single_link_list.travel()
    
    print("验证删除")
    single_link_list.remove(3)
    single_link_list.travel()
    
    print("验证查找一个节点是否在链表中")
    single_link_list.isContain(8)
    
    print("验证按下标查找节点")
    node = single_link_list.searchNodeByIndex(2)
    print("第二个节点的值为：%s"%node.element)
    
    print("\n验证排序")
    single_link_list.list_sort()
    single_link_list.travel()
    
    print("验证修改")
    single_link_list.modifyByIndex(2,10)
    single_link_list.travel()

if __name__ == '__main__':
    main()

运行结果为：

验证空链表的遍历
你要遍历的链表没有数据

验证头插
你要遍历的链表里面的元素有: 1  

验证尾插
你要遍历的链表里面的元素有: 1  2  

验证按位置插入
你要遍历的链表里面的元素有: 3  1  2  

继续验证头插
你要遍历的链表里面的元素有: 5  3  1  2  

继续验证按位置插入
你要遍历的链表里面的元素有: 5  3  1  4  2  

验证删除
你要遍历的链表里面的元素有: 5  3  4  2  

验证查找一个节点是否在链表中
8不在链表中

验证按下标查找节点
第二个节点的值为：3

验证排序
你要遍历的链表里面的元素有: 2  3  4  5  

验证修改
你要遍历的链表里面的元素有: 2  10  4  5

六、单链表的C语言代码实现

#include <stdio.h>

typedef struct N
{
    int element;
    struct N *next;
}Node;

// 1、创建节点
Node *createNode(int num)
{
    Node *node;
    node = (Node *)malloc(sizeof(Node));
    node->element = num;
    node->next = NULL;
    return node;
}

// 2、创建链表
Node *createSingleLinkList(Node *node)
{
    Node *head = node;
    return head;
}

// 3、获取链表长度
int getlength(Node *head)
{
    if (head == NULL)
    {
        return 0;
    }
    int count = 1;
    Node *current = head;
    
    while (current->next != NULL)
    {
        count++;
        current = current->next;
    }
    return count;
}

// 4、头部插入
Node * add(Node *head, Node *node)
{
    if(head == NULL)
    {
        head = node;
        return head;
    }
    else
    {
        node->next = head;
        head = node;
        return head;
    }
}

// 5、尾部插入
Node * append(Node *head,Node *node)
{
    Node *current = head;
    if (current->next == NULL)
    {
        add(head, node);
    }
    else
    {
        int len = getlength(head);
        for (int i = 0; i<len-1; i++)
        {
            current = current->next;
        }
        current->next = node;
    }
    return head;
}

// 6、按下标插入节点
Node * insert(Node *head,Node *node,int index)
{
    int len = getlength(head);
    
    if (index<=0||index>len+1)
    {
        printf("你要插入的位置不对，请重现选择位置");
    }
    Node *current = head;
    if (index == 1)
    {
       head = add(head, node);
    }
    else if (index == 2)
    {
        node->next = head->next;
        head->next = node;
    }
    else
    {
        for (int i = 1; i<index-1; i++)
        {
            current = current->next;
        }
        node->next = current->next;
        current->next = node;
    }
    return head;
}

// 7、遍历
void travel(Node *head)
{
    int len = getlength(head);
    printf("len = %d\n",len);
    Node *current = head;
    if (len == 0)
    {
        printf("你要遍历的链表没有数据\n");
    }
    else
    {
        printf("你要遍历的链表里面的元素有: ");
        for (int i = 0; i<len; i++)
        {
            printf("%d ",current->element);
            current = current->next;
        }
        printf("\n");
    }
}

// 8、根据索引删除
Node * delect(Node *head,int index)
{
    int len = getlength(head);
    if (index<=0||index>len)
    {
        printf("你输入的下标不对，请重新输入");
        return head;
    }
    else
    {
        if (index == 1)
        {
            head = head->next;
        }
        else if (index == 2)
        {
            head->next = head->next->next;
        }
        else
        {
            Node *current = head;
            for (int i = 1; i<index-1; i++)
            {
                current = current->next;
            }
            current->next = current->next->next;
        }
    }
    return head;
}

// 9、查找是否包含，并返回下标
void isContain(Node *head,int num)
{
    int contain = 0;
    Node *current = head;
    int len = getlength(head);
    for (int i = 0; i<len; i++)
    {
        if (current->element == num)
        {
            printf("%d在链表中的%d处\n",num,i+1);
            contain = 1;
        }
        current = current->next;
    }
    if (contain == 0)
    {
         printf("%d不在链表中\n",num);
    }
}

// 10、根据下标找节点
Node *searchByIndex(Node *head , int index)
{
    int len = getlength(head);
    Node *current = head;
    if (index<=0||index>len)
    {
        printf("你输入的下标不对，请重新输入");
        return head;
    }
    else
    {
        for (int i = 0; i<index-1; i++)
        {
            current = current->next;
        }
        return current;
    }
}

// 11、根据下标修改节点的值
void modifyByIndex(Node *head,int index,int num)
{
    int len = getlength(head);
    Node *current = head;
    if (index<=0||index>len)
    {
        printf("你输入的下标不对，请重新输入");
    }
    else
    {
        for (int i = 0; i<index-1; i++)
        {
            current = current->next;
        }
        current->element = num;
    }
}

int main(int argc, const char * argv[])
{
    printf("==========1、创建节点==========\n");
    Node * node1 = createNode(1);
    printf("==========2、创建单链表==========\n");
    Node * head = createSingleLinkList(node1);
    travel(head);
   
    printf("==========3、验证头插==========\n");
    Node *node2 = createNode(0);
    head = add(head, node2);
    travel(head);
    
    Node *node3 = createNode(2);
    head = add(head, node3);
    travel(head);
    
    printf("==========4、验证尾插==========\n");
    Node *node4 = createNode(4);
    head = append(head,node4);
    travel(head);
    Node *node5 = createNode(5);
    head = append(head,node5);
    travel(head);
    
    printf("==========5、验证按下标插入==========\n");
    Node *node6 = createNode(6);
    head = insert(head, node6, 1);
    travel(head);
    
    printf("==========6、验证按下标删除==========\n");
    head = delect(head, 2);
    travel(head);
    
    printf("==========7、验证是否包含==========\n");
    isContain(head, 8);
    
    printf("==========8、验证根据下标找节点==========\n");
    Node *n = searchByIndex(head, 1);
    printf("第一个节点是%d\n",n->element);
    
    printf("==========9、验证根据下标修改==========\n");
    modifyByIndex(head, 3, 9);
    travel(head);
    
    return 0;
}

运行结果为：

==========1、创建节点==========
==========2、创建单链表==========
len = 1
你要遍历的链表里面的元素有: 1 
==========3、验证头插==========
len = 2
你要遍历的链表里面的元素有: 0 1 
len = 3
你要遍历的链表里面的元素有: 2 0 1 
==========4、验证尾插==========
len = 4
你要遍历的链表里面的元素有: 2 0 1 4 
len = 5
你要遍历的链表里面的元素有: 2 0 1 4 5 
==========5、验证按下标插入==========
len = 6
你要遍历的链表里面的元素有: 6 2 0 1 4 5 
==========6、验证按下标删除==========
len = 5
你要遍历的链表里面的元素有: 6 0 1 4 5 
==========7、验证是否包含==========
8不在链表中
==========8、验证根据下标找节点==========
第一个节点是6
==========9、验证根据下标修改==========
len = 5
你要遍历的链表里面的元素有: 6 0 9 4 5