精华内容
下载资源
问答
  • 在线性表的顺序存储结构中,我们要通过任意位置读取元素的值是十分方便容易的,但在单链表中,对于第i个元素具体在哪无法一开始就得知,必须从头指针开始寻找。因此对于单链表的读取第i个元素的操作在算法上相对要...
    线性表
    一、线性表定义:
    1、线性表的定义

    通过一个例子来体验什么是线性表的定义:小朋友出游排队。谁在谁的前面,谁在谁的后面,保证不会有人丢失。
    定义:线性表(List):零个或多个数据元素的有限序列。

    注意:
    1)线性表是一个序列。也就是说,线性表的元素之间是有序的。若元素存在多个,对于其中一个元素来说,它前面的元素叫前驱,后面的元素叫后继。第一个元素无前驱,最后一个元素无后继,中间的元素只有一个前驱,一个后继。
    2)线性表是有限的。事实上,在计算机科学领域,我们只研究有限的序列,因为计算机的处理对象都是有限的。而对于那些无限的序列,只在数学中讨论。

    线性表的元素个数n(n>=0)定义为线性表的长度,当n=0时,称为空表。
    练习:说明以下数据集是否是线性表
    1、一年中的十二星座(古巴比伦人发明,使用60进制,空中花园,时间也是他们发明的,被波斯灭国,对数学的贡献有着极其重要地位)
    2、一个公司的组织架构(非皮包公司)
    3、一个班级间的同学关系
    4、班级同学的点名册
    5、播放器的播放列表
    6、linux的文件系统
    答案:
    1、4、5是,2、3、6不是
    ===============================================================================
    二、线性表的顺序存储结构
    1、定义存储结构
    线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。
    在C语言中,我们可以使用一维数组来实现顺序表的存储结构。即把表的第一个元素数据存放到数组下标为0的位置中,接着把线性表相邻的元素存储到数组中的相邻位置。
    线性表的顺序存储结构代码:
    #define MAXSIZE 20
    typedef int data_t; //编程的普适性、方便移植,脚本没有变量类型
    typedef struct
    {
    data_t data[MAXSIZE];
    int length;
    }SqList;
    这里要区分线性表长度与数组长度的区别。数组长度是存放线性表的存储空间长度,在编译后这个存储空间就不变了。而线性表长度指的是线性表中的数据元素个数,随着线性表的操作,这个数据是变化的。在任意时刻,线性表长度应该小于等于数组长度。
    对于顺序表来说,逻辑位置上相邻的两个元素,其在存储位置上也是相邻的。例如a[i]和a[i+1],二者在逻辑结构上是前后关系,在存储结构上也是前后关系。
    ===============================================================================
    2、顺序表的操作:
    设有顺序表sq,对顺序表的操作有:
    ⒈建立一个空顺序表(CreateEmptySqList)
    ⒉清空一个顺序表(ClearSqList)
    ⒊判断顺序表是否为空(ListEmpty)
    ⒋求表长(SqListLength)
    ⒌获得表中第i个位置的元素(GetElem)
    ⒍确定某元素在顺序表中的位置(LocateElem)
    ⒎插入一个新的元素(InsertSqList)
    ⒏删除第i个位置的元素(DeleteSqList)
    ⒐遍历该顺序表(PrintSqList)
    ===============================================================================
    3、插入与删除
    有关于顺序表的相关操作,一些操作是十分简单的。例如:求表长,查询第i个位置元素,置空,遍历等。这里不详细讲解。对于顺序表来说,重点要掌握它的插入与删除操作。
    1)获得元素
    对于线性表的顺序存储结构来说,获取第i个位置的元素是非常简单的。
    //代码见附录
    2)插入操作
    举个例子:一队人在排队买票,这时来了一个插队的,他插入到的队伍的第i个位置,那么在他之后的人都要向后挪一步。
    在这个例子中我们已经说明了线性表的顺序存储结构在插入数据时的实现过程。
    插入算法思路:
    ⒈如果插入位置不合理,返回异常
    ⒉如果线性表长度大于等于数组长度,则返回异常或增加容量
    ⒊从最后一个位置开始向前遍历到第i个位置,分别将它们都向后移动一个位置
    ⒋将要插入元素填入位置i处
    ⒌表长加1
    //代码见附录
    3)删除操作
    接着刚才的例子:此时后边排队的人意见很大,这时他冲出了队伍,消失在人群中。于是排队的人群又想蠕虫一样向前移动了一步,队伍又恢复了平静。
    这就是线性表的顺序存储结构删除元素的过程。
    删除算法思路:
    ⒈如果删除位置不合理,返回异常
    ⒉取出删除元素
    ⒊从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
    ⒋表长减1
    //代码见附录
    ===============================================================================
    4、线性表顺序存储结构的优缺点
    优点:
    ⒈无需为表示表中元素之间的逻辑关系而额外增加额外的存储空间
    ⒉可以快速地存取表中任意位置的元素
    缺点:
    ⒈插入和删除操作需要移动大量元素
    ⒉当线性表长度变化较大时,难以确定存储空间的容量
    ⒊可能造成存储空间“碎片”
    ===============================================================================
    下下下下下下下下下下下下下下下下下下半段
    ===============================================================================
    一、线性表的链式存储结构--------- 空表,头插法等有头节点的话很方便,
    前面所讲的线性表的顺序存储结构是有缺点的,最大的缺点就是插入和删除时需要移动大量的元素,这显然就需要耗费大量时间。
    仔细考虑一下产生该问题的原因,在于相邻元素的存储位置也具有邻居关系,它们在内存中是紧挨着的,没有空隙,自然也没有空位进行介入,而删除后留下的空隙自然也需要弥补。
    为了解决上述问题,我们打破常规,不再让相邻元素在内存中紧挨着,而是上一个元素留存下一个元素的“线索”,这样我们找到第一个元素时,根据“线索”自然而然就找到下一个元素的位置;依次类推,通过遍历的方法每一个元素的位置都可以通过遍历找到。(达芬奇密码、国家宝藏)
    ===============================================================================
    1、线性表的链式存储定义
    定义:节点(或译为“结点”)(Node):为了表示每个数据元素ai与其后续数据元素ai+1之间的逻辑关系,对数据ai来说,除了存储本身的数据信息之外,还需要存储一个指示其直接后继信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像,称为节点(Node)。
    定义:单链表:n个节点(ai的存储映像)链接成一个链表,即为线性表的链式存储结构。因为此链表的每个节点中只包含一个指针域,所以叫单链表。
    定义:头指针:我们把链表中第一个节点的存储位置叫做头指针,整个单链表的存储就必须从头指针开始进行。
    但是,单纯使用头指针无法区分一个单链表是否为空 还是 一个单链表不存在。因为二者从头指针的角度来说,都是指针为空,而单链表为空和单链表不存在是两种完全不同的概念。
    为了解决这个问题,我们引入头结点head的概念。头结点即单链表的第一个节点,该节点不存储任何有效数据,实际链表的起点是头结点的后继节点。
    当头结点的后继节点为空,即
    head->next==NULL
    时,此时我们判定该链表为空链表。而当头结点head不存在时,此时我们判定该单链表不存在。
    ===============================================================================
    2、线性表的链式存储结构代码描述
    单链表的存储结构的C语言描述:
    typedef struct Node
    {
    data_t data;
    struct Node *next;
    }Node;
    typedef struct Node *LinkList;
    由代码我们可以看出,节点是由存放数据元素的数据域和存放后继节点的指针域组成的。假设指针p是指向第i个元素ai的指针,则p->data表示ai的数据域,p->next表示ai的指针域。p->next指向下一个元素,即ai+1,也就是说,p->data=ai,p->next->data=ai+1。
    ===============================================================================
    3、链表的操作:
    设有线性表Head,对链表的操作有:
    ⒈建立一个空链表(CreateEmptyLinkList)
    ⒉清空一个链表(ClearLinkList)
    ⒊判断线性表是否为空(LinkListEmpty)
    ⒋整表创建(InsertTail、InsertHead)
    ⒌获得表中第i个位置的元素(GetElem)
    ⒍插入一个新的元素(InsertLinkList)
    ⒎删除第i个位置的元素(DeleteLinkList)
    ⒏遍历该线性表(PrintLinkList)
    ⒐倒置一个链表(LinkListReverse面试经常问到)

    1)单链表的整表创建
    在顺序表中,顺序表的创建其实就是一个数组的初始化过程。而单链表和顺序表的存储结构不同,它不能像顺序表一样整体集中地操作数据,而且单链表是一种动态结构。所以创建单链表的过程实际上是将一个“空表”动态依次建立各元素节点并逐步插入到链表中的过程。
    单链表的整表创建的算法思路(头插法):
    ⒈声明指针p和计数器i
    ⒉初始化一个空链表头结点head
    ⒊让head的结点指针指向NULL,即建立一个带头结点的空单链表
    ⒋循环以下过程:
    ⒋⒈通过指针p生成新节点
    ⒋⒉新节点获得数据,即p->data=数据
    ⒋⒊将p插入到头结点与前一新节点之间
    //代码见附录
    以上代码里,我们让新生成的节点始终处在第一个位置,我们把这种方法称为“头插法”。
    实际上,按照日常生活中“先来后到”的思想,新生成的节点应当插入到当前链表的尾部。若采用这种方法创建单链表,我们称为“尾插法”。
    尾插法的算法思路基本等同于头插法,只需将上文的头插法的算法
    ⒋⒊将p插入到头结点与前一新节点之间
    改为:
    ⒋⒊将p插入到当前链表的尾节点之后
    即可。
    //代码见附录
    注意代码中L与r的关系,L是指向整个单链表,而r是指向当前链表的尾节点。L不会随着循环变换位置,而r会随着循环实时变换位置。

    2)单链表的整表删除
    当我们不打算使用一个链表时,我们应当对其进行销毁,也就是在内存中释放这个链表,以便留出空间供其他程序使用。
    单链表的整表删除的算法思路:
    ⒈声明指针p和q;
    ⒉将链表的第一个节点赋值给p
    ⒊循环以下过程:
    ⒊⒈将p的下一个节点赋值给q
    ⒊⒉释放p
    ⒊⒊将q赋值给p
    //代码见附录
    注意代码中指针q的作用,q的作用是引导指针p,若无指针q的话,在执行free(p)语句之后,指针p就无法找到其下一个节点p->next的位置了,因为该节点的指针域已经随节点一并释放了。

    3)单链表的读取
    在线性表的顺序存储结构中,我们要通过任意位置读取元素的值是十分方便容易的,但在单链表中,对于第i个元素具体在哪无法一开始就得知,必须从头指针开始寻找。因此对于单链表的读取第i个元素的操作在算法上相对要麻烦很多。
    获得单链表第i个元素的算法:
    ⒈定义一个指针指向链表的第一个节点。初始化循环变量j
    ⒉当j<i时,不断让指针p向后移动
    ⒊若到链表结尾p为空,则说明第i个节点不存在,返回错误
    ⒋当p移动到i位置成功时,返回节点p的数据
    //代码见附录
    因为该链表的时间复杂度取决于位置i,因此该算法的时间复杂度为O(n)。
    因为单链表结构定义时没有定义表长,所以无法事先获知循环次数,因此不推荐使用for循环。该算法的主要核心是“当前工作指针”,这其实也是多数关于链表算法的核心思想。
    4)单链表的插入与删除
    单链表的插入与删除操作是单链表的优势之一。插入和删除操作无需像线性表的顺序存储结构一样,插入或删除一个节点需要影响到众多其他节点。
    假设在单链表中,待插入节点的指针为s,s节点的前驱节点为p,则插入操作只需2步即可:
    s->next=p->next;p->next=s;
    但是注意,这两句顺序不可交换。
    如果先让p->next=s;那么下一句s->next=p->next就相当于s->next=s,这样新加入节点s就无法接入它的后继节点了,“临场掉链子”。
    单链表的第i个数据位置插入节点的算法思路:
    ⒈声明一个指针p指向链表头结点,初始化j从1开始
    ⒉当j<i时,遍历链表,即指针p不断向后移动
    ⒊若到链表末尾p为空,则位置i不存在
    ⒋p找到第i个位置,生成待插入空结点s
    ⒌将数据元素e赋值给s->data
    ⒍执行单链表的插入语句:s->next=p->next;p->next=s;
    ⒎返回成功
    //代码见附录

    接下来我们来看单链表的删除。假设第i个位置节点为q,它的前驱节点是p,现在要删除节点q,其实只需将q的前驱节点p绕过q节点指向q的后继节点即可:
    q=p->next;p->next=q->next;
    单链表的第i个数据位置删除节点的算法思路:
    ⒈声明一个指针p指向链表头结点,初始化j从1开始
    ⒉当j<i时,遍历链表,即指针p不断向后移动
    ⒊若到链表末尾p为空,则说明第i个位置的节点不存在
    ⒋p指向q的前驱节点,即q==p->next
    ⒌执行单链表的删除语句:p->next=q->next;
    ⒍将q节点中数据取出作为结果
    ⒎释放q节点
    ⒏返回成功
    //代码见附录
    分析单链表的插入和删除代码,我们可以发现,它们的算法其实都是由两部分组成:第一部分是遍历查找第i个节点,第二部分是对它进行相应的操作。而且我们可以看出,对于第i个节点的操作不会影响到其他位置的节点,这也是单链表比顺序表优势的地方。显然,对于插入/删除比较频繁的操作,单链表的效率要明显高于顺序表。
    ===============================================================================
    4、顺序表与单链表的优缺点
    //见附图2
    通过对比,我们可以得出一些结论:
    ⒈若该线性表需要频繁进行查找操作,而很少进行插入/删除操作时,我们推荐采用顺序表存储。而若该线性表需要频繁进行插入/删除操作时,我们推荐使用单链表。例如在一款游戏中,玩家个人信息除注册时涉及到插入数据外,一般不会发生大的改变,因此我们使用顺序表存储。而玩家的装备列表则会随着玩家的游戏而发生改变,即随时会发生插入/删除操作,这时使用顺序表就不太合适,而应采用单链表。
    ⒉当线性表中的元素数量变化较大,或无法事先预制数目时,我们推荐使用单链表,这样可以无需考虑存储空间大小分配的问题。反之,若我们已事先知道了数据规模(例如1年有12月,1星期有7天等情况),则我们推荐使用顺序表,这样存储效率会高很多。
    总之,顺序表与单链表各有其优缺点,需要在实际情况中权衡需要使用哪种方式。
    ===============================================================================
    练习1:单链表反序
    已有单链表L,编写函数使得单链表的元素反序存储。
    提示:函数原型:int ListReverse(LinkList L)
    //代码见附录
    练习2:已有单链表L存放的数据类型为整型,其头结点为head,编写函数,求单链表中相邻两点数据data之和为最大的一对节点的第一节点的指针。
    提示:函数原型:LinkList Adjmax(LinkList h)
    //代码见附录
    ===============================================================================
    ===============================================================================
    二、循环链表
    若将单链表的尾节点的指针由空改成指向头结点,则将整个单链表形成了一个环,这种头尾相接的单链表称为单循环链表,简称循环链表(Circular linked list)。
    循环链表解决了一个单链表存在的很麻烦的问题:如何从链表的任意节点出发,访问到链表的全部节点。
    同单链表一样,为了解决单循环链表的空表与非空表操作一致问题,我们通常会设置一个头结点,该头结点里不存任何数据(或只存其他无关数据)。这样对于循环的判断结束条件就从p->next是否为空,变成了p->next是否为头结点。
    //代码见附录
    练习:使用单项循环链表求解约瑟夫环问题,其中人数n为33人,每逢m=7人枪毙一人,起始位置为第k=1个人
    /***********约瑟夫环问题描述******************/
    约瑟夫入狱,监狱内共有n=33个犯人。某日33名犯人围成一圈,从第k=1个犯人开始报数,报到数字m=7的犯人出列,被枪毙,下一名犯人重新从1开始报数。依次类推,直至剩下最后1名犯人可被赦免。聪明的约瑟夫在心里稍加计算,算出了最后枪毙的位置,他站在这个位置,最终避免了自己被枪毙,逃出升天。
    问:约瑟夫算出的是哪个位置?
    /***********约瑟夫环问题描述end***************/
    #include <stdio.h>  #include <stdlib.h>  typedef int data_t;  /* use a cycle linked list without header node */  typedef struct node_t  {  data_t data;  struct node_t *next;  } linknode_t, *linklist_t;  //注意:该题目使用的为不带头结点的循环链表  int main()  {  int i, n, m, k;  linklist_t p, q;  printf("total N people will join this suicide game, please input N:");  scanf("%d", &n);  printf( "people stand in a circle, assume everyone is assigned\n"  "a sequence number from 1 to %d.\n"\  "which one would you like to start the number off (1~%d):", n, n);  scanf("%d", &k); printf("every Xth people should kill himself, please decide the X:");  scanf("%d", &m);  if (n < 1 || k > n || m < 1) {  printf("input error!\n");  return -1;  }  printf("game is starting ...\n");  /* added the first one */  //第一部分:创建n个人的循环链表  p = q = (linklist_t)malloc(sizeof(linknode_t));  p->data = 1;  /* added other left people */  for (i = 2; i <= n; i++) {  q->next = (linklist_t)malloc(sizeof(linknode_t));  q = q->next;  q->data = i;  }  /* complete the circle */  q->next = p;  /* find the people ahead of #k */  //第二部分:寻找起始位置  q = p;  while (q->next != p) {  if (q->next->data == k)//寻找起始位置k的前驱节点  break;  q = q->next;  }  //第三部分:开始Johsph环逻辑  while (q->next != q) { /* till the last one */  /* every m people */  for (i = 0; i < m - 1; i++)//删除m号节点需要寻找它的前驱(m-1号)节点  {  q = q->next;  }  /* kill the m-th people */  p = q->next;  q->next = p->next;  printf("%-2d was killed\n", p->data);  free(p);  }  /* kill the last one */  printf("%-2d was alive\n", q->data);  free(q);  return 0;  }
    ===============================================================================
    ===============================================================================
    三、双向链表
    我们在单链表中,有了next指针,它使得我们要查找某节点的下一个节点的时间复杂度为O(1)。可是若要查找某节点的上一个节点,那时间复杂度就是O(n)了。因为我们每次要查找某节点的上一个节点,必须从头指针开始遍历查找。
    为了克服单向性这一缺陷,我们设计出了双向链表。双向链表(double linked list)是在单链表的每个节点中,再设置一个指向其前驱节点的指针域。所以在双向链表的每个节点都有两个指针域,一个指向直接后继,另一个指向直接前驱
    /*双向链表的存储结构*/
    typedef struct DulNode
    {
    data_t data;
    struct DulNode *prior;
    struct DulNode *next;
    }DulNode,*DuLinkList;
    由于双向链表的节点指针有两个,那么对于某节点p,它的后继的前驱是其本身,它的前驱的后继也是其本身,即:
    p->next->prior = p = p->prior->next
    因为双向链表是单链表扩展出来的结构,因此它的很多操作与单链表是基本相同的。比如获得位置i的节点的数据、遍历打印整个链表、求表长等操作,这些操作都只涉及到一个方向的指针(prior或next),另一个方向的指针基本无用,因此操作与单链表本身并无区别。
    对于双向链表的插入/删除操作,需要更改两个指针变量,因此双向链表的插入/删除操作需要注意两个指针变量的操作顺序。
    双向链表的插入操作:向节点p与p->next之间插入节点s
    //见附图3
    注意4步的顺序不能错:
    ①s->prior = p;
    ②s->next = p->next;
    ③p->next->prior = s;
    ④p->next = s;
    由于第二步与第三步都涉及到p->next,如果先行执行第四步的话,会使得p->next节点提前变成s,使得后续的工作无法完成。所以,实现双向链表的插入操作的顺序是:先解决s的前驱和后继,再解决后节点的前驱,最后解决前节点的后继。
    //代码见附录
    双向链表的删除操作比较简单,若要删除节点p,只需两个步骤即可:
    //见附图3
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    //代码见附录
    对于单链表来说,双向链表要复杂一些,对于插入和删除操作要注意其操作顺序。另外每个节点都使用了额外的存储空间来存储前驱节点。但是双向链表有良好的对称性,而且对某节点的前驱节点操作要方便许多。
    ===============================================================================
    ===============================================================================
    展开全文
  • 循环链表(Circular Linked List)是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。 循环单链表的操作和单链表基本一致,差别仅在于:当链表遍历时,判别当前指针p...

    循环链表

    • 循环链表(Circular Linked List)是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

    • 循环单链表的操作和单链表基本一致,差别仅在于:当链表遍历时,判别当前指针p是否指向表尾结点的终止条件不同。在单链表中,判别条件为 p!=L 或 p->next != L。
    • 在某些情况下,若在循环链表中设立尾指针而不设头指针,可使一些操作简化。
    • 当线性表以下图的循环链表作存储结构时,这个操作仅需改变两个指针值即可,主要语句段如下:p=B->next->next;  B->next=A->next;  A->next=p;上述操作的时间复杂度为O(1),合并后的表如下图。

    双向链表

    • 以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱,则必须从表头指针出发。
    • 在单链表中,查找直接后继点的执行时间为O(1),而查找直接前驱的执行时间为O(n)。为克服单链表折中单向性的缺点,可利用双向链表(Double Linked List)。
    • 在双向链表的结点中有两个指针域,一个指向直接后继,另一个指向直接前驱。
    //- - - - -双向链表的存储结构- - - - -
    typedef struct DuLNode
    {
       ElemType data;               //数据域
       struct DuLNode *prior;       //直接前驱
       struct DuLNode *next;        //直接后继
    }DuLNode,*DuLinkList;

     

    • 双向链表也可以有循环表。在双向链表中,若d为指向表中某一结点的指针(即d为DuLinkList型变量),则显然有 d->next->prior=d->prior->next=d。
    • 在双向链表中,有些操作(如ListLength、GetElem和LocateElem等)仅需涉及一个方向的指针,则它们的算法描述和线性链表的操作相同,但在插入、删除时有很大的不同,在双向链表中需同时修改两个方向上的指针。在插入结点时需要修改四个指针,在删除结点时需要修改两个指针。两者的时间复杂度均为O(n)。

    Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
    {//在带头结点的双向链表L中第i个位置之前插入元素e
       if(!(p=GetElem_DuL(L,i)))            //在L中确定第i个元素的位置指针p
         return ERROR;                      //p为NULL时,第i个元素不存在
       s=new DulNode;                       //生成新结点*s
       s->data=e;                           //将结点*s数据域置为e
       s->prior=p->prior;                   //将结点*s插入L中,对应1
       p->prior->next=s;                    //对应2
       s->next=p;                           //对应3
       p->prior=s;                          //对应4
       return OK;
    }
         

    Status ListDelete_DuL(DuLinkList &L,int i)
    {//删除带头结点的双向链表L中的第i个元素
       if(!(p=GetElem_DuL(L,i)))                 //在L中确定第i个元素的位置指针p
          return ERROR;                          //p为NULL时,第i个元素不存在
       p->prior->next=p->next;                   //修改被删结点的前驱结点的后继指针,对应1
       p->next->prior=p->prior;                  //修改被删结点的后继结点的前驱指针,对应2
       delete p;                                 //释放被删结点的空间
       return OK;
    }

    对单链表、循环链表和双向链表的比较

    对顺序表和链表进行比较

    展开全文
  • 目录1.... 单链表与顺序存储结构优缺点4. 循环链表4.1 循环链表定义4.2 循环链表创建4.3 循环链表插入数据4.4 循环链表删除数据4.5 循环链表查询数据位置 1. 链式存储定义 为了表示每个数据元素a...

    1. 链式存储定义

    为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。这两部分信息组成数据元素的存储映像,称为结点。
    n个结点链组成一个链表,即为线性表的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表。
    对于线性表来说,有头有尾,链表中的第一个结点的存储位置叫做头指针,链表的存取必须是从头指针开始进行。
    有时候我了增加对链表操作的方便性,我们会在链表的第一个结点(首元结点)前增加一个结点,称为头结点。头结点的数据域可以不存任何数据,指针域存储第一个结点的指针。
    链式存储结构中我们默认都带上头结点。
    图片示意如下:
    在这里插入图片描述
    在这里插入图片描述
    头指针和头结点的区别:

    头指针:

    • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。
    • 头指针具有标识作用,所以常用头指针冠以链表的名字。
    • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素。

    头结点:

    • 头结点是为了操作的统一和方便而设立的,放在第一个元素的结点前,其数据域一般无意思。
    • 有了头结点,对在第一个元素结点前插入结点和删除第一个结点,与操作其他结点的操作就统一了。
    • 头结点不一定是链表的必要元素。

    2. 单链表

    单链表结点中包含了数据域指针域,如下图所示:
    在这里插入图片描述

    结点定义如下:

    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    /* ElemType类型根据实际情况而定,这里假设为int */
    typedef int ElemType;
    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef int Status;
    //定义结点
    typedef struct Node{
        ElemType data; // 存储在数据域中的数据
        struct Node *next; // 直接后继结点的地址指针
    }Node;
    
    typedef struct Node * LinkList;
    

    2.1 单链表初始化

    思路:

    1. 在内存开辟空间,创建头结点。
    2. 初始化头结点。
    Status InitList(LinkList *L){
        //产生头结点,并使用L指向此头结点
        *L = (LinkList)malloc(sizeof(Node));
        //存储空间分配失败
        if(*L == NULL) return ERROR;
        //将头结点的指针域置空
        (*L)->next = NULL;
        return OK;
    }
    

    2.2 单链表插入数据

    假设要在单链表的两个数据元素A和B之间插⼊一个数据元素e,已知p为其单链表存储结构中指向结点A指针。如下图所示
    在这里插入图片描述

    思路:

    1. 声明一结点p指针指向链表头结点,初始化j从1开始。
    2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,查找插入位置的前一个结点,j累加。
    3. 若到链表末尾p为空,则说明插入的位置不存在。
    4. 否则查找成功,在系统中生成一个空节点s。
    5. 将数据元素e赋值给s->data。
    6. 然后将s->next指向p->next,p->next指向s。
    7. 返回成功。

    代码实现如下:

    /*
     初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
     操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1;
     */
    Status ListInsert(LinkList *L,int i,ElemType e){
        int j;
        LinkList p,s;
        p = *L;
        j = 1;
        //寻找第i-1个结点
        while (p && j<i) {
            p = p->next;
            ++j;
        }
        //第i-1个元素不存在
        if(!p || j>i) return ERROR;
        //生成新结点s
        s = (LinkList)malloc(sizeof(Node));
        //将e赋值给s的数值域
        s->data = e;
        //将p的后继结点赋值给s的后继
        s->next = p->next;
        //将s赋值给p的后继
        p->next = s;
        return OK;
    }
    

    2.3 单链表删除数据

    要删除单链表中指定位置的元素,同插入元素一样,首先应该找到该位置的前驱结点,如下图所示在单链表中删除元素B时,应该首先找到其前驱结点A,为了在单链表中实现元素A,B,C之间的逻辑关系的变化,仅需修改结点A中的指针域即可.
    在这里插入图片描述
    思路:

    1. 声明一结点p指针指向链表头结点,初始化j从1开始。
    2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,查找待删除位置的前一个结点,j累加。
    3. 若到链表末尾p为空,则说明删除的位置不存在。
    4. 否则查找成功,则将q指向要删除的结点。
    5. 将q的直接后继赋值给p的直接后继。
    6. 将q结点中的数据给e。
    7. 释放删除的结点。
    8. 返回成功。

    代码实现如下:

    /*
     初始条件:顺序线性表L已存在,1≤i≤ListLength(L)
     操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1
     */
    Status ListDelete(LinkList *L,int i,ElemType *e){
        int j;
        LinkList p,q;
        p = *L;
        j = 1;
        //查找第i-1个结点,p指向该结点
        while (p->next && j<i) {
            p = p->next;
            ++j;
        }
        //当i>n 或者 i<1 时,删除位置不合理
        if (!(p->next) || j>i) return  ERROR;
        //q指向要删除的结点
        q = p->next;
        //将q的后继赋值给p的后继
        p->next = q->next;
        //将q结点中的数据给e
        *e = q->data;
        //让系统回收此结点,释放内存;
        free(q);
        return OK;
    }
    

    2.4 单链表读取数据

    在单链表中,我们不能像顺序存储结构那样直接通过下标直接获取数据,我们没办法一开始就知道,必须得从头开始找,进行遍历。
    思路:

    1. 声明一结点p指针指向链表首元结点(不是头结点),初始化j从1开始。
    2. 当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加。
    3. 若到链表末尾p为空,则说明读取的元素不存在。
    4. 否则查找成功,返回节点p的数据。

    代码实现如下:

    /*
     初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
     操作结果:用e返回L中第i个数据元素的值
     */
    Status GetElem(LinkList L,int i,ElemType *e){
        int j = 1;
        //声明结点p;
        LinkList p;
        //将结点p 指向链表L的首元结点;
        p = L->next;
        //p不为空,且计算j不等于i,则循环继续
        while (p && j<i) {
            //p指向下一个结点
            p = p->next;
            ++j;
        }
        //如果p为空或者j>i,则返回error
        if(!p || j > i) return ERROR;
        //e = p所指的结点的data
        *e = p->data;
        return OK;
    }
    

    2.5 头插法整体创建链表

    思路:

    1. 声明一个结点p。
    2. 初始化一空链表L。
    3. 让L的头结点的指针指向NULL,即建立一个带头结点的单链表。
    4. 循环:
      ①. 生成一个新的结点赋值给p。
      ②. 给p->data赋值。
      ③.将p插入到头结点之后。

    代码实现如下:

    /* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
    void CreateListHead(LinkList *L, int n){
        LinkList p;
        //建立1个带头结点的单链表
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;
        //循环前插入随机数据
        for(int i = 0; i < n;i++)
        {
            //生成新结点
            p = (LinkList)malloc(sizeof(Node));
            //i赋值给新结点的data
            p->data = i;
            p->next = (*L)->next;
            //将结点P插入到头结点之后;
            (*L)->next = p;
        }
    }
    

    2.6 尾插法整体创建链表

    思路:

    1. 声明一个结点p、r, r指向尾部结点。
    2. 初始化一空链表L。
    3. 让L的头结点的指针指向NULL,即建立一个带头结点的单链表。
    4. 循环:
      ①.生成一个新的结点赋值给p。
      ②.给p->data赋值。
      ③.将p插入到尾部结点r之后。
    5. 将尾结点r的next设置为NULL。

    代码实现如下:

    /* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
    void CreateListTail(LinkList *L, int n){
        LinkList p,r;
        //建立1个带头结点的单链表
        *L = (LinkList)malloc(sizeof(Node));
        //r指向尾部的结点
        r = *L;
        for (int i=0; i<n; i++) {
            //生成新结点
            p = (Node *)malloc(sizeof(Node));
            p->data = i;
            //将表尾终端结点的指针指向新结点
            r->next = p;
            //将当前的新结点定义为表尾终端结点
            r = p;
        }
        //将尾指针的next = null
        r->next = NULL;
    }
    

    2.7 单链表整体删除

    思路:

    1. 声明一个结点p和q。
    2. 将第一个结点赋值给p。
    3. 循环:
      ①. 将下一个结点赋值给q。
      ②. 释放p。
      ③. 将q赋值给p。
    4. 将头结点的next设置为NULL。

    代码实现如下:

    /* 初始条件:顺序线性表L已存在。操作结果:将L重置为空表 */
    Status ClearList(LinkList *L)
    {
        LinkList p,q;
        p=(*L)->next;           /*  p指向第一个结点 */
        while(p)                /*  没到表尾 */
        {
            q=p->next;
            free(p);
            p=q;
        }
        (*L)->next=NULL;        /* 头结点指针域为空 */
        return OK;
    }
    

    3. 单链表与顺序存储结构优缺点

    存储分配方式:

    • 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
    • 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。

    时间性能:

    • 查找
      • 顺序存储结构O(1)。
      • 单链表O(n)。
    • 插入与删除
      • 顺序存储结构需要平均移动表长一半的元素,时间为O(n)。
      • 单链表在找出某位置的指针后,插入和删除时间为O(1)。

    空间性能:

    • 顺序存储结构需要预分配存储空间,分大了,浪费,分小了,容易溢出。
    • 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制。

    通过对比,我们可得知:
    若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。
    当线性表中的元素个数变化较大或者根本不知道有多大的时候,最好采用单链表结构,这样可以不需要考虑存储空间大小的问题。而如果事先知道线性表的大致长度,就可以用这个顺序存储结构,用起来比较高效。

    4. 循环链表

    4.1 循环链表定义

    将单链表中的终端结点的指针从空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。
    为了使空链表与非空链表处理一致,我们通常设一个头结点。
    循环列表中带有头结点的空链表如下图:
    在这里插入图片描述
    对于非空的循环链表如下图:
    在这里插入图片描述

    4.2 循环链表创建

    思路:

    1. 判断链表是否已经存在,即是否已经存在头结点。
    2. 如果存在头结点,那么直接依次往里插入数据。
    3. 如果不存在头结点,那么先创建头结点,然后依次往里插入数据。
    4. 返回OK。

    代码实现:

    /* 创建一个带有头结点的循环链表 */
    Status CreateList(LinkList *L) {
        int item;
        LinkList temp = NULL;
        LinkList r = NULL; // 尾结点指针
        printf("请输入新的结点, 当输入0时结束!\n");
        while (1) {
            scanf("%d",&item);
            if (item == 0) {
                break;
            }
            // 当链表为空时,创建链表,带上头结点。
            if (*L == NULL) {
                *L = (LinkList)malloc(sizeof(Node));
                if (!*L) return ERROR;
                (*L)->next = *L; // 使其next指针指向自己
                r = *L;
            }
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return  ERROR;
            temp->data = item;
            temp->next = *L;
            r->next = temp;
            r = temp;
        }
        return OK;
    }
    

    4.3 循环链表插入数据

    思路:

    1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR。
    2. 先找到插入的位置的前一个结点target,如果插入位置超过链表长度,则自动插入队尾。
    3. 新结点的next指向target原来的next位置,target的next指向新结点。
    4. 返回OK。

    代码实现如下:

    /* 循环链表插入数据 */
    Status ListInsert2(LinkList *L, int place, int num) {
        if (place < 1) {
            return ERROR;
        }
        LinkList target;
        LinkList temp;
        int k;
        temp = (LinkList)malloc(sizeof(Node));
        if (!temp) return ERROR;
        temp->data = num;
        // 查找插入位置的前一个结点
        for (k = 1, target = *L; k < place && target->next != *L; k++, target = target->next);
        temp->next = target->next;
        target->next = temp;
        return OK;
    }
    

    4.4 循环链表删除数据

    思路:

    1. 创建新结点temp,用于记录要删除的元素。
    2. 先找到删除位置的前一个结点target,如果删除的位置大于链表长度,返回ERROR。
    3. 将target->next赋值给temp,temp->next赋值给target->next。
    4. 释放temp。
    5. 返回OK。

    代码实现如下:

    /* 循环链表删除数据,链表表L已存在,1≤place≤ListLength(L) */
    Status LinkListDelete(LinkList *L,int place) {
        if (place < 1) {
            return ERROR;
        }
        LinkList temp, target;
        int k;
        for (k = 1, target = *L; k < place && target->next != *L; k++, target = target->next);
        if (place > k) {
            return ERROR;
        }
        temp = target->next;
        target->next = temp->next;
        free(temp);
        return OK;
    }
    

    4.5 循环链表查询数据位置

    思路:

    1. 创建结点指针p,并将p指向首元结点,声明变量i,用来记录位置。
    2. 循环查找结点值等于value的结点,直到遍历到最后一个节点停止。
    3. 如果已经遍历到最后一个元素,且还没有找到,那么直接返回-1.
    4. 返回查找到的位置。

    代码实现如下:

    /* 循环链表查询值的位置 */
    int findValue(LinkList L, int value) {
        int i = 1;
        LinkList p;
        p = L->next;
        while (p->data != value && p->next != L) {
            i++;
            p = p->next;
        }
        // 如果已经遍历到最后一个元素,且还没有找到,那么直接返回-1.
        if (p->next == L && p->data != value) {
            return  -1;
        }
        return i;
    }
    
    展开全文
  • 单向循环链表 约瑟夫 c++ 利用单向循环链表存储结构模拟约瑟夫问题,按照出列的顺序印出每个人的编号。
  • 线性表 ---顺序存储结构 ---链式存储结构(单链表、静态链表、循环链表、双向链表)

    提示:以下内容不适合零基础人员,仅供笔者复习之用。

    一、线性结构的基本特征:
    1.集合中必存在唯一的一个“第一元素”;
    2.集合中必存在唯一的一个 “最后元素”;
    3.除最后元素在外,均有 唯一的后继;
    4.除第一元素之外,均有 唯一的前驱。
    如:java中的List接口,就是线性表。ArrayList就是顺序线性表,LinkedList就是链表线性表。

    二、线性表的基本操作:
    1.InitList(*L): 初始化操作,建立一个空的线性表L。
    2.ListEmpty(L): 判断线性表是否为空表,若线性表为空,返回true,否则返回false。
    3.ClearList(*L): 将线性表清空。
    4.GetElem(L,i,*e): 将线性表L中的第i个位置元素值返回给e。
    5.LocateElem(L,e): 在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
    6.ListInsert(*L,i,e): 在线性表L中第i个位置插入新元素e。
    7.ListDelete(*L,i,*e): 删除线性表L中第i个位置元素,并用e返回其值。
    8.ListLength(L): 返回线性表L的元素个数。
    ——对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的。对于实际问题中涉及的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现。

    三、两种不同的线性表
    我们知道,数据结构分为逻辑结构物理结构,逻辑结构分为集合结构、线性结构、树形结构和图形结构四大类。物理结构分为顺序存储结构和链式存储结构。
    线性表是线性结构的一种,那么线性表当然也有物理结构,也就是说,线性表有两种,分别是顺序结构的线性表(叫做顺序表)和链式结构的线性表(叫做链表)。

    3.1 顺序存储结构的线性表
    3.1.1 定义
    指的是用一段地址连续的存储单元依次存储线性表的数据元素。和数组不一样,数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。线性表是线性表中数据元素的个数,随着插入和删除的操作,长度会变。所以,这里要区分两个概念,即数组长度和线性表的长度是不一样的。在任意时刻,线性表的长度应该小于等于数组的长度

    3.1.2 存储方式
    因为每个数据元素的类型都相同,所以可以使用一维数组来实现。结构代码如下:

    //线性表的顺序存储结构  
    #define MAXSIZE 20;//存储空间初始分配量为20  
    typedef int ElemType;//数据类型为int  
    type struct  
    {  
        ElemType data[MAXSIZE];//数组存储数据元素  
        int length;//线性表长度  
    }SqList; 

    这里可以看到,顺序存储结构需要三个属性:

    • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
    • 线性表的最大存储容量:数组长度MaxSize。
    • 线性表的当前长度:length。

    3.1.3 地址计算方法
    这里写图片描述
    若每个存储元素占用c个存储单元,那么线性表中元素的位置可以由此计算出:
    这里写图片描述
    通过这个公式,可随时算出线性表中任意位置的地址,使用相同的时间。它的存取时间性能为O(1),这一特点的存储结构称之为随机存取结构。

    3.1.4 操作
    获取元素:

    #define MAXSIZE 20  //存储空间初始分配量
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    
    typedef int ElemType; //ElemType类型根据实际情况而定,这里设为int
    
    Status GetElem(SqList L, int i, ElemType *e){//获取元素
        if (L.length == 0 || i<1 || i>L.length){
            return ERROR;
        }
        *e = L.data[i - 1];
        return OK;
    }

    插入元素:

    • 如果插入位置不合理,抛出异常
    • 如果线性表长度大于等于数组长度,则抛出异常或者动态增加容量
    • 从最后一个元素开始向前遍历到第i个位置,分别将它们向后移动一个位置
    • 将要插入元素填入位置i处
    • 表长度加1
    Status ListInsert(SqList L, int i, ElemType e){//插入操作
        int k;
        if (L.length == MAXSIZE){//顺序线性表已满
            return ERROR;
        }
    
        if (i<1 || i>L.length + 1){//当i不在范围内时
            return ERROR;
        }
    
        if (i <= L.length){//若插入数据的位置不在表尾
            for (k = L.length - 1; k >= i - 1; k--)
            {
                L.data[k + 1] = L.data[k];
            }
        }
    
        L.data[i - 1] = e;//将新元素插入
        L.length++;
        return OK;
    }

    删除元素:

    • 如果删除位置不合理,抛出异常
    • 取出删除元素
    • 从删除元素位置开始遍历到最后一个元素位置,分别将它们向前移动一个位置
    • 表长减1
    Status ListDelete(SqList L, int i, ElemType *e){//删除操作
        int k;
    
        if (L.length==0){//线性表为空
            return ERROR;
        }
    
        if (i<1 || i>L.length + 1){//删除位置不正确
            return ERROR;
        }
    
        *e = L.data[i - 1];
    
        if (i < L.length){//将删除位置的后继元素前移
            for (k = i; k < L.length; k++)
            {
                L.data[k - 1] = L.data[k];
            }
        }
    
        L.length--;
        return OK;
    }
    

    3.1.5 时间复杂度
    在存、读数据时,不管是哪个位置,时间复杂度都是O(1);而插入或删除操作时,时间复杂度都是O(n)。

    3.1.6 优缺点
    优点:

    • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
    • 可以快速地存取表中任一位置的元素

    缺点:

    • 插入和删除操作需要移动大量元素
    • 当线性表长度变化较大时,难以确定存储空间的容量
    • 造成存储空间的“碎片”

    3.2 链式存储结构的线性表
    3.2.1 定义
    单链表:n个结点(ai的存储映像,每个结点中只包括一个指针域)链接成一个链表,即为线性表(a1,a2,….an)的链式存储结构。
    头指针:链表中第一个结点的存储位置。
    这里写图片描述
    头结点:有时为了便于操作,在单链表的第一个结点前附设一个结点,称为头结点。头结点的数据域可以不存信息,可以存线性表的长度等附加信息,头结点的指针域指向第一个结点的指针。
    这里写图片描述

    头指针和头结点的区别
    头指针

    • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
    • 头指针具有标识作用,常用头指针冠以链表的名字
    • 无论链表是否为空,头指针均不为空。头指针是链表的必要元素

    头结点

    • 头结点是为了操作的统一和方便设立的,在第一个元素的结点之前,其数据域一般无意义(或存放链表长度)。
    • 有了头结点,对在第一个元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了
    • 头结点不一定是链表必须要素

    3.2.2 线性表链式存储结构

    typedef struct Node{//线性表的单链表存储结构
        ElemType data;
        struct Node *next;
    }Node;
    
    typedef struct Node *LinkList;//定义LinkList

    这里写图片描述

    3.2.3 单链表的读取

    • 声明一个结点p指向链表第一个结点,初始化j从1开始
    • 当j < i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
    • 若到链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,返回结点p的数据
    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
    /* 操作结果:用e返回L中第i个数据元素的值 */
    Status GetElem(LinkList L,int i,ElemType *e)
    {
        int j;
        LinkList p;     /* 声明一结点p */
        p = L->next;        /* 让p指向链表L的第一个结点 */
        j = 1;      /*  j为计数器 */
        while (p && j<i)  /* p不为空或者计数器j还没有等于i时,循环继续 */
        {   
            p = p->next;  /* 让p指向下一个结点 */
            ++j;
        }
        if ( !p || j>i ) 
            return ERROR;  /*  第i个元素不存在 */
        *e = p->data;   /*  取第i个元素的数据 */
        return OK;
    }

    说白了,就是从头开始找,直到第i个元素为止。最好情况的时间复杂度为O(1),最坏情况的时间复杂度为O(n)

    3.2.4 单链表的插入
    这里写图片描述
    ① s->next = p->next;
    ② p->next = s;
    注意以上顺序不能颠倒,否则p->next给覆盖成s的地址了,这样,a(i+1)结点就没有了上级。

    算法思路:

    • 声明一个结点p指向链表第一个结点,初始化j从1开始
    • 当j<1时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
    • 若到链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,在系统中新生成一个空结点s
    • 将数据元素e赋值为s->data
    • 单链表的插入标准语句s->next=p->next;p->next=s;
    • 返回成功
    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */
    /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */
    Status ListInsert(LinkList *L,int i,ElemType e)
    { 
        int j;
        LinkList p,s;
        p = *L;   
        j = 1;
        while (p && j < i)     /* 寻找第i个结点 */
        {
            p = p->next;
            ++j;
        } 
        if (!p || j > i) 
            return ERROR;   /* 第i个元素不存在 */
        s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
        s->data = e;  
        s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
        p->next = s;          /* 将s赋值给p的后继 */
        return OK;
    }

    3.2.5 单链表的删除
    这里写图片描述
    实际上就是一步,p->next=p->next->next;用q取代p->next,即是:
    q=p->next;
    p->next=q->next;

    算法思路:

    • 声明一个结点p指向链表第一个结点,初始化j从1开始
    • 当j<1时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
    • 若到链表末尾p为空,则说明第i个元素不存在
    • 否则查找成功,将要删除的结点p->next赋值给q
    • 单链表的删除标准语句p->next=q->next;
    • 将q结点中的数据赋值给e,作为返回
    • 释放q结点
    • 返回成功
    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
    /* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */
    Status ListDelete(LinkList *L,int i,ElemType *e) 
    { 
        int j;
        LinkList p,q;
        p = *L;
        j = 1;
        while (p->next && j < i)    /* 遍历寻找第i个元素 */
        {
            p = p->next;
            ++j;
        }
        if (!(p->next) || j > i) 
            return ERROR;           /* 第i个元素不存在 */
        q = p->next;
        p->next = q->next;          /* 将q的后继赋值给p的后继 */
        *e = q->data;               /* 将q结点中的数据给e */
        free(q);                    /* 让系统回收此结点,释放内存 */
        return OK;
    }

    3.2.6 单链表操作的时间复杂度
    分析单链表的插入和删除算法,第一步就是遍历查找到第i个元素;第二步就是插入和删除元素。容易看出,它们的时间复杂度都是O(n),如果在不知道第i个元素的指针位置,单链表数据结构在插入和删除操作上,与线性表的顺序存储结构是没有太大优势的。但如果,我们希望从第i个位置,插入10个元素,对于顺序存储结构意味着,每一次插入都需要移动n-i个元素,每次都是O(n),而单链表,我们只需要在第一次时,找到第i个位置的指针,此时为O(n),接下来只是简单地通过赋值移动指针而已,时间复杂度都是O(1)。显然,对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显

    3.2.7 单链表的整表创建
    因为单链表占用空间的大小和位置是不需要预先分配划定的,可以根据系统的实际情况和需求即时生成。其创建的过程就是一个动态生成链表的过程,即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。
    算法思路:

    • 声明一结点p和计数器变量i
    • 初始化一空链表L
    • 让L的头结点的指针指向NULL,即建立一个带头结点的单链表
    • 循环:
      生成一个新结点赋值给p
      随机生成一数字赋值给p的数据域p->data
      将p插入到头结点与前一新结点之间
    /*  随机产生n个元素的值,建立带表头结点的单链线性表L(头插法) */
    void CreateListHead(LinkList *L, int n) 
    {
        LinkList p;
        int i;
        srand(time(0));                         /* 初始化随机数种子 */
        *L = (LinkList)malloc(sizeof(Node));
        (*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
        for (i=0; i<n; i++) 
        {
            p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
            p->data = rand()%100+1;             /*  随机生成100以内的数字 */
            p->next = (*L)->next;    
            (*L)->next = p;                     /*  插入到表头 */
        }
    }

    以上是使用头插法实现,还可以使用尾插法实现,即按排队顺序,先来后到,每次加入的新结点都插在终端结点后面:

    /*  随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法) */
    void CreateListTail(LinkList *L, int n) 
    {
        LinkList p,r;
        int i;
        srand(time(0));                      /* 初始化随机数种子 */
        *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
        r=*L;                                /* r为指向尾部的结点 */
        for (i=0; i<n; i++) 
        {
            p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
            p->data = rand()%100+1;           /*  随机生成100以内的数字 */
            r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
            r = p;                            /* 将当前的新结点定义为表尾终端结点 */
        }
        r->next = NULL;                       /* 表示当前链表结束 */
    }

    3.2.8 单链表的整表删除
    算法思路:

    • 声明一结点p和q
    • 将第一个结点赋值给p
    • 循环:
      将下一结点赋值给q
      释放p
      将q赋值给p
    /* 初始条件:顺序线性表L已存在。操作结果:将L重置为空表 */
    Status ClearList(LinkList *L)
    { 
        LinkList p,q;
        p=(*L)->next;           /*  p指向第一个结点 */
        while(p)                /*  没到表尾 */
        {
            q=p->next;
            free(p);
            p=q;
        }
        (*L)->next=NULL;        /* 头结点指针域为空 */
        return OK;
    }

    提示:q变量很重要,不能直接free(p);因为:p是一个结点,除了数据域,还有指针域。free(p);是对整个结点进行删除和内存释放的工作。而变量q的作用是,使得下一个结点得到了记录,以便于释放当前结点后,把下一结点拿回来补充。(类似皇帝的遗嘱)

    3.3 单链表结构与顺序存储结构优缺点
    对单链表结构和顺序存储作对比:
    这里写图片描述
    经分析,可得出一些经验结论:

    • 若线性表需要频繁查找,很少进行插入、删除操作,宜采用顺序存储结构。若需要频繁插入和删除时,宜采用单链表结构。比如游戏开发中,用户注册的个人信息,除注册时插入数据外,绝大多数是读取,所以应该考虑顺序存储结构。而玩家的武器或装备列表,可能随时增加或减少,这时可以考虑单链表结构。
    • 当线性表中的元素个数变化较大或根本不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间的大小问题。而事先知道线性表的大致长度,比如一年12个月,这种用顺序结构效率会高很多。

    3.4 静态链表(链表的游标实现)
    数组描述的链表叫做静态链表。数组的每个下表都对应一个data和一个cur,数据域data用于存放数据元素,cur相当于单链表中的next指针,存放该元素后继在数组中的下标。

    /* 线性表的静态链表存储结构 */
    #define MAXSIZE 1000 /* 存储空间初始分配量 */
    
    typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef char ElemType;        /* ElemType类型根据实际情况而定,这里假设为char */
    
    /* 线性表的静态链表存储结构 */
    typedef struct 
    {
        ElemType data;
        int cur;  /* 游标(Cursor) ,为0时表示无指向 */
    } Component,StaticLinkList[MAXSIZE];

    补充概念:备用链表——未被使用的数组元素。
    静态链表特点:

    • 数组的第一个元素,即下标为0的元素的cur就存放备用链表的第一个结点的下标;
    • 数组的最后一个元素的cur则存放第一个有数值的元素的下标,相当于单链表中头结点的作用,当整个链表为空时为0。

    这里写图片描述
    3.4.1 初始化:

    /* 将一维数组space中各分量链成一个备用链表,space[0].cur为头指针,"0"表示空指针 */
    Status InitList(StaticLinkList space) 
    {
        int i;
        for (i=0; i<MAXSIZE-1; i++)  
            space[i].cur = i+1;
        space[MAXSIZE-1].cur = 0; /* 目前静态链表为空,最后一个元素的cur为0 */
        return OK;
    }

    假设已存入甲、乙、丁、戊、己、庚等数据,则存储分配示意如下:
    这里写图片描述

    3.4.2 插入:
    静态链表中要解决的是,如何用静态模拟动态链表结构的存储空间的分配,需要时申请,无用时释放。可将所有未被使用的及已被删除的分量用游标链成一个备用的链表,每当进行插入时,便可以从备用链表上取得第一个结点作为待插入的新结点。

    /* 若备用空间链表非空,则返回分配的结点下标,否则返回0 */
    int Malloc_SSL(StaticLinkList space) 
    { 
        int i = space[0].cur;                   /* 当前数组第一个元素的cur存的值 */
                                                /* 就是要返回的第一个备用空闲的下标 */
        if (space[0]. cur)         
            space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了, */
                                                /* 所以我们就得把它的下一个 */
                                                /* 分量用来做备用 */
        return i;
    }

    这段代码用于返回一个下标值,即数组头元素的cur存的第一个空闲的下标,如上图的话,应该返回7。
    如果在上述存储内容中继续插入丙,步骤是,先把丙放在位置7,把乙的cur改为7,再把丙的cur改为3,这样就完成了插入。

    /*  在L中第i个元素之前插入新的数据元素e   */
    Status ListInsert(StaticLinkList L, int i, ElemType e)   
    {  
        int j, k, l;   
        k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
        if (i < 1 || i > ListLength(L) + 1)   
            return ERROR;   
        j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
        if (j)   
        {   
            L[j].data = e;   /* 将数据赋值给此分量的data */
            for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
               k = L[k].cur;           
            L[j].cur = L[k].cur;    /* (逻辑重点)把第i个元素之前的cur赋值给新元素的cur */
            L[k].cur = j;           /* (逻辑重点)把新元素的下标赋值给第i个元素之前元素的cur */
            return OK;   
        }   
        return ERROR;   
    }

    调用时输入i为3,
    第4行k=MAXSIZE-1=999。
    第7行,j=7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8。(Malloc_SSL方法内更新备用链表首结点位置
    第11-12行,for循环l由1到2,执行两次,代码k=L[k].cur;使得k=999,得到k=L[999].cur=1,再得到k=L[i].cur=2。
    第13行,L[j].cur=L[k].cur;因j=7,而k=2得到L[7].cur=L[2].cur=3。就是刚说的把丙的cur改为3。
    第14行,L[k].cur=j;意思就是L[2].cur=7。也就是把乙的cur改为指向丙的下标7。
    这里写图片描述

    3.4.3 删除:
    如果要删除甲,这个位置就空出来,有新元素进来就优先考虑这里,所以原来的第一个空位分量,即下标是8 的分量要降级了(后退为备用链表的第二个结点),把8给“甲”所在下标为1的分量的cur,也就是space[1].cur=space[0].cur=8,而space[0].cur=k=1就是让这个删除的位置称为第一个优先空位,把它存入第一个元素的cur中,如图:
    这里写图片描述
    相关代码描述:

    /*  将下标为k的空闲结点回收到备用链表 */
    void Free_SSL(StaticLinkList space, int k) 
    {  
        space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
        space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
    }
    
    /*  删除在L中第i个数据元素   */
    Status ListDelete(StaticLinkList L, int i)   
    { 
        int j, k;   
        if (i < 1 || i > ListLength(L))   
            return ERROR;   
        k = MAXSIZE - 1;   
        for (j = 1; j <= i - 1; j++)   
            k = L[k].cur;   
        j = L[k].cur;   
        L[k].cur = L[j].cur;   
        Free_SSL(L, j);   
        return OK;   
    } 

    3.4.4 静态链表优缺点:
    这里写图片描述
    总的说,静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法。虽使用较少,但思考方式比较巧妙,思想值得借鉴。

    3.5 循环链表
    将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。
    循环链表解决了一个问题:如何从当中一个结点出发,访问到链表的全部结点。
    为使空链表与非空链表处理一致,通常设置一个头结点。
    循环链表带有头结点的空链表如图:
    这里写图片描述
    非空的循环链表如图:
    这里写图片描述
    循环链表和单链表的主要差异就在于循环的条件判断上,原来是p->next是否为空,现在是p->next不等于头结点,则循环未结束。
    如果用头指针表示循环链表,则需O(n)时间找到最后一个结点。若改用尾指针表示循环链表,此时查找开始结点和终端结点都很方便了。(这是由循环链表的特点决定的)如图:
    这里写图片描述
    此时若尾指针用rear指示,则查找终端结点时间是O(1),而开始结点,其实就是rear->next->next,其时间复杂也为O(1)。

    3.5.1 循环链表的合并:
    合并时,有了尾指针就非常简单了。如图:
    这里写图片描述
    操作如下:
    这里写图片描述

    p=rearA->next;    /*保存A表的头结点,即①*/
    rearA->next=rearB->next->next;    /*将本是指向B表的第一个结点(不是头结点)赋值给reaA->next,即②*/
    rearB->next=p;    /*将原A表的头结点赋值给rearB->next,即③*/
    free(p);    /*释放p*/

    以上代码free(p);出自书中,笔者认为有误,应该是释放rearB->next。敬请读者发表意见。

    3.6 双向链表
    在单链表的每个结点中,再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。
    双向链表的循环带头结点的空链表如图:
    这里写图片描述
    非空的循环的带头结点的双向链表如图:
    这里写图片描述
    其中某个结点的前驱的后继是自身,后继的前驱也是自身。

    3.6.1 插入
    注意顺序:
    这里写图片描述
    顺序是:先搞定s的前驱和后继,再搞定后结点的前驱,最后解决前结点的后继
    s->prior=p;//①
    s->next=p->next;//②
    p->next->prior=s;//③
    p->next=s;//④

    3.6.2 删除
    这里写图片描述
    p->prior->next=p->next;//①
    p->next->prior=p->prior;//②

    3.6.3 特点
    由于多了prior指针,对于插入和删除操作要注意。因为每个结点是两份指针,所以在空间上是要占用略多。不过因为良好的对称性,使得对某个结点的前后结点的操作带来了方便,可以有效提高算法的时间性能。即,用空间换时间

    3.7 总结
    线性表
    —顺序存储结构
    —链式存储结构(单链表、静态链表、循环链表、双向链表)

    参考:
    《大话数据结构》

    展开全文
  • 循环链表:在单链表中,如果将终端结点的指针域由空指针改为指向头结点,就使得整个单链表形成一个环,这种头尾相接的单链表称为循环单链表,简称循环链表。 在用头指针指示的循环链表中,找到开始结点的时间是O(1...
  • 严蔚敏吴伟民版《数据结构》课本源码第2章线性表第8节双循环链表链式存储结构
  • 数据结构中的线性表 是理解图,堆栈,二叉树的基础,他的官方定义为:线性表 是 零个或多个数据元素的有限序列。比如:a1, a2, a3 ,a4, ...... , ai-1, ai, ai+1,....., anai-1 是ai的前驱元素,而ai+1是ai的后继...
  • 线性表之顺序存储结构和链式存储结构

    万次阅读 多人点赞 2018-09-28 14:17:06
    线性表包括顺序表和链表,其中链表又包括单链表、循环链表、双向链表。 顺序存储结构和链式存储结构有所不同,具体区别如下表所示: 通过上面的对比,可以得出一些经验性的结论: 若线性表需要频繁查找,很少...
  • 顺序表与链表比较4.1 存取方式4.2 逻辑结构、物理结构4.3 基本操作4.4 内存空间总结4.5 怎样选择线性表的存储结构4.6 三个常用操作4.6.1 最值:4.6.1.1 顺序表4.6.1.2 单链表4.6.2 逆置4.6.2.1 顺序表:4.6.2.2 ...
  • 链式存储结构中栈、队列、循环链表,都是在上篇的单链表基础上进行实现的。话不多说先看链式存储的栈。 栈 先看一下的类图: 接下来是实现: public class LinkedStack<E> implements Stack<E>{ ...
  • 文章目录链式存储结构单链表单链表的读取插入 删除整表创建 整表删除单链表 与 顺序存储结构 的优缺点静态链表循环链表双向链表总结 链式存储结构 为了表示每个数据 ai 与其直接后继数据元素 a_(i+1) 之间的逻辑...
  • 线性表:顺序表(数组)、链表 栈:插入和删除都限制在表的同一端进行(后入先出) 队列:插入在一端,删除在另一端(先进先出) //线性表类模板如下,是顺序表类和链表类的基类,用虚函数virtual template...
  • 文章目录链表思维 链表思维 动态创建链表:动态内存申请+模块化设计 创建链表(创建一个表头表示整个链表) 创建结点 插入结点 删除结点 打印遍历链表(测试用一般) 创建链表
  • 线性表 是一种数据结构:n个数据元素的有限序列 表示形式: L = (a1,a2...an) a1是线性表的元素,小写。 ...相邻元素之间存在序偶关系:即有唯一的第一和最后一个元素,除了第一个元素外...存储结构顺序、链式...
  • 它的实现方式有很多,下面用顺序表、单链表、双链表、循环链表来对它进行实现。   线性表的抽象数据类型 数据元素:可以为任意类型,只要同属于一种数据类型即可; 数据关系:数据元素之间呈线性关系; 数据...
  • 一、实验原理 ...一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数直到报m的人,将此人删除,并将他的密码作为新的m值,从他在顺时针方向... 实现:利用单向循环链表存储结构模拟约瑟
  • 线性表从存储结构上分为:顺序存储结构(数组)和 链式存储结构(链表顺序存储结构:是用一段连续的内存空间存储表中的数据 L=(a1,a2,a3....an) 链式存储结构:是用一段一段连续的内存空间存储表中每一行的数据...
  • 今天总结线性表中的双向循环链表。 什么是双向循环链表?  看名字估计也就知道了,首相他是一个循环链表,也就是最后一个结点的指针域不为空,而是指向头结点,其次与单向循环链表相比,它是双向的。所谓双向,...
  • 循环链表与双向链表

    千次阅读 2014-04-21 14:55:36
    1、循环链表 循环链表也是一种链式存储结构,他的
  • 循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。    双向循环链表——在双链表中,将终端结点的下一个(Next)指针域NULL改为指向表头结点或开始结点...
  • 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。其次,数据结构中的链表在面试中是常常被...
  • 循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。    单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。  循环...
  • 循环链表

    2017-03-30 10:37:42
    循环链表 将单链表中终端节点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表循环链表的判断条件循环链表和单链表的主要差异就在于循环的判断...
  • 写在前面的 顺序表 插入 删除 定位 单链表 插入 删除 双向循环链表 删除 ...总结写在前面的 在复习... 接下来主要总结一下单链表和循环链表的插入与删除的方法和具体的代码。导图如下 顺序表插入 步骤:首先将节点依次
  • 2、顺序存储结构: 三个重要属性:  存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置  线性表的最大存储容量:数组data的长度MAXSIZE(这里是20)  线性表的当前长度:length 顺序存储...
  • 数据结构-双循环链表

    2017-06-15 11:29:38
    循环列表dcList结构循环列表中有三个成员ListNode * first、 ListNode * last、 size_t size , 三个成员变量分别是,指向头结点的指针,指向尾部节点的指针,以及链表的大小(即结点的个数)。 其结点...
  • 顺序存储结构: 定义:在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,以数据元素为单位,按数据元素在表中的次序存储。 优点: 不用为表示节点间的逻辑关系而增加额外的存储开销。 具有按...
  • 还记得数据结构这个经典的分类图吧: pic1 今天主要关注一下线性表。 什么是线性表 线性表的划分是从数据的逻辑结构上进行的。线性指的是在数据的逻辑结构上是线性的。即在数据元素的非空有限集中 (1) 存在唯一的...
  • 双向循环链表和链表实现LRU

    千次阅读 2018-12-27 17:50:52
    循环链表的概念 如上图所示:单链表的尾结点指针指向空地址,表示这就是...和单链表相比,循环链表的优点是从链尾到链头比较方便,当要处理的数据具有环型结构特点时,适合采用循环链表。 双向链表概念 双向链表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 88,084
精华内容 35,233
关键字:

循环链表是顺序存储结构吗