数据结构---串与数组

字符串的基本概念

字符串是由0个或多个字符构成的有限序列，一般可以表示为如下形式。

根据字符串的定义，字符串时元素类型为字符型的特殊线性表，其每个元素的类型一定为字符型，不能为其他类型。因此字符串的处理既可以使用线性表的基本操作，也可以自定义一些独特操作。

#define NULL 0
# define MAXSIZE 100
typedef struct
{
         char str[MAXSIZE];
         int length ; 
     } seqstring;

字符串的操作

//顺序串的插入
void strinsert(seqstring *S, int i , seqstring T)
{
  int k;
  if (i<1 || i>S->length+1 || S->length + T.length>MAXSIZE-1)
  printf("connot insert\n");
else
   {
      for(k=S->length-1;k>=i-1;k--)
        S->str[T.length+k]=S->str[k];
      for (k=0;k<T.length;k++) 
        S->str[i+k-1]=T.str[k];
      S->length= S->length + T.length;
      S->str[S->length]='\0';
    }
}

//顺序串的删除
void strdelete(seqstring *S,int i,int len)
{
    int k;
    if (i<1 || i>S->length||i+len-1>S->length) printf(" cannot delete\n");
    else
      {
         for(k=i+len-1; k<S->length;k++) S->str[k-len]= S->str[k];
         S->length=S->length-len;
         S->str[S->length]='\0';
      }
}

//顺序串的连接
seqstring * strconcat(seqstring S1,seqstring S2)
    {
      int i;
      seqstring *r;
      if(S1.length+S2.length>MAXSIZE-1) {printf("cannot concate");
                                       return(NULL);}
      else
        {
           r=(seqstring*)malloc (sizeof(seqstring));           
           for (i=0; i<S1.length;i++) r->str[i]= S1.str[i];
           for (i=0; i<S2.length;i++) r->str[ S1.length+i]= S2.str[i];
           r->length= S1.length+ S2.length;
           r->str[r->length]='\0';
        }
      return (r);
}

//求给定顺序串的子串
seqstring *substring(seqstring S,int i, int len)
{
   int k;
   seqstring *r;
   if (i<1 || i>S.length || i+len-1>S.length) 
          {printf("error\n");
           return(NULL);}
   else
        {
             r=(seqstring*) malloc (sizeof(seqstring));
             for(k=0;k<len;k++) 
               r->str[k]= S.str[i+k-1];
               r->length=len;
               r->str[r->length]='\0';
         }
    return(r);
}

链式串

#define null 0
typedef struct node
   {
      char data;
      struct node *next;
    } linkstrnode;
typedef linkstrnode *linkstring;

链式串的操作

//链式串的创建
void strcreate(linkstring *S)
{ char ch;
  linkstrnode *p,*r;
  *S=NULL; r=NULL;
  while ((ch=getchar())!='\n')
   { p=(linkstrnode *)malloc(sizeof(linkstrnode));
     p->data=ch;     /*产生新结点*/
     if (*S==NULL) /*新结点插入空表*/
         *S=p;
     else r->next=p;
     r=p;
   } /*处理表尾结点指针域*/
   if (r!=NULL)  r->next=NULL;
}

//链式串的插入
void strinsert(linkstring *S,int i,linkstring T)
/*将串T插入到串S中第i个字符之前*/
{
  int k ;
  linkstring p,q;
  p=*S, k=1;
  while (p && k<i-1)
     {
       p=p->next ; k++;
      }
  if (!p) printf("error\n");
  else
    {
      q=T;
      while(q->next)  q=q->next;
      q->next=p->next;
      p->next=T;
    }
 }

//链式串的删除
void strdelete(linkstring*S,int i,int len)
 {
    int k ;
    linkstring p,q,r;
    p=*S, q=null; k=1;
    while (p && k<i)
      {q=p; p=p->next ; k++;}
    if (!p) printf("error1\n");
    else
     { k=1;
       while(k<len && p )
          { p=p->next ;k++;}
       if(!p)  printf("error2\n");
       else
        {  if (!q) { r=*S; *S=p->next; }
           else 
            {
              r=q->next; q->next= p->next;}
           p->next=null;
           while (r !=null)
             {p=r; r=r->next; free(p);}
        }
     }
 } 

//链式串的连接
void strconcat(linkstring *S1, linkstring S2)
{
  linkstring p;
  if (!(*S1) )  
       {*S1=S2; return;}
  else
    if (S2)  
      {
        p=*S1;
        while(p->next ) p= p->next;
        p->next=S2;
      }
}

//求给定链式串的子串
linkstring substring(linkstring S,int i, int len)
{
    int k;
    linkstring p,q,r,t;
    p=S, k=1;
    while (p && k<i) {p= p->next;k++;}
    if (!p)  {printf("error1\n"); return(null);}
    else
      { 
         r=(linkstring ) malloc (sizeof(linkstrnode));
         r->data=p->data; r->next=null;
         k=1; q=r;
         while (p->next  && k<len)
           { p=p->next ;k++;
             t=(linkstring) malloc (sizeof (linkstrnode));
             t->data=p->data; q->next=t; q=t;
            }
         if (k<len) {printf("error2\n") ; return(null);}
         else
            {q->next=null; return(r);}
       }
}

数组

数组是一个具有固定数量数据元素的有序集合。

//三维数组的头文件
typedef int datatype;  /*假设数组元素的值为整型*/
typedef  struct {
      datatype *base;  /* 数组存储区的首地址指针*/
      int   index[3];  /* 存放三维数组各维的长度*/
      int   c[3]      /* 存放三维数组各维的ci值*/
} array；

数组元素的运算操作

//初始化三维数组
int initarray(array *A,int b1,int b2,int b3)
{
    int elements;
    if(b1<=0||b2<=0||b3<=0) return (0);//处理非法情况
    A->index[0]b1;A->index[1]=b2;A->index[2]=b3;
    elements =b1×b2×b3;//求数组元素的个数
    A->base=(datatype*)malloc(elements × sizeof (datatype));
   //为数组分配空间
    if(!(A->base)) return (0);
    A->c[0]=b2 × b3;A->c[1]=b3;A->c[2]=1;
    return (1);
}

//访问数组元素
nt value(array A, int i1 , int i2, int i3; datatype *x)
 {   
   int off;
   if (i1<0 || i1>=A.index[0] || i2< 0 || i2>=A.index[1] || i3<0 || i3>=A.index[2])
     return(0);    /*处理下标非法的情况*/
   off= i1×A.c[0]+ i2×A.c[1]+ i3×A.c[2];  /*计算数组元素的位移*/
   *x=*(A.base + off);    /*赋值*/
   return(1);
   }

//实现对数组元素的赋值运算
int assign( array *A, datatype e, int i1, int i2, int i3)
 {  
   int off;
   if (i1<0 || i1>=A->index[0] || i2< 0 || i2>=A->index[1] || i3<0 || i3>=A->index[2])
       return (0 );   /*处理下标非法的情况*/
   off= i1×A->c[0]+ i2×A->c[1]+ i3×A->c[2];  /*计算数组元素的位移*/
   *(A->base + off)=e;    /*赋值*/
   return(1);
   }