list.c

C语言编写的标准链表模板。包含链表的9种基本操作

/*********
 *                A Template of Linked List
 *
 * - Always assume there exists a header in the list
 *
 *                                     -- Copyright (C) =iEDi=
 **************************************************************/

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

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

////// Declare your own element's type here //////
typedef int ElementType;
//////////////////////////////////////////////////

struct Node
{
	ElementType Element;
	Position Next;
};

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Delete(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
ElementType GetElement(Position P);

/* Initialize a list */
List MakeEmpty(List L)
{
	L = (List) malloc(sizeof(struct Node));
	/***** Error Handler ******/
//	if(L == NULL)
//		printf("Runtime Error: Out of memory!");

	L->Next = NULL;
	return L;
}

/* Return true if L is empty */
int IsEmpty(List L)
{
	return L->Next == NULL;
}

/* Return true if P is the last position in list L */
int IsLast(Position P, List L)
{
	return P->Next == NULL;
}

/* Return position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
	Position P;

	P = L->Next;
	while (P != NULL && P->Element != X)	////// Modify here if your element is structure //////
		P = P->Next;

	return P;
}

/* Return position of X's previous element in L */
/* If X is not found, the last field in L returned */
Position FindPrevious(ElementType X, List L)
{
	Position P;

	P = L;
	while (P->Next != NULL && P->Next->Element != X)	////// Modify here if your element is structure //////
		P = P->Next;

	return P;
}

/* Delete first occurrence of X from a list */
void Delete(ElementType X, List L)
{
	Position P, TmpCell;

	P = FindPrevious(X, L);
	if (!IsLast(P, L)) {
		TmpCell = P->Next;
		P->Next = TmpCell->Next;
		free(TmpCell);
	}
}

/* Insert after legal position P */
void Insert(ElementType X, List L, Position P)
{
	Position TmpCell;

	TmpCell = malloc(sizeof(struct Node));
	/***** Error Handler ******/
//	if(TmpCell == NULL)
//		printf("Runtime Error: Out of memory!");

	TmpCell->Element = X;
	TmpCell->Next = P->Next;
	P->Next = TmpCell;
}

/* Delete list L */
void DeleteList(List L)
{
	Position P, Tmp;

	P = L->Next;
	L->Next = NULL;
	while (P != NULL) {
		Tmp = P->Next;
		free(P);
		P = Tmp;
	}
}

/* Return element at position P */
ElementType GetElement(Position P)
{
	return P->Element;
}



/******************** Sample Code ********************/
// This sample will transform an array into a list, then do some tests.

void PrintList(List L)
{
	Position P;

	P = L->Next;	// skip header
	while (P != NULL) {
		printf("%d ", P->Element);
		P = P->Next;
	}
	printf("\n");
}

int main(void)
{
	int number_array[10] = {6, 8, 7, 3, 4, 2, 0, 9, 5, 1};
	int i;

	List number_list;	// declare a list;
	Position P;		// record current position
	Position found;

	number_list = MakeEmpty(number_list);	// initialize a list
	P = number_list;	//initialize P

	if (IsEmpty(number_list))	//test function IsEmpty()
		printf("number_list initialized!\n");

	// transform begin...
	for (i=0; i<10; i++) {
		Insert(number_array[i], number_list, P);
		P = P->Next;
	} // when the for loop is done, P is pointing to the last field
	PrintList(number_list);

	if (!IsEmpty(number_list))
		printf("number_list transformed!\n");

	printf("now, we are looking for where number 0 is:\n");
	found = Find(0, number_list);	// test function Find()
	printf("number 0 was found, and we see found->Element = %d!\n", GetElement(found));

	printf("now, we will delete number 0 from the list:\n");
	Delete(0, number_list);		// test function Delete()
	PrintList(number_list);

	printf("now, we will insert 0 back to its original position:\n");
	Insert(0, number_list, Find(2, number_list));	// test function Insert()
	PrintList(number_list);

	printf("now, we will see if 1 is the last number:\n");
	if (IsLast(Find(1, number_list), number_list))	// test function IsLast()
		printf("Yes!\n");

	DeleteList(number_list);	// test function DeleteList()
	if (IsEmpty(number_list))
		printf("number_list deleted!\n");

	return 0;
}