数据结构之线性表中顺序表的基本操作

落日映苍穹つ 2022-08-14 00:48 243阅读 0赞

精读数据结构第一篇之线性表的操作实现。欢迎转载：转载请注明：[http://blog.csdn.net/smile5005/article/details/41130209][http_blog.csdn.net_smile5005_article_details_41130209]

数据结构中的线性表可以分为顺序表和链表，链表又分为单链表和双向链表。至于两者的区别这里也不再多说。可以借助数组来描述顺序表，由于C语言中的数组有动态和静态两种分配方法，故顺序表的存储定义也有两种不同的方式，这里先采用动态的方式来进行描述顺序表。

1、首先，看一下顺序表的存储定义；

#define INITSIZE   100  //线性表的存储空间初始分配量
    #define INCREMENT  10   //线性表存储空间的分配增量，如果存在溢出的情况，则一次增加该数组的存储空间
    #define elementype int  //定义线性表的为int型的顺序表
    
    typedef struct 
    { 
        elementype     *elem； //elem为存储的首地址； 
        int length；           //线性表的长度；
        int listsize；         //线性表已分配的空间容量；
     }sqllist；

2、构造一个空的线性表并初始化;

算法描述如下：

int ListInit_sql(sqllist& l)
    {
      l.elem=(elementype*)malloc(sizeof(elementype)*INITSIZE);
    
      if(0==l.elem)      //需要判断存储空间分配是否失败;
      {
         printf("overflow");
         return 0;
      }
      else
      { 
         l.length=0;
         l.listsize=INITSIZE;
         printf("OK");
         return 1; 
      }
    }

3、顺序表的查找;

设在顺序表中查找值为x的元素，若找到，则返回其在顺序表中的位置，如果存在多个，则返回第一个，否则返回为0。算法如下：

int LocatElem_sql(sqllist &l,elementype x)
    {
       int i;
       elementype *p;
       p=l.elem;
       for(int i=1;i<=l.length;++i)   //注意这里顺序表的索引是从0开始;
       {
          if(*p++==x)
          {
             return i; 
          }
       }
       
       return 0;
    }

4、顺序表的插入；

当需要在顺序表i的位置的前方进行插入时，需要把位置i处以及i后的元素往后进行移动，如果存在溢出的情况则需要重新分配内存。

int ListInsert_sql(sqllist &l,int i，elementype e)
    {
       elementype *newbase，*p,*q；
    
       //首先判断i的值是否合法;
       if(i<1||i>l.length)
       {
          printf("i error");
          return 0;
       } 
       if(l.length>=l.listsize)
       {
          newbase=(elementype*)realloc(sizeof(elementype)*(l.listsize+INCREMENT));
          
          if(0==newbase)
          {
              printf("overflow");
              return 0; 
          } 
          l.elem=newbase;
          l.listsize+=INCREMENT；
       }
       
       p=&l.elem[i-1];
       
       for(q=&l.elem[l.length-1];q>==p;--q)
       {
          *(q+1)=*q;
       }
       *q=e;
       ++l.length;
       printf("OK");  
       
       return 1;
    }

5、顺序表的删除

顺序表的删除和插入类似，删除不需要考虑顺序表是否溢出，删除一个元素后，该元素右方的元素向左进行移动;

/**
    *	线性表的删除操作,删除顺序表中第i位置处的元素,注意i并不是索引;
    *	分析：
    *	1、需要判断i的合法性,i应该大于等于1小于等于n;
    *	2、删除元素后需要对顺序表进行移动，并且长度减一;
    */
    int ListDelete_sql(sqlist &l,int i, elementype &e)
    {
    	if(i<1||i>l.length)
    	{
    		printf("i error");
    		return 0;
    	}
    
    	elementype *p,*q;
    
    	q=&l.elem[l.length-1];
    	e=l.elem[i-1];
    
    	for(p=&l.elem[i];p<=q;++p)
    	{
    		*p=*(p+1);
    	}
    	--l.length;
    	printf("ok");
    	return 1;
    }

6、总结：数据结构是算法设计的基础，也是计算机的基础，需要多多精读，如果有不妥之处，敬请留言指出，谢谢！

[http_blog.csdn.net_smile5005_article_details_41130209]: http://blog.csdn.net/smile5005