数据结构-----顺序表与单链表的实现

1.顺序表

//
//  实现顺序表的初始化，插入，删除，查找，逆置，合并等操作
//

//

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef  int        ElemType ;
#define  MAXSIZE    100
#define  INCREMENT  100

typedef struct SeqList
{
	ElemType * head ;  // 数据存储空间
	int length ; // 长度
	int size ;   // 最大容量
} SeqList ;

// 初始化
void InitSeqList( SeqList * S )
{
	S->head = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE) ;
	if( S->head == NULL )
	{
		printf("线性表初始化时内存分配失败!\n") ;
		exit(0) ;
	}
	S->length = 0 ;
	S->size = MAXSIZE ;
}

// 查找
// 输入元素的值，返回元素的索引 ; 查找失败返回-1
int Find( SeqList * S , ElemType elem )
{
	int i = 0 ;
	for( ; i < S->length ; i++ )
	{
		if( S->head[i] == elem )
		{
			return i ;
		}
	}
	return -1 ;
}

// 插入
// 在某个索引前面插入某个元素的值
void Insert( SeqList * S , int pos , ElemType elem )
{
	if( S->length + 1 == S->size )   // 检查顺序表内存是否足够
	{
		ElemType * top = (ElemType*)realloc( S->head , MAXSIZE + INCREMENT ) ;
		if( !top )
		{
			printf("内存分配失败!\n") ;
			exit(0) ;
		}
		S->head = top ;
		S->size = S->length + INCREMENT ;
	}

	if( pos > S->length  || pos < 0 )  // 检查输入的索引是否合法
	{
		printf("输入的索引不合法!\n") ;
		exit(0) ;
	}

	int  i = S->length - 1 ;
	for( ; i >= pos ; i-- )
	{
		S->head[i+1] = S->head[i] ;
	}
	S->head[pos] = elem ;
	S->length ++ ;
}

//删除
//删除顺序表中的指定值的元素 
void Delete( SeqList * S , ElemType elem )
{
	int pos = Find( S , elem ) ;
	int i = 0 ;
	for( i = pos ; i < S->length ; i++ )
	{
		S->head[i] = S->head[i+1] ;
	}
	S->length -- ;
}

//交换
void Swap( ElemType * e1 , ElemType * e2 )
{
	ElemType tmp ;
	tmp = *e1 ;
	*e1 = *e2 ;
	*e2 = tmp ;
}

// 逆置
// 逆置线性表中的元素
void Reverse( SeqList * S )
{
	int i = 0 ;
	for( ; i < S->length / 2 ; i++ )
	{
		Swap( &S->head[i] , &S->head[S->length-1-i] ) ;
	}
}

// 递增排序
// 冒泡排序
void Sort( SeqList * S )
{
	int i = 0 ;
	int j = 0 ;
	for( ; i < S->length - 1 ; i++ )
	{
		for( j = i + 1 ; j < S->length ; j++ )
		{
			if( S->head[i] > S->head[j] )
			{
				Swap( &S->head[i] , &S->head[j] ) ;
			}
		}
	}
}


// 合并两个顺序表
// 保证合并后具有递增的顺序

void Union( SeqList * S1 , SeqList * S2 , SeqList * S3 )
{
	if( S3->size < S1->length + S2->length )
	{
		printf("顺序表过小，容纳不下合并之后的两个线性表!\n") ;
		exit(0) ;
	}

	Sort( S1 ) ;
	Sort( S2 ) ;

	int i = 0 ; 
	int j = 0 ;
	int k = 0 ;

	while( i < S1->length && j < S2->length )
	{
		if( S1->head[i] < S2->head[j] )
		{
			S3->head[k++] = S1->head[i++] ;
		}
	    else if( S1->head[i] > S2->head[j] )
		{
			S3->head[k++] = S2->head[j++] ;
		}
		else
		{
			S3->head[k++] = S1->head[i] ;
			S3->head[k++] = S2->head[j] ;
			i++ ;
			j++ ;
		}
	}

	if( i > S1->length - 1 )
	{
		while( j < S2->length )
		{
			S3->head[k++] = S2->head[i++] ;
		}
	}

	if( j > S2->length - 1 )
	{
		while( i < S1->length )
		{
			S3->head[k++] = S1->head[i++] ;
		}
	}
	S3->length = k ;
}

// 输出顺序表中的元素
void Print( SeqList * S )
{
	int i = 0 ; 
	for( ; i < S->length ; i++ )
	{
		printf("%d " , S->head[i] ) ;
	}
	printf("\n") ;
}

// 测试函数
int main()
{
	SeqList S1 , S2 , S3 ;

	InitSeqList( &S1 ) ;
	InitSeqList( &S2 ) ;
	InitSeqList( &S3 ) ;

	Insert( &S1 , 0 , 1 ) ;
	Insert( &S1 , 1 , 5 ) ;
	Insert( &S1 , 2 , 2 ) ;

	Insert( &S2 , 0 , 2 ) ;
	Insert( &S2 , 1 , 4 ) ;
	Insert( &S2 , 2 , 3 ) ;

	printf("S1:") ;
	Print( &S1 ) ;

	printf("S2:") ;
	Print( &S2 ) ;

	Union( &S1 , &S2 , &S3 ) ;

	printf( "S3:" ) ;
	Print( &S3 ) ;

	return 0 ;
}

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

typedef int ElemType ;

typedef struct Node 
{
	ElemType elem ;
	struct Node * next ;
}Node ;

typedef struct LinkList
{
	Node *head ;  // 头结点
	int length ;  // 链表长度
} LinkList ;

void InitLinkList( LinkList * L )
{
	L->head = (Node*)malloc(sizeof(Node)) ;
	if( !L->head )
	{
		printf("内存申请失败!\n") ;
		exit(0) ;
	}

	L->head->next = NULL ;
	L->length = 0 ;
}

//判断 节点是否在链表中
bool Find( LinkList * L , Node node )
{
	Node * p = L->head ;

	while( ( p = p->next ) != NULL )
	{
		if( p->elem == node.elem )
		{
			return true ;
		}
	}
	return false ;
}

// 在表尾插入结点
void Insert( LinkList * L , ElemType elem ) 
{
	Node * node = (Node*)malloc(sizeof(Node)) ;
	if( !node )
	{
		printf("申请内存失败!\n") ;
		exit(0) ;
	}
	node->elem = elem ;
	node->next = NULL ;

	Node * p = L->head ;
	while( p->next != NULL )
	{
		p = p->next ;
	}
	p->next = node ;
	L->length++ ;
}

// 删除结点
bool Delete( LinkList * L , ElemType elem )
{
	Node * p = L->head ;
	Node * q = p ;

	while( p->next != NULL )
	{
		q = p ;
		p = p->next ;
		if( p->elem == elem )
		{
			q->next = p->next ;
			free( p ) ;
			L->length-- ;
			return true ;
		}
	}
	return false ;
}


void Print( LinkList * L )
{
	Node * p = L->head ;

	while( p->next != NULL )
	{
		p = p->next ;
		printf("%d " , p->elem ) ;
	}
	printf("\n") ;
}

int main()
{
	LinkList L ;
	InitLinkList( &L ) ;

	Insert( &L , 5 ) ;
	Insert( &L , 4 ) ;
	Insert( &L , 8 ) ;
	Insert( &L , 2 ) ;

	Print( &L ) ;

	Delete( &L , 8 ) ;

	Print( &L ) ;

	return 0 ;
}