slist.c

来自「1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）」· C语言 代码 · 共 243 行

/*
 * 作者：antigloss
 * 最后修改：05-8-16 00:10
 * 蚂蚁的 C/C++ 标准编程
 *    cpp.ga-la.com
 */

#include <stdlib.h>
#include <stdio.h>
#include "../header/slist.h"

/* begin of FormList 05-8-15 20:15 */
LinkList FormList( void ) /* 正向形成链表 */
{
	int temp;
	LinkList h, head, end;

	if ( !( h = head = malloc(sizeof(Node)) ) ) {
		return NULL;
	}
	head->next = NULL;
	while ( ( temp=getchar() ) != '\n' && temp != EOF ) {
		if ( !( end = malloc(sizeof(Node)) ) ) {
			Destroy( head ); /* 分配空间失败，释放空间 */
			return NULL;     /* 返回 NULL */
		}
		h->next = end;
		h = end;
		h->data = temp;
		h->next = NULL;
	}

	return head;
} /* end of FormList */

/* begin of FormList2 05-8-15 20:30 */
LinkList FormList2( void ) /* 逆向形成链表 */
{
	LinkList head, end;
	int temp;

	if ( !( head = malloc(sizeof(Node)) ) ) {
		return NULL;
	}
	head->next = NULL;
	while ( ( temp=getchar() ) != '\n' && temp != EOF ) {
		if ( !( end = malloc(sizeof(Node)) ) ) {
			Destroy( head );
			return NULL;
		}
		end->data = temp;
		end->next = head->next;
		head->next = end;
	}

	return head;
} /* end of FormList2 */

/* begin of Insert 05-8-15 22:20 */ 
int Insert(LinkList L, unsigned i) /* 插入数据 */
{ /* 若单链表没有头结点，需对在第一个结点之前进行插入的情况单独进行处理。很麻烦 */
	unsigned j;
	LinkList T;
	int temp;
	
	for ( j = 1, L->next; L && j<i; L = L->next, ++j )
		;
	if ( !L || j>i ) {
		return 0;
	}
	printf( "请输入您要插入的数据：" );
	while ( ( temp=getchar() ) != '\n' && temp != EOF ) {
		if ( !( T = malloc(sizeof(Node)) ) ) {
			return 0;
		}
		T->data = temp;
		T->next = L->next;
		L->next = T;
		L = T;
	}

	return 1;
} /* end of Insert */

/* begin of Delete 05-8-15 23:40 */
void Delete(LinkList L, unsigned i, unsigned j) /* 删除数据 */
{
	LinkList T;

	if ( !i || !j ) {
		return;
	}
	for ( i--; i && L; L = L->next, --i )
		;
	if ( !L ) {
		return;
	}
	for ( T = L->next; j && T; --j ) {
		L->next = T->next;
		free( T );
		T = L->next;
	}
} /* end of Delete */

/* begin of Disp 05-8-15 20:20 */
void Disp( LinkList L ) /* 显示数据 */
{
	for( L = L->next; L; L = L->next ) {
		printf( "%c", L->data );
	}
	printf( "\n" );
} /* end of Disp */

/* begin of Destroy 05-8-15 20:00 */
void Destroy( LinkList L ) /* 释放内存 */
{
	LinkList T = L;

	for ( L = L->next; L; T = L, L = L->next ) {
		free( T );
	}
	free( T );
} /* end of Destroy */

/* begin of Bubble 05-8-15 22:40 */
void Bubble(LinkList L) /* 冒泡排序 */
{
	ElemType temp;
	LinkList T, H;
	unsigned i, j, flag = 1;

	if ( !( i = CountLen(L) ) ) { /* 计算链表长度 */
		return; /* 如果长度为 0，返回 */
	}
	
	H = L->next;
	while ( flag ) {
		L = H;
		T = H->next;
		flag = 0;
		j = 1;
		while ( j < i ) {
			if ( L->data > T->data ) {
				temp = T->data;
				T->data = L->data;
				L->data = temp;
				flag = 1;
			}
			L = L->next;
			T = T->next;
			++j;
		}
		--i;
	}
}  /* end of Bubble */

/* begin of Merge 05-8-15 23:45 */
void Merge(LinkList A, LinkList B) /* 合并有序链表 */
{
	LinkList C = A, D = B;

	A = A->next;
	B = B->next;
	while ( A && B ) {
		if ( A->data <= B->data ) {
			C->next = A;
			C = A;
			A = A->next;
		} else {
			C->next = B;
			C = B;
			B = B->next;
		}
	}
	C->next = A ? A : B;

	free( D );
} /* end of Merge */

/* begin of CountLen 05-8-15 20:25 */
unsigned CountLen( LinkList L ) /* 计算链表长度 */
{
	unsigned i = 0;

	for ( L = L->next; L; L = L->next, ++i )
		;
	return i;
} /* end of CountLen */

/* begin of Exchange 05-8-15 23:55 */
void Exchange(LinkList L, unsigned i) /* 前 m 个结点和后 n 个结点的互换 */
{
	LinkList A, B;

	if ( !i ) {
		return;
	}

	A = B = L->next;
	for ( --i; i && A; A = A->next, --i )
		;
	if ( !A ) {
		return;
	}

	L->next = A->next;
	A->next = NULL;
	A = L->next;
	while ( A->next ) {
		A = A->next;
	}
	A->next = B;
} /* end of Exchange */

/* begin of Purge 05-8-16 00:05 */
void Purge(LinkList L) /* 删除单链表中重复的数据元素 */
{
	LinkList A, B, C, D;

	B = C = L->next;
	L->next = NULL;
	while ( B ) {
		A = L->next;
		D = L;
		while ( A ) {
			if ( A->data == B->data ) {
				B = B->next;
				free( C );
				C = B;
				break;
			} else {
				A = A->next;
				D = D->next;
			}
		}
		if ( !A ) {
			D->next = B;
			B = B->next;
			C->next = NULL;
			C = B;
		}
	}
} /* end of Purge */