文章目录
数据结构与算法(C++)
第一章：绪论
一：数据与数据类型
1.1 数据与数据元素
数据是对客观事物的符号表示，它能被计算机识别、存储、和加工处理。
数据元素是数据的基本单位，有时也被称为元素、节点、顶点、记录。
数据结构是指数据元素之间的相互关系，即数据的组织形式。一般包含三个部分、
1.数据间的逻辑关系，称为数据的逻辑结构。
2.数据元素及逻辑关系在计算机存储器内的表示方式，即数据存储结构。
3.数据运算，即多数据施加的操作。
1.2 数据的逻辑结构
1.集合：任何两个元素之间都没有逻辑关系，每个元素都是孤立的。
2.线性结构：结构中的元素之间存在一对一的关系，即线性关系。
3.树形结构：结构中的数据元素之间一定存在一对多的关系。
4.图状结构：结构中的元素之间存在多对多的关系.
1.3数据的存储结构
数据的存储结构是指数据在结算及内的表示方法，是逻辑结构的具体实现。即包含两方面：数据元素本身和数据元素间逻辑关系的表示。
1.顺序结构：将数据元素依次存储与一组地址连续的存储单元中，元素间的逻辑关系由存储单元的位置直接表现，此结构为顺序存储结构。
2.链式存储：将数据元素存储在一组任意的存储的单元中，用附加的指针域表示元素之间的逻辑关系。
3.索引存储：该方法特点是存储数据元素的同时，还可以建立附加的索引表，索引表中的每一项都是索引项。形式：关键字 + 地址。关键字是指能唯一标识数据元素的数据项，每一个数据元素在索引表中均有一个索引项
4.散列存储：一句数据元素的关键字，用一个事先设计好的函数计算出该元素的存储地址，然后把它存入该地址中去。这种函数称为散列函数，有散列函数计算出的地址称为散列函数。
1.4数据运算和数据类型
数据结构包括逻辑结构、存储结构和运算三个方面
数据类型一般有原子型和结构型
原子型：其值不分解，比如C++中的基本类型(整型、字符型、实型、枚举型)、指针类型、空类型。
结构类型：其值可以分为若干成分：比如C++中的数组类型、结构类型。
1.5抽象数据类型
指一个数学模型，抽象数据类型取决于它的一组逻辑特性，不论他的结构如何变化，只要它的数学特性不改变就不影响其外部的使用。
第二章：算法
2.1算法定义及描述
1.有穷性：对于任何合法的输入必须在执行有穷步骤之后结束，且每步都在有限的时间内完成。
2.确定性：每条指令都必须要要有确切的含义，不能有二义性。
3.可行性：算法是可行的，算法中描述的操作都可以通过已经实现的的基本运算有限次执行来实现。
4.输入输出：一个算法又零个或者多个输入，一个算法有一个或者多个输出。
补充：沃斯->数据结构 + 算法 = 程序
2.2算法评价
1.正确性：没有语法错误、输入数据能有合理输出、有结果、满足规格说明要求的结果。
2.可读性：有利于人们理解，懂得都懂。
3.健壮性：当数据非法或者运行环境改变的时候，算法能恰当的作出处理。
4.时空效率：减少时间复杂度和空间复杂度。
本章小结
1.数据类型有两种，即原子类型（如整型、字符型、实型、布尔型等）和结构类型。原子类型不可再分解，结构类型由原子类型或结构类型组成。
2.数据元素是数据的一个基本单位，通常由若干个数据项组成。
3.数据项是具有独立含义的最小标识单位，有时也称域或字段。其数据可以是一个原子类型，也可以是结构类型。
4.数据结构研究的是数据的表示和数据之间的关系。从逻辑上讲，数据结构有集合类型、线性结构、树结构和图4种。从物理实现上讲，数据有顺序结构、链式结构、索引结构和散列结构4种。理论上，任意一种数据逻辑结构都可以用任何一种存储结构来实现。
5.在集合结构中，不考虑数据之间的任何关系，它们处于无序的、各自独立的状态。在线性结构中，数据之间是1对1的关系。在树结构中，数据之间是1对多的关系。在图结构中，数据之间是多对多的关系。
6.算法的评价指标主要为正确性、健壮性、可读性和时空效率4方面。
习题：
一、选择题
1.算法的计算量的大小计称为计算的（）。复杂性
2.算法的时间复杂度取决于（）。问题的规模和待处理数据的初态
3.一个算法应该满足哪五个特性（）。有穷性、确定性、可行性、输入、输出。
4.．下面关于算法说法错误的是（ ）。D
A．算法最终必须由计算机程序实现
B．为解决某问题的算法与为该问题编写的程序含义是相同的
C．算法的可行性是指指令不能有二义性
D．以上选项都是错误的
5．从逻辑上可以把数据结构分为（ ）两大类。C
A．动态结构、静态结构
B．顺序结构、链式结构
C．线性结构、非线性结构
D．初等结构、构造型结构
二、填空题
1．数据结构主要包含________、和运算3个方面的内容。逻辑结构和存储结构
2．对于给定的n个元素，可以构造出的逻辑结构有、、、4种。集合、线性、树形、图状
3．沃斯（N.Wirth）教授曾以“____ + =程序”作为他的一本著作的名称。数据结构、算法
4．评价算法优劣的4个指标是 、________ 、 、 。健壮性、正确性、可读性、时空效率
5．一个算法具有5个特性： 、 、________ 、有零个或多个输入、有一个或多个输出。
有穷性、确定性、可行性
三、判断题
1．数据元素是数据的最小单位。 （❌）
2．数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （ ❌）
3．算法的优劣与算法描述语言无关，但与所用计算机有关。 （❌）
4．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 （❌）
5．算法可以用不同的语言描述，如果用C语言或Pascal语言等高级语言来描述，则算法实际上就是程序了。 （ ❌）
6．程序一定是算法。 （❌）
7．数据结构的抽象操作的定义与具体实现有关。 （ ❌）
四、应用题
1．数据类型和抽象数据类型是如何定义的？二者有何相同和不同之处？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？
2．评价一个好的算法，你是从哪几方面来考虑的？
3．解释下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构、算法、算法的时间复杂度、算法的空间复杂度。
第三章：线性表
3.1 线性表的定义
定义：线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中，n个元素个数，称为表长。当n = 0的时候称为空表。
线性表的运算：线性表初始化、求线性表的长度、取表元、按值查找、插入操作、删除操作、
一：顺序表结构
内存中地址空间是线性的，因此用物理上的相邻实现数据元素之间的逻辑关系相邻是既简单又自然的，举个例子，设数据元素a1的存储地址为loc，每个数据元素之间占用d个存储地址，则第i个数据元素的地址为loc(a1) = loc(a1) + (i - 1)d1 <= i <= n
二：顺序表运算
1.顺序表的初始化
void SequeList::Initiate()
{
len = 0;
}
2.插入运算
步骤一：将数据元素ai-an依次向后移动一个位置，为新元素让出位置。
步骤二：将X插入空出的第i个位置。
步骤三：修改len的值，使之仍指向最后元素的下一个位置，表示表长。
int SequenList::Insert(DataType x,int i)
{
//在线性表的第i个元素之前插入一个新的数据元素x
int j；
if(len >= MAXSIZE)
{
cout << "结束！" << endl;//数据溢出
return 0;
}
else if((i < 1) || (i > len + 1))//如果插入位不合法
{
cout << "position is not correct!" << endl;
return 0;
}
else
{
for(j = len;j >= i;j--)data[j] = data[j - 1];//数据后移
data[i - 1] = x;//插入元素
len ++;//数表长度增加1
return 1;
}
}
3.删除运算
操作和插入是类似的
int SequenList::Deleted(DataType x,int i)
{
//在线性表的第i个元素之前插入一个新的数据元素x
int j；
if(len >= MAXSIZE)
{
cout << "结束！" << endl;//数据溢出
return 0;
}
else
{
for(j = i;j < len;j++)data[j - 1] = data[j];//数据后移
data[i - 1] = x;//插入元素
len --;//数表长度减小1
return 1;
}
}
4.按值查找
int SequenList::Locate(Datatype x)
{
//返回值为x的数据元素的位序值
int j = 0;
while((j < len) && (data][j] != x))j++;
if(j < len)return j + 1;
else return 0;
}
5.读取第i个数据元素的值
DataType SequenList::Get(int i)
{
if((i < 1) ||(i > len))
{
cout << "position is not correct！" << endl;
}
}
6.取得数据元素的个数
int Sequenlist::Length()
{
return len;
}
三：顺序表存储空间的动态分配
上述都是说的已经预定好了的空间大小，这是一种存储空间的静态分配。
typedef struct
{
int *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
void InitList(SeqList &L)
{
//用malloc函数申请一片连续的存储空间
L.data = (int*)malloc(sizeof(int) * InitSize);
L.MaxSize = InitSize;
L.length = 0;
}
void IncreaseSize(SeqList &L,int len)
{
int *p = L.data;
L.data = (int*)malloc(sizeof(int) * (InitSize+len));
for(int i=0;i<L.length;i++)
{
L.data[i] = p[i];
}
L.MaxSize = L.MaxSize + len;
free(p);
}
四：线性表的链式存储结构
链表是通过一组任意的存储单元来存储线性表中的数据元素。我们一般来说链表是由数据节点构成的，一个数据节点一般有两个区域构成，一个是数据域，一个是指针域。(当然对于双链表这种就有两个指针域一个数据域)。
1.单链表运算
一.初始化
void Link::Initiate()
{
DeleteAll();
head = NULL;
}
二.建立单链表
a.从表尾到表头建立单链表（不带有空白头结点）
void Link::headCreate(int n)
{
DeleteAll();
Item *s, *p;
int i;
p = NULL;
for(int i = 1; i <= n; i++)
{
s = new Item();
cin >> s -> data;
s->next = p;
p = s;
}
head = p;
}
b.从表头到表尾建立单链表（不带有空白节点）
void Link::TailCreate(int n)
{
Item ＊s, ＊r, ＊p;
int i;
DeleteAll();
p=NULL;
for(i=1; i<=n; i++)
{
s=new Item();
cin>>s->data;
s->next=NULL;
if(p==NULL)p=r=s;
else
{
r->next=s;
r=s;
}
}
head = p;
}
c.从表尾到表头建立单链表（建立带有空白头节点）
void Link::HeadCreateWithHead(int n)
{
Item ＊s, ＊p;
int i;
DeleteAll();
p=new Item();
p->next=NULL;
for(i=1; i<=n; i++)
{
s=new Item();
cin>>s->data;
s->next=p->next;
p->next=s;
}
head= p;
}
d.从表头到表尾建立单链表（带有空白节点）
void Link::TailCreateWithHead(int n)
{
Item ＊s, ＊r, ＊p;
int i;
DeleteAll();
p=new Item();
p->next=NULL;
r=p;
for(i=1; i<=n; i++)
{
s=new Item();
cin>>s->data;
r->next=s;
r=s;
}
r->next=NULL;
head= p;
}
暂停链表的笔记！
第四章：栈和队列
什么是栈？
栈是限制在表的一端进行插入和删除的线性表。表中允许插入、删除的这一端称为栈顶，栈顶的当前位置是动态变化的；不允许插入和删除的另一端称为占地，栈底是固定不变的。当表中没有元素的时候我们往往称它为空栈。
栈都是先进后出的。
4.1顺序栈
栈的存储与一般的线性表的存储方式是类似的，主要两种存储方式：顺序存储、链式存储
一：顺序存储
利用顺序存储的方式实现的栈称为顺序栈，类似于顺序表的定义，要分配一块连续的空间存放栈中的元素，栈底位置可以固定的设置在数组的任何一端（一般在下标为0的一端是栈底），而栈顶是随着插入和删除而变化的，再用一个变量指明当前栈顶的位置。
顺序栈的描述：
typedef int DateType;
class SeqStack
{
private:
DateType *base;//栈底指针
DateType * top;//栈顶指针：始终指向栈顶元素的后一个位置
int size;//栈的大小
public:
SeStack(int stacksize = 100)
{
base = new DateType{stacksize};
top = base;//指向栈顶元素的后一位
size = stacksize;//构造了一个空栈，默认大小为100个单元
~SeqStaCK();//销毁一个已经存在了的栈
{
delete[] base;
top = NULL;
base = NULL;
}
int Empty_Stack();//判断栈是否为空
int Push_Satck(DateType e);//将元素e插入栈顶
int Pop_Stack(DataType &e);//从栈顶删除一个元素到e中返回
int Get_Stack(DataType &e);//从栈顶取出一个元素到e中返回
}
顺序栈下的成员函数实现
1.判断栈是否为空
思想：判断top是否小于base，小于等于则为空栈，返回1，否则返回0。
int SeStack::Empty_stack()
{
return((top <= base));
}
2.入栈操作
入栈操作就是在栈的顶部进行插入操作，相当于在顺序表的表尾进行插入，因此无需移动元素。
思想：首先判断栈顶是否已经满了，满了则失败返回0。否则，由于栈的top指向栈顶元素的最后一个位置，将入栈元素赋到top的位置，再将top + 1指向新的位置，成功返回1.
int SeqStack::Push_Stack(DataType e)
{
if(top - base < size)//判断栈是否为满的
{
*top = e;
top ++;
return 1;
}
else return 0;
}
3.出栈操作
出栈操作就是在栈的顶部进行删除操作，相当于在顺序表的尾表进行删除，因此也无需移动元素。
思想：
首先判断栈顶是否为空，如果是空的则失败，返回0；否则由于栈的top指向栈顶元素的后一个位置，要先修改top为top - 1，再将其指向的元素以引用参数e返回，成功返回1。
int SeqStack::Pop_Stack(DataType &e)
{
if(top > base)//判断栈是否为满的
{
top --;
*e = *top;
return 1;
}
else return 0;
}
4.取栈顶元素的操作
取栈顶元素是获取出栈顶元素的值，而不改变栈。
思想：首先判断栈顶是否为空，若空则失败，返回0；否则由于栈的top，指向栈顶元素的最后一位置，返回top - 1所指单元的值，栈不发生变化。
int SeqStack::Get_Stack(DataType &e)
{
if(top > base)//判断栈是否为满的
{
e = *(top - 1);
return 1;
}
else return 0;
}
二：链栈
栈也可以用链式存储的方法来实现，一般是用单链来表示，其节点结构和单链表的结构相同：
typedef int DataType;//整型栈的数据类型
class StackNode
{
public:
DataType data;
StackNode *next;
StackNode()
{
next = NULL;
};
}
在栈中的主要运算时在栈顶进行插入和删除操作，显然在单链表的表头进行滚滚插入和删除都是比较方便的，因此作为栈顶，而且没有必要像单链表那样为了运算方便就附加一个头节点。
1.判断栈是否为空
思想：判断top是不是空的，为空则为空栈
int LinkStack::Empty_Stack)() //判断链栈是否为空
{
return( !top);
}
2.入栈操作
3.入栈操作就是再栈顶进行插入操作，相当于在单链表的表头插入一个新的元素。
思想：首先为链栈分配空间，成功将入栈元素赋值到申请的链栈节点，并插入栈顶，使其成为栈顶元素，成功返回1，反之。
int LinkStack::Push_Stack(DataType e)
{
StackNode *p = new StackNode;//申请节点
if(p) //申请节点成功
{
p->data = e;
p->next = top;
top = p ;
}
return 1;
else return 0;
}
3.出栈操作
出栈操作就是在栈的顶部进行输出操作，相当于删除单链表的第一个元素。
思想：
首先判断栈是否为空，非空，则取出栈顶元素，引用参数e返回，并删除这个节点，成功返回1，否则返回0.
int LinkStack::Push_Stack(DataType e) //链栈入栈操作
{
StackNode ＊p = new StackNode; //申请结点
if(p) //申请结点成功
{
p->data=e;
p->next=top;
top=p; //修改栈顶指针
return 1;
}
else return 0;
4.取栈顶元素操作
取栈顶元素是获取出栈顶元素的值，而不改变栈。
思想：
首先判断栈是不是空的，非空则取出栈顶元素，以引用参数e返回，成功则返回1.否则0（与出栈操作不同在于不删除节点）
int LinkStack::Get_Stack(DataType &e) //链栈取栈顶元素
{
if(top)
{
e = top->data;
return 1;
}
else return 0;
}