精华内容
下载资源
问答
  • 目录1 单链表节点实现单链表操作单链表实现测试链表与顺序表对比2 单向循环链表操作实现测试3 双向链表操作实现测试 1 单链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域...

    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
    

    测试

    在这里插入图片描述

    展开全文
  • 对于单链表单循环链表和双向链表,如果仅仅知道一个指向链表中某个节点链表的指针P,能否将P所指结点的数据元素与其确实存在的直接前驱?请对每一中链表作出判断,若可以,写出程序段;否则说明理由。 单链表...
  • 单链表、双链表、循环链表

    千次阅读 2019-09-20 20:39:18
    这学期的数据结构课有讲到链表,所以再来温故一下,毕竟温故知新嘛。 链表与数组的区别 链表和数组都是线性表,两者区别如下: 数组静态分配内存,链表动态分配内存;更进一步说就是数组不易拓展,但链表易...

    这学期的数据结构课有讲到链表,所以再来温故一下,毕竟温故知新嘛。

    链表与数组的区别

    链表和数组都是线性表,两者区别如下:

    • 数组静态分配内存,链表动态分配内存;更进一步说就是数组不易拓展,但链表易拓展。
    • 数组在内存中连续,链表不连续;更进一步说就是数组可能会造成内存浪费,但链表的内存利用率高;
    • 数组利用下标定位元素,时间复杂度为O(1),链表在最坏情况下是O(n);即在随机性查找上数组比链表更快。
    • 在数组中进行插入和删除操作的时间是O(n),链表是O(1)。

    单链表

    单链表接触的太多了,单链表中每一个结点由数据域和指针域构成,因为C语言有指针的概念,可以很方便的控制内存,因此大多数关于链表的实现代码都是C/C++版本的,其它语言则大多都是模拟链表,但其实Python也可以实现真实链表,尽管Python不能直接操作内存,但因为Python是动态语言,因此可以直接把对象赋值给新的变量而不需要预先定义。

    这篇博客仍以C语言来实现链表,Python版本感兴趣的可以自己尝试。

    链表其实就是一个又一个的结点连接而成,这很好理解,如果你的指针学的还不错的话,那么创建一个链表并不是一件难事。

    创建结点:

    typedef struct Node{
        int data;
        struct Node *next;
    }*Linklist;   
    

    创建链表:

    Linklist createList(int n)
    {
        Linklist p,q,head;
        head = (Linklist)malloc(sizeof(Linklist));
        q = head;
        for(int i = 0; i < n; i++)
        {
            p = (Linklist)malloc(sizeof(Linklist));
            scanf("%d",&p->data);
            p->next = NULL;
            q->next = p;
            q = p;
        }
        return head;
    }
    

    输出链表:

    void print(Linklist head)
    {
    	  Linklist p = head->next;
    	  while(p)
    	  {
               printf("%d ",p->data);
               p = p->next;
    	}
    }
    

    修改结点:

    void changeList(Linklist head,int pos,int x)//修改第pos位的结点,修改值为x
    {
        Linklist p = head;
        int i = 0;
        while(i < pos && p != NULL)
        {
            p = p->next;
            i++;
        }
        if(p)
            p->data = x;
        else
            printf("结点不存在!\n");
    }
    

    插入结点:

    void insertList(Linklist head,int pos,int x)
    {
    	  Linklist p = head;
    	  int i = 0;
    	  while(i < pos - 1 && p != NULL) //遍历到pos位置的前驱结点
    	  {
    		  p = p->next;
    		  i++;
    	  }
    	  Linklist newnode = (Linklist)malloc(sizeof(Linklist));
    	  newnode->data = x;
    	  newnode->next = p->next; //先后插
    	  p->next = newnode; //再前插
    }
    

    删除结点(按位置删):

    void deleteList(Linklist head,int pos)
    {
    	  Linklist p = head; //记录前驱
    	  Linklist q = head->next; //记录当前结点
    	  int i = 0;
    	  while(i < pos - 1 && p != NULL) //遍历到pos位置
    	  {
    	      p = p->next;
    		  q = q->next;
    		  i++;
    	  }
    	  p->next = q->next; //前驱结点指向待删结点的后继结点,即把待删结点隔离出来
    	  free(q); //删除
    	  q->next = NULL; //结点指向空
    }
    

    关于单链表的基本操作基本上也就上面那些,其中一些简单的细节被我省略了,比如在插入或者删除之前判断pos是否是不合理的值等,这些都比较好写,也就不再说,另外,因为如果每一个操作都详细辅以文字说明的话篇幅太长,所以大部分情况下我都直接给出了代码并附上少量的关键性注释,目的只是起到一个快速浏览和记忆的作用,因此这篇博客不太适合刚入门的新手,适合学过但记忆的不太牢固的人拿来复习。

    双链表

    单链表因为每一个结点只保存next的缘故,在它中只能通过一个结点访问它的后继结点而无法访问前驱,如果你想要通过一个结点既能访问前驱又能访问后继,那么可以使用双链表。

    双链表与单链表在结构上唯一的不同在于,构成双链表的每一个结点,除了数据域和指向后继的next域之外,新添了一个指向前驱的pre域。在双链表中,查找或者插入等操作不仅可以从链表的头部开始,也可以从尾部开始。仿照创建单链表的思路,在创建双链表时,我们将创建两个哑元结点,分别代表双链表的head和tail。head以及tail结点都不保存数据,head结点的pre域为空,tail结点的next域为空。

    双链表看起来是高大上了不少,但对于插入、查找等大部分操作,单链表和双链表在最坏情况下的时间损耗其实是相同的,均为O(n)。双链表更重要的作用是用在散列表中,在采用了双链表的散列表中,删除操作具有O(1)的时间复杂度,因为删除操作不仅需要找到待删结点的前驱还需要找到它的后继,在单链表中只能找到后继,但在双链表中,前驱和后继都可以同时找到。

    创建结点:

    typedef struct Node{
        int data;
        struct Node *pre,*next;
    }*Linklist;
    

    创建链表:

    Linklist head = (Linklist)malloc(sizeof(Linklist));
    Linklist tail = (Linklist)malloc(sizeof(Linklist));
    void createList(int n)
    {
    	  Linklist p,q;
    	  head->pre = head->next = NULL;
    	  tail->pre = tail->next = NULL;
    	  q = head;
    	  for(int i = 0; i < n; i++)
    	  {
    		  p = (Linklist)malloc(sizeof(Linklist));
    		  scanf("%d",&p->data);
    		  p->next = NULL;
    		  p->pre = q;
    		  q->next = p;
    		  q = p;
    	  }
    	  p->next = tail;
    	  tail->pre = p;
    }
    

    输出链表:

    void next_print(Linklist head) //正向输出
    {
    	  Linklist p = head->next;
    	  while(p && p != tail)
    	  {
              printf("%d ",p->data);
              p = p->next;
    	  }
    	  printf("\n");
      }
    
    void pre_print(Linklist tail) //反向输出
    {
    	  Linklist p = tail->pre;
    	  while(p && p != head)
    	  {
              printf("%d ",p->data);
              p = p->pre;
    	  }
    	  printf("\n");
    }
    

    对于查找结点、修改结点、插入结点等等之类,与单链表基本一致,唯一不同的就是双链表可以选择正向遍历或者反向遍历两种方式。

    接下来给出与单链表稍微有些许不同的删除操作:
    删除结点:

    void deleteList(Linklist head,int pos)
    {
          Linklist p = head;
          int i = 0;
          while(i < pos && p != tail) //遍历到当前结点
          {
        	  p = p->next;
          	  i++;
    	  }
    	  p->pre->next = p->next; //前驱指向后继
    	  p->next->pre = p->pre; //后继指向前驱
    	  free(p);
    	  p->next = p->pre = NULL;
    }
    

    循环链表

    将一条链表的首尾相连我们就会得到一条循环链表。在单链表中,将尾结点的next域指向head结点,由此构造出一条单循环链表。在双链表中,将head结点的pre域指向尾结点,尾结点的next域指向head结点,由此构造出一条双循环链表。

    循环链表有什么好处呢?首先,因为是循环结构,因此无须增加存储量,仅对表的连接方式稍作改变,即可使表的处理更加方便灵活。
    ① 循环链表没有NULL指针,因此在值判断操作中就不再是判别p == NULL 或者 p->next == NULL等方式,而是判别它们是否等于某一指针;
    ② 在单链表中实现全遍历只能从head节点开始,在双链表中只能从head或者tail结点开始,而在循环链表中可以从链表的任意位置开始;

    单循环链表

    单循环链表是在单链表的基础上实现的,在这里有两种实现方式,一种是带头结点的单循环链表,一种是带尾结点的单循环链表,两种方式均可实现,但有时候带尾结点的单循环链表可能更为方便。比方说:我们如果要查找链表的首元素和尾元素,那么用带头结点的单循环链表的话分别需要O(1)和O(n)的复杂的,因为虽然首元素可以直接得到,但尾元素却只能遍历得到,而如果采用带尾结点的单循环链表,则时间复杂度均是O(1)。

    本来我是打算附上关于单循环链表一些基本操作的代码实现的,但敲了几个感觉实在是没什么用处,因为这些代码几乎和单链表的完全一样,所以这里我就略去了。

    双循环链表

    嗯。。。没啥需要说的,会写双链表就肯定会写双循环,双循环继承了双链表的许多优势同时又具有循环链表的优势,我就不再重复赘述了。

    令附一表,在各种链表中实现相关基础操作的时间复杂度对比,包括单链表,已排序的单链表,双链表,以及已排序的双链表。
    在这里插入图片描述

    关于链表还有很多值得说的地方,但碍于篇幅这篇就不再介绍了,下一篇再补充吧。

    展开全文
  • 数据结构学习笔记(链表链表的概念及结构链表结构的分类链表的实现三级目录整体代码总结参考博客 链表的概念及结构 链表结构的分类 链表的实现 三级目录 整体代码 总结 参考博客

    数据结构学习笔记(单链表、单循环链表、带头双向循环链表)的增删查改排序等

    链表的概念及结构

    概念:
    链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
    结构:
    在这里插入图片描述

    链表结构的分类

    1. 单向、双向
    2. 带头、不带头
    3. 循环、非循环
      组合下来可分为8类链表结构:
      a:单向链表、双向链表
      b:不带头单链表、带头链表
      c:单链表、循环单链表
      d:无头单向非循环链表
      在这里插入图片描述
      e:带头双向循环链表
      在这里插入图片描述

    链表的常用操作实现

    无头单链表

    概念:单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
    代码:

    **结构代码**
    
    // An highlighted block
    typedef struct ListNode
    {
    	ElemType data;
    	struct ListNode *next;
    }ListNode;
    
    typedef ListNode* List;//把链表定义为一个指针结构
    
    **初始化**
    
    // An highlighted block
    void ListInit(List *plist)
    {
    	*plist = NULL;
    }
    
    **尾插**
    
    // An highlighted block
    void ListPushBack(List *plist, ElemType v)
    {
    	//申请节点
    	ListNode *s = _Buynode(v);//此处写了一个购买节点的函数——buynode,在后面会写出来,在这里替代ListNode *s = (ListNode*)malloc(sizeof(ListNode));这样一个过程
    	//插入节点
    	ListNode *p = *plist;
    	if(p == NULL)
    	{
    		*plist = s;
    		return;
    	}
    
    	while(p->next != NULL)
    		p = p->next;
    
    	p->next = s;
    }
    
    **头插**
    
    // An highlighted block
    void ListPushFront(List *plist, ElemType v)
    {
    	ListNode *s = _Buynode(v);
    	s->next = *plist;
    	*plist = s;
    }
    
    **尾删**
    
    // An highlighted block
    void ListPopBack(List *plist)
    {
    	ListNode *p = *plist;
    	ListNode *prev = NULL;
    //判断是否为空
    	if(*plist == NULL)
    		return;
    //	
    	while(p->next != NULL)
    	{
    		prev = p;
    		p = p->next;
    	}
    //判断头节点若为空直接返回空值,最后将删除的节点free掉,因为每一个节点都是用malloc函数申请的
    	if(prev == NULL)
    		*plist = NULL;
    	else
    		prev->next = NULL;
    	free(p);
    }
    
    **头删**
    
    // An highlighted block
    void ListPopFront(List *plist)
    {
    	ListNode *p = *plist;
    	if(*plist == NULL)//判断节点是否为头节点,若为空直接返回否定就指向下一个节点
    		return;
    //删除该节点与链表的连接
    	*plist = p->next;
    	free(p);//删除节点
    }
    
    显示链表内数据
    
    // An highlighted block
    var foo = 'bar';
    
    **显示链表内数据**
    
    // An highlighted block
    void ListShow(List plist)
    {
    	ListNode *p = plist;
    	while(p != NULL)
    	{
    		printf("%d->", p->data);
    		p = p->next;
    	}
    	printf("Over.\n");//在循环体外面一定要有所返回或者输出的值
    }
    
    **查找链表中有效结点的个数**
    
    // An highlighted block
    size_t ListLength(List plist)
    {
    	ListNode *p = plist;
    	size_t len = 0;
    	while(p != NULL)
    	{
    		len++;
    		p = p->next;
    	}
    	return len;
    }
    
    **查找数据**
    
    // An highlighted block
    ListNode* ListFind(List plist, ElemType key)
    {
    	ListNode *p = plist;
    	while(p!=NULL && p->data!=key)
    		p = p->next;
    	return p;;
    
    **删除节点**
    
    // An highlighted block
    void ListErase(List *plist, ElemType key)
    {
    	ListNode *p = *plist;
    	ListNode *prev = NULL;
    	if(p == NULL)//链表是否为空
    		return;
    
    	while(p!=NULL && p->data!=key)
    	{
    		prev = p;
    		p = p->next;
    	}
    	if(p == NULL)
    		return;
    
    	if(prev == NULL)//考虑头节点
    		*plist = p->next;
    	else
    		prev->next = p->next;//拷贝下一节点
    	free(p);//更改有效节点数
    }
    
    **消除和摧毁**
    
    // An highlighted block
    void ListClear(List *plist)
    {
    	ListNode *p = NULL;
    	while(*plist != NULL)
    	{
    		p = *plist;
    		*plist = p->next;
    		free(p);//对所有节点进行删除
    	}
    }
    //直接引用消除是一样的效果
    void ListDestroy(List *plist)
    {
    	ListClear(plist);
    };
    
    **按值插入**
    
    // An highlighted block
    void ListInsertByVal(List *plist, ElemType v)
    {
        //默认在数据有序的前提下
    	ListNode *p = NULL;
    	ListNode *s = _Buynode(v);//申请节点
    	if(*plist == NULL) //空链表
    	{
    		*plist = s;
    		return;
    	}
    //如果插入的节点比第一个节点小
    	if(v < (*plist)->data)
    	{
    		s->next = *plist;
    		*plist = s;
    		return;
    	}
    //查找节点
    	p = *plist;
    	while(p->next!=NULL && v>p->next->data)
    		p = p->next;
    //插入
    	s->next = p->next;
    	p->next = s;
    };
    
    **排序**
    
    // An highlighted block
    void ListSort(List *plist)
    {
    	ListNode *p;
    	if(*plist==NULL || (*plist)->next==NULL)//只有一个节点或者空链表的时候不需要排序直接返回即可
    		return;
    	p = (*plist)->next;
    	(*plist)->next = NULL; // 断开链表
    	while(p != NULL)
    	{
    		ListNode *q = p->next;
    		if(p->data < (*plist)->data)
    		{
    			p->next = *plist;
    			*plist = p;
    		}
    		else
    		{
    			ListNode *prev = *plist;
    			while(prev->next!=NULL && p->data>prev->next->data)
    				prev = prev->next;
    			p->next = prev->next;
    			prev->next = p;
    		}
    		p = q;
    	}
    }
    
    **反转**
    
    // An highlighted block
    void ListReverse(List *plist)
    {
    	ListNode *p = NULL;//声明定义的节点p并初始化为NULL
    	if(*plist==NULL || (*plist)->next==NULL)
    		return;
    
    	p = (*plist)->next;//接收链表的下一个节点
    	(*plist)->next = NULL; // 断开链表
    
    	while(p != NULL)
    	{
    		ListNode *q = p->next
    		//头插节点
    		p->next = *plist;
    		*plist = p;
    		p = q;//p跳到q接着进行重新判断
    	}
    }
    

    单链表补充

    **此处写了一个购买节点的函数供调用,使得代码得到优化**
    
    // An highlighted block
    ListNode* _Buynode(ElemType v)
    {
    	ListNode *s = (ListNode*)malloc(sizeof(ListNode));
    	assert(s != NULL);
    	s->data = v;
    	s->next = NULL;
    	return s;
    }
    

    单循环链表

    定义:循环单链表是单链表的另一种形式,其结构特点是: 链表中最后一个结点的指针域不再是结束标记,而是指向整个链表的第一个结点,从而使链表形成一个环。和单链表相同,循环链表也有带头结点结构和不带头结点结构两种,带头结点的循环单链表实现插入和删除操作较为方便。
    结构
    在这里插入图片描述
    代码

    **定义单循环链表**
    
    // An highlighted block
    typedef struct SCListNode
    {
    	ElemType data;
    	struct SCListNode *next;
    }SCListNode;
    
    typedef struct SCList
    {
    	SCListNode *phead;
    }SCList;
    

    代码:

    **初始化**
    
    // An highlighted block
    void SCListInit(SCList *plist)
    {
    	plist->phead = NULL;
    }
    
    **尾插**
    
    // An highlighted block
    void SCListPushBack(SCList *plist, ElemType v)
    {
    	SCListNode *s = (SCListNode *)malloc(sizeof(SCListNode));
    	assert(s != NULL);
    	s->data = v;
    	s->next = NULL;
    
    	SCListNode *p = plist->phead;
    	if(p == NULL)
    	{
    		plist->phead = s;
    		plist->phead->next = plist->phead;
    		return;
    	}
    
    	while(p->next != plist->phead)
    		p = p->next;
    
    	s->next = plist->phead;
    	p->next = s;
    }
    

    带头双向循环链表

    定义:循环双链表是对双链表的改进,将尾结点与头结点建立连接,使得尾结点可以直接查找到头结点,头结点也能够直接查找到头结点,以此来提高查找的效率。
    结构:
    在这里插入图片描述
    代码:

    **结构体定义**
    
    // An highlighted block
    typedef struct DCListNode
    {
    	ElemType data;
    	struct DCListNode *next;
    	struct DCListNode *prev;
    }DCListNode;
    
    typedef struct DCList
    {
    	DCListNode *head;
    }DCList;;
    
    **初始化**
    
    // An highlighted block
    void DCListInit(DCList *plist)
    {
    	plist->head = _Buynode(-1);//此处也可设为0,头节点不具有相关值
    }
    
    **购买获取节点**
    
    // An highlighted block
    DCListNode* _Buynode(ElemType v)
    {
    	DCListNode *s = (DCListNode*)malloc(sizeof(DCListNode));
    	assert(s != NULL);
    	s->data = v;
    	s->next = s->prev = s;
    	return s;
    }
    
    **尾插**
    

    在这里插入图片描述

    // An highlighted block
    void DCListPushBack(DCList *plist, ElemType v)
    {
    	DCListNode *s = _Buynode(v);
    	s->next = plist->head;
    	s->prev = plist->head->prev;
    	s->next->prev = s;
    	s->prev->next = s;
    }
    
    **头插**
    

    在这里插入图片描述

    // An highlighted block
    void DCListPushFront(DCList *plist, ElemType v)
    {
    	DCListNode *s = _Buynode(v);
    	s->next = plist->head->next;
    	s->prev = plist->head;
    	s->next->prev = s;
    	s->prev->next = s;
    }
    
    **尾删**
    

    在这里插入图片描述

    // An highlighted block
    void DCListPopBack(DCList *plist)
    {
    	DCListNode *p;
    	if(plist->head->next == plist->head)
    		return;
    
    	//查找最后一个节点
    	p = plist->head->prev; 
    	
    	//删除节点
    	p->next->prev = p->prev;
    	p->prev->next = p->next;
    	free(p);
    }
    
    **头删**
    
    // An highlighted block
    void DCListPopFront(DCList *plist)
    {
    	DCListNode *p = plist->head->next;
    	if(plist->head->next == plist->head)
    		return;
    
    	p->prev->next = p->next;
    	p->next->prev = p->prev;
    	free(p);
    }
    
    **按值插入**
    
    // An highlighted block
    void DCListInsertByVal(DCList *plist, ElemType v)
    {
    	DCListNode *p = plist->head->next;
    	while(p!=plist->head && v>p->data)
    		p = p->next;
    
    	DCListNode *s = _Buynode(v);
    	s->next = p;
    	s->prev = p->prev;
    	s->next->prev = s;
    	s->prev->next = s;
    }
    
    **查找**
    
    // An highlighted block
    DCListNode* DCListFind(DCList *plist, ElemType key)
    {
    	DCListNode *p = plist->head->next;
    	while(p!=plist->head && key!=p->data)
    		p = p->next;
    	if(p == plist->head)
    		return NULL;
    	return p;
    }
    
    **按值删除**
    
    // An highlighted block
    void DCListErase(DCList *plist, ElemType key)
    {
    	DCListNode *p = DCListFind(plist, key);
    	if(p == NULL)
    		return;
    
    	p->next->prev = p->prev;
    	p->prev->next = p->next;
    
    	free(p);
    }
    
    **查看循环双链表数据**
    
    // An highlighted block
    void DCListShow(DCList *plist)
    {
    	DCListNode *p = plist->head->next;
    	while(p != plist->head)
    	{
    		printf("%d->", p->data);
    		p = p->next;
    	}
    	printf("Over.\n");
    }
    
    **链表长度**
    
    // An highlighted block
    size_t DCListLength(DCList *plist)
    {
    	DCListNode *p = plist->head->next;
    	size_t len = 0;
    	while(p != plist->head)
    	{
    		len++;
    		p = p->next;
    	}
    	return len;
    }
    
    **排序**
    
    // An highlighted block
    void DCListSort(DCList *plist)
    {
    	DCListNode *p, *q;
    	size_t size = DCListLength(plist);
    	if(size <= 1)
    		return;
    
    	p = plist->head->next;
    	q = p->next;
    
    	p->next = plist->head;
    	plist->head->prev = p;
    
    	while(q != plist->head)
    	{
    		p = q;
    		q = q->next;
    
    		//寻找插入的位置
    		DCListNode *pos = plist->head->next;
    		while(pos!=plist->head && p->data>pos->data)
    			pos = pos->next;
    
    		//插入节点
    		p->next = pos;
    		p->prev = pos->prev;
    		p->next->prev = p;
    		p->prev->next = p;
    	}
    }
    

    下面展示一些 内联代码片

    // A code block
    var foo = 'bar';
    
    // An highlighted block
    var foo = 'bar';
    
    **反转**
    
    // An highlighted block
    void DCListReverse(DCList *plist)
    {
    	DCListNode *p, *q;
    	size_t size = DCListLength(plist);
    	if(size <= 1)
    		return;
    
    	p = plist->head->next;
    	q = p->next;
    	//断开链表
    	p->next = plist->head;
    	plist->head->prev = p;
    
    	while(q != plist->head)
    	{
    		p = q;
    		q = q->next;
    
    		p->next = plist->head->next;
    		p->prev = plist->head;
    		p->next->prev = p;
    		p->prev->next = p;
    	}
    }**加粗样式**
    
    **清除**
    
    // An highlighted block
    void DCListClear(DCList *plist)
    {
    	DCListNode *p = plist->head->next;
    	while(p != plist->head)
    	{
    		p->prev->next = p->next;
    		p->next->prev = p->prev;
    		free(p);
    
    		p = plist->head->next;
    	}
    }
    
    **摧毁**
    
    // An highlighted block
    void DCListDestroy(DCList *plist)
    {
    	DCListClear(plist);
    	free(plist->head);
    	plist->head = NULL;
    }
    
    展开全文
  • 单链表、双向链表、循环链表

    千次阅读 多人点赞 2019-07-26 14:26:09
    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表单链表 单链表有两个较特殊节点,头结点和尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向...

    常见链表

    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表。

    单链表

    单链表有两个较特殊节点,头结点尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向一个空地址NULL,表示链表上的最后一个节点。

    和数组一样,链表也支持数据的查找、插入和删除操作。但相对于数据的插入删除需要做大量的搬移操作,链表的插入,删除的时间复杂度为O(1)。但是链表想要随机访问第k个元素,就没有数组高效,随机访问数据的时间复杂度为O(n)。单向链表的简单实现代码如下:

    link_list.h

    /*
     *****************************************************************************
     *
     * File:       linke_list.h
     *
     * Description: Single link list header file
     *
     *
     * History:
     *    Created:  Apri, 2019
     *
     * Copyright (c) 2019 
     * All rights reserved.
     *
     ****************************************************************************/
     #ifndef LINK_LIST_
     #define LINK_LIST_
     
     
     typedef struct _node{
    	 struct _node *next;
    	 int date;
     }node, *list;
    
    list init_single_link_list();
    int insert_to_link_list_head(list list, int date);
    int insert_to_link_list_tail(list list, int date);
    void show_single_link_list (list head);
    void delete_from_link_tail(list list_);
    #endif
    

    link_list.c

    /*
     *****************************************************************************
     *
     * File:        link_list.c
     *
     * Description: Single link list file
     *
     *
     * History:
     *    Created:  Apri, 2019
     *
     * Copyright (c) 2019 
     * All rights reserved.
     *
     ****************************************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include "link_list.h"
    
     
    list init_single_link_list()
    {
    	list link_list = NULL;
    	
    	link_list = (list)malloc(sizeof(list));
    	if(NULL == link_list){
    		printf("malloc failed !!\n");
    		exit(1);
    	}
    	link_list->next = NULL;
    	return link_list;
    }
    
    /*
      insert a node to single link list
      头插法
    */
    int insert_to_link_list_head(list list_, int date)
    {
    	list p = NULL;
            
            if (NULL == list_) {
               printf("list is NULL ...\n");
               exit(1);
            }	
    	p = (list)malloc(sizeof(list));
    	if(p == NULL) {
    		printf("malloc failed \n");
    		exit(1);
    	}
    	p->date = date;
    	
    	p->next = list_->next;
    	list_->next = p;
    	
    	return 1;
    }
    /*
     * 尾插法实现
    */
    int insert_to_link_list_tail(list list_, int date)
    {
    	list p = NULL;
            
            if (NULL == list_) {
                printf("list is NULL ...\n");
                exit(1);
            }
    	p = (list)malloc(sizeof(list));
    	if(NULL == p) {
    		printf("malloc fialed !\n");
    		exit(1);
    	}
    	while(list_->next) {
                       
                list_ = list_->next;    
            } 
            p->date = date;
            list_->next = p;
            p->next = NULL; 
    	
    	return 1;
    	
    }
    
    void show_single_link_list (list head)
    {
    	if (NULL == head) {
    		printf(" list is null ...\n");
    		return;
    	}
    	head = head->next;
    	while(head) {
    		printf("date ---- > %d \n", head->date);
    		head = head->next;
    	}
    	
    	return;
    }
    /*
     * delete element from tail of link list
     * */
    void delete_from_link_tail(list list_)
    {
        if(NULL == list_) {
            printf("list is NULL ...\n");
            exit(1);
        }
        if(list_->next == NULL) {
            free(list_);
            list_ = NULL;
        }
        while(list_->next->next) {
            list_ = list_->next;
        }
        free(list_->next);
        list_->next= NULL;
        
        return ;
    }
    /*
     * delete from link head
     * */
    void delete_from_link_head(list list_)
    {   
        list p = NULL;
        if(NULL == list_) {
            printf("link is NULL ...\n");
            exit(1);
        }
        
        if(list_->next) {
            p = list_->next;
            list_->next = p->next;
            free(p);
        }
        return;
    }
    /*
     * get link list size
     * 
     * */
    int get_link_size(list list_)
    {
        int size = 0;
        if(NULL == list_) {
            printf("link is NULL ...\n");
            exit(1);
        }
        while(list_->next) {
            ++size;
            list_ = list_->next;
        }
        return size;
    }
    void delete_specific_date(list list_, int date)
    {
        list p = NULL;
        int size = 0;
        if(NULL == list_) {
            printf("list is NULL ...\n");
            exit(1);
        }
        size = get_link_size(list_);
        if (size <= 0) {
            printf("link hasn't element ...\n");
            exit(1);
        }
        p = list_->next;
        while(p->date != date) {
            p = list_->next;
        }
      
       list_->next = p;
       free(list_);
        
        return;
    }
    int main()
    {
    	list head = NULL;
    	int i;
    	
    	head = init_single_link_list();
    #if 0
    	for (i = 0; i < 2; i++) {
    		
               //insert_to_link_list_head(head, i);
               insert_to_link_list_tail(head, i);
    	}
    #endif
    	show_single_link_list(head);
            printf("list size is %d\n", get_link_size(head));
            //delete_from_link_tail(head);
            //delete_from_link_head(head);
            delete_specific_date(head, 0);
            show_single_link_list(head);	
    }
    
    
    

    双向链表

    双向链表支持两个方向,每个节点有一个后继指针next指向后面的节点,还有一个前驱指针指向前面的节点。
    在这里插入图片描述
    双向链表简单实现:
    double_linklist.h

    #ifndef DOUBLE_LINKLIST_
    #define DOUBLE_LINKLIST_
    
    #include "stdbool.h"
    typedef int ElementType;
    typedef struct _double_link {
        ElementType date;
        struct _double_link *next;
        struct _double_link *pre;     
    }double_linklist;
    
    double_linklist *init_double_linklist();
    bool insert_linklist_head(double_linklist* d_linklist, ElementType date);
    ElementType delete(double_linklist* d_linklist);
    void display(double_linklist* d_linklist);
    bool isEmpty(double_linklist* d_linklist);
    
    #endif
    

    double_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "double_linklist.h"
    
    /*
    @func :创建头结点和尾结点,新增的节点插入头结点和尾结点之间
    */
    double_linklist *init_double_linklist()
    {
        double_linklist *head = (double_linklist *)malloc(sizeof(double_linklist));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        head->next = NULL;
        head->pre = NULL;
        double_linklist *pNew = (double_linklist *)malloc(sizeof(double_linklist));
        if (!pNew) {
            perror("malloc failed.");
            exit(1);
        }
        pNew->next = NULL;
        pNew->pre = head;
        head->next = pNew;
        
        return head;
    }
    /*
    @func: 头插法,新增的节点插入头结点后面
    */
    bool insert_linklist_head(double_linklist* head, ElementType date)
    {
        if (!head) {
            perror("d_linklist is NULL");
            exit(1);
        }
        double_linklist* pNew = (double_linklist *)malloc(sizeof(double_linklist));
        if (!pNew) {
            perror("malloc failed.");
            exit(1);
        }
        pNew->date = date;
        /*先确定新增节点的前后指针指向*/
        pNew->pre = head;
        pNew->next = head->next;
        head->next->pre = pNew;
        head->next = pNew;
        
        printf("insert %d\n", head->next->date);
        return true;
    }
    bool isEmpty(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.");
            exit(1);
        }
        if (head->next->next == NULL && head->next->pre == head)
            return true;
        else
            return false;
    }
    /*
    @func: 删除一个节点
    */
    ElementType delete(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.");
            exit(1);
        }
        if (isEmpty(head)) {
            printf("double linklist is empty.\n");
            exit(1);
        }
        double_linklist* pDel = head->next;
        ElementType val = pDel->date;
        
        pDel->next->pre = head;
        head->next = pDel->next;
        if (pDel) {
            free(pDel);
            pDel = NULL;
        }
        return val;
    }
    
    void display(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.\n");
            exit(1);
        }
        if (isEmpty(head)) {
            printf("double linklist is empty.\n");
            exit(1);
        }
        double_linklist* tmp = head->next;
        while (tmp->next != NULL) {
            printf("val ---> %d\n", tmp->date);
            tmp = tmp->next;
        }
    }
    int main()
    {
        double_linklist* d_link = init_double_linklist();
        insert_linklist_head(d_link, 20);
        insert_linklist_head(d_link, 10);
        printf("delete val is %d .\n", delete(d_link));
        printf("delete val is %d .\n", delete(d_link));
        display(d_link);
        
    }
    

    循环链表

    单向循环链表

    和单链表相比,循环链表的优点是从链尾到链头特别容易,适合处理具有环形结构特点的数据,如著名的约瑟夫问题。循环链表的简单实现如下:
    robin_linklist.h

    #ifndef ROBIN_LINKLIST_
    #define ROBIN_LINKLIST_
    
    #include "stdbool.h"
    typedef int ElementType;
    typedef struct _node {
        ElementType date;
        struct _node* next;
    }robin_linklist;
    
    robin_linklist* init_robin_linklist();
    bool insert_to_robin_linklist(robin_linklist* link, ElementType date);
    bool delete_from_robin_linklist(robin_linklist* link);
    void display_robin_linklist(robin_linklist* link);
    #endif
    

    robin_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "robin_linklist.h"
    
    robin_linklist* init_robin_linklist()
    {
        robin_linklist *head = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        /*next指针指向自己*/
        head->next = head;
        robin_linklist *node = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!node) {
            perror("malloc failed.");
            exit(1);
        }
        node->next = head;
        head->next = node;
        return head;
    }
    /*
    @func : insert a element to linklist
    */
    bool insert_to_robin_linklist(robin_linklist* link, ElementType date)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        robin_linklist* node = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!node) {
            perror("malloc failed.");
            exit(1);
        }
        node->date = date;
        node->next = link->next;
        link->next = node;
        
        return true;  
    }
    /*
    @func : delete a element from linklist
    */
    bool delete_from_robin_linklist(robin_linklist* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (link->next->next != link) {
            robin_linklist *tmp = link->next;
            link->next = tmp->next;
            return true;
        }else {
            printf("link is empty.\n");
            return false;
        }
    }
    void display_robin_linklist(robin_linklist* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        robin_linklist *tmp = link->next;
        while(link != tmp->next) {
          printf("val ---> %d\n", tmp->date);
          tmp = tmp->next;
        }
    }
    int main()
    {
        /*test code*/
        robin_linklist *ro_linklist = init_robin_linklist();
        insert_to_robin_linklist(ro_linklist, 10);
        display_robin_linklist(ro_linklist);
        delete_from_robin_linklist(ro_linklist);
        display_robin_linklist(ro_linklist);
        delete_from_robin_linklist(ro_linklist);
          
    }
    
    

    双向循环链表

    在这里插入图片描述
    双向链表的简单实现:
    double_robin_linklist.h

    #ifndef DOUBLE_ROBIN_LINKLIST_
    #define DOUBLE_ROBIN_LINKLIST_
    
    #include "stdbool.h"
    
    typedef int ElementType;
    typedef struct _double_robin_link {
        ElementType date;
        struct _double_robin_link *next;
        struct _double_robin_link *pre;
    }dou_robin_link;
    
    dou_robin_link* init_double_robin_linklist();
    bool insert_head(dou_robin_link * link, ElementType date);
    ElementType delete(dou_robin_link* link);
    bool isEmpty(dou_robin_link* link);
    void display(dou_robin_link* link);
    
    #endif
    

    double_robin_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "double_robin_linklist.h"
    
    
    dou_robin_link * init_double_robin_linklist()
    {
        dou_robin_link* head = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        head->next = head;
        head->pre = head;
        
        /*创建尾节点*/
        dou_robin_link *tail = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!tail) {
            perror("malloc failed.");
            exit(1);
        }
        tail->pre = head;
        tail->next = head;
        head->next = tail;
        
        return head;
    }
    bool isEmpty(dou_robin_link* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (link->next->next == link && link->next->pre == link) {
            
            printf("double robin linklist is empty.\n");
            return true;
        }
        else {
            return false;
        }
    }
    /*
    @func: 头插法
    */
    bool insert_head(dou_robin_link * link, ElementType date)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        dou_robin_link *pNew = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!pNew) {
            perror("malloc is NULL.");
            exit(1);
        }
        pNew->date = date;
        pNew->next = link->next;
        pNew->pre = link;
        
        link->next = pNew;
        link->next->next->pre = pNew;
        printf("insert -->%d\n", link->next->date);
        
        return true;
    }
    /*
    @func: 头删法
    */
    ElementType delete(dou_robin_link* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (isEmpty(link)) {
            exit(1);
        }
        dou_robin_link *pDel = link->next;
        ElementType val = pDel->date;
        link->next = pDel->next;
        pDel->next->pre = link;
        
        printf("delete ---> %d\n", val);
        if(pDel) {
            free(pDel);
            pDel = NULL;
        }
        return val;
    }
    
    void display(dou_robin_link* link)
    {
        if(!link) {
            perror("link is NULL.");
            exit(1);
        }
        if(isEmpty(link)) {
            exit(1);
        }
        dou_robin_link* tmp = link->next;
        while (tmp->next != link && tmp->next->pre != link) {
            printf("val ---> %d\n", tmp->date);
            tmp = tmp->next;
        }
    }
    int main()
    {
        dou_robin_link *head = init_double_robin_linklist();
        insert_head(head, 10);
        insert_head(head, 20);
        delete(head);
        display(head);
    }
    
    展开全文
  • 文章目录前言单链表单循环链表双链表双循环链表错误纠正说明时间复杂度比较关于头结点 前言 博主最近在复习算法与数据结构,由于平时主力语言是Python,所以找了个用Python讲解数据结构的视频看了下,链接为:...
  • 单链表,双链表,循环链表的区别

    千次阅读 2019-02-18 16:45:06
    单向链表单链表)  单向链表,它包含两个域,一个信息域一个指针域。这个链接指向表中的下一个节点,而最后一个节点则 指向一个空值NULL。 单向链表只可向一个方向遍历。 查找一个节点的时候需要从第一个节点...
  • 单链表循环链表、双向循环链表总结

    千次阅读 多人点赞 2019-11-23 18:56:31
    链表介绍 不带头结点的单向链表 带头结点的单向链表 循环链表 双向循环链表
  • 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域 value)一个链接域(或者称为指针域next)。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。...
  • 单循环链表单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。 ...
  • 写在前面的话: 版权声明:本文为博主原创文章,转载请注明出处! 博主是一个小菜鸟,并且非常玻璃心...对于单链表,由于每个结点只存储了向后的指针,到了尾标志就停止了向后的操作,这样,当某一个结点找不到前驱...
  • 总结:以空间换取时间。
  • 单链表:  一.单链表与顺序表相比: 1.顺序表可以方便的随机存取表中的任一节点,速度快;...相反,链表则适用于插入删除频繁,表长估计不定的情形。 3.单链表中的逻辑位置连续,物理位置非连续;而顺
  • 单链表循环链表和双向链表

    千次阅读 2018-05-01 12:26:40
    单链表: 一.单链表与顺序表相比: 1.顺序表可以方便的随机存取表中的任一节点,速度快;...相反,链表则适用于插入删除频繁,表长估计不定的情形。 3.单链表中的逻辑位置连续,物理位置非连续;而顺序...
  • 循环链表(循环单链表和双链表)

    千次阅读 2021-02-04 13:52:36
    循环链表前言一、循环单链表的初始化二、判断是否为空或表尾结点三、循环双链表的初始化四、循环双链表的插入与删除 前言 对于循环单链表而言,在进行插入删除时,可以让指针指向尾部,对于表头(通过尾部找到头部...
  • 单链表是一种线性数据结构,特点是:(1) .分配空间是不需要一块大的内存空间,因为每个节点都可以独立存储; (2) .从最后添加一个节点的时间复杂度为 O(1) , 增删查找操作的时间复杂度都为O(n) 节点类 : class ...
  • c/c++ 循环单链表循环链表

    千次阅读 2018-05-13 16:57:27
    最近遇到了一个作业题目是:建立一个循环单链表,其节点有 prior,data next 三个域,其中 data 为数据域,存放元素的有效信息,next 域为指针域,指向后继节点,prior 为指针域,它的值为 NULL。编写一个算法将...
  • 内部结点唯一的前驱后继,表头 只有后继,表尾只有前驱。 1、线性结构 ...//线性表类模板如下,是顺序表类和链表类的基类,用虚函数virtual template <class T> //value的类型是T class LinearLi...
  • 单循环链表单链表的区别就是,单循环链表的尾指针指向头结点,可以想象成一个环,首尾相连,这时候需要考虑两种情况: 1.不带头结点 2.带头节点 不带头节点的情况: 对比单链表,直接尾结点的指针指向头节点就好了...
  • 1、链表(Linked List)介绍 1.1、内存结构 ...又由于此链表的每个结点中只有一个指向后继的指针,所以称其为单链表或线性链表。下图的单链表是带有头结点的单链表,头结点的作用是方便单链表的特殊操作,简化代
  • 链表有很多种不同类型:单向链表,双向链表和循环链表。 在链表中第一个节点叫头节点(如果有头节点)头节点不存放有效信息,是为了方便链表的删除和插入操作,第一个有效节点叫首节点,最后一个节点叫尾节点。 2....
  • 单循环链表 双循环链表 总结 顺序表 package com.list; import java.lang.*; import java.util.*; /** * @author PangWanjia * @date 2020/11/3 14:50 */ /* 顺序表java的ArrayList类 创建顺序表,顺序...
  • 数据结构纯属新手,小白...单循环链表单链表类似只有数据域指向下一个结点的指针域,不过尾结点的指针域指向第一个结点。 创建链表 //创建单循环链表 Node* initList() { Node* L = (Node*)malloc(sizeof(Node))
  • 链表不仅作为链式存储的一种实现方式,还表达了计算机不连续(离散)的存储思想。
  • 线性顺序表、单链表循环链表、双向链表的区别 1、线性顺序表 用一种地址连续的存储单元依次存储线性表的数据元素 2、单链表(又称线性链表) 用一组任意的存储单元(此存储单元可以是连续的也可以是不连续的)来...
  • 单链表 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据...
  • 单链表循环链表

    2021-04-13 20:02:09
    判断是否为循环链表循环链表) (循环链表) (非循环链表) 题目: 给定一个链表,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环...
  • 其中单链表循环链表和双向链表用于实现线性表的链式存储结构。 单链表 下图为线性表的单链表存储结构 扩展: 头指针是以确定线性表中第一个元素对应的存储位置,一般用于处理数组、链表、队列等...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,594
精华内容 7,437
关键字:

单链表和单循环链表