• 非金属矿物粉体加工技术现状和发展探讨 不要轻易放弃。学习成长的路上,我们长路漫漫,只因学无止境。


    链表是线性表链式实现方式,是数据结构中一个重要组成部分,而链表创建方法直接影响人们对单链表理解。经过对“数据结构”多年教学经验积累,对链表创建方法进行了归纳和总结,提出了相对容易理解创建思路以及简明、易懂创建方法。 关键词数据结构线性表链表前插法尾插法 中图分类号TP3 文献标识码A 文章编号1007-9416(2011)03-0105-02 线性表是数据结构结构中重要组成部分。也是算法设计中应用最广泛一种数据结构。线性表可以用链式存储来实现,链式存储指是线性表中逻辑相邻元素存储位置可以不相邻。所以在链式存储结构中,每个结点除了保存元素信息以外,至少还需一个指针来保存直接后继地址。链式存储结构表示线性表中数据元素时首先要创建一个链表。 每个链表都由若干个离散结点组成,这些结点在创建链表时总是逐个生成,从而把这些生成结点逐个地链接起来,形成链表。在此从结点链接方式进行分析与归纳,以单链表为例对链表创建方法总结为以下2种,即头插法和尾插法。 当然,在创建链表之前,需要自定义结点类型。用C语言,描述单链表结点如下 typedefstructnode {chardata; structnode*next; }linklist; 1、头插法(表头插入法) 该方法从一个空表开始,重复读入数据,生成新结点,将读入数据存放到新结点数据域中,然后将新结点插入当前链表表头上,直至读入结束标志为止。图1指明在空链表head中依次插入a,b,c之后,将d插入当前链表表头时指针修改情况。具体算法如下 linklist*CreatF()/*逐个输入字符,以“$”为结束符,返回单链表头指针*/ {charch;linklist*head,*s; head=NULL;ch=getchar();/*读入第一个结点值*/ while(ch!='$') {s=(linklist*)malloc(sizeof(linklist));/*生成新结点*/ s->data=ch;/*将输入数据放入新结点数据域中*/ s->next=head; head=s;/*将新结点插入到表头上*/ ch=getchar();/*读入下一个结点值*/ }returnhead;/*返回表头指针*/ } 2、尾插法(表尾插入法) 头插法建立单链表虽然算法简单,但生成链表中结点次序和输入顺序相反。若希望二者次序一致,可采用尾插法建立单链表。该方法是将新结点插到当前链表表尾上,为此必须增加一个尾指针r,使其始终指向当前链表尾结点。例如,在空链表head中插入a,b,c之后,将d插入当前链表表尾,其指针修改情况如图2所示。 以下通过代码来实现尾插法创建方法 linklist*CreatR()/*尾插法建立单链表,返回表头指针*/ {charch; linklist*head,*s,*r; head=NULL;r=NULL;ch=getchar(); while(ch!='$') {s=(linklist*)malloc(sizeof(linklist)); s->data=ch; if(head==NULL)head=s;/*新结点*s插入空表*/ elser->next=s;/*非空表,新结点*s插入到尾结点*r之后*/ r=s;/*将尾指针r指向新表尾*/ ch=getchar();/*读入下一个结点值*/ } if(r!=NULL)r->next=NULL;/*对于非空表,将尾结点指针域置空*/ returnhead;/*返回表头指针*/ } 在上述算法中,在表头插入操作和链表中其他位置上插入操作处理是不一样,我们必须对第一个位置上插入操作做特殊处理,为此上述算法使用了第一个if语句。算法中第二个if语句作用是为了分别处理空表和非空表这两种不同情况。如果我们在链表开始结点之前附加一个结点,并称它为头结点,那么就会解决这两个if语句问题,使尾插法建立单链表算法更加简单。 带头结点单链表如图3所示,图中阴影部分表示头结点数据域不存储信息,但是在有应用中,可利用该域来存放表长度等附加信息。 引入头结点后,尾插法建立单链表算法可简化为 linklist*CreatR1() {charch; linklist*head,*s,*r; head=(linklist*)malloc(sizeof(linklist));/*生成头结点*/ r=head;/*尾指针初值指向头结点*/ ch=getchar(); while(ch!='$') {s=(linklist*)malloc(sizeof(linklist)); s->data=ch; r->next=s;/*新结点插入表尾*/ r=s;/*将尾指针r指向新表尾*/ ch=getchar(); } r->next=NULL; returnhead;/*返回表头指针*/ } 3、结语 链表创建方法思路各异,不尽相同,在此着重强调以简单、易懂方式来创建链表,并且把那些复杂、多样思路进行归纳,形成统一创建模式。 参考文献 [1]严蔚敏,吴伟民.《数据结构》(C语言版).北京清华大学出版社,2005. [2]唐策善,黄刘生.《数据结构——用C语言描述》.高等教育出版社,2009. [3]唐宁九,游虹跃.《数据结构与算法》.北京清华大学出版社,2008. [4]陈守孔.算法与数据结构(c语言版)[M].北京机械工业出版社,2008.

    上一篇:田亮惹哭叶一茜不惧女方娘家人

    下一篇:没有了