精华内容
下载资源
问答
  • 双链表和单链表的比较????链表顺序表的优劣 ????双链表简单介绍: 博主在前面介绍了单链表,并实现了它的基本功能,详细请看博客单链表,相信有一点链表基础的同学肯定会知道,单链表的每个节点都有两部分组成那...

    🥇双链表简单介绍:

    博主在前面介绍了单链表,并实现了它的基本功能,详细请看博客单链表,相信有一点链表基础的同学肯定会知道,单链表的每个节点都有两部分组成那就是数据域和指针域,指针域指向下一个节点中数据域的地址。而双链表一个节点中包含三个部分,数值域,指向后继节点的指针,还有指向前驱节点的指针。它在单链表的基础上优化了很多,例如尾插法等就不用了逐个遍历链表节点,直接就可以找到链表的为节点,实现与添加的新节点连接。
    那让我们看看他的庐山真面目吧
    在这里插入图片描述

    🥇双链表基本实现和各种功能实现:

    新建MydoubleLinkedList.java文件在该文件中实现双向链表的所有基础操作
    新建TestDemo。java文件在文件中实现双向链表的测试,测试双向链表的功能

     class Node{
        public int val; //数值域
        public Node next; //后继
        public Node prev; //前驱
        public Node(int val){
            this.val = val;
        }
    }
    public class MydoubleLinkedList {
        //创建头节点
        public Node head;
        //创建尾节点
        public Node tail;
        }
    

    双链表之打印链表:

        public void print(){
            Node cur = this.head;
            while(cur!=null){
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
        }
    

    双链表之求链表长度

      public int size(){
            Node cur = this.head;
            int count = 0;
            while(cur != null){
                count++;
                cur = cur.next;
            }
            return count;
        }
    

    双链表之寻找链表中是否含有某个数字:

        public boolean isContains(int val){
            if(this.head == null){
                return false;
            }
            Node cur = this.head;
            while(cur!=null){
                if(cur.val == val){
                    return true; 
                }
                cur = cur.next;
            }
            return false;
        }
    

    双链表之头插法:
    终于到我要给大家介绍的重点了,前面的三种功能和单链表基本没有区别,没有使用双向链表中的前驱节点。
    💡算法思想:

    1. 第一步还是判断链表是否为空,为空就返回新加节点node
    2. 将新节点插入链表头部,新的头节点就要发生变化,它的后继node.next = this.head;也就是新链表的头节点的后继指针域指向原链表头节点的地址当然原链表头节点的前驱也就变成了新加入的node,即 this.head.prev = node,然后新链表真正的头节点 this.head = node;

    看图说话:
    在这里插入图片描述
    💯代码:

       public Node addFirst(int val){
            Node node = new Node(val);
            if(this.head == null){
                return node;
            }
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
            return head;
        }
    

    双链表之尾插法:
    💡算法思想:

    1. 还是判断链表是否为空,为空就返回新加节点node
    2. 因为在建立链表时,已经规定了尾节点tail,所以在这里不用在链表中从头节点遍历,找到尾节点。我们直接就可以让链表的尾节点tail的后继指针指向新加节点,即this.tail.next = node,还要把新节点的前驱指针指向原链表的尾节点node.prev = this.tail,然后新节点就变成链表中新的尾节点 即 this.tail = node

    看图说话:
    在这里插入图片描述
    💯 代码:

         public Node addLast(int val){
            Node node = new Node(val);
            if(this.head == null){
                return node;
            }
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
            return this.head;
        }
    

    双链表之在链表任意节点添加
    💡算法思想:

    1. 判断传来的数组下标是否合法,如果不合法就返回下标不合法
    2. 如果下标为0,也就是头插法,调用头插法方法就是了
    3. 如果下标为链表的长度,那么就直接调用尾插法就是了
    4. 如果所插节点的下标既不是0也不是和链表等长的下标,那么先遍历到原链表的这个下标让所添加节点的后继指针指向下标这个节点,即node.next = cur,然后让原下标节点的前驱节点的后继指针指向所添加节点,即cur.prev.next = node;然后让所添加节点的前驱指针指向原下标节点的前驱节点,即node.prev = cur.prev;最后让原下标节点的前驱指针指向所添加节点,即cur.prev = node;

    看图说话:
    在这里插入图片描述
    💯 代码:

     public void addNode(int index,int val){
    
            if(index < 0 || index > size()){
                System.out.println("下标不合法!!!");
                return;
            }
            if(index == 0){
                addFirst(val);
                return;
            }
            if(index == size()){
                addLast(val);
                return;
            }
            //如果添加的位置不是下标为0,或者是链表最后一位添加
            //先找到具体下标
            Node node = new Node(val);
            Node cur = findIndex(index);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            node.prev = node;
        }
        public Node findIndex(int index){
            int count = 0;
            Node cur = this.head;
            while(count != index && cur != null){
                count++;
                cur = cur.next;
            }
            return cur;
        }
    

    双向链表之删除第一次出现的的val值
    💡 算法思想:

    1. 在删除节点时,我们不需要像单链表一样从后向前找到链表可删节点的前驱节点。我们只需要找到这个可删节点,让可删节点的前驱节点的后继指针指向可删节点的后继节点,即 node.prev.next = node.next;让可删节点的后继节点的前驱指针指向可删接单的前驱node.next.prev = node.prev;
    2. 当头节点为可删节点,让链表的新头节点向原链表头节点的后继节点,即this.head = this.head.next,还有将新头节点的前驱置为null,即this.head.prev = null
    3. 当链表的尾节点为可删节点,那么就让尾节点的前驱节点的后继指针为null,即this.tail.prev.next = null,也可以写成this.tail.prev.next = this.tail.next,然后指向新的尾节点 this.tail = this.tail.prev

    看图说话:
    在这里插入图片描述
    💯 代码:

         public void remove(int key) {
            Node cur = this.head;
            while (cur != null) {
                if(cur.val == key) {
                    //判断是不是头节点
                    if(cur == this.head) {
                        this.head = this.head.next;
                        if(this.head == null) {//防止只有1个节点的
                            this.tail = null;
                        }else {
                            this.head.prev = null;
                        }
                    }else {
                        cur.prev.next = cur.next;
                        //尾巴节点
                        if(cur.next == null) {
                            this.tail = cur.prev;
                        }else {
                            cur.next.prev = cur.prev;
                        }
                    }
                    return;
                }else {
                    cur = cur.next;
                }
            }
        }
    

    双链表之删除链表中所有的val值

    💡算法思想:

    • 和删除节点一样只是要去掉代码中的return,让代码循环,直到把val值全部删除完。

    💯 代码:

     public void remove(int key) {
            Node cur = this.head;
            while (cur != null) {
                if(cur.val == key) {
                    //判断是不是头节点
                    if(cur == this.head) {
                        this.head = this.head.next;
                        if(this.head == null) {//防止只有1个节点的
                            this.tail = null;
                        }else {
                            this.head.prev = null;
                        }
                    }else {
                        cur.prev.next = cur.next;
                        //尾巴节点
                        if(cur.next == null) {
                            this.tail = cur.prev;
                        }else {
                            cur.next.prev = cur.prev;
                        }
                    }
                    return;
                }else {
                    cur = cur.next;
                }
            }
        }
    

    🥇 双链表和单链表的比较

    • 双链表和单链表比较,虽然双链表添加了一个前驱指针域,但是他在实现某些功能时,是真的比单链表方便,比如我们要删除节点就不需要遍历可删节点的前驱节点,就少了一步遍历链表的步骤,还有双向链表可以双向遍历,单链表只可以从头节点依次遍历到链表的尾节点,为实现功能带来诸多不便。

    🥇链表和顺序表的优劣

    和数组相比,链表更适合储存一个大小动态变化的数据集,如果需要在一个数据集中频繁的添加新的数据并且不需要考虑数据集的顺序,那么可以用链表来实现这个数据集,链表中的插入操作可以用O(1)的时间来实现,其次链表的删除操作也可以用O(1)的时间来实现,所以是当要实现某些数据集的插入或删除时,可以考虑链表使用,当时在查找时链表又有了弊端,他只能从链表的头节点遍历到链表的尾节点找到要查找的数值,时间复杂度为O(n).

    和链表相比,数组在读取数值时,用着很大的优势,可以凭借数组下标来读取数组中的每个数字,但是要实现添加数字,和删除数字时,要移动大量的数值,并且时间复杂度为O(n),还有在创建数组时,要预先指定数组的容量大小,然后根据容量的大小分配内存,即使只在数组中存储一个数字,也需要为所有的数据预先分配内存,依次数组的空间利用率不高,可能会有空闲的空间没有得到充分使用,并且当数组容量不够时,需要重新分配一个较大的空间,通常增加后的数组容量时原来的两倍。每次扩充数组容量时,都会有大量操作,这是时间性能有负面影响。

    展开全文
  • 数据结构与算法单链表 双链表创建单链表单链表的基本操作链表的插入链表的删除链表的查找链表的更新元素完整的代码双向循环链表双向链表的结构双向链表的操作 单链表 双链表 创建单链表 struct Link{ int elem; //...

    单链表 双链表

    创建单链表

    struct Link{
      int elem; //数据域
      struct Link *next;//指向下一个节点的指针域
    }
    

    不带头的单链表:

    第一个保存数据的节点 : 首元节点

    指向第一个数据的指针: 头指针

    //创建不带头的单链表
    #include<stdio.h>
    #include<stdlib.h>
    //1.声明一个头指针
    //2.创建多个存储数据的节点,时刻保持指向关系
    typedef struct Link{
        int elem; //数据域
        struct Link *next;//指针域
    }link;
    
    link *initLink(){
        link *p=NULL; //头指针
        link *temp = (link *)malloc(sizeof(link));
        temp->elem =1;
        temp->next = NULL;
        p = temp;
        for(int i=2;i<5;i++){
            link *a = (link *)malloc(sizeof(link));
            a->elem =i;
            a->next =NULL;
            temp->next =a;
            temp = temp->next; //后移
        }
        return p;
    }
    void display(link *p){
        link *temp = p;
        while(temp){
            printf("%d",temp->elem;
            temp = temp->next;
        }
        printf("\n");
    }
    
    

    带头的单链表:

    第一个不保存数据的节点:头节点

    //创建带头的单链表
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Link{
        int elem;
        struct Link *next;
    }link;
    
    link *initLink(){
        link *temp= NULL;
        link *p = (link *)malloc(sizeof(link));
        p->next =NULL;
        p->elem = NULL;
        temp->p;
        for(int i=1;i<5;i++){
            link *a =(link *)malloc(sizeof(link));
            a->elem = i;
            a->next = NULL;
            temp->next = a;
            temp = temp->next;
        }
        return p;
    }
    
    void display(link *p){
        link *temp = p;
        while(temp->next){
            temp = temp->next;
            printf("%d ",temp->elem;
        }
        printf("\n");
    }
    int main(){
       link *p = initLink();
        display(p);
    }
    

    单链表的基本操作

    以不带头的单链表为例

    链表的插入

    1.链表的插入:头插、尾插、中间插

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Link{
        int elem;
        struct Link *next;
    }link;
    
    link *initLink(){
        link *p=NULL; //头指针
        link *temp = (link *)malloc(sizeof(link));
        temp->elem =1;
        temp->next = NULL;
        p = temp;
        for(int i=2;i<5;i++){
            link *a = (link *)malloc(sizeof(link));
            a->elem =i;
            a->next =NULL;
            temp->next =a;
            temp = temp->next; //后移
        }
        return p;
    }
    // int add 添加的新元素的位置  int elem  插入元素
    link *insertElem(link *p,int elem,int add){
        link *temp =p;
        //移动指针 到插入位置的上一个节点
       
        for(int i=1;i<add;i++){
            temp = temp->next;
            if(temp == NULL){
                printf("位置不合法");
                return p;
            }
        }
        link *a =(link *)malloc(sizeof(link));
        a->elem = elem;
        if(add == 1){
        	a->next = temp;
        	p = a;
    	}else{
    	    a->next = temp->next;		 
            temp->next = a;
    	}
        return p;
    }
    void display(link *p){
        link *temp = p;
        while(temp){
            printf("%d  ",temp->elem);
            temp = temp->next;
        }
        printf("\n");
    }
    
    int main(){
        link *p =initLink();
        //display(p);
        link *p1 = insertElem(p,50,1);
        display(p1);
    }
    
    
    

    链表的删除

    1.将该节点摘下来,让该节点的前一个节点的指针域指向该节点的下一个节点;
    2.将摘下来的节点释放掉(free())
    
    link *delLink(link *p,int del){
        link *temp =p;
        //移动到要删除元素的前一个节点
        for(int i=0; i<del-1;i++){
            temp = temp->next;
            if(temp->next ==NULL){
                printf("指针移动到了最后一个节点!");
                return p;
            }
        }
        link *a = temp->next;
        temp->next = temp->next->next;
        free(del);
        return p;
    }
    int main(){
        link *p =initLink();
        display(p);
        link *p2 = delLink(p,3);
        display(p2);
    }
    

    链表的查找

    int selectElem(link *p ,int elem){
       link *temp =p;
       int i=1;
       while(temp->next!=NUll){
         if(temp->elem = elem){
         return i;
         }
         temp = temp->next;
         i++;
       }
       return 0;
    }
    

    链表的更新元素

    
    // 知道位置更新元素
    link *updateLink(link *p,int newElem,int add){
        link *temp =p;
        for(int i = 1;i < add;i++){
            temp = temp->next;
            if(temp->next ==NULL){
                printf("位置不合法");
            }
        }
        temp->elem = newElem;
        return p;
    }
    
    
    
    //不知道位置更新元素,将oldElem旧元素更新为newElem新元素
    link *update(link *p,int newElem,int oldElem){
        link *temp = p;
        int add = selectElem(p,oldElem);
        for(int i = 1;i < add;i++){
            temp = temp->next;
            if(temp->next ==NULL){
                printf("位置不合法");
            }
        }
        temp->elem = newElem;
        return p;
    }
    

    完整的代码

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct Link{
        int elem;
        struct Link *next;
    }link;
    
    link *initLink(){
        link *p=NULL; //头指针
        link *temp = (link *)malloc(sizeof(link));
        temp->elem =1;
        temp->next = NULL;
        p = temp;
        for(int i=2;i<5;i++){
            link *a = (link *)malloc(sizeof(link));
            a->elem =i;
            a->next =NULL;
            temp->next =a;
            temp = temp->next; //后移
        }
        return p;
    }
    // int add 添加的新元素的位置  int elem  插入元素
    link *insertElem(link *p,int elem,int add){
        link *temp =p;
        //移动指针 到插入位置的上一个节点
        for(int i=1;i<add-1;i++){
            temp = temp->next;
            if(temp == NULL){
                printf("位置不合法1");
                return p;
            }
        }
        link *a =(link *)malloc(sizeof(link));
        a->elem = elem;
        a->next = temp->next;
        temp->next = a;
        return p;
    }
    void display(link *p){
        link *temp = p;
        while(temp){
            printf("%d",temp->elem);
            temp = temp->next;
        }
        printf("\n");
    }
    //删除
    link *delLink(link *p,int del){
        link *temp =p;
        //移动到要删除元素的前一个节点
        for(int i=0; i<del-1;i++){
            temp = temp->next;
            if(temp->next ==NULL){
                printf("指针移动到了最后一个节点!");
                return p;
            }
        }
        link *a = temp->next;
        temp->next = temp->next->next;
        free(del);
        return p;
    }
    //查找
    // 知道位置更新元素
    link *updateLink(link *p,int newElem,int add){
        link *temp =p;
        for(int i = 1;i < add;i++){
            temp = temp->next;
            if(temp->next ==NULL){
                printf("位置不合法");
            }
        }
        temp->elem = newElem;
        return p;
    }
    //不知道位置更新元素,将oldElem旧元素更新为newElem新元素
    link *update(link *p,int newElem,int oldElem){
        link *temp = p;
        int add = selectElem(p,oldElem);
        for(int i = 1;i < add;i++){
            temp = temp->next;
            if(temp->next ==NULL){
                printf("位置不合法");
            }
        }
        temp->elem = newElem;
        return p;
    }
    //主函数
    int main(){
        link *p =initLink();
        display(p);
        link *p1 = insertElem(p,3,50);
        display(p1);
    }
    

    双向循环链表

    双向链表的结构

    typedef struct doubleList{
     int data;//数据域
     struct doubleList *prev;
     struct doubleList *next;
    }doubleList;
    

    双向链表的操作

    #includ<stdio.h>
    #include<stdlib.h>
    typedef struct doubleList{
     int data;//数据域
     struct doubleList *prev;
     struct doubleList *next;
    }doubleList;
    //创建链表的函数
    doubleList *createList(){
      doubleList *head,*p,*q;
      int n,x;
        //创建头节点
        head =(doubleList *) malloc(sizeof(doubleList));
        head->prev = head;
        head->next = head;
        p = head;
        printf("输入元素的个数");
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            printf("请输入第%d个元素",(i+1));
            scanf("%d",&x);
            q =(doubleList *) malloc(sizeof(doubleList));
            q->data = x;
            p->next = q;
            head->prev =q; //头节点的上一个指向最后一个
            q->prev = p;
            q->next = head;//最后一个的下一个指向第一个
            p = q;
        }
        return head;
    }
    //遍历链表
    void display(doubleList *head){
        doubleList *temp = head;
        temp = temp->next;
        while(temp!= head){
            printf("%d",temp->next);
            temp = temp->next;
        }
        printf("\n");
    }
    //统计元素个数
    int lengthList(doubleList *head){
      doubleList *temp = head;
        int count =0;
        temp = temp->next;
        while(temp!= head){
            count++;
            temp = temp->next;
        }
        return count;
    }
    //插入数据 
    //在第i个元素之前插入数据data
    doubleList *insertList(doubleList *head,int i,int newData){
        doubleList *temp = head;
        doubleLIst *q;
        temp = temp->next;
        i--;
        while(i--){
            temp = temp->next;
        }
         q =(doubleList *) malloc(sizeof(doubleList));
         q->data = newDate;
         p->prev->next =q;
         q->prev = p->prev;
         q->next = p;
         p->next = q;
         return head;
    }
     //删除第i个位置的元素
    void delList(doubleList *head,int i){
        doubleList *temp = head;
        temp = temp->next;
        i--;
        while(i--){
            temp = temp->next;
        }
        temp->prev->temp = temp->next;
        temp->next->prev = temp->prev;
        free(temp);
    }
    //删除值为x的元素
    void delList_x(doubleList *head,int i){
        doubleList *temp = head;
        doubleList *q;
        temp = temp->next;
        while(temp!=head){
            if(temp->data == x){
                q = temp->next;
                temp->prev->temp = temp->next;
                temp->next->prev = temp->prev;
                free(temp);
                temp = q;
            }else{
                temp = temp->next;
            }
        }
    }
    //排序
    void sortList(doubleList *head){
        doubleList *temp = head;
        doubleList *p;
        temp = temp->next;
        for(;temp!=head;temp=temp->next){
            for(p=temp->next;p!=head;p=p->next){
                if(temp->data < p->data){
                    int a = temp->data;
                    temp->data = p->data;
                    p->data = a;
                }
            }
        } 
    }
    int main(){
        doubleList *head = createList();
        display(head);
        //查找
        int len = lengthList(head);
        printf("%d",len);
        //添加
        head = insertList(head,3,100);
        display(head);
        //删除第i个元素
        delList(head,3);
        display(head);
        //删除x的元素
        delList_x(head,4);
        display(head);
        //排序
        sortList(head);
    }
    
    展开全文
  • 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。 表元素域elem用来存放...

    1 单链表

    单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
    ![在这里插入GLKg==,size_20,color_FFFFFF,t_70,g_se,x_16)

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

    节点实现

    class SingleNode(object):
        """单链表的结点"""
        def __init__(self,item):
            # _item存放数据元素
            self.item = item
            # _next是下一个节点的标识
            self.next = None

    单链表操作

    is_empty() 链表是否为空
    length() 链表长度
    travel() 遍历整个链表
    add(item) 链表头部添加元素
    append(item) 链表尾部添加元素
    insert(pos, item) 指定位置添加元素
    remove(item) 删除节点
    search(item) 查找节点是否存在

    单链表实现

    class SingleLinkList(object):
        #单链表
        def __init__(self,node=None):
            #初始时候头指向为空,也就是先生成一个空的链表
            self.__head=node
    
        def is_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.elem,end=" ")
                cur=cur.next
            print('')
    
        def add(self,item):
            #头部插入
            node=SingleNode(item)
            #方法一:头后插入
            if self.is_empty():
                self.__head=node
            else:
                p=self.__head
                self.__head=node
                node.next=p
    
            # #方法二:重置头
            # node.next=self.__head
            # self.__head=node
    
        def insert(self,pos,item):
            #指定位置插入   pos从零开始索引
            node = SingleNode(item)
            if pos<=0:
                self.add(item)
            elif pos > self.length():
                self.append(item)
            else:
                pre = self.__head
                count = 0
                while count<(pos-1):#当循环退出后,指向pos-1位置
                    count += 1
                    pre = pre.next
                node.next=pre.next
                pre.next = node
    
        def append(self,item):
            #尾端加入
            node=SingleNode(item)
            if self.is_empty():
                self.__head=node
            else:
                cur=self.__head
                while cur.next != None:
                    cur=cur.next
                cur.next=node
    
        def remove(self,item):
            cur = self.__head
            pre=None
            while cur != None:
                if cur.elem == item:
                    #先判断是否事头节点
                    if cur == self.__head:
                        self.__head=cur.next
                    else:
                        pre.next=cur.next
                    break
                else:
                    pre = cur
                    cur = cur.next
    
        def search(self,item):
            #查找
            cur=self.__head
            while cur!=None:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            return False

    测试

    在这里插入图片描述

    链表与顺序表对比

    链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。链表与顺序表的各种操作复杂度如下所示:
    在这里插入图片描述
    注意虽然表面看起来复杂度都是 O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。顺序表查找很快,主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行。

    2 单向循环链表

    单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。
    在这里插入图片描述

    操作

    is_empty() 判断链表是否为空
    length() 返回链表的长度
    travel() 遍历
    add(item) 在头部添加一个节点
    append(item) 在尾部添加一个节点
    insert(pos, item) 在指定位置pos添加节点
    remove(item) 删除一个节点
    search(item) 查找节点是否存在

    实现

    class Node(object):
        #节点
        def __init__(self,elem):
            self.elem=elem
            self.next=None
    
    class SingleCycleLinkList(object):
        #单项循环列表
        def __init__(self,node=None):
            #初始时候头指向为空,也就是先生成一个空的链表
            self.__head=node
            if node:
                node.next=node
    
        def is_empty(self):
            #判断是否为空
            return self.__head==None
    
        def length(self):
            #输出链表的长度
            if self.is_empty():
                return 0
            #定义一个指针进行遍历
            cur=self.__head
            count=1
            while cur.next!=self.__head:
                count+=1
                cur=cur.next
            return count
    
        def travel(self):
            #遍历整个链表
            if self.is_empty():
                return
            cur=self.__head
            while cur.next!=self.__head:
                print(cur.elem,end=" ")
                cur=cur.next
            #退出循环,cur指向尾节点,但尾节点的元素未打印
            print(cur.elem)
    
        def add(self,item):
            #头部插入
            node=Node(item)
            if self.is_empty():
                self.__head=node
                node.next=node
            else:
                cur = self.__head
                while cur.next != self.__head:
                    cur = cur.next
                # 退出循环,cur指向尾节点,
                node.next=self.__head
                cur.next=node
                self.__head=node
    
        def insert(self,pos,item):
            #指定位置插入   pos从零开始索引
            node = Node(item)
            if pos<=0:
                self.add(item)
            elif pos > self.length():
                self.append(item)
            else:
                pre = self.__head
                count = 0
                while count<(pos-1):#当循环退出后,指向pos-1位置
                    count += 1
                    pre = pre.next
                node.next=pre.next
                pre.next = node
    
        def append(self,item):
            #尾端加入
            node=Node(item)
            if self.is_empty():
                self.__head=node
                node.next=node
            else:
                cur=self.__head
                while cur.next !=self.__head:
                    cur=cur.next
                cur.next=node
                node.next=self.__head
    
        def remove(self,item):
            #删除节点
            if self.is_empty():
                return
            cur = self.__head
            pre=None
            while cur.next != self.__head:
                if cur.elem == item:
                    #先判断是否事头节点
                    if cur == self.__head:
                        #头节点的情况
                        #先找的尾节点
                        rear=self.__head
                        while rear.next!=self.__head:
                            rear=rear.next
                        self.__head=cur.next
                        rear.next=self.__head
                    else:
                        #中间节点
                        pre.next=cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # 退出循环,cur指向尾节点
            if cur.elem==item:
                if cur==self.__head:
                    #链表只有一个节点
                    self.__head=None
                pre.next = cur.next
    
        def search(self,item):
            #查找
            if self.is_empty():
                return False
            cur=self.__head
            while cur.next!=self.__head:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            if cur.elem == item:
                return True
            return False

    测试

    在这里插入图片描述

    3 双向链表

    每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
    在这里插入图片描述

    操作

    is_empty() 链表是否为空
    length() 链表长度
    travel() 遍历链表
    add(item) 链表头部添加
    append(item) 链表尾部添加
    insert(pos, item) 指定位置添加
    remove(item) 删除节点
    search(item) 查找节点是否存在

    实现

    class Node(object):
        #节点
        def __init__(self,item):
            self.elem=item
            self.next=None
            self.prev=None
    
    class DoubleLinkList(object):
        #双链表
        def __init__(self,node=None):
            #初始时候头指向为空,也就是先生成一个空的链表
            self.__head=node
    
        def is_empty(self):
            #判断是否为空
            return self.__head is 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.elem,end=" ")
                cur=cur.next
            print('')
    
        def add(self,item):
            #头部插入
            node=Node(item)
            node.next=self.__head
            self.__head=node
            node.next.prev=node
    
            # node.next=self.__head
            # self.__head.prev=node
            # self.__head=node
    
    
        def insert(self,pos,item):
            #指定位置插入   pos从零开始索引
            node = Node(item)
            if pos<=0:
                self.add(item)
            elif pos > self.length():
                self.append(item)
            else:
                cur=self.__head
                count = 0
                while count<pos:
                    count += 1
                    cur = cur.next
                #当循环退出后,cur就是指向pos这个位置
                node.next=cur
                node.prev=cur.prev
                cur.prev.next=node
                cur.prev=node
    
    
        def append(self,item):
            #尾端加入
            node=Node(item)
            if self.is_empty():
                self.__head=node
            else:
                cur=self.__head
                while cur.next != None:
                    cur=cur.next
                cur.next=node
                node.prev=cur
    
        def remove(self,item):
            cur = self.__head
            while cur != None:
                if cur.elem == item:
                    #先判断是否事头节点
                    if cur == self.__head:
                        self.__head=cur.next
                        #判断链表是否只有一个节点
                        if cur.next:
                            cur.next.prev=None
                    else:
                        cur.prev.next=cur.next
                        if cur.next:
                            cur.next.prev=cur.prev
                    break
                else:
                    cur = cur.next
    
        def search(self,item):
            #查找
            cur=self.__head
            while cur!=None:
                if cur.elem==item:
                    return True
                else:
                    cur=cur.next
            return False
    

    测试

    在这里插入图片描述

    展开全文
  • 单链表的存储结构: typedef struct LNode{ int data; struct LNode *next;//指向下一个节点 }LNode,*LinkList; 所需调用的函数: void createList(LinkList &T);//初始化 void addList(LinkList &T,int ...

    C语言-单链表和双向链表
    一、单链表
    单链表的存储结构:

    typedef struct LNode{
    	int data;
    	struct LNode *next;//指向下一个节点
    }LNode,*LinkList;
    

    定义的函数:

    void createList(LinkList &T);//初始化
    void addList(LinkList &T,int key);//添加
    void deleteList(LinkList &T,int loc);//删除
    void insertList(LinkList &T,int loc,int key);//插入
    void reverseList(LinkList &T);//倒置
    void printList(LinkList &T);//打印
    

    以下是具体代码:

    void createList(LinkList &T){//初始化
    	T = (LNode *)malloc(sizeof(LNode));
    	T->next = NULL;
    }
    
    void addList(LinkList &T,int key){//插入
    	LNode *p,*s;
    	p = T;
    	while(p->next!=NULL){
    		p = p->next;
    	}
    	s = (LNode *)malloc(sizeof(LNode));
    	s->data = key;
    	p->next = s;
    	s->next = NULL;
    }
    
    void deleteList(LinkList &T,int loc){//删除
    	LNode *p;
    	p = T;
    	for(int i = 1;i < loc;i++){
    		p = p->next;
    	}
    	p->next = p->next->next;
    }
    
    void insertList(LinkList &T,int loc,int key){//插入
    	LNode *p,*s;
    	p = T;
    	for(int i = 1;i < loc;i++){
    		p = p->next;
    	}
    	s = (LNode *)malloc(sizeof(LNode));
    	s->data = key;
    	s->next = p->next;
    	p->next = s; 
    }
    
    void reverseList(LinkList &T){//倒置
    	LNode *p,*re,*s;
    	re = (LNode *)malloc(sizeof(LNode));
    	re->next = NULL;
    	p = T->next;
    	while(p!=NULL){
    		s = (LNode *)malloc(sizeof(LNode));
    		s->data = p->data;
    	    s->next = re->next;
    		re->next = s;
    		p = p->next;	
    	}
    	T = re;
    }
    
    void printList(LinkList &T){//打印
    	LNode *p;
    	p = T->next;
    	printf("\n当前单链表为:");
    	while(p!=NULL){
    		printf("%d ",p->data);
    		p = p->next; 
    	}
    }
    

    以下是完整代码:

    #include<stdlib.h>
    #include<stdio.h>
    typedef struct LNode{
    	int data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    void createList(LinkList &T);
    void addList(LinkList &T,int key);
    void deleteList(LinkList &T,int loc);
    void insertList(LinkList &T,int loc,int key);
    void reverseList(LinkList &T);
    void printList(LinkList &T);
    
    void createList(LinkList &T){
    	T = (LNode *)malloc(sizeof(LNode));
    	T->next = NULL;
    }
    
    void addList(LinkList &T,int key){
    	LNode *p,*s;
    	p = T;
    	while(p->next!=NULL){
    		p = p->next;
    	}
    	s = (LNode *)malloc(sizeof(LNode));
    	s->data = key;
    	p->next = s;
    	s->next = NULL;
    }
    
    void deleteList(LinkList &T,int loc){
    	LNode *p;
    	p = T;
    	for(int i = 1;i < loc;i++){
    		p = p->next;
    	}
    	p->next = p->next->next;
    }
    
    void insertList(LinkList &T,int loc,int key){
    	LNode *p,*s;
    	p = T;
    	for(int i = 1;i < loc;i++){
    		p = p->next;
    	}
    	s = (LNode *)malloc(sizeof(LNode));
    	s->data = key;
    	s->next = p->next;
    	p->next = s; 
    }
    
    void reverseList(LinkList &T){
    	LNode *p,*re,*s;
    	re = (LNode *)malloc(sizeof(LNode));
    	re->next = NULL;
    	p = T->next;
    	while(p!=NULL){
    		s = (LNode *)malloc(sizeof(LNode));
    		s->data = p->data;
    	    s->next = re->next;
    		re->next = s;
    		p = p->next;	
    	}
    	T = re;
    }
    
    void printList(LinkList &T){
    	LNode *p;
    	p = T->next;
    	printf("\n当前单链表为:");
    	while(p!=NULL){
    		printf("%d ",p->data);
    		p = p->next; 
    	}
    }
    int main(){
    	LinkList T;
    	createList(T);
    	int num,i,key,loc;
    	printf("请输入插入个数:");
    	scanf("%d",&num);
    	for(i = 1;i <= num;i++){
    		printf("第%d个:",i);
    		scanf("%d",&key);
    		addList(T,key);
    	} 
    	printList(T);
    	printf("\n请输入删除位置:");
    	scanf("%d",&loc);
    	deleteList(T,loc);
    	printList(T);
    	printf("\n请输入插入位置和元素:");
    	scanf("%d %d",&loc,&key);
    	insertList(T,loc,key);
    	printList(T);
    	reverseList(T);
    	printf("\n转置");
    	printList(T);
    	return 0;
    }
    

    二、双链表
    双链表的存储结构:

    typedef struct DulNode{
    	int data;
    	struct DulNode *prior,*next;//两个分别指向前结点和后结点的指针
    }DulNode,*DulList; 
    

    定义的函数:

    void createDul(DulList &T);//初始化
    void addDul(DulList &T,int key);//添加
    void deleteDul(DulList &T,int loc);//删除
    void exchangeDul(DulList &T,int loc1,int loc2);//交换
    void insertDul(DulList &T,int loc,int key);//插入
    void printDul(DulList &T);//打印
    int eqhuiwen(DulList &T);//判断是否为回文
    

    以下是具体代码:

    void createDul(DulList &T){
    	T = (DulNode*)malloc(sizeof(DulNode)); 
    	T->next = NULL;
    	T->prior = NULL;
    }
    
    void addDul(DulList &T,int key){
    	DulNode *p,*s;
    	s = (DulNode *)malloc(sizeof(DulNode));
    	s->data = key;
    	for(p = T;p->next!=NULL;p=p->next){
    	}
    	p->next = s;
    	s->prior = p;
    	s->next = NULL;
    }
    
    void deleteDul(DulList &T,int loc){
    	DulNode *p;
    	int i;
    	p = T;
    	for(i = 1;i <= loc;i++){
    		p = p->next;
    	}
    	p->prior->next = p->next;
    	p->next->prior = p->prior;
    	free(p);
    }
    
    void exchangeDul(DulList &T,int loc1,int loc2){
    	DulNode *p1,*p2;
    	int i,temp;
    	p1 = p2 = T;
    	for(i = 1;i <= loc1 || i <= loc2;i++){
    		if(i <= loc1){
    			p1 = p1->next;
    		}
    		if(i <= loc2){
    			p2 = p2->next;
    		} 
    	}
    	temp = p1->data;
    	p1->data = p2->data;
    	p2->data = temp;
    }
    
    void insertDul(DulList &T,int loc,int key){
        DulNode *p,*s;
        int i;
    	p = T;
    	for(i = 1;i < loc;i++){
    		p = p->next;
    	}	
    	s = (DulNode *)malloc(sizeof(DulNode));
    	s->data = key;
    	s->next = p->next;
    	p->next->prior = s;
    	p->next = s;
    	s->prior = p;
    }
    
    void printDul(DulList &T){
    	DulNode *p;
    	printf("\n当前双链表为:");
    	for(p = T->next;p!=NULL;p = p->next){
    		printf("%d ",p->data);
    	}
    }
    
    int eqhuiwen(DulList &T){
    	DulNode *p1,*p2;
    	p1 = T->next;
    	p2 = T;
    	while(p2->next!=NULL){
    		p2 = p2->next;
    	}
    	while(p2->prior!=p1){
    		if(p1->data!=p2->data){
    			return 0;
    		}
    		p1 = p1->next;
    		p2 = p2->prior;
    	}
    	return 1;
    }
    

    以下为完整代码:

    #include<stdlib.h>
    #include<stdio.h>
    typedef struct DulNode{
    	int data;
    	struct DulNode *prior,*next;
    }DulNode,*DulList; 
    
    void createDul(DulList &T);
    void addDul(DulList &T,int key);
    void deleteDul(DulList &T,int loc);
    void exchangeDul(DulList &T,int loc1,int loc2);
    void insertDul(DulList &T,int loc,int key);
    void printDul(DulList &T);
    int eqhuiwen(DulList &T);
    
    void createDul(DulList &T){
    	T = (DulNode*)malloc(sizeof(DulNode)); 
    	T->next = NULL;
    	T->prior = NULL;
    }
    void addDul(DulList &T,int key){
    	DulNode *p,*s;
    	s = (DulNode *)malloc(sizeof(DulNode));
    	s->data = key;
    	for(p = T;p->next!=NULL;p=p->next){
    	}
    	p->next = s;
    	s->prior = p;
    	s->next = NULL;
    }
    void deleteDul(DulList &T,int loc){
    	DulNode *p;
    	int i;
    	p = T;
    	for(i = 1;i <= loc;i++){
    		p = p->next;
    	}
    	p->prior->next = p->next;
    	p->next->prior = p->prior;
    	free(p);
    }
    void exchangeDul(DulList &T,int loc1,int loc2){
    	DulNode *p1,*p2;
    	int i,temp;
    	p1 = p2 = T;
    	for(i = 1;i <= loc1 || i <= loc2;i++){
    		if(i <= loc1){
    			p1 = p1->next;
    		}
    		if(i <= loc2){
    			p2 = p2->next;
    		} 
    	}
    	temp = p1->data;
    	p1->data = p2->data;
    	p2->data = temp;
    }
    
    void insertDul(DulList &T,int loc,int key){
        DulNode *p,*s;
        int i;
    	p = T;
    	for(i = 1;i < loc;i++){
    		p = p->next;
    	}	
    	s = (DulNode *)malloc(sizeof(DulNode));
    	s->data = key;
    	s->next = p->next;
    	p->next->prior = s;
    	p->next = s;
    	s->prior = p;
    }
    
    void printDul(DulList &T){
    	DulNode *p;
    	printf("\n当前双链表为:");
    	for(p = T->next;p!=NULL;p = p->next){
    		printf("%d ",p->data);
    	}
    }
    
    int eqhuiwen(DulList &T){
    	DulNode *p1,*p2;
    	p1 = T->next;
    	p2 = T;
    	while(p2->next!=NULL){
    		p2 = p2->next;
    	}
    	while(p2->prior!=p1){
    		if(p1->data!=p2->data){
    			return 0;
    		}
    		p1 = p1->next;
    		p2 = p2->prior;
    	}
    	return 1;
    }
    
    int main(){
    	DulList T;
    	int num,i,key,loc,loc1;
    	createDul(T);
    	printf("请输入插入个数:");
    	scanf("%d",&num);
    	for(i = 1;i <= num;i++){
    		printf("第%d个:",i);
    		scanf("%d",&key);
    		addDul(T,key);
    	} 
    	printDul(T);
        printf("\n请输入要删除的数位置:");
    	scanf("%d",&loc);
    	deleteDul(T,loc);
    	printDul(T);
    	printf("\n请输入要交换的数位置:");
        scanf("%d %d",&loc,&loc1);
        exchangeDul(T,loc,loc1);
        printDul(T);
        printf("\n请输入要插入的位置和元素:");
        scanf("%d %d",&loc,&key);
        insertDul(T,loc,key);
        printDul(T);
        printf("\n是否为回文?");
        if(eqhuiwen(T)){
        	printf("是");
    	}
    	else{
    		printf("否");
    	}
    	return 0;
    }
    
    
    展开全文
  • 目录申明 申明   本文章属于原创,其中参考了程杰老师《大话数据结构》行文结构内容,侵删。
  • 2.双链表:(Douuble Linked List) 在单链表基础之上,还有一个prev指针指向前一个节点。 3.小结: (1)链表是以节点的方式来存储 (2)每个节点包含data域,next域:指向下一个节点 (3)链表的每个节点都...
  • C/C++ code//将c:\\tmp文件夹下的所有文件的内容全部放到用malloc分配的内存中#include #include #include #include struct FB {char fn[256];size_t fl;char *b;struct FB *next;struct FB *prev;...
  • 1.链表 链表是线性表的一种,由一系列节点(结点)组成,每个节点包含一个数据域一个指向下一个节点的...2.单向链表单链表) 单向链表,它包含两个域,一个信息域一个指针域。这个链接指向表中的下一个节点,而
  • 简单理解单链表双链表、循环单链表、循环双链表 单链表只有后继指针 ...双链表有后继指针前驱指针 循环单链表尾指针指向了头指针 循环双链表头结点的前驱指针指向了尾结点,尾结点的后继指针指向了头结点 ...
  • 单向链表和双向链表分析与操作

    万次阅读 2021-03-15 16:03:40
    单链表和双链表 链表结构: 优点: 1、在程序中使用数组之前,必须事先知道数组的大小,增加数组的大小是一个耗时的过程,在运行时几乎不可能扩展数组的大小。而链表不需要提前声明链表的大小,链表的大小是随着使用...
  • 单链表 1.1 插入 实现在aiai+1中间插入e(固定套路): e —> ai+1 ai—> e e.next = ai.next; ai.next = e; 1.2 删除节点 实现ai的删除: ai-1.next = ai-1.next.next; 二 双向链表 注意:此时理解...
  • 循环链表(循环单链表和双链表

    千次阅读 2021-02-04 13:52:36
    循环链表前言一、循环单链表的初始化二、判断是否为空或表尾结点三、循环双链表的初始化四、循环双链表的插入与删除 前言 对于循环单链表而言,在进行插入删除时,可以让指针指向尾部,对于表头(通过尾部找到头部...
  • 链表的算法实现有两种方式:动态链表和静态链表。首先回顾下动态链表: 在学习数据结构时,我们常用结构体指针实现动态链表: struct Node{ int val; // value Node *next; // 指向下一个结点的指针 } 动态链表...
  • 前言单向链表和双向链表的优缺点及使用场景双向链表的简单实现及图示分析 前言 之前写了一些文章简单地介绍顺序表,链表的基础知识,还总结了几道链表的笔试题,今天继续开干,向老铁们简单地介绍一下无头双向循环...
  • (以下源码均属于jdk1.8.0_101)单向链表只有后一节点指针,在节点删除,移动的时候,需要暂存前一节点,删除的时候将前一节点后一节点连接,因为比双向链表少维护一个前节点,只在删除的时候暂存,所以比单向链表...
  • 单链表和双链表都是链表的实现,其中单链表的每个元素都包含一些数据以及到下一个元素的链接,从而可以保持结构。另一方面,双向链接列表中的每个节点也包含指向前一个节点的链接。以下是单链接列表和双链接列表之间...
  • 链表 单链表 每个结点中只含有一个指针域 单链表的存储结构: typedef struct LNode{ ElemType data;//数据域 struct LNode *next;//指针域 } 单链表可以包含头结点,也可以直接在头部装入第一个元素。 即,所有...
  • 单向链表:只有一个指向下一个节点的指针。 优点:单向链表增加删除节点...优点:可以找到前驱后继,可进可退; 缺点:增加删除节点复杂,需要多分配一个指针存储空间。 适用于需要双向查找节点值的情况。 ...
  • 文章目录带头结点的双向循环链表和单链表的区别面试题:写一个双向链表代码实现 带头结点的双向循环链表和单链表的区别   相比我们讲的无头单向非循环的单链表结构,他的插入删除都是O(1),也不需要增容,浪费...
  • 由两部分组成:数据域指针域,每个结点都有一个指针,每个节点指针的指向都是指向自身结点的下一个结点,最后一个结点的head指向为null,对单链表的操作只能从一端开始,如果需要查找链表中的某一个结点,则需要从头...
  • 链表 单链表 单链表的每个节点由连接到下个节点的引用及值组成,通过引用字段将每个节点按一定顺序连接起来。 单链表节点结构 struct SinglyListNode { int val; SinglyListNode *next; SinglyListNode(int x) :...
  • 在创建单链表时如果使用使用动态的单链表,那么每创建一个结点时就会使用new 当数据比较大的时候,程序运行的时间很长 所以在写题的时候 往往会那数组来模拟一个链表; 先进行如下定义: head为头结点的头指针; idx...
  • 循环链表单链表操作实现的差异: 1.在初始化函数中把语句(*head)->next = NULL 改为 (*head)->next =head 2.在其他函数中把循环条件p->next!=NULL p->next->next !=NULL 中的 NULL 该为头指针 ...
  •  循环链表一般包括循环单链表和循环双链表,如下图所示: 循环单链表   循环单链表与单链表的区别在于,表中最后一个结点的指针不是NULL,而改为指向头结点,从而使整个链表形成一个环。   一般对循环单链表只...
  • 链表,是Java中的一种重要的链式数据结构。 众所周知,我们日常用手机电脑收发信息,下载视频软件,都要进行数据的传输。这些数据都要以一种特定的数据结构来进行传输存储,否则数据将会是一串毫无意义的01,...
  • } } //以下实现的是单链表,没有了双链表的head头指针的哑元(空元素),但必须构造一个tail尾结点辅助。 /* * To change this template, choose Tools | Templates * and open the template in the editor. */ ...
  • ???? 作者:Linux猿 ...二、双链表 2.1 插入节点 2.2 删除节点 三、单向循环链表 3.1 插入节点 3.2 删除结点 四、双向循环链表 4.1 插入节点 4.2 删除节点 五、静态链表 六、实战讲解 6.
  • 双向链表 struct node { int val; node* next; node* pre; }; class stack { public: stack() { head=new node;//带头节点 head->next = nullptr;//建立的时候要指向空 tail = head; } void push...
  • 单链表定义,相关操作以及代码实现(JAVA) 双向链表定义,相关操作以及代码实现(JAVA) 单向环形链表定义,相关操作以及代码实现(JAVA) Josephu 问题(约瑟夫问题)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,841
精华内容 15,536
关键字:

双链表和单链表