文档介绍：线性表的链式存贮结构
⑴线性表的链式存贮结构,也称为链表。
⑵用一组任意的存贮单元(可连续,也可以不连续)来存
放线性表的数据元素值及它在内存的地址,
⑶常用的链表:
①单链表、②循环链表、③双向链表、④多重链表等。
单链表结构
⑴只含有一个指针域来存放下一个元素地址,称这
样的链表为单链表或线性链表。
⑵线性链表中的结点结构可描述为:
⑶data 域:用来存放结点本身信息,类型由具体问题
而定,本书中将其设定为elemtype类型,表示某一
种具体的已知类型,
⑷next域用来存放下一个元素地址。
⑸单链表可用C++描述为:
struct link
{ elemtype data; //元素类型
link *next; //指针类型,存放下一个元素地址
}
单链表运算
1. 头插法建立单链表(如下图所示)
单链表运算
1. 头插法建立单链表(从左边插入结点)
link *hcreat( )
{ link *s,*p; int c1; //指针S,指针P,变量C1
cin>>c1; //输入结点数值,为0时算法结束
p=NULL; //线性表为空表
while(c1)
{ s=new link; //生成新结点S
s->data=c1; //新结点S的值为C1
s->next=p; //S的后继结点的地址为P
p=s;
}
return p; //返回P结点的地址
}
2. 尾插法建立单链表(如下图所示)
2. 尾插法建立单链表(从右边插入结点)
link *rcreat( )
{ link *s,*r,*p; //指针类型
int c1;
p=r=new link; //生成新结点 p,r
p->next=NULL; //p结点的后继结点为空
cin>>c1;
while(c1)
{ s=new link; //生成新结点 s
s->data=c1; //s结点的数据值为c1
r->next=s; //r结点的后继结点为s
r=s; //s结点的地址传给r结点
cin>>c1;
}
r->next=NULL; //r的后继结点为空
return p;
}
3. 单链表上的查找运算
(1) 按值查找Locate(head,x)
在单链表head中,查找值为x的结点,若找到,返回它的地址,否则返回NULL。
(2) 按序号查找get(head,i)
在单链表head中查找第i个位置上的元素,若找到,则返回它的地址,否则返回NULL。
⑴按值查找:
Link *Locate(link *head,elemtype x)
{ link *p;
p=head->next;
while((p!=NULL)&&(p->data!=x))
p=p->next;
return p;
}
算法的时间复杂度都为O(n)。