單連結清單實作

資料結構與算法分析——c語言描述 第三章的單連結清單

很基礎的東西。走一遍流程。有人說學程式設計最簡單最笨的方法就是把書上的代碼敲一遍。這個我是頭檔案是照抄的。.c源檔案自己實作。

list.h

typedef int ElementType;
#ifndef _List_H
#define _List_H

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

List CreatList();
List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif
           

list.c

#include"list.h"
#include<stdlib.h>
#include"fatal.h"

struct  Node
{
	ElementType Element;
	Position Next;
};

List CreatList() {
	List l = malloc(sizeof(struct Node));
	if (l == NULL)
		Error("out of memory");
	l->Next = NULL;
	return l;
}

List MakeEmpty(List L) {
	if (L != NULL)
		DeleteList(L);
	L = malloc(sizeof(struct Node));
	if (L == NULL)
		FatalError("Out of memory");
	L->Next = NULL;
	return L;
}

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

int IsLast(Position P, List L) {
	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;
	P = FindPrevious(X, L);
	if (!IsLast(P, L)) {
		Position TmpCell = P->Next;
		P->Next = TmpCell->Next;
		free(TmpCell);
	}
}

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

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

void DeleteList(List L) {
	Position p;
	p = L->Next;
	L->Next = NULL;
	while (p != NULL){
		Position tmp;
		tmp = p->Next;
		free(p);
		p = tmp;
	}
}

Position Header(List L) {
	return L;
}

Position First(List L) {
	return L->Next;
}

Position Advance(Position P) {
	return P->Next;
}

ElementType Retrieve(Position P) {
	return P->Element;
}
           

fatal.h

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

#define Error(Str) FatalError(Str)
#define FatalError(Str) fprintf(stderr,"%s\n",Str),exit(1)