数据结构重学笔记

数据结构重学笔记

数据的逻辑结构（参考《数据结构（C语言版），清华大学出版社，严蔚敏 吴伟民）

生活中我们要用到各种算法来处理一些问题，而如何用算法实现呢？
数据结构就成了描述算法必不可少的工具之一。

数据结构是相互之间存在一种或多种关系的集合 仅从关系的复杂情况来说，我们可以对于大部分数据的结构给予这样的分类

• 集合：数据元素除了“同属于一个集合“以外没有其他关系
  
• 线性结构：数据元素之间存在一对一的关系，举个，比如站成一排的小人，一个接着一个。
  
• 树形结构：数据元素之间存在一对多的关系，比如细胞的分裂，一个细胞分成两个，分裂出的那两个细胞分别继续分裂，每个细胞后面都对应两个元素，是典型的树形结构。
  

• 图状结构或网状结构：数据元素之间存在多对多的关系，就像一个城市的交通网，楼与楼之间的路线十分复杂，可以有很多种选择，你从你的家出发可以到达医院，也可以到达学校，而从很多地方也可以到达你的家，是典型的网状结构。
  

  数据结构的基本概念

• 数据：对客观事物的符号化表示，在计算机中通过一些代码映射出现实生活的事物，比如在学校的教务系统中，一个学号代表一个学生，计算机无法处理运算一个活人，但一个人的性别，年龄，学号等都可以处理，这些都可以作为数据，换一种说法，计算机可以处理的所有内容都是数据。数据往往映射现实生活的各种情况以及事物。
  

• 数据元素：是数据的基本单位，同样的以教务系统为例，学生与学生之间的关系可以用线性结构来储存成一个表，虽然在现实生活中这种关系并不存在，但是我们可以在计算机中通过这种关系进行存储从而方便增删查找和维护，这个时候，每个学生的信息都作为一个整体有序的存储在教务系统中，我们称每个学生我为数据元素。
  
• 数据项：数据不可分割的最小单位，比如学生的姓名、学号等在教务系统中是数据项，但是我们要注意，数据结构一般来表示数据元素之间的关系，我们将数据项组成数据元素，之后来定义数据结构。
  
• 数据对象：性质相同的数据元素的集合，是数据的一个子集，比如三年八班的学生作为全校师生的一个子集，在教务系统中，经常要以性别、班级、年级等作为标准来对一类的数据对象进行整体的操作。
  

• 数据结构：相互之间存在一种或多种关系的集合。例如教务系统中的学生，一般来讲是以线性关系来存储的，而导航地图一般而言是网状关系。
  

  数据结构的形式定义

  二元组 Data_Structure=(D,S)
  D：是数据的有限集，例如教务系统中的所有学生。
  S：是D上关系的有限集，例如教务系统中学生与学生之间用线性关系存储。
  如果该校有10000名学生，则有如下定义
  Student=(D,S)
  其中：
  D={D1,D2,D3 … D9998,D9999,D10000}
  S={P}
  P={〈Dn,D(n+1)〉,1≤n≤9999}

  数据的存储结构（物理结构）

  那么数据结构在计算机上如何实现呢？
  这里我们就要了解一下数据的存储结构（物理结构）了。

  存储结构（物理结构）是数据结构在计算机中的表示（映射）。 在普通的计算机中，表示信息的最小单位是二进制数的一位，0/1，它可以表示正反两种事件，可以表示小灯泡的开关，可以表示杯子里是否有水，可以表示物体静止还是运动。
  我们可以用若干位组合起来形成一个位串来表示数据元素。这个位串被称为元素或结点。但通常，我们的数据元素会由n个数据项组成，每个数据项通过一个位串表示，这个位串是元素的子位串，我们称之为数据域。

  顺序映像与顺序存储结构

  通常地，我们可以利用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
  比如相邻代表相关，利用一次相邻存储数据元素的方式得到一个线性结构。

  非顺序映像与链式存储结构

  在C语言或很多比较基础的编程语言中，都有“指针”这一概念，在指针中可以存储一个地址信息，我们在每个数据元素后定义一个指向与它有关的元素的指针，从而描述元素之间的关系。

  高级语言下虚拟的数据结构

  C语言是高级语言，屏蔽了一些基础的知识，使我们不能直接通过内存地址来描述数据结构，所以这里我们利用数组和指针来描述数据结构的方式不严谨，我们可以称之为虚拟存储结构。

  数据类型与抽象数据类型

  数据类型

  数据类型是与数据结构密切相关的一个概念。
  在高级语言中，我们使用数据类型来刻画操作对象的特征，来限制每个类型的数据，以便操作。例如int，char，long等……
  在高级程序语言中数据类型可分为两类：

• 原子类型：不可分割，如C语言的整数，字符。
  

• 结构类型：由若干个原子类型组成，比如C语言的数组、字符串。

  抽象数据类型ATD

  是指一个数学模型以及定义在该模型上的一组操作。由自身的逻辑特性，与如何实现无关，只要逻辑相同，它在用户的眼里就是相同的，比如同样是一个线性表，利用顺序存储还是链式存储对于用户来说实现的功能是一样的。

• 原子类型：1-100的整数
  
• 固定聚合类型：1-100的整数的集合
  

• 可变聚合类型：任意的有序的整数序列
  

  抽象数据类型的形式定义

  ADT=(D,S,P)
  描述方法（伪码）：
  ADT 抽象数据类型名{
  数据对象：<数据对象的定义>
  数据关系：<数据关系的定义>
  基本操作：<基本操作的定义>
  }ADT 抽象数据类型名

  抽象数据类型的实现

  define TRUE 1
  #define FALSE 0
  #define OK 1
  #define ERROR 0
  #define INFEASIBLE -1
  #define OVERFLOW -2
  //Status是函数的类型，其值是函数结果的状态代码
  typedef int Status;
  Status 函数名{
  //算法说明
  语句序列;
  }//函数名

  算法分析

  算法的特性

• 有穷性 一个算法必须总是（对于任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  

• 确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只能有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
  
• 可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
  
• 输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
  

• 输出 一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。
  

  算法设计的要求

  通常设计一个“好”的算法应考虑达到以下目标。

• 正确性 算法应当满足具体问题的需求。
  

• a 程序不含语法错误。
  b 程序对于几组输入数据能够得出满足规格说明要求的结果。
  c 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。
  * d 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
  通常以第c层意义的正确性作为衡量一个程序是否合格的标准。

• 可读性 算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
  
• 健壮性 当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
  
• 效率与低存储量需求 通俗地说，效率指的是算法执行的时间。存储量需求指算法执行的过程中所需要的最大存储空间。这与问题的规模有关，而且存在一些矛盾。
  

  算法效率的度量

  事后统计的办法

  很多计算机都有计时功能，有的可精确到毫秒级，但这种方式依赖于计算机的硬件、软件等环境因素，有时很容易掩盖算法本身的优劣。因此人们常常采用另一种事前估算的方法。

  事前估算的方法

  一个用高级语言编写的程序在计算机上运行所损耗的时间取决于下列因素。
  1. 依据的算法选用何种策略；
  2. 问题的规模；
  3. 书写程序的语言；
  4. 编译程序所产生的机器代码的质量；
  5. 机器执行指令的速度；
  显然，影响算法运行时间的因素有很多，当我们描述算法效率时，是否可以绕过他们呢？

  时间复杂度：T(n)=O(f(n))

  多数情况下，原操作是循环内最深处的操作，而算法的执行时间于该操作重复执行的次数成正比。

  算法的存储空间需求

  类似于算法的时间复杂度，称为空间复杂度
  S(n)=O(f(n))

  线性表的类型定义

  线性结构是一个数据元素的有序（次序）集合。 > “有序” 仅指在数据元素之间存在一个 “领先” 或“落后” 的次序关系，而非指数据元素 “值” 的大小可比性。

  线性结构的基本特征

  在数据元素的非空有限集中:
  1. 存在唯一的一个“第一个”数据元素；
  2. 存在唯一的一个“最后一个”数据元素；
  3. 除第一个之外，每个数据元素均只有“唯一的前驱”；
  4. 除最后一个之外，每个数据元素均只有“唯一的后继”。
  记为(a1,…,ai-1,ai,…an)

  抽象数据类型定义

  ADT List{
  数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
  数据关系：R1={|ai-1,ai∈D,i=2,3,4,…,n}
  基本操作：
  InitList(&L)
  操作结果：构造一个空的线性表L。
  DestroyList(&L)
  初始条件：线性表L已存在。
  操作结果：销毁线性表L。
  ClearList(&L)
  初始条件：线性表L已存在。
  操作结果：将L重置为空表。
  ListEmpty (L)
  初始条件：线性表L已存在。
  操作结果：若L为空表，则返回TRUE，否则返回FALSE。
  ListLength(L)
  初始条件：线性表L已存在。
  操作结果：返回L中数据元素的个数。
  GetElem(L,i,&e)
  初始条件：线性表L已存在，l≤i≤ListLength(L)。
  操作结果：用e返回L中第i个数据元素的值。
  LocateElem(L,e,compare())
  初始条件：线性表L已存在，compare()是数据元素的判定函数。
  操作结果：用e返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
  PriorElem(L,cur_e,&pre_e)
  初始条件：线性表L已存在。
  操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
  NextElem(L,cur_e,&next_e)
  初始条件：线性表L已存在。
  操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的前驱，否则操作失败，next_e无定义。
  ListInsert(&L,i,e)
  初始条件：线性表L已存在，l≤i≤ListLength(L)+1。
  操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.
  ListDelete(&L,i,&e)
  初始条件；线性表L已存在且非空，l≤i≤ListLength(L)。
  操作结果：删除L中第i个数据元素，并用e返回其值，L长度减1.
  ListTraverse(L,visit())
  初始条件：线性表L已存在。
  操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
  }ADT List

  线性表的顺序表示与实现（顺序表）

  头文件

  //
  // SqList.h
  // 数据结构
  //
  // Created by 随便一个名字 on 2019/1/21.
  // Copyright © 2019 随便一个名字. All rights reserved.
  //

ifndef SqList_h
#define SqList_h

include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函数的类型，其值是函数结果的状态代码
typedef int Status;
typedef int ElemType;

define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct{
ElemType elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList );
Status DestroyList_Sq(SqList );
Status ClearList_Sq(SqList );
Status ListEmpty_Sq(SqList);
Status ListLength_Sq(SqList);
Status GetElem_Sq(SqList,int,ElemType );
Status PriorElem_Sq(SqList,ElemType,ElemType );
Status NextElem_Sq(SqList,ElemType,ElemType );
Status ListInsert_Sq(SqList ,int,ElemType);
Status ListDelete_Sq(SqList ,int,ElemType );
#endif / SqList_h /

函数.c

//
// SqList.c
// 数据结构
//
// Created by 啊啊啊 on 2019/1/21.
// Copyright © 2019 啊啊啊. All rights reserved.
//

include “SqList.h”

Status InitList_Sq(SqList L){
//构造一个空的线性表
L->elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L->elem) exit(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}//InitList_Sq

Status DestroyList_Sq(SqList L){
//销毁线性表
if(L->elem==NULL)
return ERROR;
free (L->elem);
L->length=0;
L->listsize=0;
return OK;
}
Status ClearList_Sq(SqList L){
//清空线性表
if(L->listsize==0)
return ERROR;
int i;
for(i=0;ilength;i++){
L->elem[i]=0;
}
L->length=0;
return OK;
}
Status ListEmpty_Sq(SqList L){
// 线性表判空
if(L.listsize==0)
return ERROR;
else if(L.length==0){
return TRUE;
}
else return FALSE;
}
Status ListLength_Sq(SqList L){
//线性表长度
if(L.listsize==0)
return ERROR;
return L.length;
}
Status GetElem_Sq(SqList L,int i,ElemType e){
//线性表查询
if(L.listsize==0)
return ERROR;
if(i<1&&i>L.length)
return ERROR;
else {
e=L.elem[i-1];
return OK;
}
}
Status PriorElem_Sq(SqList L,ElemType cur_e,ElemType pre_e){
//查询前驱
if(L.listsize==0)
return ERROR;
int i;
for(i=0;iif(L.elem[i]==cur_e){
if(i!=0) {
pre_e=L.elem[i-1];
}
}
}
return OK;
}
Status NextElem_Sq(SqList L,ElemType cur_e,ElemType next_e){
//查询后继
if(L.listsize==0)
return ERROR;
int i;
for(i=0;iif(L.elem[i]==cur_e){
if(i!=L.length-1) {
next_e=L.elem[i+1];
}
}
}
return OK;
}
Status ListInsert_Sq(SqList L,int i,ElemType e){
//插入元素
if(L->listsize==0)
return ERROR;
if(i<1&&i>L->length+1)
return ERROR;
if(L->listsize==L->length){
ElemType newbase;
newbase=(ElemType )realloc(L->elem,(L->listsize+LISTINCREMENT)sizeof(ElemType));
L->elem=newbase;
L->listsize=L->listsize+LISTINCREMENT;
}
int j;
for(j=L->length+1;j>i;j—)
L->elem[j-1]=L->elem[j-2];
L->elem[i-1]=e;
L->length+=1;
return OK;
}
Status ListDelete_Sq(SqList L,int i,ElemType e){
//删除元素
if(L->listsize==0)
return ERROR;
if(i<1&&i>L->length)
return ERROR;
*e=L->elem[i-1];
int j;
for(j=i;jlength;j++)
L->elem[j-1]=L->elem[j];
L->elem[L->length-1]=0;
L->length-=1;
return OK;
}

main.c

//
// main.c
// 数据结构
//
// Created by 我滴妈呀 on 2019/1/20.
// Copyright © 2019 我滴妈呀. All rights reserved.
//

include
#include “SqList.h”

int main(int argc, const char * argv[]) {
// insert code here…
printf(“Hello, World!\n”);
SqList L;
printf(“即将构建一个空的线性表…”);
InitList_Sq(&L);
printf(“\n构建成功”);
int i;
printf(“请输入要插入的元素数目：”);
scanf(“%d”,&i);
int j;
ElemType e;
for(j=0;jprintf(“请输入要插入的第%d个值：”,j+1);
scanf(“%d”,&e);
ListInsert_Sq(&L, j+1, e);
}
printf(“\n输出线性表中所有元素：”);
for(i=0;iGetElem_Sq(L, i+1, &e);
printf(“%d “,e);
}
printf(“\n请输入要删除的元素位置：”);
scanf(“%d”,&i);
ListDelete_Sq(&L, i, &e);
printf(“\n删除成功，删除了第%d个元素，元素值为%d”,i,e);
printf(“\n输出线性表中所有元素：”);
for(i=0;iGetElem_Sq(L, i+1, &e);
printf(“%d “,e);
}
printf(“\n这个线性表是否是空表？”);
i=ListEmpty_Sq(L);
if(i==TRUE) printf(“\n这个线性表是空表”);
else printf(“\n这个线性表不是空表”);
printf(“\n正在清空线性表…”);
ClearList_Sq(&L);
printf(“\n清空线性表”);
printf(“\n这个线性表是否是空表？”);
i=ListEmpty_Sq(L);
if(i==TRUE) printf(“\n这个线性表是空表”);
else printf(“\n这个线性表不是空表”);
printf(“\n正在销毁线性表…”);
DestroyList_Sq(&L);
printf(“\n销毁成功”);
return 0;
}
——————————————————更新分界线哈哈哈

关于函数指针与剩下书里有但上次没实现的顺序线性表的基本操作

有一个人评论我提问我指针的一些问题，我想说的是……
我也不太明白哈哈哈哈哈哈，顺序表的基本操作有几个是把函数作为参数传进基本操作里，我看一眼当时就蒙圈了哈哈哈哈哈
为此我就钻研了一番，终于研究明白了，学c语言的时候指针这就稀里糊涂。

指针与地址（* 与 &）

指针是什么，大家都有所耳闻，就是指向一个数据的地址的一个变量，换句话说，指针里面存的是另一个数据的地址信息。
指针的定义大家习惯两种写法，
int q;
int q;
大多数人对于符号犯浑，但这里一眼就能看明白这个是什么意思了。
q是int类型的一个量，是q指向的int型变量，而q是指针变量，我认为严格来讲，计算机理解的定义指针还是第二个比较规范一点。
所以，我们时常定义完指针（假如指针指向一个变量名为a的变量）q是一个整数，就是a的值，而q是a的地址。
q=&a;
q=a;
这样一来函数传参时怎么回事大家就都明白啦哈哈哈哈哈
int abcdef(int p){
我是一堆代码;
}//定义函数时，定义的是一个整数型指针p
int main(){
我是一堆代码;
abcdef(&a);//传参时，将a的地址传进去，也就是说这时，p=&a;所以要写取地址符号
}
指针的好处是无论是对q的操作还是对a的操作，a的值都会发生改变，他们两个是连带的，就相当于给笔记本电脑外接一个新的键盘鼠标，这个时候在函数里面的改变就相当于函数外面的a也变了。

函数指针

好了重头戏来了，也是我为什么又看了一遍指针的原因……
我有这样一个需求，就是将函数作为参数传进去，之后可以在另一个函数中用这个函数。
好刺激，看到书上基本操作有这种事的时候我就有撕书的冲动了哈哈哈哈。
有啥事，不懂就问度娘啊，我抱着虚心求学的态度和度娘进行了亲切的交流。
放假了，学校的老师肯定是不肯理你的，这个时候度娘就显得尤为的重要哈哈哈哈哈。
函数指针，顾名思义，就是函数的指针，指针里存着这个函数的地址，很好理解。
int (*abcdef)(一堆参数);
那么多括号长的特可爱，这个时候abcdef就是一个函数指针了，函数里面也可以调用这个函数了，一会我把顺序表里的那两个瘆人的例子作为这个函数指针的例子大家就都能看明白了哈哈哈哈。

指针函数

与函数指针不同的，指针函数是指针的函数，也就是说返回值是指针的函数，函数等于一个指针，大概就是这么一个东西。
int abcdef(我是一堆参数);
这个时候就可以return一个int变量了不是吗，就因为这个，所以上面的那个函数指针才要加上括号啊，不然容易闹误会了是不是哈哈哈哈

数组指针和指针数组

关于这个问题……
没查，不会
好嗨呦！用到哪查到哪哈哈哈哈哈哈哈
好了那两个函数我就接过来了
Status LocateElem_Sq(SqList L,ElemType e,Status(compare)(ElemType,ElemType)){
//判定
ElemType p;
int i=1;
p=L.elem;
while(i<=L.length&&!compare(p++,e))
++i;
if(i<=L.length)
return i;
else
return 0;
}
void ListTraverse_Sq(SqList L,void(vi)(ElemType)){
ElemType p;
int i;
p=L.elem;
for(i=1;i<=L.length;i++)
vi(p++);
printf(“\n”);
}

————————————————————————————————更新

顺序表的合并算法

好嗨呦
以我挂科的经验来看，这应该是本书中最简单的代码题考点了哈哈哈哈哈，（然而可能我并没有答对）害羞
第一道书上原装题，超简单的

假设利用两个线性表La和Lb分别表示两个集合A和B（即线性表中的数据元素即为集合中的成员），现要求一个新的集合A=A∪B。 分析：也就是要求扩大线性表La，使存在于Lb但不存在于La中的数据元素插入到线性表La中。
Status listequal(ElemType a1,ElemType a2){
if(a1==a2) return TRUE;
else return FALSE;
}
Status (equal)(ElemType,ElemType);
void Union(SqList La,SqList Lb){
//求线性表长度
int La_len=ListLength_Sq(La);
int Lb_len=ListLength_Sq(Lb);
int i;
int e;
equal=listequal;
for (i=1;i{
GetElem_Sq(Lb, i, &e);
if(!LocateElem_Sq(La, e, equal)) ListInsert_Sq(La, ++La_len, e);
}
}
第二道题也很简单
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减排列。
void MergeList(SqList La,SqList Lb,SqList *Lc){
InitList_Sq(Lc);
int i=1;
int j=1;
int k=0;
int La_len=ListLength_Sq(La);
int Lb_len=ListLength_Sq(Lb);
ElemType ai;
ElemType bj;
while((i<=La_len)&&(j<=Lb_len)){
GetElem_Sq(La, i, &ai);
GetElem_Sq(Lb, j, &bj);
if(ai<=bj){
ListInsert_Sq(Lc, ++k, ai);
++i;
}
else {
ListInsert_Sq(Lc, ++k, bj);
++j;
}
}
while(i<=La_len){
GetElem_Sq(La, i++, &ai);
ListInsert_Sq(Lc, ++k, ai);
}
while(j<=Lb_len){
GetElem_Sq(Lb, j++, &bj);
ListInsert_Sq(Lc, ++k, bj);
}
}//MergeList
Measure
Measure