链表基本操作.cpp

作业题

#include  "iostream.h"
#include  "stdio.h"
#include  "malloc.h"

typedef struct lnode
{
  char data;
  struct lnode  * next;
} lnode;

lnode *creat()//尾插法建表
{
 lnode *head,*rear,*p;
 char ch;
 head=new lnode;
 rear=head;
 printf("\n请输入链表元素,并以#键结束\n");
 while(cin>>ch,ch!='#')
 {   	 
  p=new lnode;
  p->data=ch;
  rear->next=p;
  rear=p;
 }
 rear->next=NULL;
 return head;
}
void  print(lnode *head)//打印链表
{  lnode  *p;
   printf("\n");
   p = head->next;
   while(p)
   { printf("%c",p->data);
     p=p->next;
   }
}

lnode  *visitll(lnode *h , char x)//按值查找       
{
  lnode  *p;
  p = h;
  while((p->data!=x)&&(p!=NULL))
    p = p->next;
  return(p);//返回结点指针
}




void GET(lnode *head,char i) /*按序号查找*/ 
{ 
int j; 
lnode *p; 
j='0';p=head; 
while((j <i)&&(p->next!=NULL)) 
{p=p->next;j++;} 
if(i==j)
      printf("该元素为%c",p->data);
        else
            printf("%c不在链表中",p->data);

} 


lnode  *invert(lnode *head)//反转
{
	lnode *p,*q,*r;
	p=head->next;
	q=p->next;
	while(q!=NULL)
	{r=q->next;
	q->next=p;
	p=q;
	q=r;}
	head->next->next=NULL;
	head->next=p;
	return(head);
}

int Length(lnode *head)//链表长度
{
int length;
lnode *p1;
if(head == NULL)
{
return 0;	
}
else
{
p1 = head;
length = 0;
while(p1->next != NULL) /*p1有下一个节点且不是头节点*/
{
p1 = p1->next;
length = length+1;
}
return length;
}
}

lnode *predall(lnode *h , lnode *q)//查找指针q指向结点的前驱结点，返回前驱结点的指针
{
  lnode  *p;
  if(h->next==q)
      p=NULL;
  else
   {  p = h;
      while((p->next!=q)&&(p!=NULL))
        p=p->next;
   }
  return(p);
}
void  insertll(lnode  *h , lnode  *q , char  x )//在q 指针指向结点的前面插入一个值为X的结点。
{
   lnode  *p , *r ;
   r = (lnode *)malloc(sizeof(lnode));
   r->data = x;
   if(h->next==q)
   {
  r->next=h->next;
     h->next=r;
   }
   else
      { p = predall(h , q);    //p指向q的前驱结点
        r->next=p->next;
  p->next=r;
      }
}
void deletell(lnode  *h , lnode  *q)//删除指针q指向的结点
{
  lnode  *p;
  if (h->next==q)
   h->next=NULL;
  else
   {
      p=predall(h,q);//p指向q的前驱结点
      p->next= q->next;
   }
   free(q);
}
main( )
{ lnode  *a;
  lnode  *result=NULL;
  int   choice ;
  char  data,data_cz;
  a = creat( );
  while(1)
  { printf("\n以下是单链表的应用,请选择:");
    printf("\n1、输出结点");
    printf("\n2、按值查找");
    printf("\n3、查找前驱");
    printf("\n4、查找后继");
    printf("\n5、插入结点");
    printf("\n6、删除结点");
    printf("\n7、序号查找");
	printf("\n8、反转链表");
    printf("\n9、链表长度");
	printf("\n10、退出\n");
    scanf("%d",&choice);
	
switch(choice)
{
     case  1:
        print(a);
        break;
     case  2:
         getchar( );
         printf("请输入待查结点的值:");
        data = getchar( );
		
        result = visitll(a,data);
        if  (result!=NULL)
            printf("%c在链表中",data);
        else
            printf("%c不在链表中",data);
        result = NULL;
		 print(a);
        break;
case   3:
         getchar();
         printf("请输入待查结点的值:");
        data = getchar( );
        result = visitll(a,data);
         if (result == NULL)
         {
           printf("%c不在链表中",data);
           break;
         }
        result = predall(a,result);
        if  (result!=NULL)
           printf("%c的前驱是%c",data,result->data);
        else
           printf("%c没有前驱",data);
        result = NULL;
        break;
case   4:
         getchar();
         printf("请输入待查结点的值:");
         data = getchar( );
         result = visitll(a,data);
         if (result == NULL)
          {
           printf("%c不在链表中",data);
           break;
          }
         if  (result->next!=NULL)
            printf("%c的后继是%c",data,result->next->data);
         else
            printf("%c没有后继",data);
		 print(a);
         result = NULL;
         break;
case  5:
         getchar();
         printf("请输入待插结点的值:");
         data = getchar( );
         getchar();
         printf("请输入插入在哪个结点前面:");
         data_cz=getchar( );
         result = visitll(a,data_cz);
          if (result == NULL)
          {
             printf("%c不在链表中",data);
             break;
           }
          insertll(a , result , data);
		   print(a);
        break;
case  6:
        getchar( );
        printf("请输入待删除结点的值:");
        data = getchar( );
        result = visitll(a,data);
         if (result == NULL)
         {
            printf("%c已删除",data);
            break;
         }
        deletell(a , result);
		 print(a);
        break;
case  7:
	    getchar( );
        printf("请输入待查结点的序号:");
        data = getchar( );
        GET(a,data);
        result = NULL;
		 print(a);
        break;
case 8:
	   getchar( );
       a=invert(a);
	   print(a);
	   break;
case 9:
	   getchar( );
	   Length(a);
       printf("链表长度为:%d ",Length(a));
	   break;

case 10:
        break;
defalut:
        break;
}
    if  (choice == 10 )
break;
     }
}