c语言实现单链表

链表的类型声明

#define ElementType int 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,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position); int Count(List L); void PrintList(List L);

代码实现

#include <stdio.h> #include <stdlib.h> #define ElementType int 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,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position); int Count(List L); void PrintList(List L); struct Node { ElementType Element; Position Next; }; //创建链表 List CreatList() { List L; L = malloc(sizeof(struct Node)); if(L == NULL) perror("out of memory"); L->Next = NULL; return L; } //清空链表 List MakeEmpty(List L) { if(L == NULL) return L; DeleteList(L); return CreatList(); } //测试链表是否为空 int IsEmpty(List L) { return L->Next == NULL; } //测试当前位置是否是链表末尾的函数 int IsLast(Position P,List L) { return P->Next == NULL; } //查找x Position Find(ElementType X,List L) { Position P; P = L->Next; while(P!=NULL && P->Element != X) { P = P->Next; } return P; } //返回上一个位置 Position FindPrevious(ElementType X,List L) { Position P; P= L; while(P->Next !=NULL && P->Next->Element !=X) P=P->Next; return P; } //删除 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); } } //插入 void Insert(int X,List L,Position P) { Position TmpCell; TmpCell = malloc(sizeof(struct Node)); if(TmpCell == NULL) perror("out of memory"); TmpCell->Element = X; TmpCell->Next = P->Next; P->Next = TmpCell; } //删除表 void DeleteList(List L) { Position P,Tmp; P = L->Next; L->Next = NULL; while(P!=NULL) { 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; } //返回表的元素个数 int Count(List L) { int count = 0; if(L==NULL||L->Next == NULL) return 0; while(L->Next!=NULL) { count++; L=L->Next; } return count; } //打印链表 void PrintList(List L) { if(L==NULL||L->Next == NULL) return; while(L->Next != NULL) { L=L->Next; printf("%d ",L->Element); } } int main(void) { List L = CreatList(); for(int i=0;i<10;i++) { Insert(i,L,L); } PrintList(L); return 0; }