一条链表是由很多个结点元素构成,所以,我们想要创建一个链表,只需要循环创建结点就可以完成这个任务了。按道理讲,我们可以只创建带有数据的结点就可以了,不过,为了更方便的操控链表以及更方便的创建结点,我们需要一个只保存地址域而不存放数据的一个结点,这个结点被称作是头结点。在链表正式被开始创建之前,我们可以让头结点指向空,也就是NULL。
在生活中,比如,我们去超市买东西,在收银台结账时就会需要排队,很明显,先来的排在前面,后来的排在后面,可是,总是会遇到突发情况,比如刚好有个人有急事,于是你就让他插个队,也就是说,排队,既可以排在某个人的前面,也可以排在某个的后面。同样的,链表元素的创建也有两种情况,可以创建在某个元素的前面,也可以创建在某个元素的后面,即头插法和尾插法。
先来讲头插法。因为,在正式创建链表之前,已经有了一个头结点指向空。那么,当第一个结点被创建时,该结点就要保存头结点中的地址,然后,将头结点的后继指针指向第一个被创建的结点。当开始创建第二个结点时,我们需要把第二个结点的地址域保存第一个结点的地址,然后,将头结点指向第二个被创建的结点的地址。也就是说,最新别创建的结点,总是在上一个结点的前面,紧跟在头结点的后面。代码如下:
void CreateListHead ( LinkList *L, int n ) { int i; LinkList p; *L = ( LinkList ) malloc ( sizeof ( Node ) ); *L = NULL; srand ( time ( 0 ) ); for ( i = 0; i < n; ++i ){ p = ( LinkList ) malloc ( sizeof ( Node ) ); p->data = rand() % 100 + 1; p->next = ( *L )->next; ( *L )->next = p; } }
接下来,讲一下链表的尾插法。同样的,首先就要创建一个头结点。头结点中只保存地址没有数据,并且头结点中的地址域指向NULL。那么接下来就要创建第一个结点,这个结点的后继指针保存头结点中存放的值,然后,把头结点的地址域更新为第一个结点的地址。到这里为止,尾插法跟头插法做法并无差别,接下来,差别就开始显现了。当我创建第二个结点时,我就要把它跟在第一个结点的后面,具体为,把第一个结点中保存的地址信息存放在第二个结点的地址域中,然后,让第一个结点指向第二个结点。到这里为止,一切都是那么自然,那么正常。这时,我们需要创建第三个结点了,很明显,我们需要像之前那样,把第二个结点的地址中的值保存在第三个结点中,然后,让第二个结点指向第三个结点。到这里有问题吗?如果不仔细思考,会发现毫无问题,但是,若是仔细思考,就会发现,问题是存在的。之前,在采用头插法时,我们没创建一个新的结点,都能找到上一个结点的地址,因为,这个地址就保存在头结点中,因此,我们可以很轻松的取出上一个结点的地址。不过,在尾插法时,我们创建一个新的结点时,如何找到上一个结点中保存的地址呢?因为,结点在不断的变化,所以,根本无法找到上一个结点中的地址。所以,为了解决这个问题,我们可以再申请一个指针变量来动态的跟随结点。代码如下:
void CreateListTail ( LinkList *L, int n ) { LinkList p, r; int i; p = NULL; r = NULL; *L = ( LinkList ) mallocc ( sizeof ( Node ) ); *L->next = NULL; srand ( time ( 0 ) ); r = *L; for ( i = 0; i < n; ++i ){ p = ( LinkList ) malloc ( sizeof ( Node ) ); p->data = rand() % 100 + 1; r->next = p; r = p; } r->next = NULL; //p->next = NULL; }
最后,就是单链表的删除。刚才讲了单链表的插入,有头插法和尾插法两种。那么,就会问,单链表的删除会不会也有头删和尾删两种呢?经过思考,这是不可能的,因为,你想删除一个结点,首先就得知道它的地址,而这个结点的地址被保存在上一个结点的地址域中,也就是说,你得不断的追溯,直到找到第一个结点,也就是说,你只能从第一个结点开始删除。那么,一思考发现,我要是把第一个结点给删了,那么这个链表不就断了吗,那还怎么删除后面的元素。所以,很明显,我们需要申请一个指针变量来动态跟随结点。代码如下:
Status ClearList ( LinkList *L ) { LinkList p, q; p = ( *L )->next; while ( p != NULL ){ q->next = p->next; free ( p ); p = q; } ( *L )->next = NULL; return OK; }
最后,做个小小的总结。顺序存储结构在获取元素信息时比较方便,而链式存储结构在插入或删除数据时比较方便,所以,要根据适当的情况选择合适的存储结构。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。