[数据结构与算法]数据结构与算法(C++)

第一章·绪论

渐进时间复杂度：

大O记号(big-O notation)：

T(n) : 需执行的基本操作次数

S(n) : 需占用的存储单元数

T(n) = O(f(n))

iff $?c>0,当n>>2后,有T(n)<c?f(n)<\sqrt{5n?[3n?(n+2)+4]+6}<\sqrt{5n?[6n^2+4]+6}<\sqrt{35?n^3+6}$ < $6?n^{1.5}$ = $O(n^{1.5})$

与T(n)相比,f(n)更为简洁，但依然梵音前者的增长趋势

常数项可忽略:

O( f(n) ) = O( $c\times$f(n) )

低次项可忽略:

$O(n^a+n^b)=O(n^a),a>b>0$

其他记号

最好情况T(n) = $\Omega$( f(n) )

$?$ c > 0,当n >> 2后,有 T(n) > c·f(n)

一般情况T(n) = $\Theta$( f(n) )

$?$ $c_1>c_2$ > 0,当n >> 2后,有 $c_1$·f(n) > T(n) > $c_2$·f(n)

级数

算数级数:$T(n)=1+2+3+......+n=O(n^2)$

幂方级数:$T(n)=1^2+2^2+3^2+......+n^2=O(n^3)$

几何级数(a>1),与末项同阶:$T(n)=a^0+a^1+a^2+.....+a^n=O(a^n)$

调和级数:$h(n)=1+1/2+1/3+.....+1/n=\Theta (logn)$

对数级数:$log1+log2+log3+......+logn=log(n!)=\Theta (nlogn)$

实例1

for(int i = 1;i < n;i <<= 1)
	for(int j = 0;j < i;j ++)
		operation(i,j);

时间复杂度为O(n)

实例2

for(int i = 0;i <= n;i ++)
	for(int j = 1;j <i;j += j)
		operation(i,j);

时间复杂度为O(nlogn)

时间复杂度按数量级递增顺序：

$O(1)>O(lo{g}_{2}n)>O(n)>O(nlo{g}_{2}n)>O(n^2)>O(n^3)>......O(n^k)>O(2^n)$

第二章·线性表

线性结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

例如：线性表、栈、队列、字符串、数组、广义表

非线性结构：一个结点可能有多个直接前趋和直接后继

例如：树、图

四种基本的存储结构：

1. 顺序存储结构

2.链式存储结构

3.索引存储结构

4.散列存储结构

顺序表：地址连续、依次存放、随机存取、类型相同

//线性表的定义模板
#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
typedef struct{
	ElemType elem[LIST_INIT_SIZE];
	int length;  //当前长度
}Sqlist;  //顺序表类型

数组的定义

#define MaxSize 100
//数组静态分配
typedef struct{
	ElemType data[MaxSize];
	int length;
}Sqlist;
//数组动态分配
typedef struct{
	ElemType *data;
	int length;
}Sqlist;
Sqlist L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize); //c语言 动态申请内存空间

内存动态分配

malloc(m)函数,开辟m字节长度的地址空间，并返回这段空间的首地址

sizeof(x)运算，计算变量x的长度

free§函数，释放指针p所指变量的存储空间，即彻底删除一个变量

线性表的基本操作

InitList(&L)          //初始化操作，建立一个空的线性表L
DestroyList(&L)       //销毁已存在的线性表L
ClearList(&L)         //将线性表清空
ListInsert(&L,i,e)    //在线性表L中第i个位置插入新元素e
ListDelete(&L,i,&e)   //删除线性表L中第i个位置元素，用e返回
IsEmpty(L)            //若线性表L为空，返回True，否则False
ListLength(L)         //返回线性表L的元素个数
LocateElem(L,e)       //L中查找与给定值相等的元素位置，若不存在则返回0
GetElem(L,i,&e)       //将线性表中的第i位置元素返回给e

平均查找长度ASL(Average Search Length)：

为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度

$ASL={\sum }_{i=1}^n{P}_i{C}_i(P_i表示第i个记录被查找的概率，C_i表示找到第i个记录需比较的次数)$

线性表的链式表示和实现

1.结点：数据元素的存储映像。由数据域和指针域两部分组成
2.链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。

3.单链表：结点只有一个指针域的链表，称为单链表或线性链表
4.双链表：结点有两个指针域的链表，两个指针分别指向前趋和后继结点的链表称为双链表
5.循环链表：首尾相接的链表称为循环链表
6.头指针：是指向链表中第一个结点的指针
7.首元结点：是指链表中存储第一个数据元素$a_1$的结点
8.头结点：是在链表的首元结点之前附设的一个结点

空表的表示：

1.无头结点时，头指针为空时表示空表
head = null
2.有头结点时，当头结点的指针域为空时表示空表
head->next = null

链表的特点:(顺序存取)

1.结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
2.访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等

单链表的定义：

typedef struct Lnode{		  //声明结点的类型和指向结点的指针类型
	ElemType data;			 //结点的数据域
	struct Lnode *next;		//结点的指针域
}Lnode,*LinkList;		//LinkList为指向结构体Lnode的指针类型
LinkList L;            //定义链表L
LNode *p;			  //定义结点指针p，等价于LinkList p;

单链表的初始化：

#include<iostream>
#include<cstring>

using namespace std;

//存储学生学号、姓名、成绩的单链表结点类型
typedef struct{
  char num[10];
  char name[10];
  int score;
}ElemType;

typedef struct Lnode{
  ElemType data;
  struct Lnode *next;
}Lnode,*LinkList;
int main()
{
  LinkList L = new Lnode;
  L->data.score = 100;
  cout << L->data.score << endl ;
  
  LinkList p = new Lnode;
  L->next = p;
  // p->data.score = 98;
  L->next->data.score = 98;
  cout <<  L->next->data.score << endl;;
  return 0;
}

输出

100
98

单链表的销毁：

Status DestroyList(LinkList &L){
   Lnode *p;  //或LinkList p;
   while(L)
   {
   	p = l;
   	L = L->next;
   	delete  p;
   }
   return OK;
}

清空单链表:

链表中无元素，成为空链表，依次释放所有结点，并将头结点指针域设置为空

Status ClearList(LinkList &L){    //将L重置为空表
	Lnode *p,*q;		 //或LinkList p,q;
	p = L -> next;
	while(p)            //没到表尾
	{
		q = p->next;
		delete p;
		p = q;
	}
	L->next = null;   //头结点指针域为空
	return OK;
}

求单链表的表长

int ListLength(LinkList L){
	Lnode *p;    //或LinkList p;
	p = L->next;
	int length = 0;
	while(p)
	{
		p = p->next;
		length ++;
	}
	return length;
}

单链表插入操作

Status ListInsert_L(LinkList &L,int i ,ElemType e){
	auto p = L;
	int j = 0;
	while(p && j < i - 1)
	{
		p = p->next;
		j ++;
	}
	if(!p || j > i - 1) return ERROR;
	auto s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

单链表删除第i个结点：

Status LinkListDelete_L(LinkList &L,int i,ElemType &e){
	auto p = L;
	j = 0;
	while(p->next && j < i - 1)
	{
		p = p->next;
		j ++;
	}
	if(!p->next || j > i - 1) return ERROR;
 	auto q = p->next;
 	p->next = q->next;
 	e = q->data;
 	delete q;
	return OK;
}

头插法创建链表

void CreatList_H(LinkList &L,int n)
{
	L = new LNode;
	L->next = NULL;
	for(int i = n;i > 0;i --)
	{
		p = new LNode;
		cin >> p->data;
		p->next = L->next;  
		L->next=p;
	}
}

尾插法创建链表

void CreatList_R(LinkList &L,int n){
	L=new LNode;
	L->next=NULL;
	auto r = L;       //尾指针r指向头结点
	for(int i = 0;i < n;i ++){
		p = new LNode;
		cin >> p->data;
		p->next=NULL;
		r->next = p;
		r = p;     //r指向新的尾结点
	}
}

循环链表