薛映冰的代码狂躁症

人最痛苦的不是失败，而是我本可以

链表

| Comments

一、什么是链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

结构如下图：

附上wiki链接：Linked List (为什么发英文的呢，因为我看不懂)

二、链表特点

链表相对于数组链表的优点是，数组大小可变，插入、删除速度蛮快，但是查找的效率却不如数组链表。

结构上：
1、每一个元素都有指针next指向下一下元素
2、最后一个元素的next为NULL

三、链表操作

1、删除

2、插入

四、实现

不说了，好累，上代码：

list.h 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

typedef int ElementType;

#ifndef _List_H
#define _List_H

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

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 P);

#endif

struct Node
{
  ElementType Element;
  Position Next;
};
list.c 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

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

List MakeEmpty(List L)
{
  if(L !=NULL)
      DeleteList(L);

  L = (List) 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, TmpCell;

  P = FindPrevious(X, L);

  if(!IsLast(P, L))
  {
      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, List L, Position P)
{
  Position TmpCell;

  TmpCell = (Position)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 , 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;
}
test-list.c 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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

void PrintList(const List L)
{
  Position P = Header(L);

  if(IsEmpty(L))
      printf("Empty list\n");
  else
  {
      do
      {
          P = Advance(P);
          printf("%d", Retrieve(P));
      } while( !IsLast(P, L));
      printf("\n");
  }
}

int main()
{
  List L;
  Position P;

  int i;

  L = MakeEmpty(NULL);
  P = Header(L);

  for (i = 0; i < 10; i++)
  {
      Insert(i, L, P);
      PrintList(L);
      P = Advance(P);
  }
  for (i = 0; i < 10; i+=2)
  {
      Delete(i, L);
  }
  for (i = 0; i < 10; i++)
  {
      if((i%2==0)==(Find(i, L)!=NULL))
          printf("Find fails\n");
  }

  printf("Finished deletions\n");

  PrintList(L);

  DeleteList(L);

  return 0;
}

附上github代码地址：here

Comments