数据结构(1)

数据结构前导篇1.什么是数据结构一组用来保存一种或多种特定关系的数据集合组织和存储数据。程序设计 数据结构 算法2. 数据与数据之间的关系2.1逻辑结构数据元素与元素之间的关系集合平等关系线性结构元素与元素之间一对一的关系(顺序表链表队列、栈)树形结构元素与元素之间一对多的关系(二叉树)图形结构元素与元素之间多对多的关系(图)2.2物理结构 数据元素在计算机内存中的存储方式2.2.1 顺序结构选用一段连续的内存空间数组1. 数据访问方便通过角标直接访问O12. 元素插入和删除需要移动大量数据效率低3. 预分配内存空间2.2.2 链式结构选用非连续的内存空间链表1. 数据访问需要遍历On2. 插入和删除元素方便3. 不需要预分配可以动态存储需要的时候申请空间 malloc4. 可以有效利用内存碎片2.1.3 内存碎片一些游离的小的内存空间2.1.4 散列结构哈希结构将要存储的数据的关键字和存储位置之间构建映射关系哈希函数存储和查找都根据映射关系查找。2.1.5索引存储通关索引表寻找数据的存储位置。为了提高数据的查找效率。3.知识储备1. 指针2. 动态内存分配3. 结构体4. 指针函数设计思想封装----》模块化------》高内聚一个功能模块只做一件事低耦合模块与模块之间的关联度低增强复用性。4. 学习内容1. 顺序表数组2. 链表单向链表双向链表循环链表内核链表3. 队列4. 栈5. 二叉树6. 排序和查找算法链表1.单向链表节点1.头节点地址 ( phead )2. 当前结点个数 (clen)3. ......1.1. 创建链表//创建一个头结点 Link_t *create_link() { Link_t *plink malloc(sizeof(Link_t));//申请堆空间 //判断空间是否申请成功为空返回 值-1并输出“malloc error” if (NULL plink) { printf(malloc error\n); return NULL; } plink-phead NULL; plink-clen 0; return plink; }1.2. 插入数据头插、判空、尾插1.2.1. 头插//头插 int insert_link_head(Link_t *plink, Datatype_t data) { Node_t *pnode malloc(sizeof(Node_t));//申请堆空间 //判断空间是否申请成功为空返回 值-1并输出“malloc error” if (NULL pnode) { printf(malloc error\n); return -1; } pnode-data data; pnode-pnext NULL; //交换的顺序不能变不然会导致原本第一个节点的指针丢失 pnode-pnext plink-phead;//先将要加入的节点的pnext指针指向原本第一个节点的指针即指向plink-phead plink-phead pnode;//再将链表头指针指向要插入节点的指针即指向pnode plink-clen; return 0; }1.2.2. 判空//判断链表是否为空是则返回 值1不是则返回 值0 int is_empty_link(Link_t *plink) { if (NULL plink-phead) { return 1; } return 0; }1.2.3. 尾插//查找尾结点p plink-phead;while (p-pnext ! NULL){p p-pnext;}//尾插 int insert_link_wei(Link_t *plink, Datatype_t data) { Node_t *pnode malloc(sizeof(Node_t));//申请堆空间 Node_t *p NULL; //判断空间是否申请成功为空返回 值-1并输出“malloc error” if (NULL pnode) { printf(malloc error\n); return -1; } pnode-data data; pnode-pnext NULL; //判断链表是否为空 if (is_empty_link(plink)) { plink-phead pnode; } else { p plink-phead; while (p-pnext ! NULL) //查找尾结点 { p p-pnext; } p-pnext pnode; } plink-clen; return 0; }3.遍历输出//遍历结点p plink-phead;while (p ! NULL){p p-pnext;}//遍历输出 int show_link(Link_t *plink) { Node_t *ptmp NULL; ptmp plink-phead; int i 0; //while里的条件要注意满足条件才执行 while (NULL ! ptmp) { printf(no%d is %d\n, i, ptmp-data); ptmp ptmp-pnext; i; } printf(\n); return 0; }4. 删除数据头删、尾删1.4.1. 头删//头删 int delete_link_head(Link_t *plink) { if (is_empty_link(plink)) { return 0; } Node_t *pfree plink-phead; plink-phead pfree-pnext; free(pfree); plink-clen--; return 0; }1.4.2. 尾删//查找倒数第二个结点p plink-phead;while (p-pnext-pnext ! NULL){p p-pnext;}//尾删 int delete_link_wei(Link_t *plink) { Node_t *p NULL; if (is_empty_link(plink)) { return 0; } else if (1 plink-clen) { delete_link_head(plink); } else { p plink-phead; //遍历链节点 while (p-pnext-pnext ! NULL) //查找倒数第二个结点 { p p-pnext; } free(p-pnext);//释放空间 p-pnext NULL;//指针指向空NULL避免成为野指针 plink-clen--; } return 0; }5.释放链表//释放申请的堆区域内存空间 void destory_link(Link_t *plink) { while (!is_empty_link(plink)) { delete_link_head(plink); } free(plink); }. 查找. 修改valgrind GNU提供的一个内存错误检查软件1.简介valgrind 是GNU提供的一个内存错误检查软件检测是否有内存泄漏在程序运行过程中检查内存错误。2.安装方法Linux联网后在终端输入如下命令sudo apt-get install valgrind3. 使用方法valgrind ./可执行程序valgrind ./a.outlinuxubuntu:~/2026/5.22$ valgrind ./a.out43550 Memcheck, a memory error detector43550 Copyright (C) 2002-2017, and GNU GPLd, by Julian Seward et al.43550 Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info43550 Command: ./a.out43550no0 is 10no1 is 3no2 is 2no3 is 1no4 is 12no0 is 3no1 is 2no2 is 12, 0x522f0e01, 0x522f090no0 is 3no1 is 2no2 is 1no0 is 3no1 is 8no2 is 7clen is 30x522f0907, 0x522f0908, 0x522f0e04355043550 HEAP SUMMARY:43550 in use at exit: 0 bytes in 0 blocks43550 total heap usage: 7 allocs, 7 frees, 1,120 bytes allocated4355043550 All heap blocks were freed -- no leaks are possible4355043550 For counts of detected and suppressed errors, rerun with: -v43550 ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)