数据结构——线性表（静态链表、循环链表以及双向链表）

1、静态链表

---

用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。

静态链表需要对数组的第一个和最后一个元素作为特殊元素处理，不存数据。

最后一个指向第一个有数据的下标地址，第一个游标指向第一个没有数据的下标地址。

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

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

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

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

1.1静态链表的初始化

bool InitList(StaticLinkList list)
{int i;for(i=0;i<MAXSIZE;i++)list[i].cur = i+1;list[MAXSIZE-1].cur = 0;  //当前链表为空，所以最后一个元素的cur为0 return true;
}

1.2静态链表的插入操作

首先是获得空闲分量的下标：

int Malloc_SLL(StaticLinkList space)
{int i = space[0].cur;    //将第一个游标赋值给i，也就是第一个空闲的结点的下标赋值i。if(space[0].cur)space[0].cur = space[i].cur;return i;
}// 这段代码是给静态链表的第i-1个元素后添加新元素 
bool ListInsert(StaticLinkList list,int i,ElemType e) 
{int i,j,l;k = MAXSIZE-1;if(i < 1 || i > ListLength() + 1)return false;j = Malloc_SSL(L);   //获取空闲下标 if(j){list[i].data = e;   //将数据值赋值给要空闲位置 for(l = 1;l<=i-1;l++)k = list[k].cur;    //找到第i-1个元素 list[i].cur = list[k].cur; //把第i-1个元素的cur赋值给新元素的cur list[i].cur = j; //把新元素的下标赋值给第i-1个元素的cur; return true;}return false;
}

1.3静态链表的删除操作

Status ListDelete(StaticLinkList L,int i)
{int j,k;if(i<1||i>ListLength(L)){return ERROR;}k = Max_SIZE-1;for(j=0;j<=i-1;j++){k = L[k].cur;     //找出要删除元素的前一个元素的下标}j = L[k].cur;         //找到要删除元素的下标L[k].cur = L[j].cur;  //把要删除元素的游标赋值给其前一个元素的游标Free_SLL(L,j);        //释放删除元素的内存return OK;
}
void Free_SLL(StaticLinkList space,int j)
{space[j].cur = space[0].cur;space[0] = j;     //删除元素后，该位置变为备用链表表头，数组第一个元素的游标存储第一个空闲结点的下表
}
int ListLength(StaticLinkList L)
{int j = 0;int i = L[MaxSIZE-1].cur;  //取出有数据的第一个元素的下标while(i){i = L[i].cur;   //有数据的最后一个元素的游标为0，即为数组第一个元素的下标j++;}return j;
}

1.4静态链表的优缺点总结

优点：

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

缺点：

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

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

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

2、循环链表

---

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

2.1循环链表初始化

/*循环单链表初始化*/
Status Init_CLinklist(CLinklist *L)
{*L=(CLinklist)malloc(sizeof(CLNode)); //创建头结点 if(!(*L)) return ERROR;               //创建失败返回ERROR (*L)->next=*L;                        //头结点指针指向本身 return OK;
}

2.2循环链表尾插法构建 

/*循环单链表的尾插法构建，输入data，0的时候结束输入*/
void Create_CLinklist(CLinklist *L)
{CLNode *p,*q;                                //定义链尾节点和新生节点 int flag=1,number;                           //设立旗帜， p = *L;while(flag){scanf("%d",&number);if( number!=0 ){q=(CLinklist)malloc(sizeof(CLNode)); //创建新生节点 if(!q) exit(0);                      //创建失败结束程序 q->data=number;p->next=q; 	p=q;                     //这里和单链表的尾插法相同 }else{p->next = *L;                         //尾指针指向头结点 flag=0;}}}

2.3循环链表插入

/*循环单链表的插入，插入错误返回0，插入成功返回1*/
Status Insert_CLinklist(CLinklist *L,int i,Elemtype e)
{int j=1; CLNode *p,*q;                               //定义链尾节点和新生节点 p = *L;if(i<1||p->next==*L||i>Length_CLinklist(L))  return ERROR;                               //插入位置小于1，空表或大于表长则返回0  while( p->next!=*L && j<i ){p=p->next;j++;}q=(CLinklist)malloc(sizeof(CLNode));q->data=e;q->next=p->next;p->next=q;return OK;
} 

2.4循环链表删除

/*循环单链表的删除,删除错误返回0，删除成功返回1，用e返回被删除的元素*/
Status Delete_CLinklist(CLinklist *L,int i,Elemtype *e)
{int j=1; CLNode *p,*q;p = *L;if(i<1||p->next==*L||i>Length_CLinklist(L))  return ERROR;  //删除位置小于1，空表或大于表长则返回0while( p->next != *L && j<i){p=p->next;j++;}q=p->next;*e=q->data;p->next=q->next;free(q);                           //释放掉删除结点 return OK;
}

2.5返回结点所在的位置

/*返回结点所在的位置*/
int search_CLinklist(node *pNode, int elem)
{node *target;int i = 1;for(target = pNode; target->data != elem && target != pNode; ++i){target = target->next;}if(target->next == pNode) //表中不存在该元素return 0;else return i;
}

 2.6约瑟夫问题

1. 算法思想：

   1. 根据总人数n创建n个结点的循环链表模拟约瑟夫环，每个人为链表中的一个结点
   2. 工作指针从循环链表表头向后移动至第k个结点
   3. 从当前开始报数
      • 若不满足出列条件，工作指针后移，继续报数
      • 如满足出列条件，删除当前结点

2. 算法描述：

//n个人围圈报数，报m出列，最后剩下的是几号？
#include <stdio.h>
#include <stdlib.h>typedef struct node
{int data;struct node* next;
}node;node* create(int n)
{node* p = NULL, * head;head = (node*)malloc(sizeof(node));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;//s指向第一个结点，形成循环链表}free(head); //释放辅助的头结点return s->next;
}
int main()
{int n = 41;int m = 3;int i;node* p = create(n);node* temp;m %= n;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;
}

2.7例题

1、实现将两个线性表（a1，a2，...，an）和（b1，b2，...，bm）连接成一个线性表（a1，...，an，b1，...，bm）的运算。

分析：

-若在单链表或头指针表示的单循环链表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O（n）。

-若在尾指针表示的单循环链表上实现，则只需修改指针，无需遍历，其执行时间是O（1）。

//假设A，B为非空循环链表的尾指针
LinkList Connect(LinkList A, LinkList B)
{LinkList p = A->next; //保存A表的头结点位置A->next = B->next->next;//B表的开始结点链接到A表表尾free(B->next);//释放B表的头结点B->next = p;return B;  //返回新循环链表的尾指针
}

2、判断单链表中是否有环。

• 有环的定义是，链表的尾结点指向了链表中的某个结点。

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

方法一：

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

 方法二：

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

3、魔术师发牌问题

魔术师手中有A、2、3……J、Q、K十三张黑桃扑克牌。在表演魔术前，魔术师已经将他们按照一定的顺序叠放好（有花色的一面朝下）。魔术表演过程为：一开始，魔术师数1，然后把最上面的那张牌翻过来，是黑桃A；然后将其放到桌面上；第二次,魔术师数1、2；将第一张牌放到这些牌的最下面，将第二张牌翻转过来，正好是黑桃2；第三次，魔术师数1、2、3；将第1、2张牌依次放到这些牌的最下面，将第三张牌翻过来正好是黑桃3……直到将所有的牌都翻出来为止。则原来牌的顺序为？？？

#include <stdio.h>
#include <stdlib.h>
#define CardNumber 13
struct card
{int num;struct card *next;
};
//创建循环链表
struct card *Createcard()
{struct card *head = NULL, *p = NULL;head = (struct card *)malloc(sizeof(struct card)); //已申请，不为空p = head;struct card *pp = NULL;for (int i = 1; i <= CardNumber; i++){pp = (struct card *)malloc(sizeof(struct card));pp->num = 0;p->next = pp;p = pp;}pp->next = head->next; //最后一个结点的下一个执行头结点的下一个，形成环free(head);            //删除头结点（因为已经连起来了，且头结点本身又没有数据）return pp->next;
}
//定义发牌次序
void SendCard(struct card *p)
{int i;int CountNumber = 2;struct card *pp = NULL;pp = p;pp->num = 1; //正向第一个结点牌为1；while (1){//需要间隔几个数填上for (i = 0; i < CountNumber; i++){pp = pp->next;if (pp->num != 0) //已经放置过，且会优先于它被取出{i--; //跳过已经被取走的，即该位置有牌的话，则下一个位置}}//找到要填充的位置并赋值if (pp->num == 0){pp->num = CountNumber;CountNumber++;if (CountNumber == 14){break;}}}
}int main()
{struct card *p = Createcard();SendCard(p);printf("扑克牌次序为：\n");for (int i = 0; i < CardNumber; i++){printf("黑桃%d ", p->num);p = p->next;}return 0;
}

3、双向链表

---

双向链表结点结构

typedef struct DulNode
{ElemType Data;struct DulNode* prior; //前驱结点struct DulNode* next;  //后继结点
}DuNode,*DuLinkList;

3.1双向链表的插入操作

代码实现： 

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

3.2双向链表的删除操作

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

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

3.3双向循环链表实践

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

DEFGHIJKLMNOPQRSTUVWXYZABC

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

XYZABCDEFGHIJKLMNOPQRSTUVW

#include <stdio.h>
#include <stdlib.h>#define OK    1
#define ERROR 0typedef char ElemType;
typedef int  Status;
typedef struct DualNode
{ElemType data;struct DualNode* prior;struct DualNode* next;
}DualNode,*DuLinkList;Status InitList(DuLinkList* L)
{DualNode* p, * q;int i;*L = (DuLinkList)malloc(sizeof(DualNode));if (!(*L)){return ERROR;}(*L)->next = (*L)->prior = NULL;p = (*L);for (i = 0; i < 26; i++){q = (DualNode*)malloc(sizeof(DualNode));if (!q){return ERROR;}q->data = 'A'+i;q->prior = p;q->next = p->next;p->next = q;p = q;}p->next = (*L)->next;(*L)->next->prior = p;(*L) = p;return OK;
}void Caesar(DuLinkList* L, int i)
{if (i > 0){do{(*L) = (*L)->next;} while (--i);}if (i < 0){do{(*L) = (*L)->prior;} while (++i);}
}
int main()
{DuLinkList L;int i,n;InitList(&L);printf("请输入一个整数：");scanf_s("%d",&n);printf("\n");Caesar(&L,n);for (i = 0; i < 26; i++){L = L->next;printf("%c",L->data);}printf("\n");return 0;
}