链结构

#include<stdio.h>

/*
数据结构：
    在大一上学期，我们学过了C语言程序设计，可以说，所有C语言的语法规则都讲清楚了，如果学好了，给你一段C语言的
代码，至少可以看懂了。而下学期要学的，很重要的一门课：数据结构，则是在C语言的基础上，灵活应用，来实现一些功能
或者使得代码更加简洁。
    数据结构最主要的框架就是C程序设计中的结构体，我们来讲解一下结构体，结构体就是通过将不同的变量封装在一起，
用来描述一个特定的事物，目的是使得代码更加条理清楚，比如，我们要描述一个空间中的点，我们可以用，x、y、z来表示
三维坐标，那么，使用时，我们要定义int x,y,z;如果是数组，我们还需要int x[10],y[10],z[10]，然后使用时一一对应，
x[1]、y[1]、z[1]描述的是第一个点的三维坐标，这样子，代码就会显得很零散，如果这个事物的属性更多时，我们便难以判
断使用，所以，我们可以采用结构体来定义，比如三维空间的点可以定义成：
    typedef struct point  //typedef 起到的是重新给point这个结构体起名字的作用。
    {
      int x,y,z;          //将x、y、z封装在一起，共同来描述点这个事物
    }Point;               //这样子我们便可以用Point a; 来申请一个点所需的空间，用起来更加的方便。
    而数据结构里就讲解了一些前人定义好的，一些常见的结构体，通过这些结构体，我们可以更加方便地编程。


链结构：
    定义：数据存储或逻辑上是链式的
    基本实现方式：数组和链表

==============================================================================================================
    数组：
        数组大家都接触得比较多，就不细讲了，不过在结构化中，我们可以将数组的大小和数组封装在一起，如下：
        typedef struct
        {
          int data[1000];
          int num;
        }Node;
        这样子，我们便可以用Node a;定义一个数组，并且a.num是这个数组中存放数的数量。
==============================================================================================================
    链表：
    我们可以通过指针或者数组下标将一些元素链接在一起，和数组相似又不完全一样。
    一. 指针链接的链表：
    指针初步了解：
    我们先来了解一下指针，比如说int *a; 我定义了一个指向整型数据的指针变量a，我们可以用这个指针指向另外一个整型
变量，比如说int b=3; a=&b;我们把b的地址给a，然后我们便可以通过a来访问b所在的空间来查看或修改b这个变量空间里面的
内容，比如说printf("%d
",*a);我们可以输出b空间里的内容，比如*a=4;我们修改b这个变量的值为4;
    基本上，指针有两种用法，一个比较简单，就像是前面那样，我们将这个指针指向某一个已经定义好的变量来访问这个变
量，或者，我们为这个指针申请一个空间，a=(int *)malloc(sizeof(int)); 这段代码就叫做动态申请，我们通过这段代码手
动地向系统申请到了一个整型数据大小的空间，现在，这个指针就是通往这个空间的梯子，通过这个指针我们可以访问到这个
空间，当然，如果我们现在将指针a指向b，也是可以的，但你申请到的这个空间就再也找不到了，因为你把梯子给撤掉了，这
个空间又没有别的标记，自然就再也找不到了，这就是所谓的内存泄漏，我们写程序的时候要避免出现这种情况。
    链表实现：
    指针的用途基本看到了，我们现在用指针来链接几个元素，来构建一个链表。
    我们可以封装一个结构体如下：
    typedef struct node
    {
      int data; //这个链表所存放的元素，这里用int来定义，也可以是自己定义的其他结构体。
      struct node *next; //这是一个struct node类型的指针，用来指向下一个这种类型的变量
    }Node;
    现在我们先定义两个变量：Node a,b;
    接下来，我们赋值：a.data=1; b.data=2; 然后要将这两个变量链接在一起：
    a.next=&b; //将b的地址赋值给a的next属性，这样，a.next就指向了b，自然，a、b就连在一起了，如果b的后面没有别的
元素，我们可以让b的next指向NULL，表明b是这个链表的最后一个元素：b.next=NULL;
    这样子，一个最基本的链表就构建完成了，表头是a，表尾是b，甚至，我们接下来都用不到b这个变量名了，a.next就表示
b。不管链表的元素有多少，我们都可以用表头来表示任意一个元素，差别只不过是.next的数量而已，比如有五个元素，那么
a.next->next->next->next就代表着第五个元素。当然，实际应用的时候，肯定不是这样用的。
    我们平时写链表的时候都是动态申请空间的，也就是说链表里面的每一个元素都是通过malloc来获取空间的，如下：
    Node *CreatNode()   //写一个单独函数来重复调用，每一次调用获得一个Node变量大小的空间
    {
      Node *s;
      s=(Node *)malloc(sizeof(Node));
      s->next=NULL;     //如果后面不接东西的话，必须置为NULL，这样遍历链表的时候遇到NULL就表示链表结束
      return s;         //创建完这个空间，要将这个空间的地址返回回去
    }
    接下来，要创建链表，我们可以先调用一次CreatNode来获取表头。
    Node *p; //我们设立的表头p
    p=CreatNode();  //一般链表有两种模式：有表头和无表头，有表头的意思就是在正式数据前多弄一个空的变量，这样做
                    //的好处，用过就知道！
    比如现在我们不断添加元素，从键盘读取整数，遇到-9999时链表创建结束，如下：
    while(1)
    {
      scanf("%d",&x);        //输入
      if(x==-9999) break;    //如果是-9999就退出循环
      Node *s;
      s=CreatNode();         //定义了一个指针，用过不指向一个可用的空间的话，被称作是野指针，直接用程序会崩的
      s->data=x;             //赋值
      s->next=p->next;       //这种插入方式叫做头插法，也就是说每创建一个变量就插在表头的后面
      p->next=s;             //将表头的next指针指向s，那么p->next就等于s，这就是将这些元素链接在一起的链。
    }
    这样子，链表就创建完毕。那么如何通过一个表头来遍历整个链表呢。如下：
    比如我要输出这个链表：
    void Dis(Node *p) //将你要输出的链表的表头当作参数传递给函数
    {
      p=p->next;      //表头是空的
      while(p)        //当p不是NULL的时候，说明p->data是有值得，当等于NULL的时候，就是链表的结尾了
      {
        printf("-> %d ",p->data); //输出
        p=p->next;                //p移动到他链接的下一个变量上。
      }
      printf("
");
      //指针和函数参数深入：
      //不知道大家会不会疑惑，我没有新生成一个指针来遍历数组，直接用表头来遍历，会不会出现遍历一遍，链表就找不
      //到了，因为老师肯定讲过swap(int *a,int *b)的例子，当传递的是指针进来的时候，好像可以实现a、b的互换，为
      //什么这里可以直接用表头遍历呢。其实和函数的形参一个道理，函数在接收外面传进来的参数的时候，其实是自己重
      //新弄了一个变量来接收，所以才会出现函数内部a、b交换了而外部不变的现象，用指针之所以可以交换是因为，虽然
      //指针也是新创的，但由于值一样，所以指向的空间一样，通过地址来改变里面的元素，所以可以实现交换，但是如果
      //函数内部是直接改变指针的值，也就是指针指向的地址的话，他改变的只是函数内部的这个变量值，外面的实参是不
      //会有变化的。
    }
    遍历链表的方法很重要，很多操作都是通过这个方法来实现的。
    比如说，我要所有data值为5的结点，如下：
    void Del(Node *p,int x) //表头和删除的值传进来
    {
      Node *q;              //重新弄一个指针来遍历链表
      q=p->next;            //表头里面是不存值的
      while(q)              //当q不为空，也就是链表还没结束的时候
      {
        if(q->data==x)      //如果q指向的结点的data值等于x，那么就要删除它
        {
          p->next=q->next;  //p一直是q的前一项，现在删除q就是将p的next指针指向q的下一项，自然就跳过了q
          free(q);          //因为空间是我们动态申请的，现在也要手动收回，不然会内存泄漏
          q=p->next;        //q重新指向p的下一项
        }
        else
        {
          p=p->next;        //如果不等于x，p就跳一格，q也跳一格，始终保持q在p的下一项
          q=q->next;
        }
      }
    }
    插入与删除类似。
    值得注意的是：严谨的代码中，动态申请到的空间，必须在不用时释放掉，不然会造成内存泄漏，如下：
    void Des(Node *p)    //递归程序
    {
      if(p)              //如果还没到达链表尾部，那么就要先释放掉该结点后面的结点，再释放本结点
      {
        Des(p->next);
        free(p);
      }
    }
    以上就是用指针链接的链表，建议大家都自己手写一份，实现插入、删除等操作。。。
    现在大家有没有发现数组和链表的优缺点，明明数组更加简便，为什么要创造链表这种东西呢？
    实际上，对于插入、删除操作来说，链表比起数组是有巨大优势的，数组想要插入一个数，插入以后还得移动n个数来维持
顺序，但对于链表，你只需要找到这个数的位置，然后修改上一个结点的指针指向就可以了。不需要移动大量的数据，如果这
个表非常长的话，那么优势是巨大的。当然，如果你想知道某一个位置的数的话，那么数组可以直接输出，链表却需要O（n）
的时间，因此，数组和链表是各有优缺点的。
    二. 数组下标链接的链表：
    比如我们有一串数3 4 7
    那么我们可以构成一个数组表
    地址下标  存放的数   下一个数存放的位置，如果为-1就代表这个数就是表尾
    0        | 3        | 1
    1        | 4        | 2
    2        | 7        | -1
    我们可以用一个二维数组来实现这个功能，比如：a[100][2]; 总共有100个空间，a[i][0]代表存放的数、a[i][1]代表下
一个数存在的位置，这样子，我们便构建了一个链表，只不过这个链表不是由指针链接，而是由下标链接在一起的。那么，他
和前面讲的链表一样，实现方法也差不多，你们可以自己手写一份。
    链表的用法多种多样，而且可以根据实际用途来自己决定他的结构，比如我们可以将最后一个结点的next指针指向第一个
结点，形成循环链表，比如我们可以在每个结点内多包含一个struct node *pre; 用来指向上一个结点，称作双向链表。还可
结合到栈和队列中去用，总之，只要能实现目标，一起都好说。。。。

注：
    我们来看一下有表头的链表和没有表头的链表的差别：（指针实现）
    如果有表头，删除第一个结点的时候，直接将表头的next指向第二个结点就可以了，如果没有表头，你的头指针指向了第
二个结点，但你必须将这个头指针返回回去，或者通过双重指针来实现，不然就会出错，原因和上面的形参实参关系一样。
*/