陈少博.cpp

编写程序完成单链表的创建、插入、删除、排序、并、交、差运算、及输出等基本操作。

#include <malloc.h> 
#include<stdlib.h> 
#include <stdio.h> 
typedef struct Lnode
{int data; 
struct Lnode *next; 
}*Linklist,Lnode;       
void CreatList(Lnode *L)   /*建立链表函数*/
{ Lnode *p;
  int value;
  L->next=NULL;
 while (1)  /*当输入非0数值时*/
  {scanf( "%d",&value); 
  if (value==NULL)
   return;	
   p=(Lnode *)malloc(sizeof(Lnode));  /*建立P链表*/
   p->data=value;
   p->next=L->next;   /*把后输入的插到前面*/
   L->next=p;
 }
}
void paixu(Lnode *L)
{
 Linklist r,q,small;int temp; 
 for(r=L->next;r->next!=NULL;r=r->next) 
 {small=r; 
  for(q=r->next;q;q=q->next) /*找到链表中最小元素*/
     if(q->data<small->data) 
        small=q; 
  if(small!=r) 
  {temp=r->data; 
  r->data=small->data;        /*把最小的数值换到P指针所指的位置数值上（原P指针的next指向不变）*/
  small->data=temp;           /*把原先p指针所指位置的数值填入被置换出的最小元素位置*/
  } 
 } 
 printf("正在对新链表进行排序……\n"); 
} 
void PrintList(Lnode *L) /*打印链表函数*/
{ 
 Lnode *p=L->next;     /*带头节点，把指针置于第一个数*/
 if(p==0)
 {printf("链表为空");}
 else
 printf("链表为：");
 {while(p)
 {
 printf("%d>>", p->data);
 p=p->next;
 }
 } 
 printf("\n");
}  

inter(Lnode *L,int i)
{
 Lnode *k=L->next;
 while(k)
 {if (k->data==i)
    return 1;
  k=k->next;
 }
 return 0;
}

int ListInsert_L(Lnode *L, int i, int e)
{
 Lnode *p=L->next;
 Lnode *s;
 int j=0;
 while (p && j<i-1) {p=p->next; ++j;}
 if (!p || j>i-1) return 0; 
 s=(Lnode *)malloc(sizeof(Lnode));
 s->data=e;
 s->next=p->next;
 p->next=s;
 return 1;
}

int ListDelete_L(Lnode *L,int i)
{
 Lnode *p=L->next;
 int j=0;
 Lnode *q;
 while (p->next && j<i-1) {p=p->next; ++j;} /*找出第i节点，并令p指向其前趋*/
 if (!p->next || j>i-1) return 0; 
 q=p->next;
 p->next=q->next;
 free(q);
 return 1;
}

main()
{
 int sign,sign1,signa,signb,signc,i,x,ca,cb,cc;
 int choice=1;
 Lnode *A,*B,*C,*D,*E,*L,*p,*q,*n,*m;
 A=(Lnode *)malloc(sizeof(Lnode));
 B=(Lnode *)malloc(sizeof(Lnode));
 C=(Lnode *)malloc(sizeof(Lnode));
 D=(Lnode *)malloc(sizeof(Lnode));
 E=(Lnode *)malloc(sizeof(Lnode));
 printf("\t 《数据结构课程设计——单链表的基本操作》\n\n");
 while (choice)
	{
	 printf("\t 请选择您想进行的操作:\n 1:对A链表操作 \n 2:对B链表操作 \n 3:两链表运算 \n 4:退出程序 \n \n 您的选择是：");
	 scanf("%d",&sign1);
			if (sign1==1)
				{L=A;
				 ca=1;
			 while (ca)
			   {printf("\t 请选择对A链表进行的操作:\n 1:建立链表 \n 2:对链表排序 \n 3:在链表中插入元素 \n 4:在链表中删除元素 \n 5:返回上一级菜单 \n 您的选择是：");
				scanf("%d",&signa);
	            switch(signa)
	             {
		          case 1:
			          printf("\n请输入链表元素(输入0结束)\n");
			          CreatList(A);
			          PrintList(A);
					  break;
		          case 2:
					  printf("对A链表进行排序，结果为：\n ");
			          paixu(A);
                      PrintList(A);
					  break;
				  case 3:
			          printf("请输入想要插入的位置及插入的数值（以逗号分隔）: ");
			          scanf("%d,%d",&i,&x);
			          if (ListInsert_L(L,i,x)==1)
				        {printf("修改成功!目前A链表为：\n");
			             PrintList(L);}
                      else 
			            printf("警告!您输入的插入位置超过链表长度。 \n");
			  			break;
			  	  case 4:
			  	      printf("请输入想要删除的元素位置: ");
			          scanf("%d",&i);
			          if (ListDelete_L(L,i)==1)
				        {printf("删除元素成功!目前A链表为：\n");
			             PrintList(L);}
                      else 
			            printf("警告!您输入的删除位置超过链表长度。 \n");
			  			break;
			  	  case 5: 
			  	       ca=0;
			  	       break;
			  	  default: 
			  	  printf("警告!只能选择1-5。 \n");
			  	  break;
			  	 }
			     }
			    }
			else if (sign1==2) 
				{L=B;
				 cb=1;
			 while (cb)
			   {printf("\t 请选择对B链表进行的操作:\n 1:建立链表 \n 2:对链表排序 \n 3:在链表中插入元素 \n 4:在链表中删除元素 \n 5:返回上一级菜单 \n 您的选择是：");
				scanf("%d",&signb);
	            switch(signb)
	             {
		          case 1:
			          printf("\n请输入链表元素(输入0结束)\n");
			          CreatList(B);
			          PrintList(B);
					  break;
		          case 2:
					  printf("对B链表进行排序，结果为：\n ");
			          paixu(B);
                      PrintList(B);
					  break;
				  case 3:
			          printf("请输入想要插入的位置及插入的数值（以逗号分隔）: ");
			          scanf("%d,%d",&i,&x);
			          if (ListInsert_L(L,i,x)==1)
				        {printf("修改成功!目前B链表为：\n");
			             PrintList(L);}
                      else 
			            printf("警告!您输入的插入位置超过链表长度。 \n");
			  			break;
			  	  case 4:
			  	      printf("请输入想要删除的元素位置: ");
			          scanf("%d",&i);
			          if (ListDelete_L(L,i)==1)
				        {printf("删除元素成功!目前B链表为：\n");
			             PrintList(L);}
                      else 
			            printf("警告!您输入的删除位置超过链表长度。 \n");
			  			break;
			  	  case 5: 
			  	       cb=0;
			  	       break;
			  	  default: 
			  	  printf("警告!只能选择1-5。 \n");
			  	  break;
			  	 }
			     }
				}
				
			else if (sign1==3) 
				{cc=1;
			     while (cc)
			      {printf("\t 请选择操作的名称:\n 1:显示当前的A、B链表 \n 2:进行差运算 \n 3:进行交运算 \n 4:进行并运算 \n 5:返回上一级菜单 \n 您的选择是：");
				   scanf("%d",&signc);
	               switch(signc)
	                {
		             case 1:
		                 printf(" \n 当前A");
		                 PrintList(A);
		                 printf(" \n 当前B");
		                 PrintList(B);
		                 break;
		             case 2:
				         p=B->next;
                       while(p)
                        {if (!inter(A,p->data))
                         {m=(Lnode *)malloc(sizeof(Lnode));
                          m->data=p->data;
                          m->next=C->next;
                          C->next=m;
                         }
                         p=p->next;
                        }
                       printf(" \n 进行差运算，结果为：\n");
                       PrintList(C);
			           C=(Lnode *)malloc(sizeof(Lnode)); /*必须再分配一次地址空间以用来把原链表清空，否则每次运行都会使链表元素增加*/
			           break;
                     case 3:
			             p=B->next;
                       while(p)
                        {if (inter(A,p->data))
                         {q=(Lnode *)malloc(sizeof(Lnode));
                          q->data=p->data;
                          q->next=D->next;
                          D->next=q;
                         }
                         p=p->next;
                        }
                       printf(" \n 进行交运算，结果为：\n");
                       PrintList(D);
                       D=(Lnode *)malloc(sizeof(Lnode));
                       break;
		             case 4:
			             *E=*A;
                         p=B->next;
                       while(p)
                        {if (!inter(E,p->data))
                         {n=(Lnode *)malloc(sizeof(Lnode));
                          n->data=p->data;
                          n->next=E->next;
                          E->next=n;
                         }
                         p=p->next;
                        }
                       printf(" \n 进行并运算，结果为：\n");
                       PrintList(E);
                       E=(Lnode *)malloc(sizeof(Lnode));
                       break;		
			         case 5:
			             cc=0;
			             break;
			         default: 
			  	       printf("警告!只能选择1-5。 \n");
			  	       break;
	                }
			      }
			     }
			else if (sign1==4) 
			{
			 printf("谢谢使用，请按任意键退出!\n");
			 break;
			}
	 	    else
	 	     {printf("提示:仅能在1-4之间选择！\n");
			  break;
	 	     }
	 	   }
	
	return 0;
}