数据结构与算法

一、数据结构引入

（一）基础

C语言-结构体-内存（malloc）

（二）要解决的问题

使数据更加有条例

计算机要处理的是完整的信息组合

编程能力-可复用-效率

（三）什么是数据结构

1、可以凌驾于语言之上讨论

2、数据结构研究数据之间的关系

3、数据结构最重要的三个元素：逻辑结构、存储结构以及操作（数据之间的运算）

4、语言是最低要求，数据结构比所有语言出现的早

（四）数据结构基本概念

1、数据

2、数据元素

3、数据结构

数据结构研究的是数据元素之间的关系，数据元素又称数据项

例如：同学之间是线性结构，上下级领导是层级关系

4、逻辑结构

数据的逻辑结构可分为一对一、一对多、多对多

通过找前驱后继区分不同的逻辑结构

5、存储结构

1）顺序存储

利用数组，在一段连续的存储空间存储，前驱后继关系就是数组下标

2）链式存储

通过指针维护前驱后继关系，链式结构非常重要

3）索引存储

4）散列存储

适合查找频率比较高的时候

 二、线性表之顺序表

（一）什么是线性表及顺序表

单链表是线性表

1、线性表

2、线性表概念的标准答案

3、顺序存储-查找多，修改少

例如:图书管理

1）顺序表的优点

存储密度高，逻辑相邻物理相邻，支持随机存取或按地址存取

2）顺序表的不足

3）图书管理系统

结构体套结构体

book:存放图书信息

list：存放图书编号

（二）线性表的基本操作

（三）代码设计

1、sqlist.h

ds定义、提供的运算

2、sqlist.c

实现数据结构运算

3、test.c

数据结构的具体应用

1）结构清晰

2）软件复用

（四）顺序表的实现

1、创建目录

/ds/liner/sqlist

2、定义sqlist,*sqlink

3、线性表的创建

1）sqlist.h

分层操作vsp sqlist.h

2)保证每个文件可以独立的被编译

（五）线性表的创建

malloc申请的空间数组加last

1、创建线性表

2、将线性表清空

3、判断线性表是否为空

4、求线性表的长度

5、memset(L,0,sizeof(sqlist));

6、对代码进行标注

（六）顺序表的实现

1、在某个位置插入一个数

2、打印函数

3、插入元素的位置

4、无效插入情况

5、释放空间函数

6、如果有意测试某个函数，可以进行函数的封装

7、判断文件描述符

8、删除某个位置上的元素

9、顺序表的优缺点

优点：存储密度高、随机存储

缺点：插入删除耗费大

三、线性表之链表

（一）什么是链表及原理

1、单链表的重要性

使用频率非常高

2、头结点的好处

可以很快的找到第一个节点的位置

3、节点定义

指针指向什么数据就是什么类型的指针，单链表的指针指向一个节点，因此设置节点指针。

4、一般的段错误是内存越界或者非法指针

5、给节点分配内存

1)listnode A;

linklist p =&A;

分配的内存在栈上

由编译器自动分配和释放，通常在函数执行完之后释放

A.data

A.next

2)动态分配内存

p=(linklist)malloc(sizeof(listnode));

p->data

p->next

(二)单链表实现-创建

1、单链表的创建

1）输入-1停止输入

2）与顺序表不同，链表建立是动态的未知的。

3）单链表的存储结构

三、单链表实现-尾部插入

1、单链表的插入

2、单链表的打印

四、单链表实现-按位置插入

1、链表的查找

1）按序号查找

从序号0开始

2）按值查找

3）按位置插入

4）链表的删除

pos不合法

2、释放链表之后，H还是指向同样的位置，可以设置linklist类型的free函数，H被free后指向空

返回的指针指向空

接收空指针

改变后的结果

五、单链表的操作实现

（一）链表的反转

（二）链表求相邻两个节点的最大值

1、需要考虑的要素

1）空链表，一个节点，两个节点

2）初始化 sum

3）p,q移动

3、加一个参数，返回最大和

主函数

（三）有序链表的合并

主函数：

函数：

六、栈实现及应用

（一）栈-顺序栈的原理

栈的定义

（二）栈-顺序栈的实现-顺序表

1、创建栈

2、栈的内存

3、出栈

4、释放

因为在创建栈的时候，如果data没成功已经释放了s;

所以释放函数只需要考虑data创建成功一种情况

（三）栈-链式栈原理及实现

1、链式栈是加了限制的链式表

2、删除链表

入栈操作

3、释放一个节点

4、释放栈

七、队列的实现及其应用

（一）顺序队列的原理

1、只能在两端插入删除

2、双端队列

3、循环队列

为了区别队空和队满，要求队列留一个空间

八、链式队列

（一）链式队列的原理

1、链式队列结构体

（二）链式队列的实现

1、删除节点

删除头节点，所以删除后的front保存的是被删除节点的值

九、树及实现（上）

（一）树的概念

（二)二叉树的原理

1、二叉树的性质

2、二叉树的编号

 3、二叉树的存储-顺序结构

可能存在浪费空间的情况

4、二叉树的存储-链式结构

（三）二叉树的运算

1、二叉树的遍历

2、左子树右子树也是二叉树

十、树及实现（下）

（一）二叉树的三种遍历

（二）二叉树的层次遍历

十、查找

（一）查找的原理

1、关键字

2、查找算法

3、衡量标准

4、顺序查找

5、折半查找-有序

6、分块查找-块内无序，块间有序

7、hash查找-查找的元素与地址有关，不需要比较

（二）hash表原理

1、不经过比较，快速得到要找的值

2、建表与存储地址相关

3、冲突-不可避免

4、保留除数法

取不同的数效果不同，质数越大越好（不能太大，余数范围大，浪费内存）

5、冲突

6、质数选取，比m小的最大质数

7、填入的数-申请多大内存空间-定质数-定hash函数

8、发生冲突时-开放地址法

9、发生冲突时-链地址法

十一、排序

（一）排序的原理