基本概念数据结构存储一种或者多种特定关系的数据集合如何组织和存储程序设计数据结构算法数据与数据之间的关系逻辑结构数据元素与元素之间的关系集合数据元素与元素之间关系平等线性结构数据元素与元素支架确定一对一的关系顺序表数组链表队列栈树形结构元素与元素之间具有一对多的关系二叉数图形结构数据元素与元素之间多对多的关系A向上向下都可以检索到很多的数据元素物理结构顺序存储结构1.一个连着一个存储有连续性与顺序表数组时间复杂度为o12. 预算数据插入或者删除需要把删除位置后面的元素向前提一个地址3.访问元素效率高4.需要预分配空间可能造成空间浪费或者数组越界链式存储方式可以选取非连续的空间进行存储1.内存空间可以不连续2.插入和删除只需要 将上一个元素跟的指针指向插入元素的首地址比比较方便3.访问元素需要进行遍历4.不需要预分配内存空间可以根据数据动态储存散列存储哈希存储将要储存的元素用函数映射在内存上索引存储将要储存元关键字和储存诶之构建索引表数据的索引需要通过查表查找真正的数据地址单项链表API应用程序接口1. 创建链表2. 链表插入(头插、尾插)3. 链表删除头删、尾删4. 查找5. 修改6. 链表遍历7. 链表销毁在一下我会用图文的形式演示如何构造单列表其中我们可以把头节点也就是操作主链设置为一个结构体link_h * plink 那么plink就是头节点的首地址 其中存有 plink首地址 和 clean 链表的长度链表数据类型构造//链表结点类型 typedef struct node { int data; //数据域保存的数据 struct node *pnext; //指针域下一个结点的地址 }Node_t; //链表对象类型 typedef struct link { Node_t *phead; //链表头节点指针 int clen; //链表当前结点的个数 }Link_t;单向链表的创建当我们在创建的时候需要为头结点进行开辟堆上的空间进行储存然而在我们开辟node节点的时候也需要我们开辟一个malloc的储存空间去进行增加节点 并且头文件中需要增加#include《stdlib.h》单向链表尾插 Link_t *create_link() { Link_t *plink malloc(sizeof(Link_t)); if (NULL plink) { printf(malloc error\n); return NULL; } plink-phead NULL; plink-clen 0; return plink; }单向链表头插int insert_link_head(Link_t *plink, int data) { Node_t *pinsert malloc(sizeof(Node_t)); if (NULL pinsert) { printf(malloc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; pinsert-pnext plink-phead; plink-phead pinsert; plink-clen; return 0;extern }单向链表尾插int insert_link_tail(Link_t *plink, int data) { Node_t *pinsert malloc(sizeof(Node_t)); if (NULL pinsert) { printf(mallocc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; if (is_empty_link(plink)) { plink-phead pinsert; } else { Node_t *ptmp plink-phead; while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } ptmp-pnext pinsert; } plink-clen; return 0; }单向链表尾删int delete_link_tail(Link_t *plink) { if (is_empty_link(plink)) { return -1; } else if (NULL plink-phead) { free(plink-phead); plink-phead NULL; } else { Node_t *ptmp plink-phead; while (ptmp-pnext-pnext ! NULL) { ptmp ptmp-pnext; } free(ptmp-pnext); ptmp-pnext NULL; } plink-clen--; return 0; }内存泄露谨防就是要用户自己申请的堆区空间使用完没有及时释放则造成内存泄露。检测程序有没有内存泄露valgrind内存错误检测工具GNU提供可以检测程序运行过程中的内存泄露情况以及野指针的使用情况等。使用方法 在linux命令行进行输入valgrind a.out进行检测安装valgrind工具sudo apt-get isntall valgrind 编译完程序后使用 valgrind ./a.out valgrind --leak-checkfull ./a.out 6742 HEAP SUMMARY: 6742 in use at exit: 112 bytes in 7 blocks 6742 total heap usage: 10 allocs, 3 frees, 1,168 bytes allocated 6742 6742 LEAK SUMMARY: 6742 definitely lost: 16 bytes in 1 blocks 6742 indirectly lost: 96 bytes in 6 blocks 6742 possibly lost: 0 bytes in 0 blocks 6742 still reachable: 0 bytes in 0 blocks 6742 suppressed: 0 bytes in 0 blocks 6742 Rerun with --leak-checkfull to see details of leaked memory
