day 18 数据结构
一、数据结构基础概念
程序=数据结构+算法。
数据结构：数据的结构数据 = 元素之间的关系 = 数据的组织方式。
算法 = 数据元素之间的相互作用的操作(运算）。
1.数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别并输入给计算机处理的符号集合。
2.数据对象：性质相同的数据元素的集合。
3.数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
4.数据项是数据不可分割的最小单位。
数据结构研究的是数据元素之间的关系。
二、数据结构分为逻辑结构和物理结构。
逻辑关系：逻辑上存在一种联系；物理结构(关系）：存储到计算机中的结构。
逻辑结构：数据元素之间无关联的集合。
线性结构（特点：除了第一个元素和最后一个元素之外其余元素素都只有一个前驱和后继）；
树：目录层次结构一对多关系；
图：地图地点---图的结构多对多关系。
物理结构：指存储方式，如顺序存储（数组）和链式存储（指针）。
计算机本身的存储结构-------线性。
计算机的线性存储空间中表示不同的逻辑机构。
存储结构：
顺序结构：用一片连续的内存空间存放数据。对应到c语言数组 (单一性，有序性，连续性）----- 数据结构-------顺序表。
特点：访问数据方便 O(1)，插入删除不方便O(n)。
链式结构：通过指针指向下一个元素。也可以用来表示一种线性关系彼此联系起来 eg:铁链
特点：访问数据需要遍历O(n)，插入删除方便O(1)。
索引结构：找---【索引表(有序)】-----数据 eg：查字典，书目录。
散列（哈希）结构：找（key）------【散列结构(无序)】------计算在哪里。
算法5个基本特性：输入，输出，有穷性，确定性和可行性。
设计算法：正确性，健壮性，可读性，时间和空间效率。
算法效率的度量：
时间复杂度（更重要）：时间复杂度用于衡量算法执行时间随输入规模增长的变化趋势。常见的表示方法为大O符号（O），描述最坏情况下算法的增长上限。（最好，最坏，平均）
空间复杂度：空间复杂度用于衡量算法在运行过程中临时占用存储空间的大小随输入规模增长的变化趋势。同样使用大O符号表示。
非原地插入排序O(n)；原地插入排序O(1);
三、学习数据结构
线性表：顺序表---以顺序结构存储的线性表（数组）；链表----以链式结构存储的线性表。
链表：
1.数据元素-----节点{数据---数据域 联系-----指针域}
头节点------数据部分不关心-----只是为了方便操作链表，链表---都是有头链表
尾节点的指针域为空NULL；
2.代码的实现：创建（增删改查），销毁。
链表：1.创建空列表2.销毁链表3.增数据--插入4.删数据---删除；5.查数据---找值；6.改数据----改值
//结构体
struct node
{
int data；//要处理的数据是int类型的数据
struct node*pnext：//指向下一个节点
}数据插入到链表：
1.头插法
step1.创建了一个新节点并且给值
step2.新节点指向原先首节点
p_new->pnextt=phead->pnext
step3.将头节点指向新节点
phead->pnextt=p_new;
#include
#include
typedef int date_t;
typedef struct node
{
date_t date;
struct node *pnext;
}node_t;
node_t *create_linklist(void)
{
node_t *head = malloc(sizeof(node_t));//在堆上开空间不用传参不会自动销毁
if(head == NULL)
{
printf("malloc fail");
return NULL;
}
head->pnext = NULL;//头节点指针域为空
return head;
}
void linklist_insert_head(node_t *phead,date_t date) //插入一个新的节点
{
node_t *p_new = malloc(sizeof(node_t)); //创建新节点
if(head == NULL) //开空间可能失败
{
printf("malloc fail");
return NULL;
}
p_new->date = date; //传入数据
p_new->pnext = NULL; //指针域给空（可写可不写）
//连接链表
p_new->pnext = phead->pnext; //插入，指向头节点所指的指针域
phead->pnext = p_new; //头节点指向新节点
}
int is_empty(node_t *phead) //判断链表是否为空
{
return phead->pnext == NULL;
}
int length(node_t *phead)
{
if(is_empty(phead) == 1)
{
return 0;
}
int i = 0;
node_t *p = phead->pnext;
while(p!=NULL)
{
i++;
p = p->pnext;
}
return i；
}
void linklist_print(node_t *phead) //打印链表
{
if(is_empty(phead) == 1)
{
printf("empty linklist
");
return;
}
node_t *p = phead->pnext; //头节点之后的节点指针域
while(p!=NULL)
{
printf("%d ",p->date); //打印数据域
p = p->pnext; //指向链表下一个指针域
}
putchar('
');
}
int main()
{
node_t *phead = create_linklist();
linklist_insert_head(phead,4);
linklist_insert_head(phead,3);
linklist_insert_head(phead,2);
linklist_insert_head(phead,1);
linklist_print(phead);
int i = length（phead）；
printf("i = %d ",i);
return 0;
} 查----遍历---打印
遍历打印逐个节点访问：
step1.指针遍历p ； p->pnext != NULL //后面还有节点继续往后
2.尾插法
stepl.创建了一个新节点并且给值
p_new->pnextt=NULL;
step2.找到尾节点p初始位置就从头节点开始判断p的指针域是否为NULL
p->pnext != NULL
step3.链接
p->pnextt=p_new
void linklist_insert_tail(node_t *phead,date_t date)
{
node_t *p_new = malloc(sizeof(node_t));
if(p_new == NULL) //判断链表是不是空
{
printf("%smalloc fail
",__func__);
return;
}
p_new->date = date;
p_new->pnext = NULL;//必须有
node_t *p = phead;
while(p->pnext != NULL)
{
p = p->pnext;
}
p->pnext = p_new; //连接
}
找值：从头遍历
node_t * linklist_find_key(node_t *phead,date_t key)
{
if(is_empty(phead) == 1)
{
return NULL;
}
node_t *p = phead->pnext;
while(p != NULL)
{
if(p->date == key)
{
return p;
}
p = p->pnext;
}
return NULL;
}
3.删除：头删，尾删
头删
//判断链表是否为空
step1.有一个指针变量指向首节点phead->pnext
step2.让头节点指向p->pnext
step3.释放p所在的节点free(p);
void linklist_delete_head(node_t *phead)
{
if(is_empty(phead) == 1)
{
return;
}
node_t *p = phead->pnext;
phead->pnext = p->pnext;
free(p);
}尾删
//判断链表是否为空--空直接返回
s1.找到尾节点前一个节点
//统一操作逻辑p的初值得从phead开始
p->pnext->pnext == NULL
s2.释放尾节点 free（p->pnext）
s3.将前一个节点，设置为新的尾节点 p->pnext=NULL
void linklist_delete_tail(node_t *phead)
{
if(is_empty(phead) == 1)
{
printf("empty linklist
");
return;
}
node_t *p = phead;
while(p->pnext->pnext != NULL)
{
p = p->pnext;
}
free(p->pnext);
p->pnext = NULL;
}
