插入与删除（无头结点）.cpp

数据结构实验--实现链表的插入与删除（源码

/*	实验内容
1．链表是有序的，现在删除数据x，若x不存在，输出一段提示信息。
（无头结点）
2．线性表v的数据递增有序，试将x插入表中并保持有序性
   (2)链表表示（无头结点）
*/
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct LNode)
//定义LNode结构体
struct LNode
{
	int data;
	LNode *next;
};
int n;

LNode *creatlist(void)//创建链表
{
	LNode *head,*p1,*p2;
	n=0;
	p1=p2=(LNode *)malloc(LEN);//生成一个结点，p1、p2都指向该结点
	scanf("%d",&p1->data);
	head=NULL;
	while(p1->data!=0)//这里0是结束标志
	{
		n=n+1;
		if(n==1)//如果只有一个结点，将head指针也指向该结点
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(LNode *) malloc(LEN);
		scanf("%d",&p1->data);
	}
	p2->next=NULL;
	return head;
}
void print(LNode *head)//输出链表
{
	LNode *p;
	printf("\n输入的%d个记录为：\n",n);
	p=head;
    if(head!=NULL)//判断链表是否为空
		do
		{
			printf("%d ",p->data);
			p=p->next;
		}while(p!=NULL);
}
LNode *del(LNode *head,int num)//删除结点数据为num的数
{
	LNode *p1,*p2;
	if(head==NULL)
	{	printf("\n该链表为空！\n");}
	p1=head;
	while(num!=p1->data&&p1->next!=NULL)
	{    //从第一个结点开始，如果要删除的数不等于该结点上的数，
		 //而且链表不止一个结点，那么继续指向下一个结点，直到找到需要的数。
		p2=p1;
		p1=p1->next;
	}
	if(num==p1->data)//输入的数据可以在链表中找到
	{
		if(p1==head)//如果只有一个结点的情况
			head=p1->next;
		else
			p2->next=p1->next;
		printf("\n删除的结点为:%d\n",num);
		n=n-1;
	}
	else
	{	printf("\n没找到要删除的结点！\n");}
	return head;
}
LNode * insert(LNode *head,LNode *data)//将数据插到链表中第一个比它大的数据前
{
	LNode *p0,*p1,*p2;
	p1=head;
	p0=data;
	if(head==NULL)
	{
		head=p0;
		p0->next=NULL;
	}
	else//将插入的数与链表中的原数据进行比较，插在第一个比他打的数据前
	{
		while((p0->data>p1->data)&&(p1->next!=NULL))
		{//插入的数>p1指向的结点数据，而且不止一个结点，继续寻找直到比他大的数据
			p2=p1;
			p1=p1->next;
		}
		if(p0->data<=p1->data)
		{//插入的数<=p1指向的结点数据，将数插入到p1结点之前
			if(head==p1)
				head=p0;
			else
				p2->next=p0;
		    	p0->next=p1;
		}
		else/*链表为空，插到最后的结点之后*/
		{
			p1->next=p0;
			p0->next=NULL;
		}
	}
	n=n+1;
	return head;
}
void main()
{
	LNode *head,*h;
	int del_num;
	int select;
	printf("请输入一组有序数列(结束符：0)：\n");
	head=creatlist();
	print(head);
//clrscr();	
  do
  {     //操作选择
   printf("\n1:插入一个数\n");
   printf("2:删除一个数\n"); 
   printf("3:结束\n");     
   scanf("%d",&select); 
   switch(select)
   {
   case 1:
	printf("\n请输入要插入的数new_num：\n");
    h=(LNode *)malloc(LEN);
	scanf("%d",&h->data);
	while(h->data!=0)
	{head=insert(head,h);
	 print(head);
     printf("\n请输入要插入的数(输入0可结束插入)new_num：\n");
     h=(LNode *)malloc(LEN);
	 scanf("%d",&h->data);}
	 break;
   case 2:
	printf("\n输入要删除的数del_num:\n");
	scanf("%d",&del_num);
	while(del_num!=0)
	{head=del(head,del_num);
	 print(head);
	 printf("\n输入要删除的数(输入0可结束删除)del_num:\n");
	 scanf("%d",&del_num);}
	break;
   case 3:
     printf("结束本程序！");   
     printf("\n");
     break;
	}
   }
   while(select!=3);
   
}