朴孝敏演过的r电影:单链表的考察

正向生成单链表算法的研究
谭庆，雷治军
(洛}H师范学院，河IfJ洛}H 471022)
摘要:许多数据结构》教材只讨论了从表尾到表头逆向生成巾一链表的算法，I(IJ没有讨论从表头到表尾正向牛
成巾一链表的算法。木文对巾一链表进行研究少{提出了从表头到表尾正向生成巾一链表的算法。
关键词:数据结构:顺序存储结构:链式存储结构
中图分类号:TP301.文献标识码:A文章编号:1008-4916( 2004) 01-0031-02
A research on arithmetic creation of simply linked list from head to tail
TAN Qing, 1.F1 7.hi一Jun
(Luoyann Teacher's Collene, Luoyann 471022, China)
Abstract: There are only discussions about arithmetic creation of simply linked list from tail to head
that from head to tail. The simply linked list is fully researched into and its creation from head to tail is
in the article.
Key WOI'C1S: data structure; sequential storane structure; linked storane structure
without
offered
1单链表结构综述
线性表链式存储结构的特l从是用一组任意存储
单兀存储线性表的数据兀素。因此.为表示每个数据
兀素a.与其直接后继数据兀素a.十i之间的逻辑关系.
对数据兀素a.来说.除了存储其木身的信急之外.还
需存储一个指示其直接后继的信VI,。这两部分信VI,组
成数据兀素a.的存储映象.即结l从。它包括两个域.
其中存储数据兀素信急的域称为数据域.存储直接后
继存储位置的域称为指针域。指针域中存储的信急称
做指针或链。n个结} l(a}(l}i}n)的存储映象)链结
{ElemType data;
struct 1,Node*next;
}1.Node,*1.inkl.ist;
在单链表的第一个结l从之前附设一个结l从.称之
为头结l从。头结l从的数据域可以不存储任何信急一也
可存储如线性表的长度等的附加信VI,.头结l从的指针
域存储指向第一个结l从的指针(即第一个兀素结l从的
存储位置).如图1所示。此时.中一链表的头指针指向
头结l从。若线性表为空表.则头结l从的指针域为空”
如图2所示。
成一个链表.即为线性表(ai, a2,· } , a.,)的链式存储结I.
构。又因此链表的每个结l从中只包含一个指针域.故
又称线性链表或单链表。
整个链表的存取必须从头指针开始进行.头指针
指示链表中第一个结l从的存储位置。同时.山」几最后
一个数据兀素无直接后继.则单链表中最后一个结l从
的指针为空”。可见.中一链表可山头指针唯一确定.在
C语言中可用结构指针”来描述。
typedef struct 1,Node
头指针头维点
图1单链表结构
L一教习.:.{
名呀寸昔钊.头么古买氛
图2空链表
2对正向生成单链表算法的研究
木文引用C语言的标准函数m all、来动态生成
结i从o假设p是l.in k list型的变量.则执行p=
( l,inkl,ist) malloc( sizeof(1,Node) )后山系统生成一
个1.N ode型的结l从.同时将该结l从的起始位置赋给
指针变量Po
在从表尾到表头逆向生成单链表的算法中每次
都是在头结l从的后而插入一个新结l从。因此新结l从的
插入位置是不变的.要插入的新结l从的直接前驱结l从
一直是头结l从。头结l从的位置是固定的.它山头指针
来指向。因此在插入一个新结l从时算法很简单。只要
做一个循环.就可以在头结l从的后而插入n个新结
点.从血生成一个新的单链表。
在从表头到表尾正向生成中一链表的算法中.首先
生成头结l从.然后在头结l从后而插入ai结l从.这时ai
结l从的直接前驱结l从是头结l从。ai结l从插入后.在ai
结l从后而插入a:结l从.此时a:结l从的直接前驱结l从
是ai结l从.血不是头结l从。a:结l从插入后.在a:结l从
后而插入a:结l从.此时a:结l从的直接前驱结l从又变
成了a:结l从。因此.新结l从的插入位置是一直在变化
的.要插入的新结i从a.的(2}i}n)直接前驱结i从是
a卜i。为了确定要插入的新结l从的直接前驱结i从的位
置.需要设一个辅助指针q.初始时让q指向头结i从。
当生成ai结i从后.指针p指向ai结i从.再将p指针送
入头结l从的指针域.便完成了a、结l从的插入。如图3
所示。可用以卜语句实现(以卜假设数据兀素类型为
int型)。
q=1.;
t}=(l,inkl,ist) malloc( sizeof(1,Node));
scanf(跳d”.&p一>dat a);
q一>next= p;
p一>next= N[丁1.1. ;
t}=(l,inkl,ist) malloc( sizeof(1,Node))
scanf(跳d”.&p一>d at a);
q一>next= p;
p一>next= N[丁1.1. ;
图5插入a:结点后
按同样的方法.重复卜述语句可以完成其余后继
结l从a;. a}.…a.的插入。
q=t};
p= N[丁1.1. ;
t}=(l,inkl,ist) malloc( sizeof(1,Node));
scanf(跳d”.&p一>d at a);
q一>next= p;
p一>next= N[丁1.1
图3插入a.结点后
当ai结i从插入完成后.再插入的新结i从a:的直
接前驱结i从就变成了ai结l从。指钊一q就要向后移动.
指向ai结i从。指钊一p所指的ai结i从己经插入.此时将
p赋为空”。可用以卜语句实现(如图4所示):
q=t};
p= N[丁1,1.;
图4指针q的变化
此时指钊一q所指向的.i结l从就是要插入的新结
点a:的直接前驱结l从。插入a:结i从可用以卜语句实
「日l知1}义I‘日千五几、.
3从表头到表尾正向生成单链表算法的实现
以卜用C语言实现此算法:
void Createl}ist(1}inkl}ist c}1}, int n)
{
1.inkl.ist p, q;
int i;
l.=(l,inkl,ist) malloc( sizeof(1,Node));
1.一>next= N[丁1.1. ;
q=1.;
for(i= l; i<=n; i++)
{t}=(l,inkl,ist) malloc( sizeof(1,Node));
scanf(跳d”.&p一>d at a);
q一>next= p;
P一>next= N[丁1.1. ;
q=t};
p= N[丁1.1. ;
}
q= N[丁1.1. ;
}
4吉语
从表头到表尾正向生成单链表算法的时间复杂
度是0( n).它和从表尾到表头逆向生成单链表算法
的时间复杂度相同。在空间上只是多用了一个辅助指
针q。但正向生成中一链表的算法却比逆向生成中一链表
的算法在使用上更加方便。
参考文献:
f I } i}'}} }}'}强.〔:程序设计(第一版>f}l.化尔:消华人学出版社，
I 999.
[ 2]严蔚敏，吴伟民.数据纤构(〔:语汀版)[VI ]
版沦1_.1997.
a七尔:消华人学出
(编辑:夏新奎)