数据结构学习第四天

  1 #ifndef _CURSOR_H
  2 #define _CURSOR_H
  3 #define Size 50
  4 #define Null 0
  5 typedef int PtrToNode;
  6 typedef PtrToNode List;
  7 typedef PtrToNode Position;
  8 
  9 void InitializeCursorSpace();
 10 
 11 List MakeEmpty(List L);
 12 int IsEmpty(const List L);
 13 int IsLast(const Position P, const List L);
 14 Position Find(int Element, const List L);
 15 void Delete(int Element, List L);
 16 Position FindPrevious(int Element, const List L);
 17 void Insert(int Element, List L, Position P);
 18 void DeleteList(List L);
 19 Position Header(List L);
 20 Position First(List L);
 21 int Retrive(const Position P);
 22 
 23 struct Node
 24 {
 25     int Element;
 26     Position Next;
 27 };
 28 struct Node CursorSpace[Size];
 29 static Position CursorAlloc()
 30 {
 31     Position P;
 32     P = CursorSpace[0].Next;
 33     CursorSpace[0].Next = CursorSpace[P].Next;
 34     CursorSpace[P].Next = Null;
 35     return P;
 36 }
 37 
 38 static void FreeCursor(Position P)
 39 {
 40     CursorSpace[P].Element = 0;
 41     CursorSpace[P].Next = CursorSpace[0].Next;
 42     CursorSpace[0].Next = P;
 43 }
 44 
 45 void InitializeCursorSpace()
 46 {
 47     for (int i = 0; i < Size - 1; i++)
 48     {
 49         CursorSpace[i].Element = 0;
 50         CursorSpace[i].Next = i + 1;
 51     }
 52     CursorSpace[Size - 1].Next = 0;
 53     CursorSpace[Size - 1].Element = 0;
 54 }
 55 List MakeEmpty(List L)
 56 {
 57     CursorSpace[L].Element = 0;
 58     CursorSpace[L].Next = Null;
 59     return L;
 60 }
 61 int IsEmpty(const List L)
 62 {
 63     return    CursorSpace[L].Next == Null;
 64 }
 65 int IsLast(const Position P, const List L)
 66 {
 67     return CursorSpace[P].Next == Null;
 68 }
 69 Position Find(int Element, const List L)
 70 {
 71     Position P = CursorSpace[L].Next;
 72     /*while (P!=Null)
 73     {
 74         if (CursorSpace[P].Element ==Element)
 75             return P;
 76         P = CursorSpace[P].Next;
 77     }
 78     return Null;*/
 79     //下面这个版本更加简化
 80     while (P && CursorSpace[P].Element != Element)
 81     {
 82         P = CursorSpace[P].Next;
 83     }
 84     return P;
 85 }
 86 
 87 void Delete(int Element, List L)
 88 {
 89     Position P1, P2;
 90     P1 = P2 = FindPrevious(Element, L);
 91     if (P1==L)
 92     {
 93         CursorSpace[L].Next = Null;
 94         FreeCursor(CursorSpace[L].Next);
 95     }
 96     else
 97     {
 98         CursorSpace[P1].Next = CursorSpace[CursorSpace[P1].Next].Next;
 99         FreeCursor(CursorSpace[P1].Next);
100     }
101 }
102 
103 Position FindPrevious(int Element, const List L)
104 {
105     Position P = L;
106     /*while (CursorSpace[P].Next!=Null)
107     {
108         if (CursorSpace[CursorSpace[P].Next].Element == Element)
109             return P;
110         P = CursorSpace[P].Next;
111     }
112     return Null;*/
113     while (CursorSpace[P].Next && CursorSpace[CursorSpace[P].Next].Element != Element)
114     {
115         P = CursorSpace[P].Next;
116     }
117     return P;
118 }
119 void Insert(int Element, List L, Position P)
120 {
121     Position P1 = CursorAlloc();
122     CursorSpace[P1].Element = Element;
123     CursorSpace[P1].Next = P;
124     Position P2 = FindPrevious(CursorSpace[P].Element, L);
125     CursorSpace[P2].Next = P1;
126 }
127 void DeleteList(List L)
128 {
129     Position P1, P2;
130     P1 = P2 = CursorSpace[L].Next;
131     while (P2 != Null)
132     {
133         P2 = CursorSpace[P1].Next;
134         FreeCursor(P1);
135         P1 = P2;
136     }
137 }
138 int Retrive(const Position P)
139 {
140     return CursorSpace[P].Element;
141 }
142 Position Header(List L)
143 {
144     return L;
145 }
146 Position First(List L)
147 {
148     return CursorSpace[L].Next;
149 }
150 
151 #endif // !_CURSOR_H

 1 #include<stdio.h>
 2 #include"Cursor.h"
 3 int main()
 4 {
 5     InitializeCursorSpace();   //初始化
 6     int L = CursorAlloc();
 7     MakeEmpty(L);
 8     printf("%d\n",  IsEmpty(L));
 9     printf("%d\n", CursorSpace[L].Element);
10     int P = CursorAlloc();
11     CursorSpace[P].Element = 20;
12     CursorSpace[L].Next = P;
13     printf("%d\n", CursorSpace[P].Element);
14     Insert(25, L, P);
15     printf("%d\n", CursorSpace[CursorSpace[L].Next].Element);
16     printf("%d\n", Retrive(P));
17     printf("%d\n", CursorSpace[P].Next);
18     Delete(20, L);
19     //Delete(25, L);
20     printf("%d\n", CursorSpace[P].Next);
21     return 0;
22 }