算法与数据结构之一------顺序表

/**************************************************************** 文件内容：线性表之顺序表操作 版本V1.0 时间：2013-12-12 说明：顺便表其实就是一个数组，在数组附近添加一个标记指针。 顺序表读和写操作方便，有效信息大(相比链表来说），但查找，插入，删除效率低。 通常一个数据结构只涉及到读和写操作，一般使用顺序表来描述，而涉及到 查找，插入删除，等耗时操作，一般使用链表。  *****************************************************************/  #include<stdio.h> #include<stdlib.h> //#define RELEASE_VERSION  //release版本开关 //#define TRIDiTION /*inlude<malloc.h> stdlib.h 包含malloc.h*/ #ifdef RELEASE_VERSION #define  Log  #else #define  Log  printf #endif #define MAX 15 /*为了提高程序的可移植性，千万不能使用裸露的数据类型*/ #ifndef UINT32  typedef unsigned int UINT32 ; #endif #ifndef INT32  typedef  int  INT32 ; #endif /*定义一个顺序表*/ #ifndef TRIDiTION typedef  struct { UINT32 tab[MAX]; //数组来描述顺序表 UINT32 probe;  //顺便表的位置标志 } SeqList; #else /*也可以使用传统的结构体,传统中struct SeqList = 新型的SeqList*/   struct SeqList { UINT32 tab[MAX]; UINT32 probe; } ; #endif  /**************************************************************** 函数功能：初始化顺序表                         输入参数:  无 返回值： 顺序的表的标头指针  作者:HFL  时间：2013-12-12  *****************************************************************/              #ifdef TRIDiTION   struct SeqList * Init_Seqlist() #else   SeqList * Init_Seqlist() #endif  { #ifdef TRIDiTION     struct SeqList * P;     P =( struct SeqList *)malloc(sizeof(SeqList)); #else     SeqList *P; P =( SeqList *)malloc(sizeof(SeqList)); #endif if (!P) { Log("malloc is failed! \n"); } else { Log("malloc is secussed!\n"); } P->probe = -1;     return P; }   /**************************************************************** 函数功能：反初始化顺序表                         输入参数:  无 返回值： 顺序的表的标头指针  作者:HFL  时间：2013-12-12  *****************************************************************/              #ifdef TRIDiTION   void  Uninit_Seqlist(SeqList * L) #else   void Uninit_Seqlist(SeqList * L) #endif  { free (L); return ; }  /**************************************************************** 函数功能：想顺序表i 位置插入数据                        输入参数:  插入的数据值，插入的对象表 返回值：  返回值：  成功:0 ；失败：-1  作者:HFL  时间：2013-12-12  *****************************************************************/  #ifdef TRIDiTION   INT32 Insert_Into_I_Seqlist(UINT32  X, struct SeqList *L,INT32 i ) #else   INT32 Insert_Into_I_Seqlist(UINT32  X, SeqList * L,INT32 i) #endif    {     INT32  temp ;// 有符号和无符号不能比较，因此都要统一成有符号类型   if ( i<=-1|| i>=MAX )   {  Log ("sorry the Insert position is illegal \n");  return -1;  }  if(L->probe==MAX-1 )  {  Log(" sorry!The SeqListb is FULL !\n");  return -1;  }  else  {   L->probe++;   temp = L->probe;   while(i< temp)   {         L->tab[temp]=L->tab[temp-1];    temp --;   }   L->tab[i] = X;  }  return 0;   } /**************************************************************** 函数功能：向顺序表尾部插入数据                        输入参数:  插入的数据值，插入的对象表 返回值：  返回值：  成功:0 ；失败：-1  作者:HFL  时间：2013-12-12  *****************************************************************/  #ifdef TRIDiTION   INT32 Insert_Seqlist(UINT32  X, struct SeqList *L ) #else   INT32 Insert_Seqlist(UINT32  X, SeqList * L) #endif    {     if(L->probe==MAX-1)  {  Log(" sorry!The SeqListb is FULL!\n");  return -1;  }  else  {        L->probe++;   L->tab[L->probe] = X;  }  return 0;   } /**************************************************************** 函数功能：向顺序表尾部删除数据                        输入参数:  顺序表的对象表 返回值：  顺序的表的标头指针  作者:HFL  时间：2013-12-12  *****************************************************************/   #ifdef TRIDiTION   struct INT32 Delete_I_Seqlist( struct SeqList * L ,INT32 i) #else   INT32 Delete_I_Seqlist(SeqList * L,INT32 i) #endif    {     INT32 temp;  if (i<=-1 || i>=MAX)  {  Log("sorry!The I Position is illgeal!\n");  return -1;  }  if(L->probe==-1 )  {  Log("sorry!The SeqListb is NULL!\n");  return -1;  }  else  {  for(temp=i;temp<L->probe;temp++)    L->tab[temp]=L->tab[temp+1];    L->probe--;  }  return L->probe;   } /**************************************************************** 函数功能：向顺序表尾部删除数据                        输入参数:  顺序表的对象表 返回值：  顺序的表的标头指针  作者:HFL  时间：2013-12-12  *****************************************************************/   #ifdef TRIDiTION   struct INT32 Delete_Seqlist( struct SeqList * L ) #else   INT32 Delete_Seqlist(SeqList * L) #endif    {     if(L->probe==-1)  {  Log("sorry!The SeqListb is NULL!\n");  return -1;  }  else  {     L->probe--;  }  return L->probe;   }   /**************************************************************** 函数功能：遍历顺序表                        输入参数:  顺序表的对象表 返回值：  成功:0 ；失败：-1 作者:HFL  时间：2013-12-12  *****************************************************************/   #ifdef TRIDiTION   INT32 List_Seqlist( struct SeqList * L ) #else   INT32  List_Seqlist(SeqList * L) #endif    {     INT32 Last = L->probe;  if(Last==-1)  {  Log(" sorry!The SeqListb is NULL!\n");  return -1;  }  else  { while(-1!=Last) { Log( "the Nume%d is %d\n",Last, L->tab[Last]); Last--; }  }  return 0;   }  /**************************************************************** 函数功能：从顺序表查找一个元素                        输入参数:  顺序表的对象表 返回值：   成功：0，失败为：-1  作者:HFL  时间：2013-12-12  *****************************************************************/   #ifdef TRIDiTION   INT32 Seach_Seqlist( struct SeqList * L,UINT32 X ) #else   INT32 Seach_Seqlist(SeqList * L,UINT32 X) #endif    {     UINT32 i = L->probe ; //再引入一个标志，probe指针作为顺便表指针，不能动它，否则顺序表就动了。  if(i ==-1)  {  Log(" sorry!The SeqListb is NULL!\n");  return -1;  }  else  {    while(-1!=i)  { if( X==L->tab[i]) { Log("The data is seached now!the %d is the %d position \n",X,i); return L->probe; } // Log("L->tab[L->probe]=%d\t",L->tab[L->probe]);            i --;  }     Log("The data is can't find!\n"); return -1;  }   } void main() {  INT32 i = 0,Ret = -1; #ifdef TRIDiTION struct SeqList * L = NULL; #else SeqList * L = NULL;     #endif     Log("*******************************\n"); Log("*                             *\n"); Log("*   Init seqlist is start !   *\n"); Log("*                             *\n"); Log("*******************************\n"); L= Init_Seqlist(); if (!L) { Log( "Init_seqlist is failed!\n"); } else { Log("Init_seqlist is succsessed! \n"); } Log("*******************************\n"); Log("*                             *\n"); Log("*   setup seqlist is start !  *\n"); Log("*                             *\n"); Log("*******************************\n"); for(i=0; i<MAX-1; i++)//建立Max-1个元素的顺序表 { if( Insert_Seqlist(i+2,L) ) { Log("Insert data is failed \n"); } else { Log("Insert data[%d] is successed\n",i); } } Log("*******************************\n"); Log("*                             *\n"); Log("*   List seqlist is start !   *\n"); Log("*                             *\n"); Log("*******************************\n"); if( List_Seqlist(L)) { Log("List data is failed \n"); } else { Log("List Data is successed\n",i); } Log("*******************************\n"); Log("*                             *\n"); Log("*   Search seqlist is start ! *\n"); Log("*                             *\n"); Log("*******************************\n"); Ret = Seach_Seqlist(L,6); if(-1 == Ret) { Log( "sorry ,List data is failded\n"); } else { Log( "hi ,List data is secusssed,the position is %d\n",Ret); } Log("*******************************************\n"); Log("*                                         *\n"); Log("*Insert into I position seqlist is start !*\n"); Log("*                                         *\n"); Log("*******************************************\n");    Ret = Insert_Into_I_Seqlist(999,L,0);    if(-1 == Ret) { Log( "sorry ,Insert i position data is failded\n"); } else { Log( "hi ,Insert i position data is secusssed\n"); } if( List_Seqlist(L)) { Log("List data is failed \n"); } else { Log("List Data is successed\n",i); } Log("*******************************************\n"); Log("*                                         *\n"); Log("*        Delete seqlist is start !        *\n"); Log("*                                         *\n"); Log("*******************************************\n");    Ret = Delete_Seqlist(L);    if(-1 == Ret) { Log( "sorry ,Delete data is failded\n"); } else { Log( "hi ,Delete data is secusssed\n"); } if( List_Seqlist(L)) { Log("List data is failed \n"); } else { Log("List Data is successed\n",i); }     Log("*******************************************\n"); Log("*                                         *\n"); Log("*    Delete I Date seqlist is start !     *\n"); Log("*                                         *\n"); Log("*******************************************\n"); Ret =Delete_I_Seqlist(L,4); if(-1 == Ret) { Log( "sorry ,Delete I data is failded\n"); } else {  Log( "hi ,Delete I data is secusssed\n"); } if( List_Seqlist(L)) { Log("List data is failed \n"); } else { Log("List Data is successed\n",i); } Log("*******************************************\n"); Log("*                                         *\n"); Log("*    destroy  seqlist is start !          *\n"); Log("*                                         *\n"); Log("*******************************************\n"); while(-1!=L->probe) {  Delete_Seqlist(L); } if( List_Seqlist(L)) { Log("List data is failed \n"); } else { Log("List Data is successed\n",i); } Log("*******************************************\n"); Log("*                                         *\n"); Log("*       free  seqlist is start !          *\n"); Log("*                                         *\n"); Log("*******************************************\n"); Uninit_Seqlist(L); }