线性表是一种常用的数据结构，其中的每一个元素（结点）都有唯一的前驱和唯一的后续。当然，第一个元素只有后续，最后一个元素只有前驱。
线性表一般分为“「顺序表」”和“「链表」”。顺序表可以简单理解成前面学过的数组。它是一种逻辑上和物理上都是有序的、连续存储的静态结构。链表是一种物理上不连续存储的动态结构，数据之间的逻辑顺序是通过链表中的指针链接关系实现的。
顺序表-数组「==有了顺序表为什么还需要链表???==」
链表头指针和头结点的区别头指针：
头指针是指向第一个结点的指针，若是链表中只有头结点，则是指向头结点的指针头指针具有标识作用，所以常常以头指针冠以链表的名字（指针变量名）无论链表是否为空，头结点均不为空头指针是链表必要元素头结点：
头结点是为了操作统一和方便而设立的，放在第一个元素结点之前，其数据域一般无意义（也可以存放表长度）有了头结点，对第一个元素结点的插入，删除，其操作和其他结点操作统一了头结点不一定是链表的必要元素单向链表类型和变量的说明:
structNode{intdata;Node*next;};Node*p;
申请存储单元:
p=newNode;p-data=0x;p-next=NULL;
建立链表有“头插法”和“尾插法”两种方法，前者是把新结点插在头结点之后，后者是把新结点插在尾结点之后。
链表的操作插入Node*ss=newNode;s-data=e;s-next=p-next;p-next=s;删除
p-next=q-next;orp-next=p-next-next;链表的遍历
从链表的头结点head开始，依次访问每一个元素，直到链表尾部，包括查找、输出等操作。如果已经创建了一个链表，如何查找其中是否有给定的元素x呢？只需要从头结点开始扫描，如果当前结点数据域的值等于x，那么就表示找到了x，如果到达链表尾部还没有找到，则链表中没有x这个元素。同样，链表的输出也是从头结点开始一个一个输出，直到链表尾部结束。
Node*p=mylist;while(p!=NULL){coutp-data;p=p-next;}示例代码
#includebits/stdc++.husingnamespacestd;structNode{intdata;Node*next;};Node*mylist;intlen;voidinit(Node**yourlist){Node*p,*s;intd;p=newNode;p-next=NULL;*yourlist=p;while(cind){s=newNode;s-data=d;s-next=NULL;p-next=s;p=s;len++;}}voidprint(Node*yourlist){Node*p;p=yourlist;p=p-next;cout"mylist:";while(p!=NULL){cout"--"p-data;p=p-next;}coutendl;}intget(Node*yourlist,intidx){Node*p=yourlist;if(idxlen)return-1;while(idx--){p=p-next;}returnp-data;}boolinsert(Node*yourlist,intidx,intdata){Node*p=yourlist-next;if(idxlen)returnfalse;inti=1;while(iidx-1){p=p-next;i++;}Node*s=newNode;s-data=data;s-next=p-next;p-next=s;returntrue;}intremove(Node*yourlist,intidx){Node*p=yourlist-next;if(idxlen)returnfalse;inti=1;while(iidx-1){p=p-next;i++;}p-next=p-next-next;}intmain(){init(mylist);print(mylist);insert(mylist,2,5);print(mylist);remove(mylist,3);print(mylist);return0;}时间复杂度
单链表的查找性能为O(n)----顺序存储结构为O(1)单链表的插入和删除，在计算出某位置的指针后，插入和删除性能为O(1)-----顺序存储结构为O(n)
循环列表//循环链表判断结束条件p-next==mylist;//头结点创建时:Nodeheader=newNode;header-next=header;mylist=header;//其他操作同单链表例题
P约瑟夫问题
题目描述n个人围成一圈，从第一个人开始报数,数到m的人出列，再由下一个人重新从1开始报数，数到m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
输入格式输入两个整数n,m。
输出格式输出一行n个整数，按顺序输出每个出圈人的编号。
输入输出样例输入#1复制输出#1复制说明/提示分析
排成一圈,正好是循环链表的样子...
参考代码#includebits/stdc++.husingnamespacestd;structNode{intid;Node*next;};Node*head;Node*tail;intn,m;intmain(){structNode*p;inti;cinnm;for(i=1;i=n;i++){p=newNode;p-id=i;if(head==NULL){tail=head=p;p-next=head;}else{p-next=head;tail-next=p;tail=p;}}p=head;if(p==NULL){return0;}intcnt=1;while(p-next!=p){if(cnt=m-1){printf("%d",p-next-id);p-next=p-next-next;p=p-next;cnt=1;}else{cnt++;p=p-next;}}printf("%d",p-id);return0;}链表的数组实现
structNode{intdata;Node*next;};
next指针存放的是data结构体的地址(指针).如果data存放在数组里,那么next就是存放data的数组下标.
所以数组模拟链表的话,可以使用两个数组
inta[N],next[N];
分别存放数据data和下个数据的数组下标.
constintN=1e5+10;inthead,idx;inta[N],nxt[N];//在头节点后增加一个值为x的节点voidadd_head(intx){idx++;a[idx]=x;nxt[idx]=head;head=idx;}//在k后插入节点xvoidadd(intk,intx){idx++a[idx]=x;nxt[idx]=nxt[k];nxt[k]=idx;}///将下标为k的后面的节点删除，因为指针域存储的是下一个节点voiddel(intk){nxt[k]=nxt[nxt[k]];}参考代码
#includebits/stdc++.husingnamespacestd;constintN=+5;inthead,idx,n,m;inta[N],nxt[N];intmain(){cinnm;a[1]=1;nxt[1]=1;idx++;for(inti=2;i=n;i++)add(i-1,i);inti=1;intcnt=1;while(nxt[i]!=i){if(cnt=m-1){couta[nxt[i]]"";nxt[i]=nxt[nxt[i]];cnt=1;}else{cnt++;}i=nxt[i];}couta[i];return0;}快慢指针快速找到未知长度的单链表的中间节点
Node*find_middle(Node*head){Node*fast;Node*slow;fast=slow=head;while(fast!=NULL){if(fast-next)fast=fast-next-next;elsereturnslow;slow=slow-next;}returnslow;}如何确定单链表是否有环?
structNode{intdata;Node*next;};boolexitLoop(Node*head){Node*fast,*slow;slow=fast=head;while(slow!=NULLfast-next!=NULL){slow=slow-next;fast=fast-next-next;if(slow==fast)returntrue;}returnfalse;}题单P约瑟夫问题HDU-圆桌问题HDU-士兵队列训练问题Pfaebdc玩扑克P机器翻译
云帆编程老师联系方式：
云帆老师