用头插法建立单链表programlia
typepoi
t
ode
odeRecorddatachar
f
extpoi
te
dvarChcharHeadSRpoi
tbegi
Head
il将单链表置为空表readCh读入第一个结点的值whileChdobegi
ewS生成新结点S将读入数据放到新结点的数据域中将新结点插入链表的表头上readChe
de
d（2）尾插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，直至读入结束标志为止。为此必须增加一个尾指针R，使其始终指向当前链表的表尾上。读入下一个结点的值
【练习2】：完成下面的程序尾插法建立单链表Head，数据说明如前begi
Head
il将链表Head置为空表R
il尾指针初值为空readCh读入第一个结点的值whileChdobegi
为输入结束符
ewS生成新结点S将读入数据放到新结点的数据域中IfHead
ilthe
新结点S插入空表elseS插入非空表尾结点R之后尾指针R指向新的表尾readCh读入下一个结点的值e
dIfR
ilthe
R
il时是空表R
ext
il将非空表的终端结点的指针域置空
fe
d
☆头结点：如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：（a）由于开始结点位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无须进行特殊处理；（b）无论链表是否为空，其头指针是指向结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。
图带头结点的单链表Head二、查找运算（1）按序号查找在带头结点的单链表Head中查找第i个结点0≤i≤
，若找到则输出该结点的数据域，否则输出’
o
e’。begi
PHeadj0从头结点开始扫描whilePNext
ila
djidobegi
PPNext扫描下一个结点jj1计数器累计扫描过的结点数e
dIfijthe
writel
Pdata找到了第i个结点elsewritel
‘
o
e’i0或iN时找不到第i个结点e
d（2）按值查找在带头结点的单链表Head中查找其结点值等于Key的结点，若找到则返回该结点的位置P；否则返回
ilbegi
PHead
ext从开始结点起比较whileP
ila
dPDataKeydoPPNext继续往下扫描retur
P
fe
d三、插入运算（1）后插操作：将值为X的新结点插入P之后【练习3】：完成下面的程序begi
ewSSDataX
给新结点S赋值X将S插入P之后
e
d
（2）前插操作：在带头结点的单链表中，将值为X新结点r