链表中为何加头结点(实例)

《链表中为何加头结点(实例)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、插入(不带头结点)插入（三种情况）第一种情况：在第一个结点前插入（插入前）（插入后）Lnewnodenewnodea1a2a1a2xxnewnode->next=L;L=newnode;L第二种情况：在链表中间插入(插入前)(插入后)newnodepnewnodepnewnode->next=p->next;p->next=newnode；第三种情况：在链表末尾插入p(插入前)(插入后)newnodenewnodepnewnode->next=p->next;p->next=newnode；算法描述intInsert(LinkListL,intx,inti){//在链表

2、第i个结点处插入新元素xLnode*p=L;intj=1;while(p!=NULL&&jnext;j++;}//找第i-1个结点if(p==NULL&&L!=NULL){printf(“无效的插入位置!”);//终止插入return0;}Lnode*newnode=(Lnode*)malloc(sizeof(Lnode));//创建新结点newnode->data=x;if(L==NULL

3、

4、i==1){//插入空表或非空表第一个结点之前newnode->next=L;//新结点成为第一个结点L=newnode;}else{//插在表中间或末尾n

5、ewnode->next=p->next;p->next=newnode;}return1;}带头结点的单链表头结点位于表的最前端，本身不带数据，仅标志表头。设置头结点的目的:简化链表操作(不管单链表是否为空，头指针均不为空；并使得对单链表的操作在各种情况下统一）。非空表空表^ana1LL^插入s->next=p->next;p->next=s;LsLsLs^Ls^pppp插入前插入后ss插入pps->next=p->next;p->next=s;intInsert(LinkListL,ListDatax,inti){//将新元素x插入在链表中第i号结点位置ListNode

6、*p=Locate(L,i-1);if(p==NULL)return0;//参数i值不合理返回0ListNode*newnode=//创建新结点(ListNode*)malloc(sizeof(ListNode));newnode->data=x;newnode->link=p->link;//链入p->link=newnode;return1;}删除q=p->link;p->link=q->link;free(q);删除前L(非空表）(空表）L^Lpq^pqL删除后intdelete(LinkListL,inti){//将链表第i号元素删去ListNode*p,*qp=L

7、ocate(L,i-1);//寻找第i-1个结点if(p==NULL

8、

9、p->link==NULL)return0;//i值不合理或空表q=p->link;p->link=q->link;//删除结点free(q);//释放return1;}单链表清空voidmakeEmpty(LinkListfirst){//删去链表中除头结点外的所有其它结点Lnode*q;while(first->next!=NULL)//当链不空时，循环逐个删去所有结点{q=first->next;first->next=q->next;free(q);//释放}}计算单链表长度intLength(

10、LinkListfirst){Lnode*p=first->next;//指针p指示第一个结点intcount=0;while(p!=NULL){//逐个结点检测p=p->next;count++;}returncount;}按值查找Lnode*Find(LinkListfirst,DataTypex){//在链表中从头搜索其数据值为x的结点Lnode*p=first->next;//指针p指示第一个结点while(p!=NULL&&p->data!=x)p=p->next;returnp;}按序号查找（定位）Lnode*Locate(LinkListfirst,inti)

11、{//返回表中第i个元素的地址if(i<0)returnNULL;Lnode*p=first;intk=0;while(p->next!=NULL&&knext;k++;}//找第i个结点if(k==i)returnp;//返回第i个结点地址elsereturnNULL;}LinkListcreateListR(void){charch;LinkListL=//建立头结点(LinkList)malloc(sizeof(Lnode));Lnode*s,*r;L->next=NULL;r=L;whil