C数据结构之单链表详细示例分析

#include<stdio.h>
#include<stdlib.h>
typedefstructtype
{
 intnum;
 structtype*next;
}TYPE;
//=============================================================
//语法格式：TYPE*init_link_head(intn)
//实现功能：从头到尾，正序创建一个具有n个节点的链表，并对其值进行初始化
//参数： n:链表的长度，即节点的个数
//返回值： 所创建链表的首地址
//=============================================================
TYPE*init_link_head(intn)
{
 inti;
 TYPE*phead=NULL,*pf=NULL,*pi=NULL;
 for(i=0;i<n;i++)
 {
 pi=(TYPE*)malloc(sizeof(TYPE));
 printf("pleaseinoutnum:\n");
 scanf("%d",&pi->num);
 if(i==0)
  pf=phead=pi;
 else
 {
  pf->next=pi;
  pf=pi;
 }
 pi->next=NULL;
 }
 returnphead;
}
//=============================================================
//语法格式：TYPE*init_link_end(intn)
//实现功能：从尾到头，倒序创建一个具有n个节点的链表，并对其值进行初始化
//参数： n:链表的长度，即节点的个数
//返回值： 所创建链表的首地址
//=============================================================
TYPE*init_link_end(intn)
{
 TYPE*phead=NULL,*pi=NULL;
 inti;
 for(i=0;i<n;i++)
 {
 pi=(TYPE*)malloc(sizeof(TYPE));
 printf("pleaseinoutnum:\n");
 scanf("%d",&pi->num);
 if(i==0)
  pi->next=NULL;
 else
  pi->next=phead;
 phead=pi;
 }
 returnphead;
}
//=============================================================
//语法格式：insert_link(TYPE*phead,TYPE*pi)
//实现功能：将新申请的节点加入到指定链表中
//参数： *phead:待插入链表
//   *pi：带插入节点
//返回值： 插入指定节点后的新链表首址
//=============================================================
TYPE*insert_link(TYPE*phead,TYPE*pi)
{
 TYPE*pb,*pf;
 pb=phead;
 if(phead==NULL)
 {
 phead=pi;
 phead->next=NULL;
 }
 else
 {
 while((pi->num>pb->num)&&(pb->next!=NULL))
 {
  pf=pb;
  pb=pb->next;
 }
 if(pi->num<=pb->num)
 {
  if(pb==phead)
  {
   pi->next=phead;
   phead=pi;
  }
  else
  {
   pf->next=pi;
   pi->next=pb;
  }
 }
 else
 {
  pi->next=NULL;
  pb->next=pi;
 }
 }
 returnphead;
}
//=============================================================
//语法格式：delete_link(TYPE*phead,intnum)
//实现功能：删除给定序号所指向的节点
//参数： *phead:待删除链表
//   num：所需删除的节点
//返回值： 删除指定节点后的新链表首址
//=============================================================
TYPE*delete_link(TYPE*phead,intnum)
{
 TYPE*pf;
 TYPE*pb;
 if(phead==NULL)
 {
 printf("\nemptylink\n");
 returnNULL;
 }
 pb=phead;
 while((pb->num!=num)&&pb->next!=NULL)
 {
 pf=pb;
 pb=pb->next;
 }
 if(pb->num==num)
 {
 if(pb==phead)
  phead=phead->next;
 else
  pf->next=pb->next;
 free(pb);
 printf("thenodeisdeleted\n");
 }
 else
 printf("thenodenotfound\n");
 returnphead;
}
//=============================================================
//语法格式：print_link(TYPE*phead)
//实现功能：打印指定链表中的全部节点数据
//参数： *phead：待打印的链表首址
//返回值： 无
//=============================================================
voidprint_link(TYPE*phead)
{
 TYPE*temp=phead;
 while(temp!=NULL)
 {
 printf("%d",temp->num);
 temp=temp->next;
 }
}
//=============================================================
//语法格式：search_num(TYPE*phead，intnum)
//实现功能：在指定的链表中，按姓名查找指定元素
//参数： phead：待查找的链首址，num需要查找的字符串
//返回值： 无
//=============================================================
voidsearch_num(TYPE*phead,intnum)
{
 TYPE*temp=phead;
 while(temp!=NULL)
 {
 if(temp->num==num)
  printf(" %d",num);
 temp=temp->next;
 }
 if(temp==NULL)
 printf("nodenotbeenfound\n");
}
//=============================================================
//语法格式：order_link(TYPE*phead)
//实现功能：采用冒泡法，对指定链表按序号进行排序（交换数据域）
//参数： phead：待排序的链首址
//返回值： 排好序的链表phead指针
//=============================================================
TYPE*order_link(TYPE*phead)
{
 TYPE*pb,*pf,temp;
 pb=pf=phead;
 if(phead==NULL)
 returnNULL;
 while(pb->next!=NULL)
 {
 pf=pb->next;
 while(pf!=NULL)
 {
  if(pb->num>pf->num)
  {
   temp=*pb;
   *pb=*pf;
   *pf=temp;
   temp.next=pb->next;
   pb->next=pf->next;
   pf->next=temp.next;
  }
  pf=pf->next;
 }
 pb=pb->next;
 }
 returnphead;
}
//=============================================================
//语法格式：reverse_link(TYPE*phead)
//实现功能：对给定链表按序号进行倒序排序
//参数： phead：待排序的链首址
//返回值： 排好序的链表phead指针
//=============================================================
TYPE*reverse_link(TYPE*phead)
{
 TYPE*pb,*pf,*temp;
 pb=phead;
 pf=pb->next;
 while(pf!=NULL)
 {
 temp=pf->next;
 pf->next=pb;
 pb=pf;
 pf=temp;
 }
 phead->next=NULL;
 phead=pb;
 returnphead;
}
//=============================================================
//语法格式：free_all(TYPE*phead)
//实现功能：释放链表中所有的节点
//参数： phead：待释放的链表首址
//返回值： 无
//=============================================================
voidfree_all(TYPE*phead)
{
 TYPE*p;
 while(phead!=NULL)
 {
 p=phead->next;
 free(phead);
 phead=p;
 }
}
//=============================================================
//语法格式：merge(TYPE*p1,TYPE*p2)
//实现功能：对两个链表进行升序合并
//参数： p1,p2两个代合并的链表
//返回值： 合并后的链表
//=============================================================
TYPE*merge_link(TYPE*p1,TYPE*p2)
{
 TYPE*p,*phead;
 if(p1==NULL)
 returnp2;
 if(p2==NULL)
 returnp1;
 if(p1->num<p2->num)
 {
 phead=p=p1;
 p1=p1->next;
 }
 else
 {
 phead=p=p2;
 p2=p2->next;
 }
 while(p1!=NULL&&p2!=NULL)
 {
 if(p1->num<p2->num)
 {
  p->next=p1;
  p=p1;
  p1=p1->next;
 }
 else
 {
  p->next=p2;
  p=p2;
  p2=p2->next;
 }
 }
 if(p1!=NULL)
 p->next=p1;
 else
 p->next=p2;
 returnphead;
}
//=============================================================
//实现方法：  运用递归
//语法格式：merge(TYPE*p1,TYPE*p2)
//实现功能：对两个链表进行升序合并
//参数： p1,p2两个代合并的链表
//返回值： 合并后的链表
//=============================================================
TYPE*merge_link_self(TYPE*p1,TYPE*p2)
{
 TYPE*phead=NULL;
 if(p1==NULL)
 returnp2;
 if(p2==NULL)
 returnp1;
 if(p1->num<p2->num)
 {
 phead=p1;
 phead->next=merge_link(p1->next,p2);
 }
 else
 {
 phead=p2;
 phead->next=merge_link(p1,p2->next);
 }
 returnphead;
}
intmain(void)
{
 return0;
}