Posted on 2012-08-21 22:38
hoshelly 阅读(187)
评论(0) 编辑 收藏 引用 所属分类:
DS && Algorithm
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
typedef struct {
ElemType *elem; //存储空间基址
int length; //当前的线性表长度
int listsize; //当前分配的存储容量
}SqList;
//初始化线性表
Status InitList_Sq(SqList *L) //用线性表的指针操作
{
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem) exit(OVERFLOW);
(*L).length=0;
(*L).listsize=LIST_INIT_SIZE;
return OK;
}
int ListLength(SqList L)
{
return L.length;
}
Status GetElem(SqList L,int i,ElemType *e)
{
if(i<1 || i>L.length)
exit(ERROR);
*e=*(L.elem+i-1);
return OK;
}
Status ListInsert(SqList *L,int i,ElemType e)
{
ElemType *newbase,*p,*q;
if(i<1 || i>(*L).length+1)
return ERROR;
if((*L).length >= (*L).listsize)
{
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*L).elem=newbase;
(*L).listsize +=LISTINCREMENT;
}
q=(*L).elem+i-1; //插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p)
*(p+1)=*p;
*q=e;
++(*L).length;
return OK;
}
int LocateElem(SqList L,ElemType e)
{
int i;
for(i=0;i<L.length;i++)
{
if(*(L.elem+i) == e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
Status Visit(ElemType *c)
{
printf("%d ",*c);
return OK;
}
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
Visit(L.elem+i);
printf("\n");
return OK;
}
void Union(SqList *La,SqList Lb) //求La和Lb中元素的集合La,即把Lb中与La不相同的元素取出来插入La中
{
ElemType La_len,Lb_len;
int i,e;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e);
if(!LocateElem(*La,e))
ListInsert(La,++La_len,e);
}
}//Union
int main()
{
SqList La,Lb;
int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
InitList_Sq(&La);
for(j=1;j<=4;j++)
ListInsert(&La,j,a[j-1]);
printf("print La: \n");
ListTraverse(La);
InitList_Sq(&Lb);
for(j=1;j<=7;j++)
ListInsert(&Lb,j,b[j-1]);
printf("print Lb: \n");
ListTraverse(Lb);
Union(&La,Lb);
printf("print La: \n");
ListTraverse(La);
return 0;
}