双链表的插入与删除.c

双链表的一个简单实现

#include<stdio.h>
#include<malloc.h>

#define OK 1
#define ERROR 0


typedef struct DuLNode{
	int data;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode,*DuLinkList;


DuLinkList CreateList(int n);
int ListInsert(DuLinkList L,int i,int e);
int ListDelete(DuLinkList L,int i);
void Display(DuLinkList L);


main()
{
	int n;
	int i,e;
	int choose=0;
	DuLinkList L;
	printf("\n*********  程序开始前，先创建双链表  ************\n");
	printf("请输入你要创建双链表结点数 :");
	scanf("%d",&n);
	L=CreateList(n);
	printf("\n链表创建成功,输出如下:\n");

	Display(L);
	
	while(choose!=3)
	{
		choose=0;
		printf("\n你可以对双链表进行的操作如下 :\n");
	    printf("1. 插入\n2. 删除\n3. 退出\n");
	    while(choose!=1&&choose!=2&&choose!=3)
		{
		    printf("请输入 1 或 2 或 3 选择 插入 或 删除 或 退出:");
	        scanf("%d",&choose);
		    if(choose!=1&&choose!=2&&choose!=3) printf("输入错误，请重新输入\n");
		}

	    //printf(" Check choose %d\n",choose);

	    if(choose==1)
		{
		    while(1)
			{
			    printf("\n双链表插入前为:\n");
			    Display(L);
			    printf("请输入要插入的数:");
		        scanf("%d",&e);
		        printf("请输入要插入的位置:");
		        scanf("%d",&i);
			    if(ListInsert(L,i,e)==1) { printf("\n双链表插入后为:\n"); Display(L); break;}
			    else printf("输入的插入位置错误，请重试\n");
			}
		}
	    else if(choose==2)
		{
		    while(1)
			{
			    printf("\n双链表删除前为:\n");
			    Display(L);
			    printf("请输入删除的结点的序号:");
		        scanf("%d",&i);
			    if(ListDelete(L,i)==1) { printf("\n双链表删除后为:\n"); Display(L); break; }
			    else printf("输入的结点序号错误，请重试\n");
			}
		}
	    else if(choose==3)
		{
		    printf("\n双链表最后为:\n");
		    Display(L);
		    continue;
		}
	}

	

}

DuLinkList CreateList(int n)
{
	int i,m;
	DuLinkList L,p,s;

	L=(DuLinkList)malloc(sizeof(DuLNode));
	L->data=n;
	L->prior=NULL;
	L->next=NULL;

	p=L;

	for(i=1;i<=n;i++)
    {
		printf("请输入第%d个结点的值 :",i);
		scanf("%d",&m);

		s=(DuLinkList)malloc(sizeof(DuLNode));
		s->data=m;
		s->next=NULL;
		s->prior=p;
		p->next=s;
		p=s;
	}

	return L;
}




int ListInsert(DuLinkList L,int i,int e)
{
	int j=0;
	DuLinkList p,s;

	p=L;

	while(p!=NULL&&j<i-1) { p=p->next; j++;}

	if(p==NULL||j>i-1) { printf("插入位置错误"); return ERROR; }

	s=(DuLinkList)malloc(sizeof(DuLNode));
	s->data=e;
	s->next=p->next;
	s->prior=p;
	p->next=s;
	s->next->prior=s;

	L->data++;

	return OK;
}

int ListDelete(DuLinkList L,int i)
{
	int j=0;
	DuLinkList p,temp;

	p=L;

	while(p!=NULL&&j<i-1) { p=p->next; j++; }

	if(p==NULL||j>i-1) { printf("删除位置错误"); return ERROR; }

	temp=p->next;
	p->next=p->next->next;
	p->next->prior=p;
	free(temp);

	L->data--;
	
	return OK;

}

void Display(DuLinkList L)
{
	int i,n;
	DuLinkList p;
	n=L->data;
	p=L->next;
	printf("\n开始输出链表\n");
	printf("链表共有 %d 个结点，下面是各个结点的值 :\n",n);
	for(i=1;i<=n;i++)
	{
		printf("结点 %d 的值 : %d\n",i,p->data);
		p=p->next;
	}
	printf("链表输出完毕\n\n");

}