#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100//線性表存儲空間的初始分量
#define LISTINCREAMENT 10//線性表存儲空間的配置設定增量
typedef int Status;
typedef int ElemType;
//=====================================================
//動态配置設定順序存儲結構
//=====================================================
typedef struct{
ElemType *elem;//存儲空間基址
int length;//目前長度
int listsize;//目前配置設定的存儲容量
}SqList;
//=========================================================
//等于函數
//=========================================================
Status equal(ElemType a,ElemType b)
{if(a==b)
return TRUE;
else
return FALSE;
}
//=====================================================
//線性表長度的計算
//=====================================================
Status ListLength(SqList La)
{
return La.length;
}
//=========================================================
//列印函數
//=========================================================
void print(ElemType *c)
{
printf("%d ",*c);
}
//=====================================================
//構造一個空的線性表L
//=====================================================
Status InitList_Sq(SqList *l)
{
(*l).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*l).elem)
exit(OVERFLOW);
(*l).length=0;//線性表中元素的個數為length=0
(*l).listsize=LIST_INIT_SIZE;//線性表的大小為100個位元組
return OK;
}
//=====================================================
//在順序線性表L中第i個位置之前插入新的元素e
//=====================================================
Status ListInsert_Sq(SqList *l,int i,ElemType e)
{
ElemType *newbase,*q,*p;
if(i<1||i>(*l).length+1)
return ERROR;
if((*l).length>=(*l).listsize){
newbase=(ElemType*)realloc((*l).elem,((*l).listsize+LISTINCREAMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*l).elem=newbase;
(*l).listsize+=LISTINCREAMENT;//線性表增加listincrement長度
}
q=&((*l).elem[i-1]);//指針q指向線性表的第i個元素
for(p=&((*l).elem[(*l).length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++(*l).length;
return OK;
}
//=====================================================
//查找第一個與e滿足compare()的元素位序
//=====================================================
int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
//若找到則傳回其在L中的為序,否則傳回0
ElemType *p;
int i=1;
p=L.elem;
while(i<=L.length&&!(*compare)(*p++,e))
i++;
if(i<=L.length)
return i;
else
return 0;
}
//=========================================================
//用e傳回L中第i個資料元素的值
//=========================================================
Status getelem(SqList l,int i,ElemType *e)
{ if(i<1||i>l.length)
exit(ERROR);
*e=*(l.elem+i-1);
return OK;
}
//=========================================================
//依次對L的每一個資料元素調用函數vi(),一旦vi()失敗,則操作失敗
//=========================================================
Status ListTraverse(SqList l,void(*vi)(ElemType *))
{
ElemType *p;
int i;
p=l.elem;
for(i=1;i<=l.length;i++)
vi(p++);
printf("\n");
return OK;
}
//=====================================================
//将所有在Lb中而不再La中的資料元素插入到La中
//=====================================================
void Union(SqList *la,SqList lb)
{
int la_len,lb_len;
int i;
ElemType e;
la_len=ListLength(*la);
lb_len=ListLength(lb);
for(i=1;i<=lb_len;i++)
{
getelem(lb,i,&e);
if(!LocateElem_Sq(*la,e,equal))
ListInsert_Sq(la,++la_len,e);
}
}
//=====================================================
//主函數
//=====================================================
void main()
{
SqList la,lb;
int j,i;
i=InitList_Sq(&la);//構造一個空的線性表,如果構造成功,則傳回ok
if(i==1)
for(j=1;j<=6;j++)
i=ListInsert_Sq(&la,j,j);
printf("la= ");
ListTraverse(la,print);
InitList_Sq(&lb);
for(j=1;j<=6;j++)
i=ListInsert_Sq(&lb,j,2*j);
printf("lb= ");
ListTraverse(lb,print);
Union(&la,lb);
printf("la= ");
ListTraverse(la,print);
}