《数据结构与算法分析：C语言描述》读书笔记------List的C语言实现

时间：2021-10-14 22:19:20

List的简单实现。在GCC下测试通过。

list.h

 #ifndef _List_H

 /*List数据结构的简单实现*/

 struct Node;
 typedef struct Node Node;
 typedef struct Node * List;
 typedef struct Node * Position;
 typedef double ElementType;

 /*
 下面的这些操作可以看做是对List ADT操作的描述。这些操作的描述可以认为和具体的编程语言无关。
 */
 List MakeEmpty();
 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 InsertToFront(ElementType X,List L);
 void InsertToBack(ElementType X,List L);
 void DeleteList(List L);
 Position Header(List L);
 Position First(List L);
 Position Tail(List L);
 Position Advance(Position P);
 ElementType Retrive(Position P);
 void PrintList(List L);

 #endif

list.c

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

 struct Node
 {
     ElementType Element;/*数据*/
     Position Next;/*指向下一个节点的指针*/
 };

 /*初始化一个List，这里的实现是采用了一个“表头节点”，表头节点的存在只是为了方便一些List操作实现上的方便*/
 List MakeEmpty()
 {
     Node * PtrToHeader = (Node *)malloc(sizeof(Node));/*给头结点分配一定的内存空间，PtrToNode是指向这部分空间的指针*/
     PtrToHeader -> Next = NULL; /*将头结点的指向下一个节点的指针置为NULL*/
     return PtrToHeader;/*返回指向头结点的指针*/
 }
 /*判断一个List是否为空*/
 int IsEmpty(List L)
 {
     return L->Next == NULL ;
 }
 /*判断P指向的是不是List中的最后一个元素,参数L在实现中没有用到*/
 int IsLast(Position P , List L)
 {
       return P->Next == NULL;
 }
 /*找到并返回指定元素的位置,如果找不到，就返回空指针*/
 Position Find(ElementType X, List L)
 {
     Position P = L->Next;
     while(P != NULL)
     {
         if(P->Element == X)
             return P;
         P = P->Next;
     }
     return NULL;
 }
 /*删除指定的元素*/
 void Delete(ElementType X,List L)
 {
     Position P = FindPrevious(X,L);
     if(P != NULL)
     {
         Position temp = P->Next;
         P->Next = temp->Next;
         free(temp);
     }
 }
 /*返回指定元素的前一个位置，如果List中没有该元素，那么返回NULL*/
 Position FindPrevious(ElementType X, List L)
 {
     Position P = L;
     while(P->Next != NULL)
     {
         if(P->Next->Element == X)
             return P;
         P = P->Next;
     }
     return NULL;
 }
 /*在Position指向的节点的后面插入一个节点*/
 void Insert(ElementType X,List L,Position P)
 {
     Node * PtrToNewNode = (Node *)malloc(sizeof(Node));
     PtrToNewNode->Element = X;
     PtrToNewNode->Next = P->Next;
     P->Next = PtrToNewNode;
 }
 /*在List前面插入X*/
 void InsertToFront(ElementType X,List L)
 {
     Position P = Header(L);
     Insert(X,L,P);
 }
 /*在List最后插入X*/
 void InsertToBack(ElementType X,List L)
 {
     Position P = Tail(L);
     Insert(X,L,P);
 }
 /*删除List*/
 void DeleteList(List L)
 {
     Position P ,temp ;
     P = L->Next;
     L->Next = NULL;
     while(P != NULL)
     {
         temp = P->Next;
         free(P);
         P = temp;
     }
 }
 /*取出P位置上的节点的值*/
 ElementType Retrive(Position P)
 {
     if(P!=NULL)
         return P->Element;
 }
 /*打印一个List*/
 void PrintList(List L)
 {
     Position P = L->Next;
     while(P != NULL)
     {
         printf("%f ",P->Element);
         P = P->Next;
     }
     printf("\n");
 }
 /*获得头结点的位置*/
 Position Header(List L)
 {
     return L;
 }
 /*获得第一个节点的位置*/
 Position First(List L)
 {
     return L->Next;/*注意，如果第一个节点不存在那么有可能会返回NULL*/
 }
 /*获得最后一个节点的位置*/
 Position Tail(List L)
 {
     if(IsEmpty(L))
         return NULL;
     else
     {
         Position P = L->Next;
         while(P->Next != NULL)
             P = P->Next;
         return P;
     }
 }

 /*获得P的下一个位置*/
 Position Advance(Position P)
 {
     return P->Next;/*注意，如果P已经是最后一个位置那么有可能会返回NULL*/
 }

listTest.c

 #include "list.h"
 #include <stdio.h>
 int main()
 {
     //生成一个只包含头结点的list
     List list = MakeEmpty();
     //判断list是否为空
     if(IsEmpty(list))
         printf("Empty List...");
     PrintList(list);
     //获得头结点位置（即指向头结点的指针）
     Position P = Header(list);
     //在头结点之后插入一些数据
     Insert(1.0,list,P);
     Insert(5.0,list,P);
     Insert(6.0,list,P);
     PrintList(list);
     //获得头结点之后、第一个真正节点的位置
     Position Q = First(list);
     //在第一个节点之后插入一些数据
     Insert(2.0,list,Q);
     Insert(3.0,list,Q);
     Insert(4.0,list,Q);
     PrintList(list);
     //删除一些数据
     Delete(1.0,list);
     Delete(6.0,list);
     Delete(3.0,list);
     PrintList(list);
     //将头结点之后的数据都清空
     DeleteList(list);
     //在最前面（也就是头结点之后、第一个数据之前）插入数据
     InsertToFront(2.0,list);
     InsertToFront(1.0,list);
     //在list的最后插入数据
     InsertToBack(3.0,list);
     InsertToBack(4.0,list);
     PrintList(list);
     //遍历list的方法
     Position R = First(list);
     while(R!=NULL)
     {
         printf("%f ", Retrive(R));
         //获得R之后的位置
         R = Advance(R);
     }
     printf("\n");

     printf("Try to find 3.0...\n");
     //查找一个数据
     Position S = Find(3.0,list);
     if(S!=NULL) printf("%f is finded...\n",Retrive(S));
     else printf("Not exists in the list!");
     //查找一个数据，然后在该数据之后插入一个数据
     Position T = Find(3.0,list);
     if(T!=NULL)
         Insert(,list,T);
     PrintList(list);
 }

相关文章