链表的C语言实现

2018/01/29 数据结构
#include <stdio.h>
#include <stdlib.h>

struct Node;

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

struct Node {
	ElementType Element;
	Position Next;
};

List MakeEmpty(List L);
int isEmpty(List L);
int IsLast(Position P);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
void PrintList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
void FatalError(const char str[]);

List MakeEmpty(List L) {
	Position P, Tem;
	P = L->Next;
	L->Next = NULL;
	while (P != NULL) {
		Tem = P->Next;
		free(P);
		P = Tem;
	}
	return L;
}

int isEmpty(List L) {
	return L->Next == NULL;
}

int IsLast(Position P) {
	return P->Next == NULL;
}

Position Find(ElementType X, List L) {
	Position P;
	P = L->Next;
	while (P != NULL && P->Element != X) {
		P = P->Next;
	}
	return P;
}

void Delete(ElementType X, List L) {
	Position P, TemCell;
	P = FindPrevious(X, L);
	if(!IsLast(P)) {
		TemCell = P->Next;
		P->Next = TemCell->Next;
		free(TemCell);
	}
}

Position FindPrevious(ElementType X, List L) {
	Position P;
	P = L;
	while (P != NULL && P->Next->Element != X) {
		P = P->Next;
	}
	return P;
}

void Insert(ElementType X, List L, Position P) {
	Position TemCell;
	TemCell = (struct Node *)malloc(sizeof(struct Node));
	if (TemCell == NULL) {
		FatalError("Out of space!!!");
	}
	TemCell->Element = X;
	TemCell->Next = P->Next;
	P->Next = TemCell;
}

void DeleteList(List L) {
	Position P, Tem;
	P = L->Next;
	free(L);
	while (P != NULL) {
		Tem = P->Next;
		free(P);
		P = Tem;
	}
}

void PrintList(List L) {
	Position P;
	P = L->Next;
	while (P != NULL) {
		printf("%d ", P->Element);
		P = P->Next;
	}
}

void FatalError(const char str[]) {
	printf("%s", str);
}

int main() {
	List L = (struct Node *)malloc(sizeof(struct Node));
	L->Next = NULL;
	Insert(3, L, L);
	Insert(2, L, L);
	Insert(1, L, L->Next);
	PrintList(L);
	return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Search

    Table of Contents