链表的创建,插入,删除,输出基本操作

2018-12-04 07:13:59来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

#include<stdio.h>
#include<cstdlib>
struct student  //定义一个学生结点,结点包括值域和指针域
{
 int num;//学号
 char name[20];//姓名
 char address[20];//地址
 struct student *next;//定义结点的指针域,指向下一个结点
};
typedef struct student LIST;
LIST *CreateList();
LIST *InsertNode(LIST *h,LIST *s);
LIST *DeleteNode(LIST *h,long no);
void Display(LIST *h);
int main()
{
 LIST *head,*p;//定义指向结点的指针
 long no;//定义学号变量
 head=CreateList();//调用CreateList函数创建链表
 printf("学号 姓名 地址\n");
 Display(head);
 printf("输入要插入的结点\n");
 p=(LIST *)malloc(sizeof(LIST));//动态的生成一个结点
 scanf("%d %s %s",&p->num,&p->name,&p->address);
 head=InsertNode(head,p);
 printf("学号 姓名 地址\n");
 Display(head);
 printf("请输入删除结点的学号:\n");
 scanf("%d",&no);
 head=DeleteNode(head,no);
 if(head!=NULL)
 {
  printf("学号 姓名 地址\n");
  Display(head);
 }
 return 0;
}
/*链表的创建*/
LIST *CreateList()
{
 LIST *head,*pre,*cur;
 int i,n;
 head=NULL;
 printf("输入结点的个数:\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  cur=(LIST *)malloc(sizeof(LIST));
  cur->next=NULL;
  if(head==NULL)//表示处理当前第一个结点
   head=cur;
  else
   pre->next=cur;
  scanf("%d %s %s",&cur->num,&cur->name,&cur->address);
  pre=cur;
 }
 return head;
}
/*链表结点的插入*/
LIST *InsertNode(LIST *h,LIST *s)
{
 LIST *pre,*p;
 p=h;
 if(h==NULL)
 {
  h=s;
  s->next=NULL;
  
 }
 else
 {
  while(s->num>p->num&&p->next!=NULL)//在链表中找到要插入的位置
  {
   pre=p;
   p=p->next;
  }
  if(s->num<=p->num)
  {
   if(h==p)//若插入的结点在第一个结点之前
   {
    h=s;
    s->next=p;
   }
   else//若插入的结点在中间位置
   {
    s->next=p->next;
    p->next=s;
   }
  }
  else
  {
   p->next=s;
   s->next=NULL;
  }    
 }
 return h; 
}
/*链表结点的元素删除*/ 
LIST *DeleteNode(LIST *h,long no)
{
 LIST *q;
 LIST *pre;
 q=h;
 if(q==NULL)
 {
  printf("链表为空,不能删除结点\n");
  return NULL;
 }
 while(q->num!=no&&q!=NULL)//查找带删结点,并保存其上一个结点
 {
  pre=q;
  q=q->next;
 }
 if(q->num==no)
 {
  if(q==h)
  {
   h=h->next;
  }
  else
  {
   pre->next=q->next;
   free(q);
   printf("该结点被删除成功!");
  }
 }
 else
 {
  printf("在链表中无法找到该学号,删除失败!");
 }
 return h;
}
/*完整的链表输出*/
void Display(LIST *h)
{
 LIST *q;
 q=h;
 while(q!=NULL)
 {
  printf("学号:%d  姓名:%s  地址:%s\n",q->num,q->name,q->address);
  q=q->next;
 }
}
/**********************************NOTE*******************************
链表主要通过指针进行访问,因此,他的地址不是连续的。因此,
链表无法实现随机存储,链表的元素查找,需要从头结点开始逐
个扫描进行查找。链表是一种动态结构,相对于顺序表而言,在
执行插入和删除过程不需要移动大量的元素,执行效率大大提高。
以下就算法的四个基本操作进行总结。
链表的创建:(此处采用尾插法,并且链表元素有序)
1、定义四个指针*h,*rear,*cur,*p;分别代表头指针,尾指针(指向
链表最后一个结点的指针),当前结点的指针,辅助指针
2、将头指针指向NULL(此处为了统一所有操作,链表都带有头
结点
,h=NULL,目的是建立一个全新的链表)
3、为全新的链表添加结点,由于是动态的,创建一个结点先要
申请内存,然后为其赋值,最后将其插入链表。由于链表的三个
部分(首部,尾部,中间)的不同,一般插入时要予以判断,
进行不同操作。具体如下:(初始时p=h)
1)申请一个结点并初始化
 cur=(LIST *)malloc(sizeof(LIST));
 cur->next=NULL;
 scanf("%d %s %s",&cur->num,&cur->name,&cur->address);//此步根据结点的定义来决定
2)插入链表
   当链表为空时
   if(h==NULL)
     h=cur;
    当链表不空时,通过某一参值比较,知道插入的位置(此处以num为参值)
    while(p->num<cur->num&&p!=NULL)
     p=p->next;
    if(p==h)//当插入位置为第一个结点时
    {
     cur->next=h->next;
     h=cur;
    }
    else if(p->next==NULL)//当插入位置为最后一个结点之后
    {
     p->next=cur;
     cur->next=NULL;//可不要
    }
    else//当插入位置在中间时
    {
     cur->next=p->next;
     p->next=cur;
    }
    插入完成,返回链表return h;
    链表的插入:略,操作与链表的创建相同
    链表的删除:
    查找与删除,根据删除的参值进行查找删除元素前一个元素的位置(此处参值为num,前一元素指针*pre)
       1)如果链表为空,则查找失败,输出提示信息
       if(h==NULL)
        printf("链表为空,查找失败!\n")
       else
       {
         while(p->num!=no&&p!=NULL)//查找待删元素及其前一个结点的位置
         {
          pre=p;
          p=p->next;
         }
         if(p->num==no)
         {
          if(p==h)//当待删结点为第一个结点
           h=pre->next;
          else
           pre->next=p->next;
         }
         else
          printf("链表中不存在这个结点,删除失败!\n");
     }
     return h;
     链表的输出:
     while(q!=NULL)
 {
  printf("学号:%d  姓名:%s  地址:%s\n",q->num,q->name,q->address);
  q=q->next;
 }
 
 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C语言实例解析精粹学习笔记——19

下一篇:c语言实现通讯录管理系统(c课程设计)