C语言 第12节 链表

链表是C语言最后一章，是和数据结构的过渡。不学数据结构是没有存储的概念的。

算法：

• 通俗定义：解题的方法和步骤

• 狭义定义：对存储数据的操作
  对不同的存储结构，要完成某一功能所要执行的操作不一样。
  比如：

  • 输出数组中所有元素的操作
  • 输出链表中所有元素的操作
    这说明算法是依附于存储结构的，不同的存储结构所执行的算法是不一样的。

• 广义定义：广义的算法也叫泛型：无论数据如果存储，对该数据的操作都是一样的。

int a[] = {1, 2, 3, ......};
int * pH = a;
for( int i = 0; i < 10; i++) {
  printf("%d\n", *pH);
  pH++; //这个数组可以用，但是链表不能用
}

数组
优点：存取速度快
缺点：需要一个连续的很大的内存空间，插入和删除元素效率低
a[3] = * (a + 3)

专业术语：

1. 头结点
   头结点的数据类型和首节点的数据类型一模一样
   头结点是首节点前面的节点
   头结点并不存放有效数据
   设置头结点的目的是方便链表的操作

2. 头指针

3. 首节点
   存放第一个有效数据的节点

4. 尾节点
   存放最后一个有效数据的节点
   尾节点的指针域是null

5. 有头指针 就能找到头节点，然后找到首节点，尾节点。

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

struct Node {
    int data;               //数据域
    struct Node * pNext;    //指针域
};

struct Node * createList(void);
void traverse_list(struct Node * pHead);
bool isEmpty(struct Node * pHead);

int main(void) {
    struct Node * pHead; //等价于struct Node * pHead = NULL
    pHead = createList();   //创建一个非循环单链表，并将
    traverse_list(pHead);
    return 0;
}

struct Node * createList(void) {
    int len;
    int i;
    int val;

    //分配了一个不存放有效数据的头节点
    //造头节点的目的是为了方便链表的操作
    //头结点的指针域非空，证明链表有数据
    struct Node * pHead = (struct Node *)malloc(sizeof(struct Node));
    if(NULL == pHead) {
        printf("分配失败，程序终止\n");
        exit(-1);
    }

    struct Node * pTail = pHead;
    pTail->pNext = NULL;
    printf("请输入您要生成的链表节点的个数：");
    scanf("%d", &len);

    for(i = 0; i < len; i++) {
        printf("请输入第%d个节点的值：", i+1);
        scanf("%d",&val);
        struct Node * pNew = (struct Node *)malloc(sizeof(struct Node));
        if(NULL == pNew) {
           printf("分配失败，程序终止\n");
           exit(-1);
        }

        pNew->data = val;
        pTail->pNext = pNew;
        pNew->pNext=NULL;
        pTail = pNew;
    }
    return pHead;
}

/**
数组为什么可以写下标？
a[i] = *(a + i) a是数组第一个元素的地址，连续的，再?i就是第i个元素的地址，
再扩起来加个星号，就是其值
而链表是不连续的，所以不能用下标
*/
void traverse_list(struct Node * pHead) {

    Node * p = pHead->pNext; //初始为首个元素
    if(isEmpty(pHead))  {
        printf("链表为空");
    } else{
         while(p != NULL) {
             printf("%d ",p->data);
             p = p->pNext;
         }
        printf("\n");
    }
    return;
}

bool isEmpty(struct Node * pHead) {
    if(NULL == pHead || pHead->pNext == NULL) {
       return true;
    } else {
        return false;
    }
}