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

作者: 遥遥无期74696531
来源: 51数据库
2021-09-21

#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;
}