shujulianbiao.c

数据结构对于链表的操作 包括创建

#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OVERFLOW -1
#define ok 1
#define TRUE 1
#define FAlSE 0

typedef struct
{
 int *elem;
 int length;
 int listsize;
}Sqlist;




typedef struct  LNode{                    //结构体定义
    int       data;
    struct LNode   *next;
  } LNode,*LinkList;



int    InitList(LinkList *L)                  //创建空线性链表
	{
  (*L)=(LNode*)malloc(sizeof(LNode) );
  if( !L) return(OVERFLOW);
  (*L)->next =  NULL;
   return 1;  }


void   CreateList(LinkList *L, int n )                //建立链表
{    
   LNode *p;
   int i;
   (*L)  = (LNode*)malloc(sizeof(LNode)); 
   (*L)->next = NULL;   
  for(i=n;i>0;i--)
  {
   p= (LNode*)malloc(sizeof(LNode ));
   scanf("%d",&p->data); p->next = (*L)->next ;
   (*L)->next =p ;}
}



int ListEmpty( LinkList   L )                 //判断线性链表是否为空
    {     
          if(! L->next )   return TRUE;
              else   return 0;
      } 


int ListLength(LinkList  L)                //求线性链表的长度
{      int i;
	   LNode *p;
	   if(!L) return(OVERFLOW);
        p  =  L->next;i  = 0;
       while(p) { i++;p  =  p->next;}
       return i;
}

int GetElem(LinkList  L, int  i, int *e)        //取线性链表中的第i个元素
{   int k,len;
	LNode *p;
	if(!L)    return(OVERFLOW);
  p  =  L->next;k  = 1; len=ListLength(L);
  while( p && k<i )  {  k++;p = p->next;}
  if( !p || k>len ) return(0);
      else  *e = p->data;
   return ok;
} 

int LocateElem( LinkList L, int e)       //定位某一元素在线性链表中的位置
{   int k;
	LNode *p;
	if(!L) return(OVERFLOW);
    k = 0; p=L->next;
     while(p)  {
        if(p->data !=e )  {
           k++;p=p->next;}
		else return k+1;}
    return 0; 
} 

int PriorElem(LinkList L,int cur_e,int *Pre_e)     //定位某元素的前驱
 { LNode *p,*q;
  if(!L) return 0;
  for(p = L->next,q=L;p&&(p->data!= cur_e);q=p,p=p->next);
  if(!p || p==L->next )    return 0;
  *Pre_e=q->data;
  return ok;
    } 

int NextElem(LinkList L,int cur_e,int *Next_e)          //定位某元素的后继 
{LNode *p;
 if(!L)  return(OVERFLOW);
 for(p=L->next;p && (p->data !=cur_e);p=p->next);
 if(!p || !p->next)   return (0);
  
   *Next_e=p->next->data;  return ok;
}


int ListInsert(LinkList *L,int i,int e)                 //顺序表中某一位置插入新的元素
{LNode *s,*q,*p;int k; 
 if(!L)  return 0;
 for(p=(*L)->next,q=(*L),k=1;p && (k!=i);q=p,p=p->next,k++)
 if(!p)   return 0;
 s=(LNode*) malloc (sizeof(LNode));
 if(!s)     return(OVERFLOW);
 s->data=e; s->next=p; q->next=s;
	 return ok;
 }




int ListDelete(LinkList *L,int i,int *e )                      //删除顺序表中指定位置的元素
{  LNode *q,*p;int k; 
	if( !L ) return 0 ;
	if(i==1) {p=(*L)->next;(*L)->next=p->next;free(p);}
	else if(i!=1){
   for(  p=(*L)->next,k =1;p && (k != i);
             k++, q = p,p = p->next);
   if(!p )    return 0;
   q->next = p->next; *e =  p->data ;free(p);}
   return ok;
     } 




                                                         
int ClearList(LinkList * L)                        //将线性链表置空
    {  LNode *p;
	   if(!(*L) ->next )  return ok;
        p=(*L)->next;
        while(p) { 
        (*L)->next = p->next;
          free(p); 
		  p  =  (*L)->next; } 
         (*L) ->next = NULL;return ok;
    } 

//销毁线性链表

int DestroyList(LinkList * L)                        
    {  LNode *p;
	   if(!(*L))  return 0;
        while ((*L)->next)  {
      p=(*L)->next;    
	  (*L)->next=p->next;
      free (p);
	  } 
      free (*L); *L=NULL;
      return ok;

    } 

/*主函数*/
void main()  {
    LinkList L;
    LNode *p;
	int s,k,i,l,m,n,b,B,c,C,x,d,D,e,f,g,j,o;
//	int s;
    printf("创建一个空线性链表：\n");
    InitList( &L ) ; 
    if(InitList( &L )==1)printf("创建线性链表成功\n");
 printf("顺序表的操作种类：\n");
 printf("\n");
 printf("\n");

 printf("\n1，  建立一个新的顺序表。\n");
 printf("\n2，  输出这个顺序表。\n");
 printf("\n3，  判断该表是否为空。\n");
 printf("\n4，  输出这个顺序表的长度。\n");
 printf("\n5，  返回顺序表中的某个元素。\n");
 printf("\n6，  定位元素在顺序表中的位置。\n");
 printf("\n7，  求某个元素的前驱。\n");
 printf("\n8，  求某个元素的后继。\n");
 printf("\n9,   插入一个元素。\n");
 printf("\n10， 删除一个元素。\n");
 printf("\n11， 清空顺序表。\n");
 printf("\n12， 销毁顺序表。\n");
  do
 {   switch(s)
 { case 1: printf("开始创建线性链表:\n"); 
          printf("请输入数据个数:");
         scanf("%d",&k);
          printf("由后到前依次输入不同的整数数据\n");
           CreateList(&L, k );  
		   printf("链表赋值成功\n");
		   break;
	case 2:	 printf("链表为:\n"); 
	         for(i=0,p=L->next;i<k;i++,p=p->next)
			 printf("%d ",p->data);
			  printf("\n");
			  break;

  case 3:ListEmpty(L);
         if(ListEmpty( L )==1)printf("顺序表为空\n");
         else if(ListEmpty( L )==0)printf("顺序表非空\n");
		 else printf("操作错误\n");
		 
          break;
  
 case 4:l=ListLength( L );
	     printf("顺序表长度为：%d\n",l);
         
         break;

  case 5: printf("请输入要寻找的第m个元素\n");
	      scanf("%d",&m);
          l=ListLength(L);
		  if((m<0)||(m>l)) {printf("error\n");break;}
			   else GetElem(L, m, &n) ;
          printf("第%d个元素为%d\n",m,n);
          
		  break;

  case 6: printf("请输入要定位的元素\n");
	      scanf("%d",&b);
          B=LocateElem(L, b) ;
                  if ( B==0 )  printf("error\n");
			    else printf("要定位的元素%d是线性表中第%d个元素\n",b,B);
				
				break;

  case 7:printf("请输入要定位前驱的元素\n");
         scanf("%d",&c);
         x=PriorElem(L,c,&C);
         if(x==0||x==0)printf("错误");
         else printf("元素%d的前驱为%d\n",c,C);

		 break;

   case 8:printf("请输入要定位后继的元素\n");
         scanf("%d",&d);
         x=NextElem(L,d, &D); 
		 if(x==0||x==0)printf("错误");
         else printf("元素%d的后继为%d\n",d,D);

		 break;

   case 9:printf("请输入要插入的新元素:\n");
		  scanf("%d",&e);
		 k++;
	     printf("请输入要插入的位置(请不要超过元素的个数):\n");
         scanf("%d",&f);
       if(f<=0||f>ListLength( L )){printf("输入错误\n");break;}
        else ListInsert(&L,f,e );
         printf("新的顺序表为：\n");
		 for(i=0,p=L->next;i<k;i++,p=p->next)
			 printf("%d ",p->data);
			  printf("\n");

		 break;

   case 10:printf("请输入要删除元素的位置\n");
	   scanf("%d",&g);
	   if(g<=0||g>ListLength( L )){printf("输入错误\n");break;}
        o=ListDelete(&L,g,&j ); 
		k=ListLength( L );
		 printf("新的顺序表为：\n");
		 for(i=0,p=L->next;i<k;i++,p=p->next)
			 printf("%d ",p->data);
			  printf("\n");

         break;
   
  case 11:ClearList(&L);
           printf("顺序表已置空\n");
		   break;

    case 12:DestroyList( &L);
	       printf("顺序表已销毁\n");
		   break;

  default: printf("error\n"); 
}  
     printf("\n终止任务请输入0,继续请选择功能:\n");
		 
	 scanf("%d",&s);
	 
	 if(s==0){printf("任务结束\n");break;}
 }while(s);
  

 }