数据结构 第4节 链表LinkedList
2019-07-18 本文已影响2人
小超_8b2f
一、链表的定义
- n个节点离散分配
- 彼此之间通过指针相连
- 每个节点只有一个后续节点
- 首节点没有前驱节点
- 尾结点没有后续节点
二、专业术语
首节点 ：第一个有效节点
尾节点 ：最后一个有效节点
头节点 ：无 有效数据，未存有效节点个数，方便操作。
头指针 ：指向头节点的指针变量
尾指针 ：指向尾节点的指针变量
三、头节点存在的意义
没有头节点也可以找到首节点的位置啊！为什么还需要一个不存任何数据的头节点呢？
原因：
方便对链表进行操作。对链表进行增删改查的时候，头节点可以简便对链表的操作。
四、确定一个链表需要几个参数？
头指针： 头节点的 地址
我们可以通过头指针推算出链表的所有其他信息，（元素个数，头节点，首节点，尾节点）
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个方面：个体的存储 ➕ 个体关系的存储 - 广义
数据结构既包括数据存储，也包括对数据的操作
对数据 的操作就是算法
- 狭义
-
算法：
对存储数据 的 操作算法都是针对存储方式而言的，存储方式不一样，算法的实现就不一样。- 狭义
算法和数据的存储方式密切相关 - 广义
算法和数据的存储方式无关
这就是泛型思想
- 狭义
