数据结构---头插法和尾插法建立链表(各分有无头结点).doc

《数据结构---头插法和尾插法建立链表(各分有无头结点).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一链表的建立及基本操作方法实现三、【算法思想】1)利用头插法和尾插法建立一个无头结点单链表链表无头结点，则在创建链表时，初始化链表指针L=NULL。当用头插法插入元素时，首先要判断头指针是否为空，若为空，则直接将新结点赋给L,新结点next指向空，即L=p,p->next=NULL，若表中已经有元素了，则将新结点的next指向首结点，然后将新结点赋给L即（p->next=L,L=p）。当用尾插法插入元素时，首先设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer和头指针一样即tailPointer=L。插入

2、元素时，首先判断链表是否为空，若为空，则直接将新结点赋给L即L=p，若不为空，else将最后一个元素的next指向新结点即tailPointer->next=p，然后跳出这个if,else语句，将新结点next指向空，并且将tailPointer指向新结点即p->next=NULL,tailPointer=p。2)利用头插法和尾插法建立一个有头结点单链表链表有头结点，则在创建链表时，初始化链表指针L->next=NULL。与无头结点区别在于，判断链表为空是根据L->next是否为空。用头插法插入元素时，要判断链表是否为空，若为空则将新结点next指

3、向空，作为表尾，若不为空，则直接插入，将新结点next指向头结点next的指向，再将头结点next指向新结点即p->next=L->next,L->next=p。用尾插法插入元素时，首先也要设置一个尾指针tailPointer以便随时指向最后一个结点，初始化tailPointer=L，与无头结点区别就只是插入第一个元素时有区别。插入元素时，不需要判断链表是否为空，直接进行插入，代码tailPointer->next=p,p->next=NULL,tailPointer=p。3）带头结点和无头结点单链表元素显示方法的区别：区别在于，显示时带头结点是从

4、头结点next开始即p=L->next，而无头结点链表是直接从L开始即p=L。四、【源程序代码】1)利用头插法和尾插法建立一个无头结点单链表#include#includetypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;/*尾插法*/voidcreatListTailInsert(LinkList&L,intn){LinkListp,tailPointer;inti;//计数L=(LinkList)malloc(sizeof(LNode)

5、);if(!L)exit(0);//分配空间失败则退出程序L=NULL;//noheadcrunodetailPointer=L;//把尾赋给尾指针printf("taillist(%d):",n);for(i=0;idata));if(L==NULL)L=p;//当链表为空,L赋给第一个结点elsetailPointer->next=p;//将新结点插入尾部；p->next=NULL;tailPointe

6、r=p;//插入的结点变为尾结点}}/*头插法*/voidcreatListHeadInsert(LinkList&L,intn){LinkListp;inti;//计数L=(LinkList)malloc(sizeof(LNode));if(!L)exit(0);//分配空间失败则退出程序L=NULL;//noheadcrunodeprintf("headlist(%d):",n);for(i=0;i

7、&(p->data));if(L!=NULL)p->next=L;elsep->next=NULL;L=p;//将头结点next指向赋给新结点}}/*依次显示表中所有元素*/voidgetAllElem(LinkList&L,intn){LinkListp;inti=0;p=L;while(p&&idata);p=p->next;i++;}printf("");}voidmain(){LinkListheadList;LinkListtailList;intcount;//插入元素个数printf("cou

8、nt=");scanf("%d",&count);creatListHeadInsert(headList,count);