数据结构 第4节 链表LinkedList

一、链表的定义

1. n个节点离散分配
2. 彼此之间通过指针相连
3. 每个节点只有一个后续节点
4. 首节点没有前驱节点
5. 尾结点没有后续节点

二、专业术语

首节点 ：第一个有效节点
尾节点 ：最后一个有效节点
头节点 ：无 有效数据，未存有效节点个数，方便操作。
头指针 ：指向头节点的指针变量
尾指针 ：指向尾节点的指针变量

三、头节点存在的意义

没有头节点也可以找到首节点的位置啊！为什么还需要一个不存任何数据的头节点呢？
原因：
方便对链表进行操作。对链表进行增删改查的时候，头节点可以简便对链表的操作。

四、确定一个链表需要几个参数？

头指针： 头节点的 地址
我们可以通过头指针推算出链表的所有其他信息，（元素个数，头节点，首节点，尾节点）

f(struct pHead_node *);

五、链表分类

单链表
双链表：每一个节点有2个指针域，前一个节点 & 后一个节点

循环链表 ： 闭环，能通任何一个节点找到其他所有节点
非循环链表

六、链表的算法

遍历
查找
清空
销毁
排序
删除节点

# 有内存泄露风险，因为你还没有手动释放啊：free(obj)❌
p -> pNext = p -> pNext -> pNext;  

#改写如下
r = p -> pNext;
p -> pNext = p -> pNext -> pNext; 
free(r);

插入节点

1 2 3 p 4 5 
q插入p后面

//方式一：中间变量
temp = p;
q -> pNext = p -> pNext;
p -> pNext = temp;

//方式二：
q -> pNext = p -> pNext;
p -> pNext = q;

算法：

狭义（从内部的底部实现上）的算法是与数据的存储方式密切相关
广义（表面上使用一模一样，内在机制不一样）的算法是与数据的存储方式无关

泛型：

利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的。内部实现不一样，但外部调用都一样。不能叫封装，叫重载。
Java里的泛型不能算是真正的泛型，已经有点不伦不类了。

数组：p , 下一个元素是p++
链表：p，下一个元素
++() { //自定义++函数
  return p -> pNext;
}

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

typedef struct Node {
    int data;               //数据域
    struct Node * pNext;    //指针域
} NODE, * PNODE;

struct Node * createList(void);
void show_ist(PNODE pHead);
bool isEmpty(PNODE pHead);


int length(PNODE pNode);
bool insert(PNODE pNode, int position, int value);
bool delete_node(PNODE pNode, int position, int * value);
void sort(PNODE pHead);

int main(void) {
    PNODE pHead = NULL; //等价于struct Node * pHead = NULL
    pHead = createList();   //创建一个非循环单链表，并将
    show_ist(pHead);
    printf("链表的长度是：%d\n",length(pHead));
    sort(pHead);
    printf("排序后链表内容是：\n");
    show_ist(pHead);

    insert(pHead, 2, 55);
    printf("插入后链表内容是：\n");
    show_ist(pHead);
    
    int i;
    delete_node(pHead, 2, &i);
    printf("删除的元素是：%d,链表变成：\n",i);
    show_ist(pHead);
    return 0;
}

/**
    创建一个非循环单链表，并将该单链表的头节点地址赋给pHead
*/
PNODE createList(void) {
    int len;
    int i;
    int val;

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

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

    for(i = 0; i < len; i++) {
        printf("请输入第%d个节点的值：", i+1);
        scanf("%d",&val);
        PNODE pNew = (PNODE)malloc(sizeof(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 show_ist(PNODE pHead) {

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

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

int length(PNODE pHead) {
    PNODE p = pHead -> pNext;
    int len = 0;
    while(p != NULL) {
        p = p -> pNext;
        len++;
    }
    return len;
}

//数组的排序
/*
void sort(int * a) {
    int i ,j, t;
    int len = length(pNode);


    int temp = 0;
    for(i = 0; i < len-1; i++) {
        for(j = i+1; j < len; j++) {
            if(a[i] > a[j]) {
               t = a[i];
               a[i] = a[j];
               a[j] = t;
            }
        }
    }
}
*/

//链表排序
void sort(PNODE pHead) {
    int i ,j,t;
    PNODE p,q;
    int len = length(pHead);

    for(i = 0,p = pHead->pNext; i < len-1; i++,p = p->pNext) {
        for(j = i+1,q = p->pNext; j < len; j++,q = q -> pNext) {
            if(p->data > q->data) {
               t = p->data;
               p->data = q->data;
               q->data = t;
            }
        }
    }
}

/*不需要判断链表空没空，满没满*/
bool insert(PNODE pNode, int pos, int val) {
    PNODE p = pNode;
    int i = 0;

    //NULL != p是用来定义条件的，i < pos-1是用来定义循环的
    //如果超出了链表长度范围，p=NULL
    while(NULL != p && i < pos-1)
    {
        p = p->pNext;   //p最终变成preNode
        ++i;            //i的最大值最终变成pos-1
    }

    if(i > pos-1 || NULL == p) //如果大于pos-1,证明超范围了，NULL = p 证明pos > 了链表的长度
        return false;

    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew) {
        printf("动态分配内存失败\n");
        exit(-1);
    }

    pNew->data = val;
    PNODE temp = p->pNext;
    p->pNext = pNew;
    pNew->pNext = temp;

    return true;
}

/*删除第5个节点就要先知道第4个节点，且第5个节点不为空
  算法源自insert
*/
bool delete_node(PNODE pHead, int pos, int * pVal) {
    PNODE p = pHead;
    int i = 0;

    //跳出循环时p是第pos-1(i)个节点，且第pos节点（要删除的节点）不为空
    while(NULL != p->pNext && i < pos-1)
    {
        p = p->pNext;   //p最终变成preNode
        ++i;            //i的最大值最终变成pos-1
    }

    if(i > pos-1 || NULL == p->pNext) //如果大于pos-1,证明超范围了，NULL = p 证明pos > 了链表的长度
        return false;

    PNODE q = p->pNext;  //待删除的节点
    *pVal = q->data;     //保存被删除的节点的数值

    p->pNext = p->pNext->pNext; //删除p节点后面的节点
    free(q);             //释放空间
    q = NULL;

    return true;
}

如何学习算法的一些感想

回文数：
1221
素数
。。。。。。

算法你搞不懂很正常，大部分人都想不出。果你看了后决定搞不定就不要再搞了，也不要觉得备受打击，大家都搞不定。重点是把答案看懂。

第一步：流程
第二步：每个语句的功能
第三步：试数

复习

• 数据结构：

  • 狭义
    是专门研究数据存储的问题
    数据存储包含2个方面：个体的存储 ➕ 个体关系的存储
  • 广义
    数据结构既包括数据存储，也包括对数据的操作
    对数据 的操作就是算法

• 算法：
  对存储数据 的 操作算法都是针对存储方式而言的，存储方式不一样，算法的实现就不一样。

  • 狭义
    算法和数据的存储方式密切相关
  • 广义
    算法和数据的存储方式无关
    这就是泛型思想