电子0602-1402050206王斯辉 链表.cpp

程序实现了带表头单链表的最基本操作

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

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
 
int over_flag=0;                        //主函数结束标识符
void CreateList(LinkList &L);          //创建链表
void Locate(LinkList L);               //查询数值
void InsertList(LinkList &L);          //插入数值
void DeleteList(LinkList &L);          //选择删除
void Deleterepeat(LinkList &L);        //删除重复结点
void DeleteEven(LinkList &L);          //删除数值为偶数的结点
void Rotate(LinkList &L);              //变为循环链表
void Divide(LinkList &L);              //分解成两个链表
int LengthList(LinkList L);            //求链表长度
void PrintList(LinkList L);            //输出链表
 
/**********************************************************************
                            主函数
**********************************************************************/
void main(void)
{   
	char operate;
	LinkList L;
	int n;
	for( n=0;n<40;n++)
	{
		printf("\n输入字符选择链表操作类型\nA:创建 B:查询 C:插入 D:选择删除 E:删除重复 F:删除偶数 \nG:变为循环链表 H:分解为两个链表\n");
        label:scanf("%c",&operate);
		switch (operate)
		{
	      case 'a':
          case 'A': CreateList(L);break;
		  case 'b':
		  case 'B': Locate(L);break;
		  case 'c':
		  case 'C': InsertList(L); break;
		  case 'd':
		  case 'D': DeleteList(L);break;
		  case 'e':
		  case 'E': Deleterepeat(L);break;
		  case 'f':
		  case 'F': DeleteEven(L);break;
		  case 'g':
		  case 'G': Rotate(L);break;
		  case 'h':
		  case 'H': Divide(L);break;
		  case '\n':goto label;          //排除换行键的影响
          default: printf("输入有误，请重新输入！");break;
		}
        if(over_flag)return;
    }

}

/**********************************************************************
                            创建链表
**********************************************************************/
void CreateList(LinkList &L)
{  
   int temp;
   printf("创建链表：\n请输入创建链表所需的整数值(以-1结束):\n");
   L = (LinkList)malloc(sizeof(LNode)); 
   L->next = NULL;
   LinkList q=L;
   scanf("%d",&temp);
   while(temp!=-1) 
   {
       LinkList p;
       p = (LinkList)malloc(sizeof(LNode));  
       p->data = temp;
       p->next = NULL;
       q->next = p;
       q = q->next;  
       scanf("%d",&temp);
	}
    L->data = LengthList(L);
    PrintList(L);

}
/**********************************************************************
                            查询元素
**********************************************************************/
void Locate(LinkList L)
{   if(!L)printf("错误：链表未创建！");
	int element;
	printf("查询数值：\n输入要查询的数值：");
    scanf("%d",&element);
	LinkList p=L->next;
	int i =1;
    while(p)
	{ 
      if(p->data==element)
	  {  
         printf("找到了，它是链表的第%d个元素。\n",i);
         return ;
	  }
	  p=p->next;
	  i++;
	}
    printf("找不到。\n");
}
/**********************************************************************
                            插入数值
**********************************************************************/
void InsertList(LinkList &L)
{
  int x,i;
  printf("插入数值：\n输入要插入的数值和插入的位置：");
  scanf("%d",&x);
  scanf("%d",&i);
  LinkList p = L;   
  int j = 0;
  while (p && j < i-1)
  {  
    p = p->next;
    ++j;
  } 
  if (!p || j > i-1) 
  {
	  printf("输入位置错误!") ;
	  return;
  }
  LinkList s = (LinkList)malloc(sizeof(LNode));  
  s->data = x;  
  s->next = p->next;      
  p->next = s;
  L->data = LengthList(L);
  PrintList(L);
} 
/**********************************************************************
                            选择位置删除节点
**********************************************************************/
void DeleteList(LinkList &L)
{ 
  int i;
  LinkList p = L;
  printf("选择位置删除结点：\n输入要删除数值的位置：");
  scanf("%d",&i);
 
  int j = 0;
  while (p->next && j < i-1)
  {  
    p = p->next;
    ++j;
  }
  if (!(p->next) || j > i-1)
  {
	  printf("输入位置错误!") ;
	  return;
  }
  LinkList q = p->next;
  p->next = q->next;          
  free(q);
  L->data = LengthList(L);
  PrintList(L);
} 
/**********************************************************************
                            删除重复结点
**********************************************************************/
void Deleterepeat(LinkList &L)
{
    printf("删除重复结点后的链表为：\n");
	int n=1;
	int a[20];
	LinkList q=L->next;
	LinkList p=q->next;
    a[0]=q->data;
	while(p)
	{
		for(int i=0;i<n;i++)
		{
			if(p->data==a[i])
			{
			    LinkList r=p;
			    q->next=p->next;
				p=p->next;
				free(r);
				break;
			}
		}
		if(i==n)
		{
			a[n++]=p->data;
            p=p->next;
			q=q->next;
		}
		
		
	}
    L->data = LengthList(L);
    PrintList(L);
}
/**********************************************************************
                            删除数值为偶数的结点
**********************************************************************/
void DeleteEven(LinkList &L)
{
    printf("删除偶数结点后的链表为：\n");
	LinkList q=L;
	LinkList p=L->next;
    while(p)
	{
		if(p->data%2==0)
		{
			LinkList r=p;
			q->next=p->next;
			p=p->next;
			free(r);
		}
	    else
		{
		    p=p->next;
			q=q->next;
		}
	}
    L->data = LengthList(L);
    PrintList(L);
}
/**********************************************************************
                            变为循环链表
**********************************************************************/
void Rotate(LinkList &L)
{
    printf("变为循环链表：\n");
	LinkList p=L;
	while(p->next)p=p->next;
	p->next=L;

    LinkList t=L->next;
	printf("长度：%d\t",L->data);
    printf("各个结点数值为：");
	while(t!=L)
	{
		printf("%d\t",t->data); 
		t=t->next;
	}
    printf("\n");
	printf("已经变为循环链表，其他操作将受影响,程序结束！\n");
	over_flag=1;
}
/**********************************************************************
                          分解成两个链表
**********************************************************************/
void Divide(LinkList &L)
{
    printf("分解成两个链表：\n");
	LinkList A=L;
	LinkList B=(LinkList)malloc(sizeof(LNode));
	B->next=NULL;
	LinkList Lb=B;
    int i=1;
    LinkList La=L;
	LinkList p=L->next;
	while(p)
	{
       if(i++%2==0)
	   {   
          La->next=p->next;
		  p->next=NULL;
		  Lb->next=p;
		  Lb=Lb->next;
		  p=La->next;
	   }
	   else
	   {
          p=p->next;
		  La=La->next;
	   }
	 }
	 A->data = LengthList(A);
	 printf("链表A:");
     PrintList(A); 
	 B->data = LengthList(B);
     printf("链表B:");
     PrintList(B);
	 printf("已经分解成两个链表，其他操作将受影响,程序结束！\n");
	 over_flag=1;
}
/**********************************************************************
                            求链表长度
**********************************************************************/
int LengthList(LinkList L)
{
	int i=0;
	LinkList p=L->next;
	while(p)
	{
		p=p->next;
		i++;
	}
	return i;
}
/**********************************************************************
                            输出链表
**********************************************************************/
void PrintList(LinkList L)
{   
    LinkList t=L->next;
	printf("长度:%d\t",L->data);
    printf("结点数值:");
	while(t)
	{
		printf("%d ",t->data); 
		t=t->next;
	}
    printf("\n");
}