链表的学习

算法：
通俗的定义：解题的方法和步骤
狭义的定义：对存储数据的操作（对不同的存储结构，要完成某一个功能所执行的操作是不一样的）
例如：输出数组中的所有元素的操作，和输出链表中的所有的元素的操作是不一样的
这说明算法是依附于存储结构的，不同的存储结构所执行的算法是不同的

    广义的定义：广义的算法也叫泛型，无论数据是如何存储的，对该数据的操作都是一样的
            存储：我们至少可以通过两种结构来存储数据：数组和链表
                    数组：
                            优点：存取速度快
                            缺点：如果数据量过大，需要一块很大的连续的内存；插入删除元素的效率很低
                    链表：
                      优点：插入删除元素效率高；不需要一个连续的很大的内存
                            缺点：查找某个位置的元素效率低

链表：专业术语：
头节点：1.头结点和首节点的数据类型是一模一样的。2.头结点是首节点前面的那个节点。3.头结点并不存放数据。4.设置头结点的目的是为了方便对链表的操作。
头指针：存放头节点地址的指针变量
首节点：存放第一个有效数据的节点
尾节点：存放最后一个有效数据的节点

                    确定一个链表，只需要一个参数：头指针

链表的创建和输出插入删除排序

// 链表1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "malloc.h"
//定义了一个链表节点的数据类型
struct Node
{
       int data;
       struct Node *nextNode;
};

struct Node * CreatList()
{
       int len;
       int value;


       struct Node *p = (struct Node *)malloc(sizeof(struct Node*));
       if (p==NULL)
       {
              printf("内存分配失败");
              return NULL;
       }
       struct Node * lastNode;
       lastNode = p;
       lastNode->nextNode = NULL;

       printf("请输入链表元素的个数:");
       scanf("%d", &len);
       for (int i=0;i<len;i++)
       {
              struct Node *newNode= (struct Node *)malloc(sizeof(struct Node*));
              if (newNode==NULL)
              {
                     printf("子节点分配失败");
                     return NULL;
              }
              printf("请输入第%d个元素的值：",i + 1);
              scanf("%d", &value);
              newNode->data = value;
              newNode->nextNode = NULL;
              lastNode->nextNode = newNode;
              lastNode = newNode;
       }
       return p;
}

void printNodeValue(struct Node *pHead) {
       struct Node *node = pHead->nextNode;
              while (node!=NULL)
              {
                     printf("当前的值是%d\n", node->data);
                     node = node->nextNode;
              }
}

bool isEmpty(struct Node *node) {
       if (node==NULL)
       {
              return true;
       }
       else
       {
              return false;
       }
}

int length_list(struct Node *node) {
       struct Node *anode = node->nextNode;
       int a = 0;
       while (anode != NULL)
       {
              anode = anode->nextNode;
              a++;
       }
       return a;
}

bool insert_list(struct Node *node, int pos, int val) {
       //在node所指向链表的第pos个节点前插入一个新的节点，该新节点的值是val

       //先检测传入的值是否有效
       int i = 0;
       struct Node * p = node;
       while (p!=NULL && i<pos-1 )
       {
              p = p->nextNode;//如果传入的参数都是有效数字，那么该循环完毕，在此处p已经指向pos的前一个位置了
              i++;
       }
       if (i>pos-1 || p==NULL )
       {
              return false;
       }

       //检测完毕过后，如果正常，开始插入
       struct Node * pNewNode = (struct Node *)malloc(sizeof(struct Node));
       if (NULL == pNewNode)
       {
              printf("内存分配失败");
              return false;
       }

       pNewNode->data = val;
       struct Node * q = p->nextNode;
       p->nextNode = pNewNode;
       pNewNode->nextNode = q;
       return true;
}
bool delete_list(struct Node *node, int pos , int * deleteResult) {

       int i = 0;
       struct Node * p = node;
       while (p->nextNode!= NULL && i < pos-1)
       {
              p = p->nextNode;//如果传入的参数都是有效数字，那么该循环完毕，在此处p已经指向pos的前一个位置了
              i++;
       }
       if (i > pos-1 || p->nextNode == NULL)
       {
              return false;
       }

       struct Node *q = p->nextNode;
       *deleteResult = q->data;
       p->nextNode = p->nextNode->nextNode;
       
       q == NULL;

       return true;
}
void sort_list(struct Node *node)
{      
       int i, j, t;
       struct Node *p, *q;
       int len = length_list(node);
       for (i = 0 , p=node->nextNode; i < len - 1; i++,p = p->nextNode)
       {
              for (j =i+1,q = p->nextNode; j < len; j++ , q = q->nextNode)
              {
                     if (p->data > q->data)
                     {
                           t = p->data;
                           p->data = q->data;
                           q->data = t;
                     }
              }
       }
}

int main()
{
       struct Node *pHead;//pHead 用来存放链表头结点的地址
       pHead = CreatList(); //创建链表，返回值是头指针
       printNodeValue(pHead); //打印该链表
       
       if (isEmpty(pHead))
       {
              printf("链表是空的\n");
       }
       else
       {
              printf("链表不为空\n");
              printf("链表长度为%d\n", length_list(pHead));
       }

       sort_list(pHead);
       printf("排序之后的链表是:\n");
       printNodeValue(pHead);


       printf("请输入要插入的节点位数：");
       int pos, val;
       scanf("%d", &pos);
       printf("请输入要插入的数值：");
       scanf("%d", &val);

       insert_list(pHead, pos, val);
       printNodeValue(pHead);


       int a = 0;
       delete_list(pHead, 3, &a);
       printf("删除之后的链表是：\n");
       printNodeValue(pHead);

       getchar();
    return 0;
}