大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 数据结构算法

数据结构算法

关键词:数据结构算法数据结构算法  阅读(628) 赞(11)

[摘要]本文主要是对数据结构算法的讲解,希望对大家学习数据结构算法有所帮助。

  数据结构算法

  Void union(List &La,List Lb)

  //将所有在线性表Lb中但不在La中的数据元素插入到La中

  {

  La_len = ListLength(La);Lb_len =ListLength(Lb);//求线性表的长度

  For(i= 1;i<=Lb_len;i++)

  {

  GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

  If(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);//la中不存在和e相同的数据元素,则插入之

  }

  }

  Void MergeList(List La,List Lb,List &Lc)

  {

  //已知线性表La和Lb中的数据元素按值非递减排列

  //归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列

  InitList(Lc);

  i=j=1;k=0;

  La_len =ListLength(La);Lb_len = ListLength(Lb);

  While((i<=La_len)&&(j<=Lb_len)) //La和Lb均非空

  {

  GetElem(La,i,ai); GetElem(Lb,j,bj);

  if(ai<=bj)

  {

  ListInsert(Lc,++k,ai);

  ++i;

  }

  else

  {

  ListInsert(Lc,++k,bj);

  ++j;

  }

  }

  While(i<=La_len)

  {

  GetElem(La,i++,ai);

  ListInsert(Lc,++k,ai);

  }

  While(j<=Lb_len)

  {

  GetElem(Lb,j++,bj);

  ListInsert(Lc,++k,bj);

  }

  }

  3.构建一个空的线性表L

  StatusInitList_Sq(SqList &L)

  {

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

  if(!L.elem) exit(OVERFLOW);//存储分配失败

  L.length = 0;//空表长度为0

  L.listsize = LIST_INIT_SIZE;//初始存储容量

  return OK;

  }

  StatusListInsert_Sq(SqList &L,int I,ElemType e)

  //在顺序线性表L中第i个位置之前插入新的元素e,i的合法值为1<=i<=ListLength_Sq(L)+1

  {

  if(i<1 || i>L.length+1) returnERROR; //i值不合法

  if(L.length>=L.listsize) //当前存储空间已满,增加分配

  {

  Newbase= (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

  if(!newbase) exit(OVREFLOW);//存储分配失败

  L.elem = newbase;//新基址

  L.listsize+=LISTINCREMENT;//增加存储容量

  }

 

  q = &(L.elem[i-1]);//q为插入位置

  for(p =&(L.elem[L.length-1]);p>=q;--p)

  *(p+1) = *p;//插入位置及之后的元素右移

  *q = e;//插入e

  ++L.length;//表长增1

  return OK;

  }

  StatusListDelete_Sq(SqList &L,int i,ElemType &e)

  {

  //在顺序线性表L中删除第i个元素,并用e返回其值,i的合法值为1<=i<=ListLength-Sq(L)

  if(i<1|| i>L.length+1) return ERROR; //i值不合法

  p= &(L.elem[i-1]);//p为被删除元素的位置

  e= *p;//被删除元素的值赋给e

  q= L.elem+L.length-1;//表尾元素的位置

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

  *(p-1) = *p;//被删除元素之后的元素左移

  --L.length;//表长减1

  returnOK;

  }

  6.在顺序线性表L中查找第1个值与e满足compare()的元素的位序,若找到返回其在L中的位序,否则返回0

  intLocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))

  {

  i=1;//i的初值为第1个元素的位序

  p = L.elem;//p的初值为第一个元素的存储位置

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

  ++i;

  if(i<=L.length) return i;

  else return 0;

  }

  VoidMergeList_Sq(SqList La,SqList Lb,SqList &Lc)

  {

  //已知线性表La和Lb中的数据元素按值非递减排列

  //归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列

  pa = La.elem;

  pb =Lb.elem;

  Lc.listsize =Lc.length = La.length + Lb.length;

  pc = Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

  if(!Lc.elem)exit(OVERFLOW);//存储分配失败

  pa_last = La.elem+La.length-1;

  pb_last=Lb.elem_Lb.length-1;

  while(pa<=pa_last&&pb<=pb_last)

  {

  if(*pa<*pb) *pc++=*pa++;

  else *pc++=*pb++;

  }

  While(pa<=pa_last)*pc+==*pa++;

  While(pb<=pb_last)*pc+==*pb++;

  }

  8.函数GetElem在单链表中的实现

  StatusGetElem_L(LinkList L,int I,ElemType &e)

  {

  L为带头结点的单链表的头指针,当第i个元素存在时,其值赋给e并返回OK,否则返回error

  p= L->next;j=1;//初始化,p指向第一个结点,j为计数器

  while(p&&j

  {

  p= p->next;

  ++j;

  }

  if(!p || j>i)return ERROR;//第i个元素不存在

  e =p->data;//取第i个元素

  return OK;

  }

 

  9.在单链表中实现插入与删除

  *************插入

  StatusListInsert_L(LinkList &L,int I,ElemType e)

  {

  //在带头结点的单链线性表L中第i个位置之前插入元素e

  P= L;j=0;

  while(p&&j

  {

  p= p->next;++j//寻找第i-1个结点

  }

  if(!p ||j>i) returnERROR;//i小于1或者大于表长

  s =(LinkList)malloc(sizeof(LNode));//生成新结点

  s->data = e;

  s->next =p->next;

  p->next = s;

  return OK;

  }

  **********************删除

  StatusListDelete_L(LinkList &L,int i ,ElemType &e)

  {

  //在带头结点的单链线性表L中,删除第i个元素,并由e返回其值

  p=L;j=0;

  while(p->next&& j

  {

  p = p->next;

  ++j;

  }

  if(!(p->next)|| j>i-1) return ERROR;//删除位置不合理

  q= p-next;p->next = q->next;//删除并释放结点

  e= q->data;free(q);

  returnOK;

  }

  11.从表尾到表头逆向建立单链表的算法

  Void CreateList_L(LinkList &L,int n)

  {

  //逆序位输入n个元素的值,建立带表头结点的单链线性表L

  L= (LinkList)malloc(sizeof(LNode));

  L->next= NULL;//先建立一个带头结点的单链表

  for(i=n;i>0;++i)

  {

  p=(LinkList)malloc(sizeof(LNode));//生成新结点

  scanf(&p->data);//输入元素值

  p->next = L->next;L-next =p;//插入到表头

  }

  }



相关评论