算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。 这样用大写O()来体现算法时间复杂度的记法,称之为大O记法。
常用的时间复杂度所消耗的时间从小到大依次是: O(1) < O(logn) < O(n) < O(nlogn) < O(n(2)) < O(n(3)) < O(2(2)) < O(n!) < O(n(n))
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n) = O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。
线性表(List):零个或多个数据元素的有限序列。
a(i-1)是a(i)的直接前驱元素,a(i+1)是a(i)的直接后继元素。
ADT 线性表(List)
Data
线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(*L):初始化操作,建立一个空的线性表L。
ListEmpty(L):若线性表为空,返回true,否则返回false。
ClearList(*L):将线性表清空。
GetElem(L,i,*e):将线性表L中的第i个位置元素返回给e。
LocaEleme(L,i,*e):将线性表L中查找与定位值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
ListInsert(*L,i,e):在线性表L中的第i个位置插入新元素e。
ListDelete(*L,i,e):在线性表L中的第i个位置元素,并用e返回其值。
ListLength(L):返回线性表L的元素个数。
endADT
线性表的顺序存储的结构代码:
#define MAXSIZE 20 /*存储空间初始分配量*/
typedef int ElemType;/*ElemType类型根据实际情况而定,这里假设为int*/
typedef struct
{
ElemType data[MAXSIZE];/*数组存储数据元素,最大值为MAXSIZE*/
int length;/*线性表当前长度*/
}SQList;
顺序存储结构需要三个属性:
用数组存储顺序表意味着要分配固定长度的数组空间,由于线性表中可以进行插入好人删除操作,因此分配的数组空间要大于等于当前线性表的长度。
存储器中的每个存储元素都有自己的编号,这个编号成为地址。
插入算法的思路:
初始条件:顺序线性表L已存在,1<= i <= ListLength(L)
操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1
Status ListInsert(SqLsit *L, int i,ElemType e)
{
int k;
if (L->length == MAXSIZE)/*顺序线性表已经满*/
return ERROR;
if(i<1 || i>L->length+1)/*当i不在范围内时*/
return ERROR;
if(i<=L->length)/*若插入数据位置不在表尾*/
{
for(k=L->length-1;k>=i-1;k--)/*将要插入位置后数据元素向后移动一位*/
L->data[k+1] = L->data[k];
}
L->data[i-1] = e;/*将新元素插入*/
L-length++;
return OK;
}
算法思路:
优点
缺点
为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。 数据域 + 指针域 = 结点
链表中第一个结点的存储位置叫做头指针,最后一个结点指针为“空”,用NULL或^表示。
获取链表第i个数据的算法思路
单链表第i个数据插入结点的算法思路
单链表第i个数据删除结点的算法思路
对于插入或删除数据越频繁的操作,单链表的效率优势就越是明显
单链表整表创建的算法思路:
### 单链表的整表删除
单链表整表删除的算法思路如下: