day 18——————数据结构单向链表

数据结构

要点

1总结：

常用的逻辑关系和物理结构
逻辑关系指的是数据之间的关系
1.集合
2，线性结构：一对一（数组，链表，栈等）
3.树形结构：一对多（二叉树）
4，图形，多对多
物理结构：
顺序结构（数组），内存空间连续
链式结构（链表），不连续
散列结构（哈希存储）：将储存位置与关键码之间确立对应关系进行查找的储存方式
索引：通过索引表

顺序存储结构和链式存储结构的区别，什么场景使用
顺序结构：

          1. 访问数据方便（O(1)--时间复杂度）2. 数据插入和删除需要移动大量数据3. 需要预分配内存空间4. 可能会造成内碎片

链式结构：在内存中选取一段非连续的内存空间（链表）

             1. 访问元素必须通过遍历（O（n））2. 插入和删除数据方便3. 不需要预分配内存空间（动态的存储结构）

单向链表基础操作（见下）
内存碎片
内部碎片：内部碎片是指分配给程序的内存块比实际需要的内存稍大，导致部分内存未被使用（数组）
外部碎片：内存中有足够的总空闲空间，但由于这些空闲空间是不连续的，无法满足一次大的内存分配请求。
内存泄露
是指程序在动态分配内存后，未能正确释放这些内存，导致内存无法被重新利用。最终有可能崩溃。
7.指针函数：返回值是指针的函数，这个返回值不能是局部变量（会悬空指针）
可以返回全局变量，静态变量，从堆申请的的地址。

2 单项链表基础操作

单向链表的创建，遍历，头尾添加删除``

#include"link.h"
#include<stdio.h>
#include<stdlib.h>/************************ 功能：创建有头单向链表*返回值：*  成功：返回头节点地址*  失败：返回NULL*  ******************/link_node * creat_link()
{link_node *phead = malloc(sizeof(link_node));if(NULL == phead)//检查是否开出内存{printf("fail malloc\n");return NULL;}else{phead->pnext = NULL;return phead;}
}/************************功能：头插*返回值：成功0；失败-1；*参数：phead(头节点地址)data（插入的值）**********************/int insert_head_link(link_node *phead,data_type data)
{link_node *pinsert = malloc(sizeof(link_node));if(NULL == pinsert ){printf("fail malloc\n");return -1;}pinsert->data = data;pinsert->pnext = phead->pnext;phead->pnext = pinsert;return 0;
}/************************功能：遍历*参数：phead(头节点地址)**********************/
void link_for_each(link_node *phead)
{link_node *p =phead->pnext;while(p != NULL){printf("%d\n",p->data);p = p->pnext;}
}/****************** 功能；判断是否是空链表* 返回值*      是：1 ；否 0；*  参数：头节点地址*  ******************/int is_empty_link(link_node *phead)
{if(NULL == phead->pnext){return 1;}elsereturn 0;
}/************************功能：尾插*返回值：成功0；失败-1；*参数：phead(头节点地址)data（插入的值）**********************/int insert_tail_link(link_node *phead,data_type data)
{link_node *pinsert = malloc(sizeof(link_node));if(NULL == pinsert){printf("fail malloc");return -1;}pinsert->data = data;pinsert->pnext = NULL;link_node *p = phead;while(NULL != p->pnext){p = p->pnext;}p->pnext = pinsert;return 0;
}/************************功能：头删*返回值：成功0；*参数：phead(头节点地址)**********************/int delete_head_link(link_node *phead)
{if(is_empty_link(phead)){return 0;}link_node *pdel = phead->pnext;phead->pnext = pdel->pnext;free(pdel);return 0;
}/************************功能：尾删*返回值：成功0；*参数：phead(头节点地址)**********************/int delete_tail_link(link_node *phead)
{if(is_empty_link(phead)){return 0;}link_node *p=phead;while(NULL != p->pnext->pnext){    p = p->pnext;  }    p->pnext = NULL;free(p->pnext);}

2.注意快速排序如果基准值定第一个要先从右向左找

void swap(int *a, int *b)
{int temp = *a;*a = *b;*b = temp;
}int quick_sort(int *begin, int *end)
{if (begin >= end){return 0;}int *p = begin;int *q = end;int *c = begin;//基准while(begin < end){while(begin < end && *end >= *c){--end;}while(begin < end && *begin<=*c){++begin;}swap(begin ,end);}swap(c,begin);quick_sort(p,begin-1);quick_sort(begin+1,q);return 0;
}int main()
{int  c[12] = {23,56,341,453,31,12,454,1235,1,2342,3};quick_sort(c,c+11);int i;for(i=0;i<12;i++){printf("%d\n",c[i]);}return 0;
}