数据结构与算法入门(一)
第一章：数据结构绪论
1.基本概念与术语
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
数据项：一个数据元素可以由若干个数据项组成（是数据不可分割的最小单位）
数据对象：是性质相同的数据元素的集合，是数据的子集
数据结构：是相互之间存在的一种或多种特定关系的特定关系的数据元素的集合
2.逻辑结构和物理结构
a.逻辑结构：是指数据对象中数据元素之间的相互关系
集合结构：集合结构中的数据元素除了属于同一个集合外，它们之间没有其他关系
线性结构：线性结构中的数据元素之间是一对一的关系
树形结构：树形结构中的数据元素之间是一对多的层次关系
图形结构：图形结构中的数据元素之间是多对多的关系
b.物理结构：是指数据的逻辑结构在计算机中的存储形式
顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的
c.总结：
逻辑结构是面向问题的，物理结构就是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中
3.抽象数据类型
a.数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称
原子类型：是不可以再分解的基本类型，包括整型，实型，字符型等
结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据组成的
b.抽象数据类型：是指一个数据模型及定义在该模型上的一组操作（体现了程序设计中的问题分解，抽象和信息隐藏的特性）
第二章：算法
1.定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
2.算法的特性
a.输入输出：算法具有零个或多个输入，至少有一个或多个输出
b.有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
c.确定性：算法的每一步骤都具有确定的含义，不会出现二义性
d.可行性：算法的每一步骤都具有确定的含义，不会出现二义性
3.算法设计的要求
a.正确性
b.可读性
c.健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果
d.时间效率高和存储量低
4.算法效率的度量方法
a.事后统计方法
b.事前分析估算方法
一个程序的运行时间，依赖于算法的好坏和问题的输入规模，问题输入规模是指输入量的多少
最终，在分析程序的运行时间时，最重要的是把程序看作是独立于程序设计语言的算法或一系列步骤
5.函数的渐近增长
给定两个函数f(n)和g(n)，那么存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)
6.算法时间复杂度
算法的时间复杂 度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模 n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐 近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函 数。
推导大O阶：
1．用常数1取代运行时间中的所有加法常数。
2．在修改后的运行次数函数中，只保留最高阶项。
3．如果最高阶项存在且不是1，则去除与这个项相乘的常数。
7.算法空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂 度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句 关于n所占存储空间的函数。
第三章：线性表
1.线性表的定义：
List：零个或者多个数据元素的有限序列
2.线性表的抽象数据类型定义：
1
2
3
4
5
6
7
8
9
10
11
12
|
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。
LocateElem(L, e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；
|
3.线性表的顺序存储结构：
顺序存储结构：使用一段地址连续的存储单元依次存储线性表的数据元素
三个属性：
1.存储空间的起始位置：数组data，它的存储位置就是存储空间的 存储位置。
2.线性表的最大存储容量：数组长度MaxSize。
3.线性表的当前长度：length。
1
2
3
4
5
6
|
#define MAXSIZE 20
typedef int ElemType;//元素类型，看具体情况定，这里使用int
typedef struct{
ElemType data[MAXSIZE];
int length;
}SqList;
|
获取元素：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//一些状态码
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;//函数类型，其值为函数返回的状态码，如OK等
//初始条件：1<= i <= ListLength(L)
Status GetElem(SqList L,int i ,ElemType *e){
if (L.length == 0 ||i <1 || i > L.length ){
return ERROR;
}
*e = L.data[i - 1];
return OK;
}
|
插入元素：
思路：
如果插入位置不合理，抛出异常；
如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移 动一个位置；
将要插入元素填入位置i处，表长加1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//初始条件：1<= i <= ListLength(L)
//操作结果：L中第i个元素前插入新元素，L的长度+1
Status ListInsert(SqList *L,int i ,ElemType e){
int k ;
//判断顺序线性表是否已经满了
if (L->length == MAXSIZE){
return ERROR;
}
//判断i是否在范围内
if (i <1 || i > L->length+1){
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] = e;
L->length ++;
return OK;
}
|
删除操作：
思路：
如果删除位置不合理，抛出异常；
取出删除元素；
从删除元素位置开始遍历到最后一个元素位置，分别将它们都向 前移动一个位置；
表长减1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
//初始条件：1<= i <= ListLength(L)
//操作结果：删除L中的第i个元素，并用e返回值，L的长度-1
Status ListDelete(SqList *L,int i , ElemType *e){
int k ;
if (L->length == 0){
return ERROR;
}
if (i <1 || i >L->length ){
return ERROR;
}
*e = L->data[i-1];
if (i <L->length){
//将删除的位置后续元素向前推移
for (k= i;k<L->length;k++){
L->data[k-1] = L->data[k];
}
}
L->length --;
return OK;
}
|
4.线性表的链式存储结构
链式存储结构：用一组任意的存储单元存储线性表的 数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意 味着，这些数据元素可以存在内存未被占用的任意位置
数据域：存储数据元素信息的域
指针域：存储直接后续位置的域，存储的信息称为指针或链
这两部分组成数据元素a(i)的存储映像，称为结点(Node)
头指针：链表中第一个结点的存储位置
为方便操作，会在单链表的第一个结点前附设一个结点，称为头结点
头结点的数据域可以不存任何数据，也可以存储线性表的长度等附加信息
头结点的指针域存储指向第一个结点的指针
我们规定链表最后一个结点指针为“空”（NULL或^）
头指针与头结点的区别：
头指针：
1.头指针是指向链表第一个节点的指针，若链表有头结点，则是指向头结点的指针
2.头指针具有标识作用，所以常用头指针冠以链表的名字
3.无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头结点：
1.头结点是为了操作的统一和方便而设立，放在第一个元素之前，其数据域一般无意义。
2.有了头节点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
3.头结点不一定是链表必须元素
1
2
3
4
5
6
|
//单链表的链式存储结构
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList;
|
获取元素：
获取第i个元素的思路：
1.声明一个指针p指向链表第一个元素，初始化j为1
2.当j<i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，l累加1
3.若到链表末尾P为空，则说明第i个元素不存在
4.若查找成功，返回结点p的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//初始条件：1<= i <= ListLength(L)
//操作结果：查L中的第i个元素，并用e返回值
Status GetElem(LinkList L,int i , ElemType *e){
int j =1;//j为计数器
LinkList p;
p = L->next;
while(p&&j<i){
p = p->next;
++j;
}
if (!p || j>i){
return ERROR;
}
*e =p->data;
return OK;
}
|
元素的插入与删除：
1.插入
核心步骤：
1
2
|
s->next = p->next ;
p->next = s;
|
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
//初始条件：1<= i <= ListLength(L)
//操作结果：在L中的第i个元素前插入新的数据元素e，L长度+1
Status ListInsert(LinkList *L,int i ,ElemType e){
int j =1 ;
LinkList p,s;
p = *L;
//查找第i-1个元素
while(p&&j <1){
p= p->next;
++j;
}
if (!p||j >i){
return ERROR;
}
//生成新结点(c 标准函数)
s = (LinkList)malloc(sizeof(Node));
s->data= e;
//将p的后续结点赋值给s的后续结点
s->next = p->next;
p->next = s;
return OK;
}
|
2.删除
实际上就是一步：
1
|
p->next = p->next->next;
|
具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/* 初始条件：顺序线性表L已存在，1≤i≤
ListLength(L) */
/* 操作结果：删除L的第i个结点，并用e返回其
值，L的长度减1 */
Status ListDelete(LinkList *L,int i ,ElemType *e){
int j = 1;
LinkList p,q;
p = *L;
while(p->next &&j <i){
p = p->next;
++j;
}
if (!p->next || j >i){
return ERROR;
}
q = p->next;
p->next = q->next;
*e = q->data;
//系统回收该结点，释放内存
free(q);
return OK;
}
|
单链表的整表创建
1.头插法：
思路：
1.声明一个指针p和计数器变量i；
2.初始化一个空链表L；
3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表
4.循环： a.生成一新结点赋值给p；
b.随机生成一个数字赋值给p的数据域p->data;
c.将p插入到头结点与前一新节点之间。
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/* 随机产生n个元素的值，建立带表头结点的单链
线性表L（头插法） */
void CreateListHead(LinkList *L,int n ){
LinkList p;
int i ;
//初始化随机数种子
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for (i = 0;i<n;i++){
//生成新结点
p = (LinkList)malloc(sizeof(Node));
//随机生成100以内的数字
p->data = rand() % 100 +1;
p->next = (*L)->next;
//插入到表头
(*L)->next = p;
}
}
|
2.尾插法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void CreateListTail(LinkList *L,int n ){
LinkList p,r;
int i ;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for (i = 0;i<n;i++){
p = (Node*)malloc(sizeof(Node));
p->data = rand()%100 +1;
r->next = p;
r= p;
}
//表示当前链表结束
r->next = NULL;
}
|
整表删除：
思路：
1.声明指针p，q
2.将第一个结点赋值给p
3.循环：
a.将下一结点赋值给q
b.释放p
c.将q赋值给p
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/* 初始条件：顺序线性表L已存在，操作结果：将L
重置为空表 */
Status ClearList(LinkList *L){
LinkList p , q;
//p指向第一个结点
p = (*L) ->next;
while (p){
q = p ->next ;
free(p);
p = q;
}
//头结点指针域为空
(*L)->next = NULL;
return OK;
}
|