当前位置: 首页 > >

重学数据结构之算法2.1

发布时间:

?????? 一年前学*的数据结构已经基本上还给老师了,现在距离找工作还有几个月时间,正好重新学*一个数据结构。这次使用的教材是严蔚敏的《数据结构》c语言版。希望能在毕业前重新学完一遍。。。


#include //输入输出函数头文件
#include //内存申请函数头文件
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 10
typedef int ElemType ;

typedef struct
{
ElemType* elem ; //存储空间基址
int length ; //当前长度
int listsize ; //当前分配的存储容量(以sizeof(ElemType)为单位)

}Sqlist ;

//操作结构,构造一个空的线性表L
void InitList( Sqlist& L )
{
//首先申请一定的空间
L.elem = ( ElemType* ) malloc( LIST_INIT_SIZE * sizeof ( ElemType ) ) ;
//判断是否申请成功
if ( ! L.elem )
{
printf( "分配内存失败:
" );
exit ( -1 ) ;
}

//将此时线性表的大小初始化为0
L.length = 0 ;
//将此线性表的剩余空间置为最大
L.listsize = LIST_INIT_SIZE ;
}

//初始条件:线性表L已经存在
//操作结果,销毁线性表L


//初始条件:线性表L已经存在
//操作结果:将L重置为空表
void ClearList ( Sqlist& L)
{
free ( L.elem ) ;
InitList(L) ;

}

//初始条件:线性表L以存在
//操作结果:若L为空表,则返回TRUE,否则返回FALSE
int ListEmpty ( Sqlist L )
{
if ( L.length == 0 )
return 0 ;
else
return 1 ;

}

//初始条件:线性表L已经存在
//返回L中数据元素的个数
int ListLength ( Sqlist L )
{
return L.length ;

}

//初始条件:线性表已存在,1<=i<=ListLength(L)
//操作结果:用e返回L中第i个数据元素的值
void GetElem( Sqlist L , int i , ElemType& e )
{
e = *( L.elem +i ) ;
}
int compare(ElemType x , ElemType y)
{
if ( x == y )
return 1 ;
else
return 0 ;
}


//初始条件:线性表L已存在,compare()是数据元素判定函数
//操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在,则返回值为0
int LocateElem ( Sqlist L , ElemType e )
{
int i = 1 ;
while( (!compare ( L.elem [ i ] , e )) && i < L.length )
{
i++ ;
}
if ( i == L.length )
return 0 ;
else
return i ;
}

//初始条件:线性表L已存在,1<=i<=ListLength(L)+1
//操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
void ListInsert( Sqlist& L , int i , ElemType e )
{
if ( i < 1 || i > L.length )
{
printf( "插入位置不在数组范围之内:
") ;
exit ( - 1 ) ;

}

if ( L.length >= L.listsize )
{
ElemType* newbase = ( ElemType* ) realloc ( L.elem , ( L.listsize + LISTINCREMENT ) * sizeof(ElemType) ) ;
if ( ! newbase )
{
printf( "追加内存失败:
") ;
exit (-1) ;
}
L.elem = newbase ;
L.listsize += LISTINCREMENT ;
}


int p =L.length - 1 ;
for ( ; p >= i ; p -- )
{
L.elem [ p + 1 ] = L.elem [ p ];
}
L.elem [ i ] = e ;
L.length += 1 ;
}


void DestroyList ( Sqlist& L )
{
free ( L.elem ) ;

}

//初始条件:La和Lb都存在
//操作结果:将Lb中值加入到La中
void union1 ( Sqlist & La, Sqlist& Lb )
{
if ( !ListEmpty( Lb ))
{
printf( "要插入的线性表为空\n" ) ;

}
else
{
int lb = 1 ;
//一次将Lb中元素取出,和La进行比较,如果没有则加入到La中,如果有,则进行下一个元素的查找比较
while ( lb < Lb.length)
{
int la = 1 ;
if( LocateElem(La,Lb.elem [ lb ]) == 0)
{
ListInsert ( La, La.length , Lb.elem [ lb ] );
}
lb ++ ;


}
}

}


int main ()
{
Sqlist M , N ;
InitList ( M ) ;
InitList ( N ) ;
for( M.length = 1 ; M.length < 10 ; M.length ++ )
{
M.elem [ M.length ] = M.length ;
}
for( N.length = 1 ; N.length < 10 ; N.length ++ )
{
N.elem [ N.length ] = N.length * 2 ;
}
union1 ( M , N ) ;
int x = 1 ;
for ( ; x < M.length ; x ++ )
{
printf("%d
", *(M.elem + x )) ;
}
ClearList ( M ) ;
ClearList ( N ) ;
DestroyList ( M ) ;
DestroyList ( N ) ;
return 0 ;
}






友情链接: