c链表的创建与操作

《c链表的创建与操作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、C++链表的创建与操作我们知道，数组式计算机根据事先定义好的数组类型与长度白动为其分配-•连续的存储单元，相同数组的位置和距离都是固定的，也就是说，任何一个数组元素的地址都可一个简单的公式计算出来，因此这种结构町以有效的对数组元義进行随机访问。但若对数组元尜进行插入和删除操作，则会引起大量数据的移动，从而使简单的数据处理变得非常复杂，低效。为丫能冇效地解决这些问题，一种称为“链表”的数据结构得到丫广泛应用。1.链表概述链表是一种动态数据结构，他的特点是用一组任意的存储单元(可以是连续的，也可以是不连续的

2、)存放数据元尜。链表屮每一个元索成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点屮的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用來指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点屮必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表屮的每个结点可以用若干个数据和若干个指针。结点屮只宥一个指针的链表称为单链表，这是最简单的链表结构。再C++巾实现一个单链表结构比较简单。例如，可定义单链表结构的

3、最简单形式如下structNodc{intData;Node*next;);这里川到了结构体类型。其中，*ncxt是指针域，用來指向该结点的下一个结点；Data是一个幣形变跫，用来存放结点中的数据。当然，Data可以是任何数据类型，包拈结构体类型或类类型。在此基础上，我们在定义一个链农类list，其•中包含链表结点的插入，删除，输出等功能的成员函数。classlist{Node*head;public:list(){hcad=NULL;}voidinsertlist(intaDate’intbDate)

4、;//链表结点的插入voidDeletelist(intaDate);//链表结点的删除voidOutputlist();//链表结点的输出Node*Gethead(){returnhead;}}；2.链表结点的访问由于链表屮的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其屮任意结点的地址无法向数组一样，用一个简单的公式计算出來，进行随机访问。只能从链表的头指针(即head)开始，用一个指针p先指向笫一个结点，然后根裾结点p找到下一个结点。以此类推，盥至找到所要访问的结点或到最后一个结

5、点(指针为空)为止。下而我们给出上述链农的输出函数；voidlist::Outputlist(){Node^current=head;while(current!=NULL){cout«currcnt->Data«Hcurrent=current->next;cout«endl;)1.链表结点的插入如果要在链表屮的结点a之前插入结点b，则需要考虑卜面儿点情况。(1)插入前链表是一个空表，这时插入新结点b后。(2)若a是链表的第一个结点，则插入后，结点b力第一个结点。(3)若链表中存在a，且不是第一个结点

6、，则首先要找出a的上一个结点a_k，然后使a_k的指针域指向b,在令b的指针域指向a，即可完成插入。(4)如链表屮不存在a，则插在ii后。先找到链表的敁后一个结点a_n，然后使a_n的指针域指向结点b，而b指针的指针为空。以下足链表类的结点插入函数，挝然其也具冇建立链表的功能。voidlist::insertlist(intaDate’intbDate)"设aDate是结点a中的数据，bDate是结点b中的数据INode*p，*q，*s;//p指向结点a，q指向结点a_k，s指向结点bs=(Node*)

7、new(Node);//动态分配一个新结点s->Data=bDatc;//设h力此結p二head;if(head==NULL){//若是空表，使b作为第一个结点head=s;s->next=NULL;)else)if(p-〉Data==aDate){//芯•a是第•一个结点s->next=p;head=s;)else{whilc(p->Data!=aDate&&p-〉ncxt!=NULL){//奔找错/Xaq=p；p=p->next;)if(p->Data==aDate){//若有结点aq->next=

8、s;s-〉ncxt=p;)else)//若没有结点ap-〉next=s;s-〉nexl=NULL;I}))2.链表结点的删除如果要在链表中删除结点a并释放被删除的结点所占的存储空间，则需要考虑下列几种情况。(1)若要删除的结点a是第一个结点，则把head指向a的下一个结点、(2)若要删除的结点a存在于链农中，但不是第-个结点，则应使a得上一个结Aa_k-1的指针域指向a的下一个结点a_k+l。(3)空表或要删除的结点a不存在，则不做任何改变