资源描述：
《数据结构-带头节点的单向链表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、带头结点的单链表线性表(List)部分操作的实现小结和作业链式存储结构及实现顺序存储和链式存储的区别链式存储结构1、每个数据元素使用一个结点表示ai2、每个数据元素在物理存储空间可以不相邻3、数据元素之间的线性关系由指针链接保证a1a3a2链式存储结构的实现1、结点用一个结构表示typedefstructLNode{ElemTypedata;structLNode*next;}LNodeai2、定义一个指向LNode的指针类型typedefLNode*LinkList带头结点的单链表逻辑形态a1a2a3L空链表L头结点部分操作的实现InitList
2、(&L)DestroyList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListMerge(La,Lb,&Lc)讨论ListLength(L)ListMerge(La,Lb,&Lc)GetItem(L,i,&e)讨论InitListStatusInitList(ListLink&L){node=(LNode*)malloc(sizeof(LNode));}return(OK);if(!node)return(OVERFLOW);node->next=NULL;L=node;LDestroyList分析:释放每
3、个结点占用的存储空间1、如果L不为空，则：1.1、p=L,L=L->next;1.2、释放p结点的空间a1a2a3Lp1.3、转12、如果L为空，结束DestroyListStatusDestroyList(LinkList&L){}while(L){p=L;L=L->next;free(p);}return(OK);ListLengtha1a2a3LpLpp=Lcount=0p->next==NULLcount=0pppcount=1count=2count=3ListLengthintListLength(LinkListL){count=0;
4、p=p->next;count++;}}return(count);p=L;while(p->next){GetItem1、p指向头结点2、重复p=p->next操作i次3、p指向了第i个元素pa1a2a3LGetItemStatusGetIem(LinkListL,inti,ElemType&e){p=L;j=0;while(jnext;j++;e=p->data;}}return(OK);if(i<1
5、
6、i>ListLength(L))return(ERROR);指向头结点循环i次ListInserta1a2a3Lp1、p指向
7、头结点2、如果p不为空，重复执行p=p-nexti-1次3、如果p不为空，p指向了第i-1个结点，执行插入操作ListInsertStatusListInsert(LinkList&L,inti,ElemTypee){p=L;j=0;while(jnext;j++;}if(i<1
8、
9、i>ListLength(L)+1)return(ERROR);ListInsert}node=(LNode*)malloc(sizeof(LNode));if(!node)return(OVERFLOW);node->data=e;node->n
10、ext=p->next;p->next=node;return(OK);ListDeletea1a2a3L1、p指向头结点2、如果p不为空，执行p=p->nexti-1次，使得p指向第i-1个结点。3、q=p->next，q指向第i个结点。4、执行删除操作ListDeleteStatusListDelete(LinkList&L,inti,ElemType&e){p=L;j=0;while(jnext;j++;}if(i<1
11、
12、i>ListLength(L))return(ERROR);q=p->next;e=q->data;
13、free(q);}return(OK);p->next=q->next;a1a2a3LListMerge原形StatusListMerge(LinkListLa,LinkListLb,LinkList&Lc)作用：把有序表La和Lb合并得到一个新的有序表La:a1≤a2≤a3……≤amLb:b1≤b2≤b3……≤bnLc:c1≤c2≤c3……≤cm+nci=ajorci=bkListMerge136La1028Lb9Lc12368910ListMerge1、首先建立空表LcLcpcnode=(LNode*)malloc(sizeof(LNode))
14、;if(!node)return(OVERFLOW);Lc=pc=node;node->next=NULL;ListMer
