www.zhblog.net

单向链表

单向链表:

此例中元素为int类型,不是通用类型。


list.h

#ifndef _List_H
#define _List_H

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

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

#endif


list.c

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

#define ARRAY_SIZE 5


struct Node {
ElementType Element;
Position Next;
};

int main() {
List L = malloc(sizeof(List));
L->Element = -1;
L->Next = NULL;

ElementType X = 10;
Insert(X, L, L);
PrintList(L);

int arr[ARRAY_SIZE] = {3, 6, 2, 8, 1};
for (int n = 0; n < ARRAY_SIZE; ++n) {
Insert(arr[n], L, L);
}
PrintList(L);

Delete(X, L);
PrintList(L);

Position P = Find(2, L);
printf("%d\n", P->Element);

Insert(5, L, P);
PrintList(L);

DeleteList(L);
PrintList(L);

printf("%d\n", IsEmpty(L));
}

/*判断是否空表*/
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 != NULL && P->Next->Element != X) {
P = P->Next;
}
return P;
}

/*在元素P后插入新元素*/
void Insert(ElementType X, List L, Position P) {
Position TempCell;
TempCell = malloc(sizeof(Position));
if (TempCell == NULL) {
perror("insert malloc: ");
}
TempCell->Element = X;
TempCell->Next = P->Next;
P->Next = TempCell;
}

/*从列表中删除值为X的元素*/
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 DeleteList(List L) {
Position P, Tmp;
P = L->Next;
L->Next = NULL;
while (P != NULL) {
Tmp = P->Next;
free(P);
P = Tmp;
}
}

/*打印链表元素*/
void PrintList(List L) {
Position P;
P = L->Next;
printf("[ ");
while (P != NULL) {
printf("%2d,", P->Element);
P = P->Next;
}
printf("\b ]\n");
}

 

结果:

[ 10 ]

[  1, 8, 2, 6, 3,10 ]

[  1, 8, 2, 6, 3 ]

2

[  1, 8, 2, 5, 6, 3 ]

[ ]

1



  

 

  

 

展开阅读全文

相关文章

评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 心情