我心飞翔

有事不慌,无事不荒,有容乃大,无欲则刚,以德立纲,外圆内方。

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 9 文章 :: 13 评论 :: 0 Trackbacks

线性表的顺序表示:

 

#define LIST_INIT_SIZE 100    定义一个线性表类型

#define LISTINCREMENT 10

typedef struct

{

  ElemType *elem; 基址

  int length; 元素的长度

  int listsize;当前的存储容量

 }Sqlist;

 

 void InitList_Sq(Sqlist &L)  初始化操作

 {

   L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

   if(!L.elem)

   return overflow;

   L.length=0;

   L.listsize=LIST_INIT_SIZE;

   return ok;

 }

 

 void DestroyList_Sq(Sqlist &L)  销毁线性表

 {

   free(L.elem);

   L.elem=NULL;

   L.length=0;

   L.listsize=0;

   return ok;

 }

 

void ClearList(Sqlist L)  清零操作

{

  L.length=0;

  return ok;

}

 

void ListEmpty(Sqlist L)  判空操作

{

  if(L.length=0)

   return True;

   else

   return False;

}

 

int ListLength(Sqlist L)  输出表的长度,数据元素个数

{

  return L.length;

}

 

void GetElem(Sqlist &L,int i,ElemType &e) 得到第I 个元素的数据元素的值

{

   if(i<1 || i>L.length)

   return error;

   e=*(L.elem+i-1);

   return ok;

}

 

int LocateElem(Sqlist &L,ElemType e,void (*compare)(ElemType,ElemType)) 查找与E相等的元素的位置

{

  ElemType *p;

  i=1;

  while(i<=L.length && !compare(*p++,e))

  ++i;

  if(i<=L.length)

  return i;

  else

  return 0;

}

 

void PriorElem(Sqlist L,ElemType cur_e,ElemType pre_e)  得到给出的数的前一个元素值

{

  int i=2;

  ElemType *p;

  p=L.elem+1;

  while(i<=L.length && !(*p++==cur_e))

  ++i;

  if(i>L.length)

  return INFEASIBLE;

  else

  {

    pre_e=*--p;

    return OK;

  }

}

 

void NextElem(Sqlist L,ElemType pre_e,ElemType cur_e)  得到后一个元素的值

{

  int i=1;

  ElemType *p

  p=L.elem;

  while(i<L.length && !(*p++==pre_e))

  ++i;

  if(i>=L.length)

  return INFEASIBLE;

  else

  {

    cur_e=*++p;

    return OK;

  }

}

 

void InsertElem(Sqlist &L,int i,ElemType e)  在第I个元素中插入一个值为E的元素

{

  if(i<1 || i>=length+1)

  return ERROR;

  if(L.length>=L.listsize)

  {

 if(!newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)

    *sizeof(ElemType))))

    return OVERFLOW;

    L.elem=newbase;

    L.listsize+=LISTINCREMENT;

  }

  p=L.elem+L.length-1;

  q=L.elem+i-1;

  for(p;p>=q;--p)

  *(p+1)=*p;

  *q=e;

  ++L.length;

  return ok;

}

 

void DeleteElem(Sqlist &L,int i,ElemType e)  删除第I个元素

{

  if(i<1 || i>=L.length)

  return FALSE;

  p=L.elem+i-1;

  q=L.elem+L.length-1;

  e=*p;

  for(p;p<=q;++p)

  *p=*(p+1);

  --L.length;

  return OK;

}

 

void ListTraverse(Sqlist &L,void (*vi)(ElemType))  对线性表进行VI的操作

{

  int i;

  ElemType *p;

  p=L.elem;

  for(i=1;i<=L.length;++i)

  vi(*p++);

  return OK;

}


以上是线性表的一些常用的原操作. 

 

例:

1.求一个新的集合A=A U B

void union(Sqlist &LA,Sqlist LB)

{

  la_len=LA.length;

  lb_len=LB.length;

  for(i=1;i<=lb_len;++i)

  {

   GetElem(LB,i,e);

   if(!Locate(LA,e,compare()))

   InsertList(LA,++la_len,e);

  }

  return OK;

}

 

2.将二个非递减的LA表和LB表归并为一个新的非递减的LC

void MergeList(Sqlist LA,Sqlist LB,Sqlist &LC)

{

  i=j=1;k=0;

  InitList(LC);

  while(i<=LA.length && j<=LB.length)

  {

   GetElem(LA,i,ai);

   GetElem(LB,j,bj);

   if(ai<=bj)

   {

     InsertList(LC,++k,ai);

     ++i;

   }

   else

   {

     InsertList(LC,++k,bj);

     ++j;

   }

  }

  while(i<=LA.length)

  {

    GetElem(LA,i,ai);

    InsertList(LC,++k,ai);

    ++i;

  }

  while(j<=LB.length)

  {

    GetElem(LB,i,bj);

    InsertList(LC,++k,bj);

    ++j;

  }

  return OK;

}

posted on 2005-10-11 00:59 无情雨 阅读(1482) 评论(2)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: 线性表的顺序表示(C语言) 2006-07-29 23:48 嘉湖孺子
请问, (*vi)(ElemType)和(*compare)(ElemType,ElemType))是怎么实现的,我在编这个程序的时候,似乎没有实现它们,也能运行啊!!
迷惑中,如蒙回答,不胜感激。
jiahuruzi@126.com
再次感激  回复  更多评论
  

# re: 线性表的顺序表示(C语言) 2007-11-16 09:03 糊涂
这是数据结构C语言版吗?
可以在TC中运行吗?
如果没有 可以在写个吗
?
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理