《数据结构与算法》阅读笔记——表1

1.表与链表：表：连续存储一组数的数据结构。假定表中存在着某个元素i，则i的前一个元素为i的前驱元素，i的后一个元素为i的后继元素。
对表的操作：1.PrintList：输出
2.MakeEmpty：创建空表（？这两个函数书上没有解释，我猜的。）
3.Find返回关键字首次出现的位置（值得注意的是返回的值是该关键字所在的位置，比如第一个就是1，第二个就是2，不用减一。）
4.Insert和Delete：一般是从表的某个位置插入和删除某个关键字。
5.FindKth：返回某个位置上的元素。
关于链表：
链表是什么：不连续储存数据的表，链表里的元素的内存地址并不连续，每一个元素的后面都跟着一个地址指针来指向下一个元素。
为什么要使用链表：链表里的每个元素相比于表，还多储存了一个指针变量，那链表的存在的意义是什么呢？
在程序中，对表的所有的操作都可以使用数组来实现，通过数组实现使得PrintList和Find以线性时间执行，而FindKth则花费常数时间执行，然而，插入和删除所使用的时间却是比较大的，
因为表的内存地址是连续的，所以当你插入或删除一个元素时，比如你在i位置插入或删除一个元素，那么i元素后面的元素的地址都要发生改变，否则这就内存地址就会出错。
（如果i=1的话，就麻烦了。）
在这种情况下，链表不连续储存的优点就展现出来了，在增加或删除一个元素时，只要修改指针变量就可以了，大量减少程序执行的时间。
链表中最后一个元素的指针指向Null。（但同样执行FindKth操作时，链表的执行效率不如表。）
程序设计细节：
书上指出了三处会出问题的地方：
1.并不存在从所给定义出发在表的起始端插入元素的真正显性的方法。（？翻译得奇奇怪怪的，上下文完全没出现过相关内容）
2.从表的起始端实行删除是一个特殊情况：因为它改变了表的起始端，编程中的疏忽将会造成表的丢失（？可能是表的起始端有什么特殊的数据，但我看了半天，书上没提到过这种特殊数据。）
3.一般的删除：删除的算法要求我们记住被删除元素前面的表元。（？是因为前面的表元中包含了指针吗）
（这三句话真的意义不明。）
不明白也没事，我自己也不是太明白，但书上立刻就给了这三个问题的解决方法:留出一个标志节点——表头（header）
下面这一串里面用了很多函数，看不懂也没事，我等下会再复制一遍。(书上说是例程，但看着应该是和函数差不多的东西。)
链表的类型声明：

#ifndef _List_H//这串真的意义不明，啥呀这是

struct Node;
struct 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( ElemntType 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;
}

第一个函数（例程）：测试一个链表是否为空表：

int IsEmpty( List L )
{
  return L->Next == NULL;//最后一个元素的指针指向NULL
}

第二个函数（例程）：测试当前位置P是否为链表的末尾：

int IsLast( Position P, List L )
{
  return P->Next == NULL;
}

第三个函数（例程）：Find：

Position P;
Find( ElementType X, List L )
{
  Position P;

  P = L->Next;//P赋值为第一个元素
  while( P != NULL && P->Element != X )//当P不处于末尾且没有找到元素X时，P指向下一个元素
    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 );
   }
}

第五个函数（例程）：FindPrevious:找出含有X的表元的前驱元P，实现删除：

Position FindPrevious( ElementType X, List L )
{
  Position P;
  P = L;
  while( P->Next != NULL && P->Next->Element != X )//P不是末尾的元素且P的下一个元素不是X
    P = P->Next;//查找P的下一个元素
  return P;
}

第六个函数（例程）：链表的插入：将要插入的元素与表L和位置P一起传入：

void Insert( ElementType X, List L, Position P )
{
  Position TmpCell;
  TmpCell = malloc( sizeof( struct Node ) );
  if( Tmpcell = NULL )
    FatalError( "Out of space!!!" );

  TmpCell->Element = X;
  TmpCell->Next = P->Next;
  P->Next = TmpCell;
}

现在我们倒回来第一个函数：

#ifndef _List_H

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

List MakeEmpty( List L );//创建空表L
int IsEmpty( List L );//测试链表L是否为空表
int IsLast( Position P, List L );//测试表元P是否为链表的L的末尾元素
Position Find( ElementType X, List L );//在链表L中查找元素X，如果不存在，则返回空
void Delete( ElemntType X, List L);//在链表L中删除元素X
Position FindPrevious( ElementType X, List L );//找出链表L中的元素X的前驱元素并删除
void Insert( ElementType X, List L,Position P);//在链表L的P位置上插入元素X
void DeleteList( List L);//删除链表L
Position Header( List L);//
Position First( List L);
Position Advance( Position P );
ElementType Retrieve( Position P);
#endif 
struct Node
{
  ElementType Element;
  Position Next;
}

关于表的笔记就先记到这里，我第二天看了这本书后发现后面的内容看不懂的地方有很多，我打算仔细啃一遍再整理出来，更重要的原因是，最近我发现自己想做的事情根本没有进展，以前什么都不会的时候，我怀揣着梦想，在没学过代码的情况下改写了插件，建立了自己的服务器，写了剧情，硬着头皮做了很多事情，现在好不容易会一点了，离自己的梦想更近了，以后可以学到更多了，我却什么都不会做了，我不想看到这样的自己，过去的我肯定也不想看到，所以我决定，每天的空闲时间一半安排给读书，一半安排给其他事情。
我会选择计算机也是因为这个，从小时候开始，心中就有一个声音在告诉我，去把自己想的东西创造出来，用音乐，画面，文字的结合，像曾经感动了我的故事一样，去感动他人，把心中的这份感情分享给别人。看书的这段时间，这份渴望愈加强烈，而开发却一点进展都没有，我不禁回想起了以前的自己，那个什么都不会，却从不迷茫的自己，反观现在，如入泥沼，如失双目，或许今天这个决定是错的，但我认为我心中的这份想法就像一盏灯火，让我不再迷茫，坚定地走在让自己变好的路上；同时它也在心中熊熊燃烧，在呐喊着，在诉说着，在提醒着我，还有什么事情没有完成，我不想就这样放弃。
对不起了，未来的我，或许我正走在一条很好很好的路上，但离开了灯火，我将在会无数次的深夜里醒来，哀悼自己的梦想；我将会在无尽的梦境中回忆起，年少时的感动。我回来了，过去的我。