- 1探索 Provectus 的 Kafka-UI：可视化管理 Apache Kafka 的利器
- 2mp-html 微信原生小程序渲染富文本
- 3flume出现org.apache.hadoop.fs.UnsupportedFileSystemException: No FileSystem for scheme “hdfs“
- 4大数据从入门到实战 - HBase 开发：使用Java操作HBase_hbase 开发:使用java操作hbase
- 5【运动规划算法项目实战】如何使用Pure Pursuit算法进行路径跟踪（附ROS C++代码）_ros c++直线跟随
- 6Python小程序——求100以内的质数_100以内的质数程序框图
- 7Linux中将终端的打印结果输出到文本文件中_如何将tar的打印写到文本上
- 8unity Holoens2开发，使用Vuforia识别实体或图片 触发交互（一）_vuforia应用hololens2识别图片
- 9蓝易云：Ubuntu离线编译安装cmake 3.22: 解决找不到OPENSSL问题以及版本查询问题处理方案
- 10机器学习前置步骤——Vscode和Anaconda的安装配置_vscode anaconda安装
数据结构概述
赞
踩
数据结构概述：
1.数据结构学习方法：
心态勇于直面问题，多听多练，主动思考，多尝试
2.数据的逻辑结构
线性结构、层次结构、网状结构
3.数据结构的意义
提升自己的编程能力
可复用性高、可读性好、效率高、可维护性好
4.数据结构的基本概念
（1）数据
数据即信息的载体，是能够输入到计算机中被计算机识别、存储和处理的符号的总称
（2）数据元素
数据元素是数据的基本单位，又称为记录，数据元素由若干基本项（或称字段、域、属性）组成
5.数据的逻辑结构
集合、线性结构、树形结构、图状结构
6.存储结构
顺序存储、索引存储、链式存储、散列存储
7.线性表
包含若干元素的一个线性序列
记为：L={a0,a1,.....,ai-1,ai,.......an-1}
L为表名，其中为数据元素，n为表长，n>0时为非空表，否则为空表
用二元组形式表示为：L=(D,R)
线性表的特征：
表头无前趋，表尾无后继，其它元素有且仅有一个直接前趋和直接后继
8.顺序存储：
将线性表中的各个元素依次存储在一片连续的内存空间，称之为顺序存储
特征：
（1）逻辑上依次排列，相邻的两个元素物理位置也是相邻的
（2）对数据元素ai的存取为随机存取或按地址存取
（3）存储密度高
存储密度=数据结构中元素所占存储空间/整个数据结构所占空间
顺序存储方便查找，但也有对表的插入和删除等运算对时间的复杂度较差的缺点
线性表的顺序存储结构：
#define N 100
typedef int data_t;
typedef struct
{
data_t data[N];//表的存储空间
int last;
} sqlist,*sqlink;
9.代码规范与顺序表的实现：
代码模块化编程：
sqlist.h sqlist.c test,c
优点：结构清晰明了、软件复用性好
当项目较大时，要编译的文件较多时，每一个.c文件都是要单独处理的，每一个.c文件生成的目标文件的过程是独立的。都要经过预处理、编译、汇编这三步，分别生成各自的.o目标文件，最后所有的目标文件加上库文件一起链接成可执行文件。
可以使用gcc *.c -o test将所有的.c文件生成可执行文件test
调用NULL指针要包含C库文件stdio.h
add:
Linux保存命令：
:w 保存文件但不退出vi
:w file 将修改另外保存到file中，不退出vi
:w! 强制保存，不推出vi
:wq 保存文件并退出vi
:wq! 强制保存文件，并退出vi
:q 不保存文件，退出vi
:q! 不保存文件，强制退出vi
:e! 放弃所有修改，从上次保存文件开始再编辑
顺序表的实现：
函数接口：
list_create();
①申请内存 申请相应数据类型的大小的一块内存，并将malloc的返回值强制类型转换为需要的类型，接下来要判断malloc内存申请是否成功，如果失败返回NULL，即线性表指针不指向任何空间，成功返回申请后得到的内存的首地址，并且如果申请内存成功，线性表指针指向该片内存，创建的内存空间初始状态为空
②初始化 使用memset函数（要包含string.h头文件）可以从起始地址往后的一片区域插入数据，这里插入0，最后标志位last = -1，表示该线性表为空表，写程序时一定要注意这两句话的顺序，先memset再last，否则last会被再次清0
③函数返回值
返回创建好的线性表指针L
list_delete();//顺序表空间销毁
int list_delete(sqlink L)
{
• if(L==NULL)
• {
• return -1;
• }
• free(L);
• L = NULL;
• return 0;
}
list_insert();
函数原型：
int list_insert(sqlink L,data_t value,int pos);
调用：list_insert(L,x,pos);
①：判断该线性表是否已满？
②：pos是否属于[0，last+1]区间 //插入规则
③：元素移动（后面元素先向后移动，依次往前）
④：存新值 last++
list_clear();//顺序表的清空
int list_clear(sqlink L)
{
• if(L==NULL)
• {
• return -1;
• }
• memset(L, 0, sizeof(sqlist));
• L ->last = -1;
• return 0;
}
list_deleteP(L,pos);//删除线性表中的元素
〇：判断是否为空表
①：检查合法性。判断要删除的位pos是否在[0，last]区间内
②：移动。被删除元素的后面紧邻元素先移动，后面元素都依次往前移动
③：更新last--
int list_deleteP(sqlink L,int pos)
{
• int i;
• //判断表是否为空表
• if(L->last == -1)
• {
• printf("list is empty\n");
• return -1;
• }
• //pos的合法性
• if(pos<0 || pos>L->last)
• {
• printf("delete pos is invalid\n");
• return -1;
• }
• //move
• for(i=pos+1;i<=L->last;i++)
• {
• L->data[i-1] = L->data[i];
• }
• //update
• L->last--;
• return 0;
}
C语言中不允许函数名称相同
list_purge();//去重复元素
int list_purge(sqlink L)
{
• int i,j;
• if(L->last == 0)//单个元素不比较，直接退出
• {
• return 0;
• }
• i=1;
• while(i<=L->last)
• {
• j=i-1;
• while(j>=0)
• {
• if(L->data[j] == L->data[i])
• {
• list_deleteP(L,i);
• break;//跳出本层循环
• }
• else
• {
• j--;
• }
• }
• if(j<0)
• {
• i++;
• }
• }
• return 0;
}
list_merge()//两个顺序表的归并
int list_merge(sqlink L1,sqlink L2)
{
• int i=0;
• int ret;
• while(i<=L2->last)
• {
• if((ret = list_locate(L1,L2->data[i]))==-1)
• {
• if((list_insert(L1,L2->data[i],L1->last+1))==-1)
• {
• return -1;
• }
• }
• i++;
• }
• return 0;
}
list_show();//顺序表的遍历
int list_show(sqlink L)
{
• int i;
• if(L==NULL)
• {
• printf("can not show\n");
• return -1;
• }
• if(L->last == -1)
• {
• printf("the list is empty\n");
• }
• for(i=0;i<=L->last;i++)
• {
• printf("%d ",L->data[i]);
• }
• puts("");
• return 0;
}
list_empty();//判断顺序表是否为空
int list_empty(sqlink L)
{
• if(L->last == -1)
• {
• return 1;
• }
• else
• return 0;
}
list_length();//求顺序表的长度
int list_length(sqlink L)
{
• if(L==NULL)
• {
• return -1;
• }
• return (L->last+1);
}
list_locate();//定位元素位置
int list_locate(sqlink L,data_t value)
{
int i=0;
for(;i<=L->last;i++)
{
if(L->data[i] == value)
{
return i;
}
}
return -1;
}
顺序表的优缺点：
优点：存储密度高、便于存取数据
缺点：要求必须是一片连续的内存空间，而且进行插入、删除等操作时耗时，可能会有大片元素移动的现象。
什么时候选择使用顺序表：
当涉及到查找、更新数据较多时，使用顺序表效率较高
编程时要先画图，理清思路，再去写程序
线性表之链表
（多画图理解）
链式存储：
将线性表L=（a0,a1,a2,....,an-1）的各元素存储在内存中的不同模块，称为结点，通过地址或指针建立元素之间的联系。
通常会引入一个头结点来指向第一个节点，方便操作，且头节点数据不重要，只要存放的是第一个结点的地址即可
结点类型描述：
typedef struct node
{
data_t data;//节点的数据域
struct node *next;//节点的后继指针域
}listnode,*linklist;
上述图片中结点放在栈上，定义好A后系统自动分配好内存空间，然后再把A结点的地址赋予结点指针P，栈上的内存有着作用域，超出作用域后内存释放
P访问成员时必须用箭头，结构体A访问成员时用“ .”
若P为NULL，访问操作成员时会出现段错误
注：一般的段错误是由于指针的非法访问或者内存越界所致
下述图片采用动态内存申请的方式申请一块内存，申请灵活，需要多少申请多少，结点放到堆上
建立单链表：
依次读入表L={a0,a1,...,an-1}中的每一个元素ai，若a[i] 不等于结束符-1，则为a[i]创建一个结点，然后插入表尾，最后返回链表的头结点指针H
链表的创建是动态形成的，算法运行前，表结构不存在
linklist list_create();
linklist list_create()
{
linklist H;
H = (linklist)malloc(sizeof(listnode));
if(H == NULL)
{
printf("malloc failed\n");
return H;
}
H->data = 0;
H->next = NULL;
return H;
}
空链表的表示：
一般赋初值时，将data置为0，next置空
list_tail_insert(linklist H,data_t value);
int list_tail_insert(linklist H,data_t value)
{
if(H == NULL)
{
printf("H is NULL\n");
return -1;
}
//创建新节点
linklist p,q;
//内存申请
if((p=(linklist)malloc(sizeof(listnode))) == NULL)
{
printf("malloc failed\n");
return -1;
}
//申请成功后赋予初值
p->data = value;
p->next = NULL;
//定位尾节点
q = H;
while(q->next!=NULL)
{
q = q->next;
}
//尾部插入
q->next = p;
return 0;
}
list_show();
int list_show(linklist H)
{
if(H == NULL)
{
printf("H is NULL\n");
return -1;
}
linklist p;
p = H;//忘记赋值的话，段错误
while(p->next != NULL)
{
printf("%d ",p->next->data);
p = p->next;
}
puts("");
return 0;
}
基本运算的相关算法：
①：list_get(H,pos);
//链表查找
约定头结点位置为-1，往后依次是0，1，2，......
linklist list_get(linklist H,int pos)
{
linklist p;
int i;
if(H == NULL)
{
printf("H is NULL\n");
return NULL;
}
if(pos==-1)
{
return H;
}
p = H;
i =-1;
while(i<pos)
{
p = p->next;
if(p == NULL)
{
printf("pos is invalid\n");
return NULL;
}
i++;
}
return p;
}
p = list_get(H,4);
printf("value=%d\n",p->data);
上图截图出现段错误，是由于上述代码段出现p->data的情况，返回空指针，空指针又去访问数据出现段错误，非法访问。
②：链表的插入
源码：
int list_insert(linklist H,data_t value,int pos)
{
linklist p,q;
if(H == NULL)
{
return -1;
}
//查找要插入的前一个结点，并返回其指针
p = list_get(H,pos-1);
if(p == NULL)
{
return -1;
}
//新建新结点
if((q=(linklist)malloc(sizeof(listnode))) == NULL)
{
printf("malloc failed\n");
return -1;
}
//给新结点赋予初值
q->data = value;
q->next = NULL;
//插入
q->next = p->next;
p->next = q;
return 0;
}
指针指向改变有先后顺序，先使 q的指针域指向ai，后使p的指针域指向新插入的元素x，即p ->next = q，否则会出现链表断掉的情况
单链表的优缺点：
优点：单链表不需要大量连续的存储空间，通过指针对元素进行操作，插入、删除时元素不需要成片移动，此时执行效率高，同时可以由用户动态申请内存，不会造成内存的浪费。
缺点：单链表查找时从头结点开始，并且只能单向移动，不能随机访问，比较耗时，效率低。
③：链表的结点删除
①：删除操作前需要调用链表查找接口函数list_get();，找到所要删除结点的直接前驱，假设用指针p指向该前驱结点
②：（1）定义一个临时变量q，用来存放所要删除结点的起始地址，即q = p->next ,便于后面的内存释放
（2）改变结点的指针指向，p->next = q->next
(3) 释放内存，合理利用内存，可持续发展，避免内存泄漏： free(q)
结点删除函数接口：
int list_delete(linklist H,int pos)
{
linklist p,q;
//check
if(H == NULL)
{
printf("H is NULL\n");
return -1;
}
//locate prior
p = list_get(H,pos-1);
//check valid?
if(p == NULL)
{
return -1;
}
if(p->next == NULL)//特殊情况，删除最后一个结点的后一个结点
{
printf("delete pos is invalid\n");
return -1;
}
//update
q = p->next;
p->next = q->next;//p->next = p->next->next;
//free
printf("delete:%d\n",q->data);
free(q);
q = NULL;//避免野指针!
return 0;
}
main函数中删除结点的实现：
int main()
{
linklist H;
int value;
H = list_create();
if(H == NULL)//链表创建失败
{
return -1;
}
printf("input:\n");
while(1)
{
scanf("%d",&value);
if(value == -1)
{
break;//结束链表创建
}
list_tail_insert(H,value);
printf("input\n");
}
list_show(H);
list_delete(H,-1);//1，3，5，7
list_show(H);
return 0;
}
④：链表的释放：
int list_free(linklist H)
{
linklist p;
if(H == NULL)
{
printf("H is NULL\n");
return -1;
}
p = H;
printf("free:");
while(H != NULL )
{
p = H;
printf("%d ",p->data);
H = H->next;
free(p);//不能把释放内存放到前面
}
puts("");
return 0;
}
如果主函数中重复调用list_free()函数，则会出现下面的情况：如下分别是主函数调用和命令行显示结果：
int main()
{
linklist H;
int value;
H = list_create();
if(H == NULL)//链表创建失败
{
return -1;
}
printf("input:\n");
while(1)
{
scanf("%d",&value);
if(value == -1)
{
break;//结束链表创建
}
list_tail_insert(H,value);
printf("input\n");
}
list_show(H);
printf("H=%p\n",H);
list_free(H);
printf("H=%p\n",H);
list_delete(H,-1);
list_show(H);
list_free(H);
return 0;
}
改进方法：
1：将list_free()函数的函数声明和定义部分的返回值改为linklist（结点指针型），list_free函数体最后返回一个空指针NULL，并在main函数中用H接收，H= list_free(H);，这样所有的内存被释放之后，又被赋予了NULL，就无法再操作内存
假如在list_free()函数最后，使用H = NULL的方式赋予空指针，这样是没用的，因为主函数中，调用list_free函数时，实参为临时变量H，形参为被调用函数的形参，改变形参的值，实参不会变
2：或者list_free传参时传二级指针，即&H，这种方法较上面的麻烦，但也行得通：
注意二级指针访问加变为一级指针访问成员，H->next,这样是错误的，会出现以下结果：（正确的做法是在H两边加上括号，因为->的优先级高于*）
error: request for member ‘next’ in something not a structure or union
链表的复杂运算：
⑤：链表的反转
思路：
代码实现：
int list_rev(linklist H)
{
linklist p,q;
if(H == NULL)
{
printf("H is NULL\n");
return -1;
}
if(H->next == NULL ||(H->next)->next == NULL)
{
printf("only one\n");
return 0;
}
p = H->next->next;
H->next->next = NULL;
while(p != NULL)
{
q = p;
p = p->next;
q->next = H->next;
H->next = q;
}
return 0;
}
问题：
1.为什么不能用一个指针P来操作？
只用指针p操作时，要负责两个任务，第一遍历所有元素，其二完成插入到H后的任务，插入H后时，p的next已经被赋新值了，不能再往后遍历了，链表已经断了
2.既然形参不能改变实参，那为什么可以通过操作形参改变成员的方式去改变链表
因为传进来的参数是地址，可以通过地址访问目标结构体，址传递可以改变操控原值
3.上面的链表的反转是取出链表中的每一个节点后头部插入，改变了原有链表的结构。
那么来看一个题目：提供一个单向链表的链表首地址，实现反向打印链表的数据，要求不能改变原有链结构。
（注意要求不能改变链表的结构）
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
typedef struct node
{
data_t data;
struct node *next;
}listnode,*linklist;
linklist list_create();
int list_show(linklist H);
int list_tail_insert(linklist H,data_t value);
int list_rev(linklist H);
int main(int argc, const char *argv[])
{
linklist H;
if((H = list_create()) == NULL)
{
return -1;
}
list_tail_insert(H,1);
list_tail_insert(H,2);
list_tail_insert(H,3);
list_tail_insert(H,5);
list_tail_insert(H,7);
list_show(H);
list_rev(H->next);
puts("");
list_show(H);
return 0;
}
linklist list_create()
{
linklist H;
if((H = (linklist)malloc(sizeof(listnode))) == NULL)
{
perror("list_create-malloc");
return NULL;
}
H->data = 0;
H->next = NULL;
return H;
}
int list_tail_insert(linklist H,data_t value)
{
linklist p = NULL;
if(H == NULL)
{
printf("list_tail_insert:H is NULL\n");
return -1;
}
if((p = (linklist)malloc(sizeof(listnode))) == NULL)
{
perror("list_tail_insert-malloc");
return -1;
}
p->data = value;
p->next = NULL;
while(H->next != NULL)
{
H = H->next;
}
H->next = p;
return 0;
}
int list_show(linklist H)
{
while(H->next)
{
printf("%d ",H->next->data);
H = H->next;
}
puts("");
return 0;
}
int list_rev(linklist H)
{
/*
linklist p,q;
p = H->next->next;
H->next->next = NULL;
while(p != NULL)
{
q = p;
p = p->next;
q->next = H->next;
H->next = q;
}
*/
/*或者可以这样写*/
if(H != NULL)
{
list_rev(H->next);
printf("%d ",H->data);
}
return 0;
}
运行结果如下：
linux@linux:~/ds/liner$ gcc test.c linux@linux:~/ds/liner$ ./a.out 1 2 3 5 7 7 5 3 2 1 1 2 3 5 7
代码思路：
递归实现在不改变链表结构的前提下，逆序打印链表数据
⑥：链表的相邻两结点之和的最大值
思路：
接口函数源码：
linklist list_adjmax(linklist H,data_t *value)
{
linklist p,q,r;
data_t sum;
if(H == NULL)
{
printf("H is NULL\n");
return NULL;
}
if(H->next == NULL || H->next->next == NULL ||H->next->next->next == NULL)
{
return H;
}
q = H->next;
p = q->next;
r = q;
sum = q->data + p->data;
while(p->next != NULL)
{
p = p->next;
q = q->next;
if(sum< q->data + p->data)
{
sum = q->data + p->data;
r = q;
}
}
*value = sum;//将sum的值带出函数
return r;//注意不是返回q，因为r不一定要更新
}
⑦：有序链表的合并
思路：
①：
②：
③：
退出循环体后，再判断p和q，一方为空，就把另一方直接插入到r后面
源码如下：
int list_merge(linklist H1,linklist H2)
{
linklist p,q,r;
if(H1 == NULL || H2 == NULL)
{
return -1;
}
p = H1->next;
q = H2->next;
r = H1;
H1->next = NULL;
H2->next = NULL;
while((p != NULL) && (q != NULL)) //while(p && q);
{
if(p->data <= q->data)
{
r->next = p;
p = p->next;
r =r->next;
r->next = NULL;
}
else
{
r->next = q;
q = q->next;
r =r->next;
r->next = NULL;
}
}
if(p == NULL)
{
r->next = q;
}
else
{
r->next = p;
}
return 0;
}
作业：无序链表的元素排序： 写一个函数，实现链表的排序（使链表中元素的从无序到有序，要求从小到大）；
结果如下：
原因是：这里系统认为是定义的变量没有malloc申请内存，那么直接使用free会出错，比如：（malloc与free要配对使用）
因此free释放的应该是malloc申请的有效空间
特别注意：这里有个陷阱：明明调用函数传递参数传的是指针（节点地址），被调用函数中又使用malloc函数申请堆内存，可为什么会出错呢？
因为指针作为参数传递，其实本质是值传递，传给被调用函数后，会在栈上给形参分配空间，空间里的值就是你所传递的指针值，H1 = list_create()这句话，其实本质是malloc申请堆上的一块内存空间，强制类型转换后给形参H1赋值，形参H1被改变了，但形参不能改变实参，实参H1并未被改变，还是野指针，根本就没有接收到malloc申请的内存空间，因此free直接报错
改进：
方法1：
H1 = list_create这句话不要放被调用函数，改成放到调用函数里
方法2：
list_sort()排序函数由一个参数增加到2个参数，传递一级指针变量的地址，用二级指针变量来接收
int list_sort(linklist H,linklist *H1)
{
linklist p,q,r,m;
if(H == NULL)
{
printf("list_sort:invalid operation\n");
return -1;
}
if(((*H1) = list_create()) == NULL)
{
return -1;
}
m = *H1;
while(H->next != NULL)
{
r = H;
p = H->next;
q = p;
p = p->next;
while(p != NULL)
{
if(p->data < q->data)
{
q = p;
while(r->next != q)
{
r = r->next;
}
p = p->next;
}
else
{
p = p->next;
}
}
r->next = q->next;
while((*H1)->next)
{
(*H1) = (*H1)->next;
}
(*H1)->next = q;
printf("*H1:%d\n",(*H1)->data);
q->next = NULL;
}
*H1 = m;
/*
这种方法比上面简单多了，只需要传一个参数H
linklist p,q;
if(H == NULL)
{
printf("list_sort:invalid operation\n");
return -1;
}
p = H->next;
q = p;
while(q->next != NULL)
{
while(p->next != NULL)
{
p = p->next;
if(p->data < q->data)
{
p->data ^= q->data;
q->data ^= p->data;
p->data ^= q->data;
}
}
q = q->next;
p = q;
}
*/
return 0;
}
int test_sort()
{
linklist H,H1;
int i;
data_t a[] = {9,2,4,0,5,7,1};
if((H = list_create()) == NULL)
{
return -1;
}
for(i = 0;i < sizeof(a)/sizeof(data_t);i++)
{
list_tail_insert(H,a[i]);
}
list_show(H);
list_sort(H,&H1);
list_show(H1);
list_free(&H);
list_free(&H1);
return 0;
}
注意测试时，list_sort函数里最后H1跑到了倒数第二个位置，实参也会跟着动，所以为了正常输出遍历结果，要使用第三方指针m来接收H1,最后再还给它
(58条消息) free(): invalid pointer的问题雪舞飞扬之殇的博客-CSDN博客free(): invalid pointer
进程退出后，malloc分配的资源会被系统回收_进程退出后占用的资源会被回收吗-CSDN博客?
数组和链表的区别:
答：
从逻辑结构上来看，数组必须实现定于固定的长度，不能适应数据动态增减的情况，即数组的大小一旦定义就不能改变。当数据增加时，可能超过原先定义的元素的个数；当数据减少时，造成内存浪费；链表动态进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。
从内存存储的角度看；数组从栈中分配空间（用new则在堆上创建），对程序员方便快速，但是自由度小；链表从堆中分配空间，自由度大但是申请管理比较麻烦。
从访问方式类看，数组在内存中是连续的存储，因此可以利用下标索引进行访问；链表是链式存储结构，在访问元素时候只能够通过线性方式由前到后顺序的访问，所以访问效率比数组要低。
栈实现及应用
栈是限制在一端进行插入和删除操作的线性表（俗称堆栈），允许进行操作的一端称为栈顶，另一固定端称为栈底，当栈中没有元素时成为空栈。 特点：后进先出
非线性问题线性化，需要用到栈，另外可以将栈看作一个容器，遵循先入后出或者后进先出，而栈和顺序表有什么不同呢？
顺序表中，元素的插入和删除可以在任意位置进行，而栈只能在栈顶进行压栈和弹出，栈的示意图如下图所示：
（1）顺序栈：
顺序栈定义：
定义一个结构体，取别名为sqstack（顺序栈），结构体中有三个成员，分别为：指向实际栈空间的data_t型指针data、当前栈的最大元素个数以及指示栈顶位置（数组下标）的变量top,见下图：
顺序栈的创建：
sqstack * sqstack_create();
根据定义好的顺序栈结构体sqstack，先定义一个顺序栈结构体指针s，首先申请一块内存用于存储结构体成员，s = (sqstack *)malloc(sizeof(sqstack)); 接着再申请一块内存用于存储实际栈的数据，被结构体成员data指向，即s->data = (data *)malloc(len * sizeof(data_t))
源码：
sqstack *sqstack_create(int len)
{
sqstack *s;
if((s = (sqstack *)malloc(sizeof(sqstack))) == NULL)
{
printf("malloc sqstack failed\n");
return NULL;
}
if((s->data = (data_t *)malloc(len * sizeof(data_t))) == NULL )
{
printf("malloc data failed\n");
free(s); //data指向的数据区申请失败时释放掉s
s = NULL;
return NULL;
}
memset(s->data,0,len*sizeof(data_t));//调用memset填充初值0
s->maxlen = len;//由用户定义栈的长度
s->top = -1;//将栈置空
return s;
}
顺序栈的释放：
int sqstack_free(sqstack *s);
顺序栈的释放和malloc配对使用（用户申请的内存使用过后要释放掉，避免内存泄漏），下面为源码：
int sqstack_free(sqstack *s)
{
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
if(s->data != NULL) //判断数据存储区是否曾经创建成功
{
free(s->data);
}
free(s);
return 0;
}
这里分为两种情况：
其一：
如果在创建栈时，创建data内存时失败，则要将之前malloc成功的内存（s）释放掉，防止内存泄漏（就程序而言，不写free的话，data申请内存失败后会返回一个NULL给s，这时s被置空，然而里面的成员未被释放，会造成内存泄漏）
其二：
如果整个栈创建成功的话，在上面的栈释放代码中会判断data指向的内存是否申请成功，若是，先则将这段内存释放掉，再释放掉顺序栈指针s
顺序栈的满判断
int sqstack_empty(sqstack *s);
在入栈前要先判断栈里的数据是否为满状态：（top）
可以将栈视为一个装水的容器，上面带有刻度，而top就像是浮标，数据入栈时从栈顶入栈，数据开始从栈底堆叠，水涨船高，top浮标也跟着上浮，当top到达maxlen-1时，数据存储区已满
int sqstack_full(sqstack *s)
{
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
return (s->top == s->maxlen-1 ? 1 : 0);//采用三目运算符，当top指向了maxlen-1，视为满
}
顺序栈的空判断
当s->top等于-1时视为无元素，此时栈为空
源码：
int sqstack_empty(sqstack *s)
{
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
return (s->top == -1 ? 1 : 0);
}
顺序栈的入栈
int sqstack_push(sqstack *s,data_t value);
int sqstack_push(sqstack *s,data_t value)
{
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
if(s->top == s->maxlen-1)
{
printf("sqstack is full\n");
return -1;
}
s->top++;
s->data[s->top] = value;// *(s->data + s->top) = value;
return 0;
}
先将top加1，再将top指向的数据赋值，入栈时先要判断栈是否为满状态
顺序栈的出栈：
data_t sqstack_pop(sqstack *s)；
data_t sqstack_pop(sqstack *s)
{
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
s->top--;
return (s->data[s->top+1]);
}
出栈时要先判断栈是否处于空状态，下面为在main函数中的调用，需要在main函数里实现
while(!sqstack_empty(s)) //出栈前先判断栈是否为空，需要在main函数里写，由用户判断
{
printf("pop:%d\n",sqstack_pop(s));
}
需要循环调用该接口函数，如果在接口函数里实现的话，while(1)是死循环，跳不出来，命令行会一直显示返回值
（2）链式栈的实现
链式表中头结点可以看作是栈的top指针，但是只在栈顶位置做插入删除，top不会变化
结构体定义体：
typedef int data_t;
typedef struct node
{
data_t data;
struct node *next;
}listnode,*linkstack;
①：链式栈的创建
申请内存，创建一个空链表s，并作初始化，代码如下：
linkstack stack_create()
{
linkstack s;
s = (linkstack)malloc(sizeof(listnode));
if(s == NULL)
{
printf("s is NULL\n");
return NULL;
}
s->data = 0;
s->next = NULL;
return s;
}
②：压栈
即在头节点s后尾部插入
int stack_push(linkstack s,data_t value)
{
linkstack p;
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
p = (linkstack)malloc(sizeof(listnode));
if(p == NULL)
{
printf("p is NULL\n");
return -1;
}
p->data = value;
//p->next = NULL;
p->next = s->next;
s->next = p;
return 0;
}
③：出栈
即头节点后栈顶元素释放
data_t stack_pop(linkstack s)
{
linkstack p;
data_t t;
p = s->next;
s->next = p->next;
t = p->data;
free(p);
p = NULL;
return t;
}
示意图：
④：链式栈释放
linkstack stack_free(linkstack s)
{
linkstack p;
if(s == NULL)
{
printf("s is NULL\n");
return NULL;
}
while(s != NULL)
{
p = s;
s = s->next;
printf("free:%d\n",p->data);
free(p);
}
return NULL;
}
示意图：
⑤：判断空状态?
int stack_empty(linkstack s)
{
if(s == NULL)
{
printf("s is NULL\n");
return -1;
}
return (s->next == NULL ? 1 : 0);//返回三目运算符结果
}
⑥：查看栈顶元素
data_t stack_top(linkstack s)
{
return (s->next->data);
}
队列
队列：
队列是限制在两端进行插入删除操作的线性表
允许进行存入一端称为“队尾”，允许进行删除一端称为“队头”；线性表没有元素时成为空队
特点：先进先出
单向队列一端进一端出，双端队列可以两端分别进出元素
顺序循环队列：
结构体定义：
typedef int data_t;
#define N 100
typedef struct
{
data_t data[N];
int front;
int rear;
}sequeue;
为什么要使用循环队列？
其一是为了充分利用队列内存空间。当进行队列操作时，队尾指针向后移动，数据元素入队，此时如果队头指针也向后移动时，数据元素出队，就导致出队的位置被空了下来，循环队列可以循环存取数据元素，内存利用率高。
其二，不使用循环队列时，当进行频繁的队列操作时，队尾指针频繁后移，会发生越界，是不被允许的，当使用循环队列时，对数据元素的存取一直在一定范围的内存空间内进行。
设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A）==(rear-front+m)%m== B）rear-front+1
C）(front-rear+m)%m D）(rear-front)%m
正确答案：A
①：循环队列的创建
先malloc一个内存空间，强制类型转化为顺序队列指针并被sq接收
初始化：调用memset函数，在申请的内存区间内全部用0填充，最后将队列置空，或者用bzero函数
sequeue *queue_create()
{
sequeue *sq;
if((sq = (sequeue *)malloc(sizeof(sequeue))) ==NULL)
{
printf("malloc failed\n");
return NULL;
}
memset(sq->data,0,sizeof(sq->data));
sq->front = 0;
sq->rear = 0;
return sq;
}
②：队列的空状态判断：
front与rear指针相等即为空
int queue_empty(sequeue *sq)
{
if(sq == NULL)
{
return -1;
}
return (sq->front == sq->rear ? 1 :0);
}
③：队列的满状态判断：
见上图，若(sq->rear +1) %N == sq->front时，即为满状态，循环队列中不是简单的rear堆叠的问题，而是要使rear+1对N取余，才能构成一个循环回路
int queue_full(sequeue *sq)
{
if(sq == NULL)
{
return -1;
}
if(((sq->rear +1) % N) == (sq->front))
{
printf("enqueue is full\n");
return 1;
}
else
{
return 0;
}
}
④：队列的入队
要先判断队列是否处于满状态，再做赋值处理
int enqueue(sequeue *sq,data_t x)
{
if(sq == NULL)
{
return -1;
}
if(((sq->rear +1) % N) == (sq->front))
{
printf("enqueue is full\n");
return -1;
}
sq->data[sq->rear] = x;
sq->rear = (sq->rear +1) % N;//新的rear值加1对N取余后赋给旧rear，这样就可保证rear在[0.5]区间内
return 0;
}
红色代码为先存值，再更新rear
⑤：队列的出队
要先用一个第三变量存储先前的值，再对front进行加一取余更新，最后返回第三变量
data_t dequeue(sequeue *sq)
{
data_t t;
if(sq == NULL)
{
return -1;
}
t = sq->data[sq->front];
sq->front= (sq->front +1) % N;
return t;
//return (sq->data[(sq->front+N - 1) % N]);
}
注意将代码改为红色部分更为简单
⑥：释放
sequeue *queue_free(sequeue *sq)
{
if(sq == NULL)
{
return NULL;
}
free(sq);
sq = NULL;
return NULL;
}
链式队列：
队列元素的插入在队尾操作，删除在队头操作，由队尾指针和队头指针分别控制
首先应该定义两个结构体：（结点结构体和链式队列结构体）
typedef int data_t;
typedef struct node
{
data_t data;
struct node *next;
}listnode,*linklist;
typedef struct
{
linklist front;
linklist rear;
}linkqueue;
①：链式队列的创建；
见上图，定义一个lq指针用于接收创建好的链式队列结构体的地址，调用malloc函数申请一段内存，lq指向该内存空间，接着再申请一段内存，将该内存的首地址返回给front，同时front赋给rear，判断是否创建内存空间成功，之后给头结点赋初值。
源码：
linkqueue *queue_create()
{
linkqueue *lq;
/* linklist front,rear;
if((front = (linklist)malloc(sizeof(listnode))) == NULL)
{
printf("malloc listnode failed\n");
return NULL;
}
if((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL)
{
printf("malloc linkqueue failed\n");
return NULL;
}
lq->rear = lq->front;
lq->front->data = 0;
lq->front->next = NULL;
*/
if((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL)
{
printf("malloc linkqueue failed\n");
return NULL;
}
if((lq->rear = lq->front = (linklist)malloc(sizeof(listnode))) == NULL)
{
printf("malloc listnode failed\n");
return NULL;
}
lq->front->data = 0;
lq->front->next = NULL;
return lq;
}
②：入队
首先创建一个新节点，p为结点指针，然后将p的地址赋给rear的指针域，然后将rear更新，源码如下：
int enqueue(linkqueue *lq,data_t x)
{
linklist p;
if(lq == NULL)
{
printf("lq is NULL\n");
return -1;
}
if((p = (linklist)malloc(sizeof(listnode))) == NULL)
{
printf("p is NULL\n");
return -1;
}
p->data = x;
p->next = NULL;
lq->rear->next = p;
lq->rear = lq->rear->next;
return 0;
}
③：出队
首先定义一个结点指针p，将front的地址先暂时存放，然后将front更新，同时释放掉p指向的内存空间，同时将p置空，最后返回释放掉的数据。
注：这里采用删除头结点的方式，另外一种方法是删除队头队尾中间的结点，只不过剩最后一个尾部结点时，需要再将rear回调，使rear和front相等。
源码：
data_t dequeue(linkqueue *lq)
{
linklist p;
if(lq == NULL)
{
printf("lq is NULL\n");
return -1;
}
p = lq->front;
lq->front = p->next;
free(p);
p = NULL;
return (lq->front->data);
}
④：判断链式队列是否为空（不用判断满状态，因为malloc进行动态申请内存）
空状态判断依据是：两个链式指针相等，或者front的指针域为NULL
int queue_empty(linkqueue *lq)
{
if(lq == NULL)
{
printf("lq is NULL\n");
return -1;
}
return (lq->front == lq->rear ? 1 : 0);//或者返回一个lq->front->next == NULL;
}
⑤：清空队列
保留头结点
int queue_clear(linkqueue *lq)
{
linklist p;
if(lq == NULL)
{
printf("lq is NULL\n");
return -1;
}
while(lq->front->next != NULL)
{
p = lq->front;
lq->front = p->next;
printf("clear-free:%d\n",p->data);
free(p);
p = NULL;
}
return 0;
}
⑥：释放队列
全部释放
注意判断条件与置空
linkqueue * queue_free(linkqueue *lq)
{
linklist p;
if(lq == NULL)
{
printf("lq is NULL\n");
return NULL;
}
while(lq->front)
{
p = lq->front;
lq->front = p->next;
printf("free:%d\n",p->data);
free(p);
p = NULL;
}
free(lq);
lq = NULL;
return lq;
}
假溢出：
什么是假溢出呢，首先我们先了解下什么是队列中的溢出/上溢，也就是当队列里的空间已经满了，还继续往队列中插入元素，就会使队列的基础数组越界而导致代码破坏；而假溢出则是由于头尾指针都不断地向前移因而超出向量空间，这时整个向量空间及队列是有空的地方却产生了"上溢"现象。
就像上图中的0和1 位置明明是空的，末端指针却指在数组外面因此加不进新的元素，就产生了数组越界的错误。
因此我们采用循环队列来防止假溢出的现象的发生。
链式、栈的综合应用--球钟问题
问题描述：
原理：
要解决的问题：
示意图如下：
分析：
三个时间指示器可看作三个栈容器，并且都是有最大存储容量的容器，因此考虑到顺序栈（maxlen），入栈出栈元素满足先进后出，球队列可以选择用更为方便的链式队列。
根据题意，三个栈容器均为空时，时间指示为0：0，当三个栈容器分别达到上限时，时间指示为11：59，最后再放一个球，时间归零，构成一个循环。故总的球链式队列里初始值应为27个球。
源码如下：
int check(linkqueue *lq);
int main()
{
linkqueue *lq;
sqstack *s_hour,*s_five,*s_min; //定义三个顺序栈
int i,min = 0; //定义初始时间
int value;
if((lq = queue_create()) == NULL)
{
return -1;
}
for(i=1;i<=27;i++)
{
enqueue(lq,i); //循环入队，设置初始元素队列
}
if((s_hour = sqstack_create(11)) == NULL) //创建11容量的一小时栈
{
return -1;
}
if((s_five = sqstack_create(11)) == NULL) //创建11容量的五分钟栈
{
return -1;
}
if((s_min = sqstack_create(4)) == NULL) //创建4容量的一分钟栈
{
return -1;
}
while(1)
{
min++; //循环计时，每过一分钟就从队列中取出一个球
if(!queue_empty(lq))
{
value = dequeue(lq); //非空取球
if(!sqstack_full(s_min)) //未满元素压栈，即分钟指示器多一个球
{
sqstack_push(s_min,value);
}
else
{
while(!sqstack_empty(s_min)) //如果分钟指示器满了，再放入一个球，分钟指示器的4个球会出栈入队（与入栈顺序相反放入队尾），直到栈为空
{
enqueue(lq,sqstack_pop(s_min));
}
if(!sqstack_full(s_five)) //如果这时5分钟指示器未满，则压栈
{
sqstack_push(s_five,value);
}
else
{
while(!sqstack_empty(s_five))//否则，视为5分钟指示器也满了，这时将5分钟指示器元素出栈入队，直到为空
{
enqueue(lq,sqstack_pop(s_five));
}
if(!sqstack_full(s_hour)) //判断小时指示器是否已满，未满则将这个球放入小时指示器
{
sqstack_push(s_hour,value);
}
else
{
while(!sqstack_empty(s_hour)) //否则，也即是小时指示器也满了，则出栈入队，直到栈为空
{
enqueue(lq,sqstack_pop(s_hour));
}
enqueue(lq,value); //将最后未放入小时指示器的球置入队尾，此时达到一个循环
//0:0
if(check(lq)) //检查链式队列是否升序
{
break; //若升序，则跳出整个循环，计时结束
}
}
}
}
}
}
printf("total:min=%d\n",min);
printf("dequeue:");
while(!queue_empty(lq))
{
printf("%d ",dequeue(lq));
}
puts("");
return 0;
}
int check(linkqueue *lq)//判断是否升序，前一个数与后一个数比较，若小于继续比较，否则退出，直到比完
{
linklist p;
if(lq == NULL)
{
return -1;
}
p = lq->front->next;
while(p && p->next)
{
if(p->data < p->next->data)
{
p = p->next;
}
else
{
return 0;
}
}
return 1;
}
树：
树的概念：
有序树和森林：
树的逻辑结构：
二叉树：
概念：
二叉树的性质：
性质一：二叉树第i层上的节点最多为2的（i-1）次方个（i>=1）
性质二：深度为k的二叉树节点数最多有2的k次方减一（k>=1）
性质三：具有n个节点的完全二叉树深度为：(log2n)+1 或者log2(n+1)
另外二叉树满足：度数为0的节点数等于度数为2的节点数加1
满二叉树：
深度为k时有2的k次方减一个节点
完全二叉树：
只有最下面两层度数小于2,且最下面一层的节点集中在最左边的若干位置上
完全二叉树的度数为1的结点只有两种情况，0或1
二叉树的顺序存储：
可以利用数组进行顺序存储，数组元素下标与二叉树的节点编号一一对应，下标0元素不用，但是这种有时会浪费存储空间，因为当遇到不完全二叉树时，需要添加虚节点，此时虚节点会占据存储空间
因此采用二叉树的链式存储结构：
结构体定义：
二叉树的遍历：
遍历：
为什么说二叉树是非线性的呢？
学习线性表时，知道线性表是表头无前驱，表尾无后继，其他节点有且仅有一个直接前驱和一个直接后继，像一串糖葫芦，是一串线性元素的序列，而对于二叉树，根节点后有多个后继节点时，这时就是树形结构，是一种非线性结构。
因为每一个节点有两个后继结点，因此存在着如何遍历的问题，每一种遍历的搜索路径不一样，遍历的结果也不一样，分情况进行遍历：
以先序遍历为例：
创建：
二叉树中的所有的字母均由用户输入（包括#号），#号代表接口函数的出口，返回NULL，图中所有的空操作全部用#号代替。
二叉树创建源码如下：
bitree *tree_create()
{
data_t ch;
bitree *r;
scanf("%c",&ch);
if(ch != '#')
{
if((r = (bitree *)malloc(sizeof(bitree))) == NULL)
{
printf("malloc failed\n");
return NULL;
}
r->data = ch;
r->left = tree_create();
r->right = tree_create();
}
else
{
return NULL;
}
return r;
}
其中，先定义一个二叉树根节点指针，用来接收创建的二叉树结点内存空间返回的首地址（强制类型转换），创建好之后，给该节点赋予初值：data域和左右子树，左右子树分别再次递归调用二叉树创建函数，执行创建函数过程中遇到#跳出，最后返回根节点指针r
二叉树先序遍历源码：
每次递归执行时执行够花括号里的四句话，遇到出口条件逐层跳出，直至结束
int preorder(bitree *r) //二叉树的根节点，看作先序遍历起始的地方
{
if(r == NULL)
{
return 0;
}
printf("%c",r->data);
preorder(r->left); //递归调用先序遍历函数，遇到#跳出一层循环
preorder(r->right);
return 0;
}
类似，中序和后序的源码如下：
int inorder(bitree *r)
{
if(r == NULL)
{
return 0;
}
inorder(r->left);
printf("%c",r->data);
inorder(r->right);
return 0;
}
int postorder(bitree *r)
{
if(r == NULL)
{
return 0;
}
postorder(r->left);
postorder(r->right);
printf("%c",r->data);
return 0;
}
三种遍历示意图;
先序遍历算法剖析：（想不明白时，最好画出最简单的二叉树，将其按照递归算法捋一捋）
层次遍历：
声明一个队列，用于存放父节点，便于之后找左右子树，基本思路是：
访问打印根节点的数据，并使根节点入队。下面构建一个循环，结束条件是队列为空，然后将根节点出队，判断根节点的左子树是否为空，若不为空则访问左子树，访问完后将该左子树入队；若为空，再判断有无右子树，若右子树不为空，则访问右子树的数据，并将右子树节点掷入队列，接下来是又一层执行。队列不为空，将先前掷入队列的节点出队访问，判断有无左右子树...............
以上面的二叉树遍历图为例：先访问根节点A，再将A入队，接着进入循环语句，队列不为空时将A出队，判断左右子树，访问左右子树的数据，然后将左、右子树入队.........
根据以上的思路，则层次遍历的顺序为A-B-E-C-F-D-G-H-K
源码如下：
int layerorder(bitree *r)
{
linkqueue *lq;
if((lq = queue_create()) == NULL)
{
return -1;
}
if(r == NULL)
{
return 0;
}
printf("%c",r->data);
enqueue(lq,r);
while(!queue_empty(lq))
{
r = dequeue(lq);
if(r->left)
{
printf("%c",r->left->data);
enqueue(lq,r->left);
}
if(r->right)
{
printf("%c",r->right->data);
enqueue(lq,r->right);
}
}
puts("");
return 0;
}
防重复定义（包含）
曾出现这样的问题：矛盾类型、重复定义
文件包含情况如下：
观察可发现，bitree.h与linkqueue.h头文件均被包含在bitree.c文件中，另外我在这两个头文件中均加上了条件编译，可为什么还会报这样的错误呢？
细看可发现，bitree.h与linkqueue.h头文件中定义的类型有一样的、重复的（比如：data_t,node）这样的话，预处理阶段进行头文件展开生成.i文件，会将bitree.h先展开，再将linkqueue.h展开，而linkqueue.h文件中又包含了bitree.h,于是又将bitree.h在bitree.c文件中展开，最后将linkqueue.h中剩下内容展开，生成最终的.i文件。
于是，bitree.h包含了两次，linkqueue.h包含了一次，此外bitree.h与linkqueue.h都进行了条件编译，因此编译时只将bitree.h与linkqueue.h各编译一次。但是重点是，即使这样，bitree.h与linkqueue.h因有重复内容，编译时也会出错
现在改为如下：将bitree.h文件中的data_t、node改为datatype、node_t
再次编译：正常
此外将bitree.c中的bitree.h注释掉也可以，因为bitree.h已经包含在了linkqueue.h，这样包含了linkqueue.h的情况下，会将bitree.h与linkqueue.h各包含一次，编译时也均编译一次
但是注意：如果将linkqueue.h文件中的#include "bitree.h"注释掉，编译时会出现以下错误：
虽然看上去和上面的类似，也都各包含一次，但是由于没有包含到linkqueue.h文件中，就会出现未知类型、找不到相关类型的错误
查找：
查找的概念：
查找的方法：
自己去实现顺序表查找与折半查找
查找的平均长度：
哈希查找法：
哈希查找可以不经过比较就可以查找到相应的记录，其时间复杂度为常数级O（C），需要建立记录与地址的链接关系
哈希函数（散列函数、杂凑函数）：
通常要找Key = k的记录时，其中k为用户要查找的数，通过建立哈希函数确定记录所在的地址，要查找时，先定位到地址，再进行查找访问，H（key）记为哈希函数，自变量key是记录，函数值为存储地址或哈希地址。
冲突：
对于同一个哈希函数，不同的key可能对应同一个地址，这时称两个记录为同义词，该现象为“冲突”
事实上，选取好的哈希函数只能尽量使冲突减少，却不能完全避免冲突现象的发生，这就需要考虑到冲突数据的存放问题
哈希表：
将一组记录（线性表），通过某种映射关系（哈希函数与解决冲突方法）映射存放到一个存储空间中，形成一个记录表，该记录表称为哈希表
哈希表的查找：
哈希函数的构造有多种方法：直接地址法、平方取中法、叠加法、保留余数法、随机函数法，主要介绍最常用的保留余数法
保留余数法：
H（key）= key % p ，p为不大于哈希表长m的最大质数
p选取质数比合数的哈希函数的随机度要好，散列程度要优，可以使得冲突现象减少
使用随机度好的哈希函数可以使得冲突减少，但不能完全避免冲突现象的发生，也就是说冲突现象可能再哈希表中发生，例如根据哈希函数得到哈希地址，不同的记录可能对应多个哈希地址，一个地址内存只能存放一个记录，这就导致了冲突现象的发生
解决冲突的方法：
哈希表的装填因子一般选取经验值0.7-0.8之间，根据记录数推算出表长m，视为哈希表长，另外表中留有余量，减少装填数据造成的冲突和聚积
开放地址法：
示意图：
链地址法：
有这样一组记录：key={23,34,14,38,46,16,68,15,7,31,26},共11个记录数据，根据前面的内容，装填因子 = n/m,选取装填因子为0.75，可推算出m=15,根据哈希函数H(key) = key % p，选取最大质数为13，即哈希表长为15，余数空间为【0，12】，也就是说记录如果分散到哈希表中，数据以链式存储的方式分布于哈希地址为【0，12】的空间。
示意图：
结构体定义：
首先定义一个链式节点listnode，成员分别为key、value、next，再将其扩充封装为一个链式节点数组，定义为hash，数组中每一个元素都是一个链式节点
#ifndef __HASH_H__
#define __HASH_H__
#define N 13
typedef int datatype;
typedef struct node
{
datatype key;
datatype value;
struct node *next;
}listnode,*linklist;
typedef struct
{
listnode data[N];
}hash;
hash *hash_create();
int hash_insert(hash *HT,datatype key);
linklist hash_search(hash *HT,datatype key);
#endif
然后定义一个hash指针HT（hash *HT）指向这一片链式节点结构体数组，便可用HT指针进行记录结点的插入和查找操作，类似于链表中的头指针
创建：
hash *hash_create()
{
hash *HT;
if((HT = (hash *)malloc(sizeof(hash))) == NULL)
{
printf("malloc failed\n");
return NULL;
}
memset(HT,0,sizeof(hash));
return HT;
}
定义一个HT指针，用于接收申请内存返回的首地址，若申请失败返回NULL，成功进行初始化赋值，调用memset函数填充
插入：（有序插入）
int hash_insert(hash *HT,datatype key)
{
linklist p,q;
if(HT == NULL)
{
return -1;
}
if((p = (linklist)malloc(sizeof(listnode))) == NULL)
{
printf("malloc listnode failed\n ");
return -1;
}
p->key = key;
p->value = (key % N);
p->next = NULL;
q = &(HT->data[key % N]);
while(q->next && q->next->key < p->key) //退出条件为q的指针域为空，此时在后面追加 ，另外如果q指向的下一个结点的记录不小于要插入的记录，那就退出循环，在两节点中间插入
{
q = q->next;
}
p->next = q->next;
q->next = p;
return 0;
}
先定义一个链式指针p，用于接收申请内存后返回的首地址，p指向该内存空间，接着对p所指向的内存，进行初始化赋值，其中key为记录，value为保留余数法求出的哈希地址，next为指向下一节点的指针域。
初始化赋值后选择要插入的那一串链表，即要先找到其头结点，这里用 q = &(HT->data[key % N])，以哈希地址为下标的数组元素就是对应头结点，然后加上7取地址，赋给指针变量q,q为该串链表的头结点指针，然后进行插入操作（循环出口为q指针域为空或要插入的值不大于q指针的下一结点的记录）
查找：
linklist hash_search(hash *HT,datatype key)
{
linklist p;
if(HT == NULL)
{
return NULL;
}
p = &(HT->data[key % N]);
while(p->next && p->next->key ！= key)
{
p = p->next;
}
if(p->next == NULL)
{
printf("not found:\n");
return NULL;
}
else
{
printf("found:\n");
return p->next;
}
}
类似于插入操作，先找到所在链表的头结点，如果p的指针域为空或者p指向的下一个节点的记录等于用户要查找的值，接着进行判断输出对应的结果
排序：
排序定义：
内排序方法：
而插入排序又可分为：
（1）直接插入排序：
（2）折半插入排序：
（3）链表插入排序：
交换排序：
①：冒泡排序（自己去实现，一定要熟练，本节不予实现）
②：快速排序：（非常重要，一定要熟练理解）
快速排序：
快排基本思路：（递归）
给一个数组或者记录集合，先找一个基准值（第一个元素），并且用一第三变量存起来。默认基准值右边的数据比基准值大、左边的数据比基准值小，以此为规则进行比较，从右边开始比较，基准值右边比基准值大的数不用动，high--（记录两个游标low、high）,若遇到基准值右边比基准值小的数，则将该数放到基准值处，方便理解可以认为基准值虚假占位（实际上基准值已经被存放到第三变量中，不用进行交换，此后开始正序比较，遇到左边比基准值大的数，数据送到刚刚反序截止的high位，该位置被基准值虚假占据），以此类推，第一次执行到退出条件时，找到一个中间轴，数据被分为两部分，分成的两部分再次调用快排函数（递归），反复调用执行，直到结束
#include <stdio.h>
#include <stdlib.h>
#define N 15
//int compare(const void *p1,const void *p2);
int partion(int *data,int low,int high);
int quicksort(int *data,int low,int high);
int main()
{
int data[N] = {0};
int i;
srandom(9); //随机值函数
for(i=0;i<N;i++)
{
data[i] = random() % 100;
}
for(i=0;i<N;i++)
{
printf("%d ",data[i]);
}
puts("");
quicksort(data,0,N-1);
//qsort(data,N,sizeof(int),compare);//库函数快排
for(i=0;i<N;i++)
{
printf("%d ",data[i]);
}
puts("");
return 0;
}
int partion(int *data,int low,int high)
{
int tem = data[low];
while(low < high)
{
while(low < high && tem <= data[high]) //如果碰到极端情况基准值右边的数都比基准值大，循环会被一直执行，即使low和high相等high还在减，大括号不能对其控制，故应把大括号的退出条件加到内层循环中
{
high--;
}
data[low] = data[high];
while(low < high && tem >= data[low]) //同上
{
low++;
}
data[high] = data[low];
}
data[low] = tem;
return low;
}
int quicksort(int *data,int low,int high)
{
int t;
if(data == NULL)
{
return -1;
}
if(low >= high) //为什么这里写为 low == high 同目录下的作业文件quicksort1c会报段错误
{
return 0;
}
t = partion(data,low,high);
quicksort(data,low,t-1);
quicksort(data,t+1,high);
return 0;
}
/*int compare(const void *p1,const void *p2)
{
return (*(const int *)p1 - *(const int *)p2);
}*/
如果low == high：
、
具体见错题集
使用库函数快排：
各种排序算法详解
多层循环编程经验：
做一件事一般要分成两步，第一步先确定分几步进行，为最外层循环，第二步确定每一大步里面的每一小步该怎么实现，为内层循环
①：冒泡排序：
#include <stdio.h>
int main()
{
int i,j;
int t,n;
int data[] = {1,5,3,8,6,2,0};
n = sizeof(data)/sizeof(int);
for(i=0;i<n;i++)
{
printf("%d ",data[i]);
}
puts("");
for(i=0;i<n-1;i++)
{
int len = n;
for(j=0;j<len-1;j++)
{
if(data[j]>data[j+1])
{
t = data[j];
data[j] = data[j+1];
data[j+1] = t;
}
}
len--;
}
for(i=0;i<n;i++)
{
printf("%d ",data[i]);
}
puts("");
return 0;
}
②：简单插入排序：
思路：
例如对于一组无序数据{3，2，5，4，11，15，13}，第0个数据为基准值下标为end，从第1个数据开始，先用第三变量存储，再和前一个数据进行比较，如果比前一个数据小，那就end--，直到碰到比该数据大的跳出循环，将先前保存的值插入到该位置的后一个位置，如果所比较的所有数都比该数据大，那么当end=-1时直接结束循环，该数据直接赋予a[0]
#include <stdio.h>
int main()
{
int a[] = {3,2,5,4,11,15,13};
int i,end;
int n,t;
n = sizeof(a)/sizeof(int);
for(i=0;i<n-1;i++)
{
end = i;
t = a[end+1];
while(end >= 0)
{
if(t < a[end])
{
a[end+1] = a[end];
end--;
}
else
{
break;
}
}
a[end+1] = t;
}
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
puts("");
return 0;
}
③：希尔排序：
思路：
例如对于一个数组{9，1，2，5，7，4，8，6，3，5}，希尔排序的思想为将数组先分成若干组，对每一组进行直接插入排序（增量为d1，程序里为gap=n/2），然后对新数组再分为若干组，在对每一组进行直接插入排序（增量为d2<d1），以此类推，直到dt=1时结束排序，而且发现dt=1即为简单插入排序
下面取gap为每一循环增量减半：
#include <stdio.h>
int main()
{
int a[] = {9,1,2,5,7,4,8,6,3,5};
int i,end,gap;
int n,t;
n = sizeof(a)/sizeof(int);
gap = n/2;
while(gap >= 1)
{
for(i=0;i<n-gap;i++)
{
end = i;
while(end >= i)
{
t = a[end + gap];
if(t < a[end])
{
a[end + gap] = a[end];
end--;
}
else
{
break;
}
}
if(end < i)
{
a[end + 1] = t;
}
}
gap /= 2;
}
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
puts("");
return 0;
}
④：选择排序：
思路：
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。
#include <stdio.h>
int main(int argc,char *argv[])
{
int a[10] = {9,1,2,5,7,4,8,6,3,5};
int b[10] = {0};
int i=0,j,r=1;
int min,t;
for(j=0;j<10;j++)
{
r = i;
while(r<=9)
{
if(a[i] > a[r])
{
t = a[i];
a[i] = a[r];
a[r] = t;
min = a[i];
}
r++;
}
b[j] = min;
i++;
}
for(j=0;j<10;j++)
{
printf("%d ",b[j]);
}
puts("");
return 0;
}
⑤：归并排序：
