第1页 / 共98页
第2页 / 共98页
第3页 / 共98页
第4页 / 共98页
第5页 / 共98页
第6页 / 共98页
第7页 / 共98页
第8页 / 共98页
数据结构与算法.pdf
数据结构与算法
1.导论
1.1 数据的逻辑结构
1.2 算法复杂度
1.3 空间换时间思想
2. 线性表设计与实现
2.1 线性表顺序存储
2.1.1设计与实现
2.1.2 案例实现（c）
案例实现（c++类模板）
2.1.3 优点与缺点
2.2 线性表的链式存储
2.2.1设计与实现
2.2.2案例
2.2.3优缺点
2.3 循环链表
2.3.1 设计与实现
2.3.2案例
2.4 双向链表
2.4.1 设计与实现
2.4.2 案例
2.4.3 优缺点
3. stack栈
3.1 stack线性存储
3.2 stack链式存储
3.3 栈的应用
应用1
应用2
应用3
4. Queue队
4.1 队列的顺序存储
4.2 队列的链式存储
5.树和二叉树
5.1 二叉树
5.1.1 二叉树基本定义
5.1.2二叉树性质
5.1.3满二叉树和完全二叉树
5.1.4二叉树的顺序存储
5.1.5二叉树的链式存储
5.1.6 树的表示法
5.2 树的基本使用
5.3 二叉树的创建
6. 排序
6.1 选择法（n*n）
6.2 插入排序(n*n)
6.3 冒泡排序(n*n)
6.4 希尔排序（nlogn）
6.5 快排（nlogn）
6.6 归并排序(nlogn)
6.7 堆排序
6.8 桶排序
数据结构与算法
1.导论
数据结构是研究数据元素与元素之间得关系（表，栈，队列。。。）
1.1 数据的逻辑结构
1.2 算法复杂度
大O表示法：
算法效率依赖于操作数量
在判断时首先关注操作数量的最高次项
操作数量的估算可以作为时间复杂度的估算
#include
using namespace std;
//时间复杂度
//每个指令在具体的计算机cpu上运行的时间是固定的
//通过具体的n的步骤的多少就可以推算出算法的复杂度
//空间复杂度
//程序所需的内存空间
void play01(int n)//2n+4==>n无穷大时，复杂度O(n) //空间复杂度 4n+12 ==>O(n)
{
long sum=0;//1 //4
int *array = (int *)malloc(sizeof(int)*n);//1 //4*n
for (int i = 0;i < n;i++)//n //4 含int i;
{
array[i] = i+1;
}
for (int i = 0;i < n;i++)//n //4
{
sum += array[i];
}
cout << sum << endl;//1 //0
free(array);//1 //0
}
void play02(int n)//n+2==>n无穷大时，复杂度O(n)//空间复杂度 8 ==>O(1)
{
long sum=0;//1 //4
for (int i = 0;i < n;i++)//n //4
{
sum += i+1;
}
cout << sum << endl;//1 //0
}
void play03(int n)//2==>n无穷大时，复杂度O(1)//空间复杂度 4 ==>O(1)
{
long sum=0;//1 //4
if (n > 0)
{
cout << (1 + n)*n / 2 << endl;//1 //0
}
}
void main()
{
play01(9);
play02(9);
play03(9);
system("pause");
}
1.3 空间换时间思想
#include
#include
}
for (map::iterator it=m.begin();it!=m.end();it++)
{
if (max<(it->second))
{
max = it->second;
}
}
for (map::iterator it = m.begin();it != m.end();it++)
{
if (max==(it->second))
{
cout << it->first;
}
}
}
void main()
{
int array[] = {1,4,56,7,54,2,3,2,1,2,2,2,2,2,2,22,3,6,6,64,5,56,4,4,6,6,6,6};
int l = sizeof(array) / sizeof(array[0]);
play(array,l);
map m;
play02(array,l,m);
system("pause");
}
2. 线性表设计与实现
线性表的操作
创建线性表
销毁线性表
清空线性表
将元素插入线性表
将元素从线性表中删除
获取线性表中某个位置的元素
获取线性表的长度
2.1 线性表顺序存储
2.1.1设计与实现
插入元素：
判断线性表是否合法
判断线性表容量是否已满
将插入位置后的所有元素后移（从最后一个元素开始）
插入元素到指定位置
线性表长度加1
获取元素：
判断线性表是否合法
判断位置是否合法
通过数组下标的方式获取元素
删除元素：
判断线性表是否合法
判断删除位置是否合法
将删除位置后的所有元素前移（从删除元素的下一个元素开始）
线性表长度减1
2.1.2 案例实现（c）
//seqlist.h
#pragma once
#include
using namespace std;
typedef void SeqList;
typedef void SeqListNode;
typedef struct tag_SeqList
{
int len;
int capacity;
unsigned int *node;//int *node[]
}TSeqList;
//创建线性表
SeqList *SeqList_Create(int capacity);
//销毁线性表
void SeqList_Destroy(SeqList *list);
//清空链表
void SeqList_Clear(SeqList *list);
//链表长度
int SeqList_Length(SeqList *list);
//链表容量
int SeqList_Capacity(SeqList *list);
//将元素插入线性表
int SeqList_Insert(SeqList *list, SeqListNode *node, int position);
//获取线性表中某个位置的元素
SeqListNode *SeqList_Get(SeqList *list, int position);
//删除元素
SeqListNode* SeqList_Delete(SeqList *list, int position);
//seqlist.cpp
#pragma once
#include
using namespace std;
#include"seqlist.h"
//创建链表
SeqList *SeqList_Create(int capacity)
{
int ret = 0;
TSeqList *tmp = NULL;
tmp = (TSeqList *)malloc(sizeof(TSeqList));
if (tmp == NULL)
{
ret = -1;
cout << "func SeqList_Create() err : " << ret << endl;
return NULL;
}
memset(tmp, 0, sizeof(TSeqList));
//根据capacity分配节点空间
tmp->node = (unsigned int *)malloc(sizeof(unsigned int *)*capacity);
if (tmp->node == NULL)
{
ret = -2;
cout << "func SeqList_Create() err : " << ret << endl;
return NULL;
}
tmp->capacity = capacity;
tmp->len = 0;
return tmp;
}
//销毁链表
void SeqList_Destroy(SeqList *list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return;
}
tlist = (TSeqList *)list;
if (tlist->node != NULL)
{
free(tlist->node);
}
free(tlist);
}
//清空链表
void SeqList_Clear(SeqList *list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return;
}
tlist = (TSeqList *)list;
tlist->len = 0;
}
//链表长度
int SeqList_Length(SeqList *list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return -1;
}
tlist = (TSeqList *)list;
return tlist->len;
}
//链表容量
int SeqList_Capacity(SeqList *list)
{
TSeqList *tlist = NULL;
if (list == NULL)
{
return -1;
}
tlist = (TSeqList *)list;
return tlist->capacity;
}
//插入元素 ！！！！！！！！！！！！
int SeqList_Insert(SeqList *list, SeqListNode *node, int position)
{
int ret = 0;
int i = 0;
TSeqList *tlist = NULL;
if (list == NULL || node == NULL || position<0)
{
ret = -1;
cout << "func SeqList_Insert() err: " << ret << endl;
return ret;
}
tlist = (TSeqList *)list;
//判断容量是否已满
if (tlist->capacity <= tlist->len)
{
ret = -2;
cout << "func SeqList_Insert() err (tlist->capacity <= tlist->len) err : " << ret
<< endl;
return ret;
}
//容器修正，长度为6 容量20 用户插入位置为10
if (position >= tlist->len)
{
position = tlist->len;
}
//元素后移
for (i = tlist->len; i > position; i--)
{
tlist->node[i] = tlist->node[i - 1];//tlist->node[i]为最后一个元素的下一个位置
}
//插入元素
tlist->node[i] = (unsigned int)node;
tlist->len++;
}
SeqListNode *SeqList_Get(SeqList *list, int position)
{
SeqListNode *ret = 0;
TSeqList *tlist = NULL;
if (list == NULL || position < 0)
{
cout << "func SeqList_Get() err : " << endl;
return NULL;
}
tlist = (TSeqList *)list;
ret = (void *)tlist->node[position];
return ret;
}
//删除元素 ！！！！！！！！！！！
SeqListNode* SeqList_Delete(SeqList *list, int position)
{
int i = 0;
SeqListNode *ret = 0;
TSeqList *tlist = NULL;
if (list == NULL || position < 0)
{
cout << "func SeqList_Delete() err : " << endl;
return NULL;
}
tlist = (TSeqList *)list;
ret = (void *)tlist->node[position];
//元素前移
for (i = position;i < tlist->len;i++)//从position位置后面的元素前移
{
tlist->node[i] = tlist->node[i + 1];
}
tlist->len--;
return ret;
}
//test.cpp
#include
using namespace std;
#include"seqlist.h"
struct student
{
student(int i)
{
age = i;
}
int age;
};
void main()
{
SeqList *list = NULL;
student s1(10), s2(20), s3(30);
list = SeqList_Create(10);
SeqList_Capacity(list);
SeqList_Length(list);
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
