linklist.c

包括线性表

/*单链表的表示和实现*/
#include <stdio.h>
typedef struct node
  {int data;
   struct node *next;
  }slink;
slink *sq;
void initlist();
void printmenu();
void createlist();
int getlen();
void displist();
void inselem(int x,int i);
int delelem(int i,int *x);
slink *getelem(int i);
int locate(int x);
main ()
{int select,len,i,x,del_elem,statu;
 slink *p;

 
 clrscr();
 initlist();
 while (1)
 {printmenu();
  scanf("%d",&select);

 switch (select)
       {case 1:
               createlist();
               break;
        case 2:
               len=getlen();
               printf("the length is %d\n",len);
               break;
        case 3:
               printf("please input the position of the element you want to find:");
               scanf("%d",&i);
               printf("\n");
               p=getelem(i);
               if (p!=NULL)
                  printf("the element your search for is:%d\n",p->data);                                          
               break;
        case 4:
               printf("please input a number you want to locate:\n");
               scanf("%d",&x);
               i=locate(x);
               if (i==0)
                  printf("the element is not exist!\n");
               else 
                  printf("the position of this element is:%d\n",i);
               
               break;
        case 5:
               printf("please input a number:\n");
               scanf("%d",&x);
               printf("please input the position you want to insert:\n");
               scanf("%d",&i);
               inselem(x,i);
               break;
        case 6:
               printf("please input the position you want to delete:\n");
               scanf("%d",&i);
               statu=delelem(i,&del_elem);
               if (statu==1)
                  printf("the element your have deleted is:%d\n",del_elem);
               break;
        case 7:
               printf("the contents of the linklist is:");
               displist();
               printf("\n");
               break;
        case 8:
               exit(1);
               break;


       }
 printf("\t\t\tpress any key to continue\n");
 getch();

 }

}

void initlist()  /*初始化链表*/
{sq=(slink *)malloc(sizeof(slink));/*建立头结点*/
 sq->next=NULL;
}

void createlist()
{slink *p,*q;
 int x;
 p=sq;
 printf("please input a node (end with 0):\n");
 scanf("%d",&x);
 while (x!=0)
     {q=(slink *)malloc(sizeof(slink));
      q->data=x;
      q->next=NULL;
      p->next=q;
      p=q;
      scanf("%d",&x);
     }

}

void printmenu()
{printf("\t\t\t\t1.create a linklist\n");
 printf("\t\t\t\t2.get length\n");
 printf("\t\t\t\t3.get element\n");
 printf("\t\t\t\t4.locate\n");
 printf("\t\t\t\t5.insert a node\n");
 printf("\t\t\t\t6.delete a node\n");
 printf("\t\t\t\t7.displist\n");
 printf("\t\t\t\t8.exit\n");
 printf("\n");
 printf("\tplease select one function\n");
}

int getlen()
{int i=0;
 slink *p=sq->next;
 while (p!=NULL)
       {i++;
        p=p->next;
       }
 return i;
}

void displist()
{slink *p;
 p=sq->next;
 while (p!=NULL)
    {printf("%d ",p->data);
     p=p->next;
    }
}

void inselem(int x,int i)
{slink *p=sq,*q;
 int j=1;
 if (i<1||i>getlen()+1)
    {printf("void insertion\n");
     return;
   }
 q=(slink *)malloc(sizeof(slink));
 q->data=x;
 q->next=NULL;
 while (j<i)
     {p=p->next;
      j++;  
     }
 q->next=p->next;
 p->next=q;
}

int delelem(int i,int *x)
{slink *p=sq,*q;
 int j=1;
 if (i<1||i>getlen())
    {printf("void deletion\n");
     return 0;
    }
while (j<i)
    {p=p->next;
     j++;
   }
q=p->next;
*x=q->data;
p->next=q->next;
free(q);
return 1;
}

slink *getelem(int i)
{int j=1;
 slink *p=sq->next;
 if (i<1||i>getlen())
    {printf("void getelem\n");
     return NULL;
    }
 while (j<i)
    {p=p->next;
     j++;
    }
 return p;
}

int locate(int x)
{slink *p=sq->next;
 int i=1;
 while (p!=NULL&&p->data!=x)
       {i++;
        p=p->next;
       }
 if (i<=getlen())
    return i;
 else 
    return 0;
 


}