一. 基本概念数据结构 ---- 用来干啥的---- 数据与数据之间的关系 以及相关的操作基本概念数据符号表示数据元素有一定意义的数据数据项数据元素包含更具体的数据数据对象性质相同的数据元素数据结构逻辑结构集合线性树图存储结构顺序链式索引 ----索引表 查找—新华字典散列(哈希)---关键词 哈希函数 ---数据程序设计 数据结构 算法数据有哪些数据?| ---- 数据改如何组织| ---- 选择了不同的数据结构 ---- 就会有不同的算法算法算法是解决特定问题求解步骤的描述在计算机中表现为 指令的有穷序列并且每条指令表示一个或多个操作。算法的特性输入输出有穷性确定性可行性算法设计的要求正确性可读性健壮性时间效率 和 存储效率排序算法时间复杂度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));//头节点指针域 为NULLp-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; }xxxNULL头节点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个节点 k2//找到倒数第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(ik) { pfirst pfirst-pnext; if(pfirstNULL) 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; } }
