Day4
线性表的链式表示和实现：
一、单链表的定义和表示：
1.单链表需要存储两部分信息，一是本身数据信息，二是下一节点的地址信息，两部分信息构成数据元素的存储映像，它包括数据域和指针域两个域。
链表种类：单链表（线性链表）、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等
代码表示：
typedef struct LNode{
elemtype data;
struct LNode *next;
}LNode,*linklist;
2.首元结点：链表中存储第一个数据元素的结点
头结点：是在首元结点前附设的一个结点，其指针域指向首元结点，则头指
针指向头结点；
头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。
二、单链表的基本操作
1.初始化
算法描述：
Status initlist(linklist &L){
L=new lnode;
L->next=NULL;
Return OK;
}
2.取值
算法描述：
Status getelem(linklist *L,int I,elemtype &e){
P=L->next;j=1;
While(p&&j<i){
P=p->next;
++j;}
If(!p||j>i) return ERROR;
e=p->data;
return OK;
}
算法分析：ASL=(n-1)/2
T(n)=O(n)
3.查找
算法描述：
Lnode *locateelem(linklist L,elemtype e){
P=L->next;
While(!p&&p->date!=e)
P=p->next;
Return p;
}
算法分析：类似于查找。
4.插入
算法描述：
Status listinsert(linklist &L,int I, elemtype e){
P=L;j=0;
While(p&&(j<i-1)){
P=p->next;
j++}
if(!p||j>i+1) return ERROR;
s=new lnode;
s->data=e;
s->next=p->next;
p->next=s;
retuen OK;
}
算法分析：类似于查找。
5.删除
算法描述：
Status listdelete(linklist &L,int i){
P=L;j=0;
While(p->next&&(j<i-1)){
p=p->next;
j++;}
if(!p->next||j>i-1) return ERROR;
q=p->next;
p->next=q->next;
delete q;
return OK;
}
算法分析：类似于查找。
6.创建单链表
前插法：
Void createlist_H(linklisr &L,int n){
L=new londe;
L->next=NULL;
For(i=0;i<n;i++){
P=new lnode;
Cin>>p->data;
p->next=L->next;;
L->next=p}
}
后插法：
Void creatlist_r(linklist &L,int n){
L=new lonode;
L->next=NULL;
R=L;
For(i=0;i<n;i++){
P=new lnode;
Cin>>p->data;
p->next=NULL;r->next=p;
r=p;}
}
三、循环链表：最后一个结点的指针域指向头结点。 标签：linklist,结点,day4,笔记,next,链表,算法,new,数据结构 From： https://www.cnblogs.com/k4fk4-shaw/p/17212842.html