线性表简单介绍和使用

Question

一、线性表的定义

线性表（List）：由零个或多个数据元素组成的有限序列。

这里需要强调几个关键的地方：

• 首先它是一个序列，也就是说元素之间是有个先来后到的。
• 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，而其他元素都有且只有一个前驱和后继。
• 另外，线性表强调是有限的，事实上无论计算机发展多强大，它所处理的元素都是有限的。

二、数据类型的定义

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称（整型、浮点型、字符型）。

三、线性表的抽象数据类型

Operation

• InitList(*L)：初始化操作，建立一个空的线性表。
• ListEmpty(L)：判断线性表是否为空表，若线性表为空，返回true,否则返回false。
• ClearList(*L)：将线性表清空。
• GetElem(L,i,*e)：将线性表L中的第i个位置元素值返回给e。
• LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功。否则，返回0表示失败。
• ListInsert(*L,i,e)：在线性表L中第i个位置插入新元素e。
• ListDeleted(l,i,e)：删除线性表L中第i个位置元素，并用e返回其值。
• ListLength(L)：返回线性表L的元素个数。

//AUB

//La表示A集合，Lb表示B集合
void unionL(List *La,List Lb){
  int La_len ,Lb_len,i;
  ElemType e;

  La_len = ListLength(*La);
  Lb_len = ListLength(Lb);

  for(i = 1;i<=Lb_len;i++){
    GetElem(Lb,i,&e)
    if(!LocateElem(*La,e)){
      ListInsert(La,++La_len,e);
    }
  }
}

四、线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。（像 C 语言的数组）

物理上的存储方式实际上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。

顺序存储结构的结构代码

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
  ElemType data[MAXSIZE];
  int length;//线性表当前长度
} SqList;

大家看到了，这里我们封装了一个结构，事实上就是对数组进行封装，增加了一个当前长度的变量罢了。

总结下，顺序存储结构封装需要三个属性：

1. 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
2. 线性表的最大存储容量：数组的长度MAXSIZE
3. 线性表的当前长度：length

地址计算方法

假设ElemType占用的是C个存储单元（字节），那么线性表中第i+1个数据元素和第i个数据元素的存储位置关系是(Loc表示获得存储位置的函数)：LOC(ai+1) = LOC(ai) + c;

所以对于第i个数据元素ai的存储位置可以由a1推算出：LOC(ai) = LOC(a1) + (i-1)*c;

通过这个公式，我们可以随时计算出线性白哦中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么它的存储时间性能当然就为O(1)，我们通常称为随机存储结构。

获得元素操作

实现GetElem的具体操作，即将线性表L中的第i个位置元素值返回。就程序而言非常简单了，我们只需要把数组第i-1下标的值返回即可。

GetElem.c

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
//Status是函数的类型，其值是函数结果的状态码，入OK等。
//初始条件：顺序线性表L已存在，1 <= i <= ListLength(L)
//操作结果：用e返回L中第i个数据元素的值

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;
}

插入操作

插入算法的思路：

1. 如果插入位置不合理，抛出异常；
2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；
3. 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；
4. 将要插入元素填入位置i处；
5. 线性表长度+1。

ListInsert.c

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e,L长度+1

Ststus ListInsert(SqList *L,int i;ElemTYpe e){
  int k;
  if(L->length == MAXSIZE){//顺序线性表已经满了
    return ERROR;
  }
  if(i<1 || i>L->length){//当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. 如果删除位置不合理，抛出异常；
2. 取出要被删除的元素；
3. 从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；
4. 表长-1。

ListDeleted.c

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1

Status ListDeleted(SqList *L,int i,ElemType *e){
  int k;

  if(L->length == 0){
    return ERROR;
  }
  if(i<1 || i>L->length){
    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;
}

性能分析

现在我们分析一下，插入和删除的时间复杂度。

• 最好的情况：插入和删除操作刚好要求在最后一个位置，因为不需要移动任何元素，所以此时的时间复杂度为 O(1)。
• 最坏的情况：如果要插入和删除的位置是第一个元素，那就意味着要移动所有的元素像后或者向前，所以这个时间复杂度为 O(n)。

至于平均情况，就去中间值 O((n-1)/2) = O(n)。

线性表的优缺点

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是 O(1)。而在插入或删除时，使劲复杂度都是O(n)。

这就说明，他比较适合元素个数比较稳定，不经常插入和删除，而更多的操作是存取数据的应用。

优点：
1、无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
2、可以快速的存取表中的任意位置的元素。

缺点：
1、插入和删除操作需要移动大量元素。
2、当线性表长度变化较大时，难以确定存储空间的容量。
3、容易造成存储空间的“碎片”。

五、线性表的链式存储结构

线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。

比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为执指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为节点(Node)。

因为此链表的每个节点中包含一个指针域，所以叫做单链表。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中的第一个节点的存储位置叫做头指针，最后以客观节点指针为空(NULL)

头指针与头节点的异同

头节点的数据域一般不存储任何信息

头指针

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

头节点

头节点是为了操作的统一和方便而设立的，方在第一个元素的节点前，其数据域一般无意义（但也可以用来存放链表的长度）。有了头节点，对在第一个元素节点前插入节点和删除第一个节点其操作与其他节点的操作就统一了。头节点不一定是链表的必须要素。

我们在C语言中可以用结构指针来描述单链表

typedef struct Node{
  ElemType data;//数据域
  struct Node *Next;//指针域
}Node;
typedef struct Node *LinkList;

我们看到节点由存放数据元素的数据域和存放后继节点地址的指针域组成。

单链表的读取

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。

但是在单链表中，由于第i个元素到底在哪？我们压根没办法一开始就知道，必须得从第一个节点开始挨个找。

因此，对于单链表实现获取第i个元素的数据的操作GetElem，在算法上相对要麻烦一些。

获得链表第i个数据的算法思路：

1、申明一个节点p指向链表的第一个节点，初始化j从1开始；

2、当j<i时，就遍历链表，让p的指针像后移动，不断指向下一个节点，j+1;

3、若到链表末尾p为空，则说明第i个元素不存在；

4、若查找成功，返回节点p的数据。

GetElem.c

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：用e返回L中第i个数据元素的值

Status GetElem(LinkList L,int i,ElemType *e){
  int j;
  LinkList p;

  p = L->next;
  j = 1;

  while(p && j<i){
    p = p->next;
    ++j;
  }

  if(!p || j>i){
    return ERROR;
  }
  *e = p->data;
  return OK;
}

说白了，就是从头开始找，知道第i个元素为止。

由于这个算法的时间复杂度取决于i的为止，当i=1时，则不需要遍历，而i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度为O(n)。

由于单链表的结构中没有定义表长，所以不能实现知道要循环多少次，因此也就不方便使用for来控制循环。

其核心思想叫做“工作指针后移”，这其实也是很多算法的常用技术。

单链表的插入

假设存储元素e的节点为s，要实现节点p、p->next和s之间逻辑关系

我们思考后发觉根本用不着惊动其他节点，只需要让s->next和p->next的指针做一点变化。

s->next = p->next;
p->next = s;

那么我们考虑一下大部分初学者最容易搞坏脑子的问题：这两句代码的顺序可以可以交换过来？

p->next = s;
s->next = p->next;

如果先执行 p->next = s 的话会先被覆盖为s的地址，那么 s->next = p->next 其实就等于 s->next = s 了。

所以这两句是无论如何不能弄反的，这点初学者一定要注意。

单链表第i个数据插入节点的算法思路：

1、声明一节点p指向链表头节点，初始化j从1开始；

2、当j<i时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1;

3、若到链表末尾p为空，则说明第i个元素不存在；

4、否则查找成功，在系统中生成一个空节点s；

5、将数据元素e复制给 s->data；

6、单链表的插入刚才两个标准语句；

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;

  while(p && j<i){
    p = p->next;
    j++;
  }

  if(!p || j>i){
    return ERROR;
  }

  s = (LinkList)malloc(sizeof(Node));
  s->data = e;

  s->next = p->next;
  p->next = s;

  return OK;
}

单链表的删除

假设元素a2的节点为q，要实现节点q删除单链表的操作，其实就是将它的前继节点的指针绕过指向后继节点即可。

那我们要做的，实际上就是一步：

p->next = p->next->next;
或
q = p->next;
p->next = q->next;

单链表的删除节点的算法思路：

1、申明节点p指向链表第一个节点，初始化j = 1;

2、当j<i时，就遍历链表，让P的指针向后移动，不断指向下一个节点，j累加1;

3、若到链表末尾p为空，则说明第i个元素不存在；

4、否则查找成功，将欲删除节点p->next赋值给q;

5、单链表的删除标准语句p->next = q->next;

6、将q节点中的数据赋值给e,作为返回；

7、释放q节点。

Status ListDeleted(LinkList *L,int i,ElemType e){
  int j;
  LinkList p,q;

  p = *L;
  j = 1;

  while(p && j<i){
    p = p->next;
    j++;
  }

  if(!(p->next) || j>i){
    return ERROR;
  }

  q = p->next;
  p->next = q->next;

  *e = q->data;
  free(q);

  return OK;
}

效率PK

我们发现无论是单链表插入还是删除算法，他们其实都是由两部分组成：第一部分就是遍历查找第i个元素，第二部分就是实现插入和删除元素。

从整个算法来书，我们很容易可以退出他们的时间复杂度都是O(n)。

在详细点分析：如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。

但如果，我们希望从第i个位置开始，插入连续10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-1个位置，所以每次都是O(n)。

而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n),接下来只是简单的通过复制移动指针而已，时间复杂度都是O(1)。

显然，对于插入或删除数据越频繁的擦欧总，单链表的效率优势就越是明显。

单链表的正表创建

对于顺序存储结构的线性表的整表创建，我们可以用数组的初始化来直观理解。

而单链表和顺序存储结构就不一样了，它不像顺序存储结构数据这么集中，它的数据可以是分散在内存各个角落的，它的增长也是动态的。

对于每个链表来说，它所占用空间的大小和位置是不需要鱼线分配划定的，可以根据系统的情况和实际的需求即时生成。

创建单链表的过程是一个动态生成链表的过程，从“空表”的初始状态起，依次建立各个元素节点并逐个插入链表。

所以，单链表整表创建的算法思路如下：

1. 声明一个节点P和计数器变量i；
2. 初始化一空链表L;
3. 让L的头节点的指针指向NULL,即建立一个带头节点的单链表；
4. 循环实现后继节点的复制和插入。

头插法建立单链表

头插法从一个空表开始，生成新节点，读取数据存放到新节点的数据域中，然后将新节点插入到当前链表的表头上，直到结束为止。

简单来说，就是把新加进的元素放在表头后的第一个位置：

先让新节点的next指向头节点之后

然后让表头的next指向新节点

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;
    p->next = (*L)->next;
    (*L)->next = p;
  }
}

尾插法建立单链表

头插法建立链表虽然算法简单，但生成的链表中节点的次序和输入的顺序相反。

void CreateListTail(LinkList *L,int n){
  LinkList p,r;
  int i;

  srand(time(0));//初始化随机数字

  *L = (LinkList)malloc(sizeof(Node));
  r = *L;

  for(i=0;i<n;i++){
    p = (LinkLIst)malloc(sizeof(Node));//生成新节点
    p->data = rand()%100+1;
    r->next = p;
    r = p;//备注：初学者可能很难理解这句，重点解释。
  }
  r->next = NULL;
}

单链表的整表删除

单链表整表删除的算法思路如下：

1. 申明节点 p 和 q;
2. 将第一个节点赋值给 p，下一节点赋值给 q；
3. 循环执行释放p和将q复制给p的操作；

Status ClearList(LinkList *L){
  LinkList p,q;

  p = (*L)->next;

  while(p){
    q = p->next;
    free(p);
    p = q;
  }
  (*L)->next = NULL;
  return OK;
}

六、单链表结构与顺序存储结构优缺点

我们分别从存储分配方式、时间性能、空间性能三方面来做对比。

存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。

单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。

时间性能

1.查找

顺序存储结构O(1)

单链表O(n)

2.插入和删除

顺序存储结构需要平均移动表长一般的元素，时间为O(n)

单链表在计算出某位置的指针后，插入和删除时间仅为O(1)

空间性能

顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出。

单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

经验性结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。

若需要频繁插入和删除时，宜采用单链表结构。

七、静态链表

在讲解原理之前，先让大家直到这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。

线性表的静态链表存储结构

#define MAXSIZE 1000
typedef struct{
  ElemType data;//数据
  int cur;//游标
}Component,StaticLinkList[MAXSIZE];

对静态链表进行初始化相当于初始化数组：

Status InitList(StaticLinkList space){
  int i;
  for(i=0;i<MAXSIZE-1;i++){
    space[i].cur = i+1;
  }

  space[MAXSIZE-1].cur = 0;
  return OK;
}

我们对数组的第一个和最后一个元素做特俗处理，他们的data不存放数据。

我们通常把未使用的数组元素称为备用链表。

数组的第一个元素，即下标为0的那个元素的cur就存放备用链表的第一个节点的下标。

数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中的头节点作用。

静态链表的插入操作

首先是获得空闲分量的下标：
int Malloc_SLL(StaticLinkList space){
  int i = space[0].cur;
  if(space[0].cur){
    space[0].cur = space[i].cur;
    //把它的下一个分量用来作为备用。
  }
  return i;
}

Status ListInsert(StaticLinkList L ,int i,ElemType e){
  int j,k,l;

  k = MAX_SIZE - 1;//数组的最后一个元素

  if(i<1 || i>ListLength(L)+1){
    return ERROR;
  }

  j = Malloc_SLL(L);
  if(j){
    L[j].data = e;
    for(l=1;l<i-1;l++){
      k = L[k].cur;
    }
    L[j].cur = L[k].cur;
    L[k].cur = j;
    return OK;
  }
  return ERROR;
}

静态链表的删除操作

void Free_SSL(StaticLinkList space,int k){
  space[k].cur = space[0].cur;
  space[0].cur = k;
}

Status ListDeleted(StaticLinkList L ,int i){
  int j,k;

  if(i<1 || j>ListLength(L)){
    return ERROR;
  }

  k = MAX_SIZE-1;

  for(j=1;j<=i-1;j++){
    k = L[k].cur;
  }

  j - L[k].cur;
  L[k].cur = L[j].cur;

  Free_SLL(L,j);
  return OK;
}

静态链表优缺点总结

1、优点

在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

2、缺点

没有解决连续存储分配（数组）带来的表长难以确定的问题

失去了顺序存储结构随机存取的特性。

3、总结

总的来说，静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方法。

尽管我们可以用单链表就不用静态链表了，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

单链表小结腾讯面试题

题目：快速找到未知长度单链表的中间节点。

既然是面试题就一定有普通方法和高级方法，而高级方法，而高级方法无疑会让面试官大大加分！

普通方法很简单，首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点触发循环L/2次找到单链表的中间节点。

算法的复杂度为：O(L+L/2) = O(3/2L)

能否再优化一下这个时间复复杂度呢？

有一个很巧妙的方法：利用快慢指针！

利用快慢指针原理：设置两个指针*search、*mid都指向单链表的头节点。其中*search的移动速度是*mid的2倍。当*search指向末尾节点的时候，*mid正好就在中间了。这也是标尺的思想。

GetMidNode.c

Status GetMidNode(LinkList L,ElemType *e){
  LinkList search,mid;
  mid = search = L;

  while(search->next != NULL){
    //search移动的速度是mid的2倍
    if(search->next->next !=NULL){
      search = search->next->next;
      mid = mid->next;
    }else{
      search = search->next;
    }
  }
  *e = mid->data;

  return OK;
}

八、循环链表

对于单链表，由于每个节点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说，按照这样的方式，只能索引后继节点不能索引前驱节点。

这会带来什么问题呢？

例如不从头节点出发，就无法访问到全部节点。

事实上要解决这个问题也并不麻烦，只需要将单链表中终端节点的指针由空指针改为指向头节点，问题就结了。

将单链表中终端节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表。

初始化循环链表

//链表存储结构定义
typedef struct CLinkList{
  int data;
  struct ClinkList *next;
}

void ds_init(node **pNode){
  int item;
  node *temp;
  node *target;

  printf("输入节点的值，输入0完成初始化");

  while(1){
    scanf("%d",&item);
    fflush(stdin);

    if(item == 0){
       return;
    }

    if((*pNode == NULL)){
      //循环链表中只有一个节点
      *pNode = (node*)malloc(sizeiof(struct ClinkList));
      if(!(*pNode)){
        exit(0);
      }
      (*pNode)->data = item;
      (*pNode)->next = *pNode;
    }else{
      //找到next指向第一个节点的节点
      for(target = (*pNode);target->next!=(*pNode);target = target->next){

      }
      //生成一个新的节点
      temp = (node *)malloc(sizeof(struct CLinkList));
      if(!temp){
        exit(0);
      }

      temp->data = item;
      temp->next = *pNode;
      target->next = temp;
    }
  }
}

循环链表的插入

void ds_insert(node **pNode,int i){
  node *temp;
  node *target;
  node *p;
  int item;
  int j;

  printf("输入要插入节点的值：");
  scanf("%d",&item);

  if(i == 1){
    //新插入的节点作为第一个节点
    temp = (node *)malloc(sizeof(struct CLinkList));

    if(!temp){
      exit(0);
    }
    temp->data = item;

    //寻找到最后一个节点
    for(target = (*pNode);target->next != (*pNode);target = target->next){}

    temp->next = (*pNode);
    target->next = temp;
    *pNode = temp;
  }else{
    target = *pNode;

    for(j = 1;j<(i-1);++j){
      target = target->next;
    }

    temp = (node *)malloc(sizeof(struct CLinkList));

    if(!temp){
      exit(0);
    }

    temp->data = item;
    p = target->next;
    target->next = temp;
    temp->next = p;
  }
}

循环链表返回节点位置

int ds_search(node *pNode,int item){
  node *8target;
  int i;

  for(target = pNode;target->data!=elem && target->next != pNode;++i){
    target = target->next;
  }

  if(target->next == pNode){
    return 0;
  }else{
    return i;
  }
}

循环链表的特点

回顾一下，在单链表中，我们有了头节点时，我们可以用 O(1) 的时间访问第一个节点，但对于要访问最后一个节点，我们必须要挨个向下索引，所以需要O(n)的时间。

如果用上今天我们学的循环链表的特点，用 O(1) 的时间就可以由链表指针访问到最后一个节点。

不过我们需要改造一下现有的循环链表，我们不用头指针，而是用指向指端节点的尾指针来表示循环链表，此时查找开始节点和终端节点都很方便了。

判断单链表中是否有环

又环的定义是，链表的尾部节点指向了链表中的某个节点（不一定是第一个节点）。

那么要判断单链表中是否有环，主要有一下两种方法。

方法一：使用 p、q 两个指针，p 总是向前走，但 q 每次都从头开始走，对于每个节点，看 p 走的步数是否和 q 一样。如图，当 p 从 6 走到 3 时候，用了 6 步，此时若 q 从 head 出发则只需要两部就到3，因为步数不等，出现矛盾，存在环。

方法二：使用 p、q 两个指针，p 每次向前走一步，q 每次向前走两步，若在某个时候 p==q，则存在环。

循环链表的应用-约瑟夫问题

据说著名犹太历史学家 Josephus 有过以下的故事：

在罗马人占领桥塔帕特后，39 个犹太人与 Josephus 及它的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人，排成一个圆圈，由第一个人开始报数，没报数到第三个人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，它将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

问题：用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出。

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
  int data;
  struct node *next;
}node;

node *create(int n){
  node *p = NULL;
  node *head;
  p = head;
  node *s;
  int i =1;

  if(0 != n){
    while(i<=n){
      s = (node *)malloc(sizeof(node));
      s->data = i++;
      p->next = s;
      p = s;
    }
    s->next = head->next;
  }
  //free(head);
  return s->next;
}

int main(){
  int n = 41;
  int m = 3;
  int i;
  node *p = create(n);
  node *temp;

  m %= n;//m = 2

  while(p != p->next){
    for(i = 1;i<m-1;i++){
      p = p->next;
    }
    printf("%d->",p->next->data);
    temp = p->next;
    p->next = temp->next;

    free(temp);
    p = p->next;
  }
  printf("%d\n",p->data);
  return 0;
}

循环链表的应用-魔术师发牌问题

问题描述：魔术师利用一副牌中的13张黑牌，预先将他们排好后叠放在一起，牌面朝下。对着观众说：“我不看牌，只数数就可以猜到每张牌是什么”

#include <stdio.h>
#include <stdlib.h>

#define CardNumber 13

typedef struct node{
  int data;
  struct node *next;
}sqlist,*linklist;

linklist CreateLinkList(){
  linklist head = NULL;
  linklist s,r;
  int i;

  r = head;

  for(i = 1;i<=CardNumber;i++){
    s = (linklist)malloc(sizeof(sqlist));
    s->data = 0;

    if(head == NULL){
      head = s;
    }else{
      r->next = s;
    }
    r = s;
  }
  r->next = head;
  return head;
}

//发牌顺序计算
void Magician(linklist head){
  linklist p;
  int j;
  int Countnumber =2;

  p = head;
  p->data = 1;//第一张牌数1

  while(1){
    for(j = 0;j<Countnumber;j++){
      p = p->next;
      if(p->data != 0){//该位置有牌的话，则下一个位置
        //p->next;
        j--;
      }
    }
    if(p->data == 0){
      p->data = Countnumber;
      Countnumber++;

      if(Countnumber == 14){
        break;
      }
    }
  }
}

int main(){
  linklist head;
  head = CreateLinkList();
  Magician(head);

  int i;
  for(i = 0;i<13;i++){
    printf("%d-->",head->data);
    head = head->next;
  }
  return 0;
}

循环链表的应用-拉丁方阵问题

拉丁方阵是一种 n*n 的方阵，方阵中恰有 n 种不同的元素，每种元素恰有 n 个，并且每种元素在一行和一列中恰好出现一次。著名数学家个物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号，拉丁方阵因此而得名。

1 2 3
2 3 1
3 1 2

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
  int data;
  struct node *next;
}node;


node * makeList(int n){
  node *head = NULL;
  node *temp;
  node *s;
  int i;
  temp = head;

  for(i=1;i<=n;i++){
    s = (node *)malloc(sizeof(node));
    s->data = i;

    if(head == NULL){
      head = s;
    }else{
      temp->next = s;
    }
    temp = s;
  }
  temp->next = head;
  return head;
}

int main(){
  int n,i,j,k;
  printf("请输入方阵的大小：");
  scanf("%d",&n);
  node * head;
  node * temp;
  head = makeList(n);
  temp = head;
  for(i = 1;i<=n;i++){
    for(j = 1;j<=n;j++){
      printf("%d  ",temp->data);
      temp = temp->next;
    }
    temp = head;
    for(k=1;k<=i;k++){
      temp = temp->next;
    }
    printf("\n");
  }

  return 0;

}

九、双向链表

双向链表节点结构

typedef struct DualNode{
  ElemType data;
  struct DualNode *prior;//前驱节点
  struct DualNode *next;//后继节点
}DualNode，*DualList;

既然单链表可以有循环链表，那么双向链表当然也可以有

双向链表的插入

插入操作其实并不复杂，不过顺序很重要，千万不能写反了。

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;

关键在于交换的过程中不要出现矛盾，例如第四步先被执行了，那么p->prior就会提前变为s,使得插入的工作出错。

双向链表的删除操作

如果刚才的插入操作理解了，那么再来理解接下来的删除操作就容易多了。

p->prior->next = p->next;
p->next->prior = p->proor;
free(p);

最后总结一下，双向链表相对于单链表来说，是要更复杂一点，买个节点多了一个prior指针，对于插入和删除操作的顺序大家要格外小心。

不过，双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间。

双向循环链表实践

题目：

要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，输出结果： DEFGHIJKLMNOPQRSTUVWXYZABC

同时需要负数，例如用户输入-3，输出结果： XYZABCDEFGHIJKLMNOPQRSTUVW