1.数据结构定义与核心概念 数据结构的本质是数据在计算机中的组织与存储方式，其经典公式为： 程序 = 数据结构 + 算法 2.数据关系的逻辑结构分类 集合结构 数据元素之间仅属于同一集合，无其他明确关系。
线性结构 元素间为一对一关系，包括顺序表、链表、队列、栈等。
树形结构 元素间为一对多关系，典型代表为二叉树。
图形结构 元素间为多对多关系（网状结构）。
3.物理结构对比 顺序存储结构 使用连续内存空间存储数据。
访问时间复杂度为 O(1)。
插入/删除需移动大量数据，效率低。
需预分配内存，可能产生内存碎片。
链式存储结构 使用非连续内存空间，通过指针链接。
访问需遍历，时间复杂度为 O(n)。
插入/删除效率高，无需移动数据。
动态分配内存，灵活性高。
索引存储结构 通过索引表建立关键字与存储位置的映射。
散列存储结构 · 利用哈希函数直接计算存储位置。
4.常见数据结构内容 链式表 单向链表 双向链表 循环链表 内核链表 栈 后进先出（LIFO）结构，支持压栈（push）和弹栈（pop）操作。
队列 先进先出（FIFO）结构，支持入队（enqueue）和出队（dequeue）操作。
二叉树 每个节点最多有两个子节点。
包括二叉搜索树、平衡二叉树等变体。
哈希表 通过哈希函数实现快速查找。
需处理哈希冲突（如开放寻址法、链地址法）。
5.单向链表相关代码 1）创建链表对象 2）插入数据（头插，尾插），尾插要判断是否为空。
3）删除数据（头删，尾删），头删要判断是否为空链表，尾删需要判断是不是空链表和一个结点。
4）查找数据 5）修改数据 6）销毁链表，调用头删，free，最后要给plink置零。
link.h
#ifndef _LINK_H
#define _LINK_H
/*typedef定义了链表存储数据的类型*/
typedef int Data_type_t;
/*节点类型*/
typedef struct node
{
Data_type_t data;
struct node *pnext;
}Node_t;
//链表对象（类型，长度），指向第一个节点的指针
typedef struct link
{
Node_t *phead;
int clen;
}Link_t;
//声明函数
extern Link_t *create_link();
extern int insert_link_head(Link_t *plink, Data_type_t data);
extern void link_for_each(Link_t *plink);
extern Node_t *find_link(Link_t *plink, Data_type_t mydata);
extern int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata);
extern int delete_head(Link_t *plink);
extern int insert_link_tail(Link_t *plink, Data_type_t mydata);
extern int delete_tail(Link_t *plink);
extern void destroyed(Link_t *plink);
#endif
link.c
#include
#include "link.h"
#include
//在堆上创建单向链表
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, Data_type_t data)
{
//申请结点
Node_t *pnode = malloc(sizeof(Node_t));
if(NULL == pnode)
{
printf("malloc error!");
return -1;
}
//第一步初始化结点
pnode->data = data;
pnode->pnext = NULL;
//第二步插入结点
pnode->pnext = plink->phead;
plink->phead = pnode;
plink->clen++;
return 0;
}
//遍历
void link_for_each(Link_t *plink)
{
Node_t *ptmp = NULL;
ptmp = plink -> phead;
while(ptmp)
{
printf("%d\n", ptmp -> data);
ptmp = ptmp -> pnext;
}
}
//查找
Node_t *find_link(Link_t *plink, Data_type_t mydata)
{
Node_t *ptmp = plink->phead;
while(ptmp != NULL)
{
if(ptmp->data != mydata)
{
ptmp = ptmp -> pnext;
}
else
{
return ptmp;
}
}
return NULL;
}
//修改
int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata)
{
Node_t *ptmp = find_link(plink, olddata);
if(ptmp == NULL)
{
return -1;
}
ptmp->data = newdata;
return 1;
}
//删除
int delete_head(Link_t *plink)
{
if(plink->phead == NULL)
{
return -1;
}
Node_t *ptmp = plink->phead;
plink->phead = ptmp->pnext;
free(ptmp);
plink->clen--;
return 0;
}
//尾插
int insert_link_tail(Link_t *plink, Data_type_t mydata)
{
Node_t *ptmp = plink->phead;
if(NULL == ptmp)
{
ptmp->pnext = NULL;
ptmp->data = mydata;
}
else
{
while(ptmp->pnext != NULL)
{
ptmp = ptmp->pnext;
}
Node_t *pnode = malloc(sizeof(Node_t));
if(NULL == pnode)
{
printf("malloc error!");
return -1;
}
pnode->pnext = NULL;
pnode->data = mydata;
ptmp->pnext = pnode;
plink->clen++;
}
return 0;
}
//尾删
int delete_tail(Link_t *plink)
{
Node_t *ptmp = plink -> phead;
if(NULL == ptmp)
{
printf("空链表\n");
return -1;
}
else if(NULL == ptmp->pnext)
{
delete_head(plink);
}
else
{
while(NULL != ptmp->pnext->pnext)
{
ptmp = ptmp->pnext;
}
free(ptmp->pnext);
ptmp->pnext = NULL;
plink->clen--;
}
return 0;
}
//销毁链表
void destroyed(Link_t *plink)
{
while(NULL != plink->phead)
{
delete_head(plink);
}
free(plink);
plink = NULL;
}
main.c
#include
#include "link.h"
int main(int argc, const char *argv[])
{
//创建结点
Link_t *plink = create_link();
if(NULL == plink)
{
return -1;
}
//插入数据（头插）
insert_link_head(plink, 1);
insert_link_head(plink, 2);
insert_link_head(plink, 3);
insert_link_head(plink, 4);
insert_link_head(plink, 5);
insert_link_head(plink, 6);
//遍历
link_for_each(plink);
Node_t *ret = find_link(plink, 4);
if(ret)
{
printf("%p\n", ret);
printf("%d\n", ret -> data);
}
else
{
printf("error\n");
}
//修改
int t = change_link(plink, 1, 7);
if(t == -1)
{
printf("error\n");
}
else
{
printf("success\n");
link_for_each(plink);
}
//修改
delete_head(plink);
link_for_each(plink);
//delete_head(plink);
//link_for_each(plink);
//尾插
/*insert_link_tail(plink, 10);
link_for_each(plink);
puts("");
//尾删
delete_tail(plink);
link_for_each(plink);*/
//销毁链表
destroyed(plink);
return 0;
}
单向链表示意图