一. 基本概念
数据结构 ---- 用来干啥的？---- 数据与数据之间的关系 以及相关的操作
基本概念：
数据：符号表示
数据元素：有一定意义的数据
数据项：数据元素包含更具体的数据
数据对象：性质相同的数据元素
数据结构：
逻辑结构
集合
线性
树
图
存储结构
顺序
链式
索引 ----索引表 查找—新华字典
散列(哈希)---关键词 哈希函数 --->数据
程序设计 = 数据结构 + 算法
数据（有哪些数据?）
| ----> 数据改如何组织？
| ----> 选择了不同的数据结构 ----> 就会有不同的算法
算法：
算法是解决特定问题求解步骤的描述，
在计算机中表现为 指令的有穷序列，并且每条指令表示一个或多个操作。
算法的特性：
输入
输出
有穷性
确定性
可行性
算法设计的要求：
正确性
可读性
健壮性
时间效率 和 存储效率
排序算法：
时间复杂度
O(n)
O(1)
空间复杂度
插入排序
如何学好数据结构？
1. 数据结构 成
逻辑结构
物理结构
算法
2. 数据结构 抽象
画图
画清楚 关系
3. 指针
指针有问题的 要及时复习
数据结构：
链表 ---- 数组 ---- 特点： 用物理结构的特点，反应了逻辑结构体的特点
物理上相邻反映了逻辑上相邻
链表 ---- 特点： 实现：
插入 删除方便 节点 ----[数据 下一个数据的地址]
查找不方便
扩容 和 缩减方便
链表：
基本概念：
节点 ----[数据|下一个数据的地址]
尾节点 ----指针域一定是NULL
头节点 ----数据域随机，指针域指向有效节点
首节点 ----第一个有效数据节点
有头链表 ---- 方便操作和实现 ----统一算法实现
无头链表
代码实现：
节点：
结构体：
typedef //这个关键字，给已有类型起别名
typedef int size_t; //此时 size_t 成了 int 的别名 typedef int data_t; struct Node { data_t d; //数据域 节点包含的数据 struct Node *pnext; //指针域 指向下一个节点的地址 };二. 算法
1. 创建
2. 插入数据
3. 删除
4. 查找
5. 修改数据
6. 销毁
1. 创建空链表
node_t * create_empty_linklist()
{
//创建头节点
p = malloc(sizeof(node_t));
//头节点指针域 为NULL
p->pnext = NULL;
return 头节点地址
}
typedef int data_t; //此时 size_t 成了 int 的别名 struct Node { data_t d; //数据域 struct Node *pnext; //指针域 }node_t; node_t *create_empty_linklist() { //创建头节点 node_t *p = malloc(sizeof(node_t)); if(p == NULL) { printf("malloc fail"); return NULL; } p->pnext = NULL; return p; }xxx
NULL
头节点
2. 插入数据
从头结点插入
void linklist_insert(node_t *head,data_t data) { //先创建一个新的节点 node_t *pNew = malloc(sizeof(node_t)); if(pNew == NULL) { printf("malloc fail"); } pNew->d = data; pNew->pnext = head->pnext; head->pnext = pNew; return; }3.删除数据
void linklist_delete_key(node_t *head,data_t key) { if(head == NULL) // 空链表检查 { return; } node_t *ret = head; while( ret->pnext->d != key ) { ret = ret->pnext; } node_t *cur = ret->pnext; ret->pnext = cur->pnext; free(cur); }4.查找数据
node_t *linklist_find_key(node_t *head,data_t key) { node_t *p = head; while( p != NULL) { if(key == p->d) { return p; } p = p->pnext; } return NULL; }5.修改数据
node_t *linklist_update_key(node_t *head,data_t old,data_t new) { if(head == NULL) { return; } node_t *p = head; while( head!= NULL) { if(p->d == old) { p->d = new; return p; } p = p->pnext; } }6.销毁
void linklist_destroy(node_t **head) { if(head == NULL || *head == NULL) { return; } // 2. 遍历释放所有节点 node_t *current = *head; node_t *next; while(current != NULL) { next = current->pnext; // 保存下一个节点的地址 free(current); // 释放当前节点 current = next; // 移动到下一个节点 } // 3. 头指针置空 *head = NULL; }三.重点
1.找到链表中间节点
node_t *linklist_find_mid(node_t *head) { if(head == NULL || is_empty(head) == 1) { return NULL; } node_t *p = head; p = head->pnext; data_t len = 0; while( p!=NULL) { len++; p = p->pnext; } while(p != len/2 ) { p = p->pnext; } return p; }//快慢指针 node_t *linklist_find_mid(node_t *head) { if(head == NULL || is_empty(head) == 1) { return NULL; } node_t *pfast = head; node_t *pslow = head; while(pfast != NULL && pslow != NULL) { pfast = pfast->pnext->pnext; //快指针走两步 pslow = pslow->pnext; //慢指针走一步 } return pslow; }2.找到链表的倒数第k个节点？ k=2
//找到倒数第k的节点 //让p1先走k步 //让p1和p2同时往后走 //直到p1走到结尾 //最终p2停的位置就是倒数第k个节点 node_t *linklist_find_end_k(node_t *head,data_t k) { if(head == NULL || is_empty(head) == 1) { return NULL; } node_t *pfirst =head ; node_t *psecond =head ; int i = 0; while(i<k) { pfirst = pfirst->pnext; if(pfirst==NULL) return NULL; i++; } while( pfirst!=NULL ) { pfirst = pfirst->pnext; psecond = psecond->pnext; } return psecond; }3.判断链表是否有环
//双指针 //快指针一次走两步 //慢指针一次走一步 int linklist_has_cycle(node_t *head) { if(head == NULL || is_empty(head) == 1) { return -1; } node_t *pfast = head; node_t *pslow = head; while(pfast != NULL && pfast->pnext != NULL) { pfast = pfast->pnext->pnext; pslow = pslow->pnext; } if(pfast == pslow) { return 1; } return 0; }4.链表的逆序（倒置）
//链表的逆序 void linklist_reverse(node_t *head) { if(head == NULL || is_empty(head) == 1|| head->pnext->pnext == NULL) { return ; } node_t *p = head->pnext; head->pnext = NULL; while(p != NULL) { node_t *current = p; p = p->pnext; current->pnext = head->pnext; head->pnext = current; } linklist_insert_head(p); }5.排序
//选择排序 void linklist_select_sort(node_t *head,data_t d) { if(head == NULL || is_empty(head) == 1|| head->pnext->pnext == NULL) { return ; } node_t *p = head->pnext; node_t *j = p->pnext; while(p->pnext != NULL) { while( j != NULL) { if(j->d < p->d) { data_t temp = j->d; j->d = p->d; j->d = temp; } j = j->pnext; } p = p->pnext; } }//冒泡排序 void bubble_sort(node_t *head) { if(head == NULL || is_empty(head) == 1|| head->pnext->pnext == NULL) { return ; } node_t *p_pos = head->next; node_t *end = NULL; while(next->pnext != end) { node_t *next = head->pnext; while(next != end) { if(next->d > next->pnext->d) { data_t temp = next->d; next->d = next->pnext->d; next->pnext->d = temp; } next = next->pnext; } end = next; } }//插入排序 void insert_sort(node_t *head) { if(head == NULL || is_empty(head) == 1|| head->pnext->pnext == NULL) { return ; } //链表被划分为有序区和无顺序区域 node_t *p_temp = head->pnext->pnext; head->pnext->pnext = NULL; while(p_temp != NULL) { //拿数据 找位置 node_t *next = p_temp; p_temp = p_temp->pnext; node_t *p_insert = head; while(p_insert->pnext != NULL && p_insert->pnext->d < next->d) { p_insert = p_insert->pnext; } next->pnext = p_insert->pnext; p_insert->pnext = next; } }
