专业课数据结构笔记

专业课数据结构笔记

（页面pXX对应于严版《数据结构》） 第一章 绪论

1.1 什么是数据结构 ?? p4 1.1.1数据结构的定义

数据： 数据元素：

数据结构：指数据以及相互之间的联系，包括： （1）数据的逻辑结构。

（2）数据的存储结构（物理结构）。 （3）施加在该数据上的运算。

同样的运算，不同的存储结构中，其实现的过程是不同的。 同样的一个逻辑结构对应的物理结构可以不同。 1.1.2 逻辑结构类型 （1）线性结构 （2）非线性结构： 1）树形结构 2）图形结构 1.1.3 存储结构类型 （1）顺序存储方法 （2）链式存储方法 （3）索引存储方法 （4）散列存储方法

1.2 算法及其描述 ?? p13 1.2.1 什么是算法 算法定义： 五个特点：

eg. 考虑下面两段描述 （1）void exam1() { n=2; while(n%2==0) n=n+2; printf(“%d\\n”,n); } （2）void exam2() { y=0; x=5/y; printf(“%d,%d”,x,y); } 违背了哪些特点： 答：算法（1）违反了有穷性，算法（2）违反了可行性。 1.2.2算法描述

要求采用C/C++描述。 注意C++中的引用&。 eg1. int a=4; int &b=a;

此时两个变量同步改变

eg2. void swap(int& x, int& y) { int temp=x; x=y; y=temp; }

执行swap(a,b)后，a、b值发生交换

如果将函数声明改成void swap1(int x, int y)，则swap1(a,b)不交换a、b的值。

在C语言中为了支持引用类型，采用指针方式回传行参的值：void swap(int *x, int *y)

1.3 算法分析 ?? p14 1.3.1时间复杂度

定义：指其基本运算在算法中重复执行的次数。

算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n)) f(n)是正常数n的一个函数，存在正常数M使n>=n0时，|T(n)|<=M*|f(n)| eg1. T(n)=3n2-5n+10000=O(n2)

eg2. 求两n阶方阵和C=A+B，分析时间复杂度 void MatrixAdd(int n, int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX]) { int i,j; for(i=0;i

eg4. 包含递归的情况（考研中最难的算法分析题，武大应该不会出） void fun(int a[], int n, int k) //a中有n个元素 { int i; if(k==n-1) { for(i=0;i

else { for(i=k;i

fun(a,n,0)调度，求时间复杂度。

设fun(a,n,0)执行时间T(n),fun(a,n,k)执行时间T1(n,k) T1(n,k)=n k=n-1时 T1(n,k)=(n-k)+T1(n,k+1) 其他情况 则

T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2) =…=n+(n-1)+…+2+T1(n,n-1) =n+(n-1)+…+2+n =O(n2)

T(n) =O(n2)

1.3.2 空间复杂度 临时占用的空间的大小 对于eg2，临时空间i,j（没有n,数组A,B,C）,空间复杂度O(1)。

第二章 线性表

2.1 线性表的基本概念 ?? p19

2.1.1 线性表：线性表是具有相同特性的数据元素的一个有限序列。

2.2.2 线性表的运算（不用死记硬背，要理解，主要重视后面具体物理结构中的实现） （1）初始化 （2）销毁 ??

2.2 线性表的顺序存储 ?? p21 2.2.1 顺序表

线性表中第一个元素的存储位置，就是指定的存储位置，第i+1个元素（1<=i<=n-1）紧邻着第i个。 typedef struct { ElemType elem[MaxSize]; /*存放顺序表元素*/ int length; /*存放顺序表的长度*/ } SqList;

2.2.2 顺序表基本运算的实现

插入数据元素ListInsert(L,i,e) ?? p24

在L的第i个位置(1<=i<=ListLength(L)+1)插入新元素e

时间复杂度：插入数据元素算法元素移动的次数不仅与表长n有关 ；插入一个元素时所需移动元素的平均次数 n／2。平均时间复杂度为O(n)。 （具体推导过程见书p21） 删除数据元素ListDelete(L,i,e) ?? p24

时间复杂度：删除数据元素算法元素移动的次数也与表长n有关 。删除一个元素时所需移

动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。 （这块的时间复杂度要记住具体的值，不仅是O(n)） 2.3 线性表的链式存储 ?? p27 2.3.1 单链表

每个结点只设一个指针域，指向后继结点。 typedef struct LNode { ElemType data;

struct LNode *next; /*指向后继结点*/ } LinkList;

在线性链表中，为了方便插入和删除算法，每个链表带一个投结点，通过该头结点唯一标识链表。（图见p28）

题目没有特别声明，你设计时可以带或不带头结点（推荐带） 2.3.2 单链表基本运算的实现 （1）建立单链表 很重要！ a、头插法建表

void CreateListF(LinkeList* &L, ElemType a[], int n) { LinkList *s,int i; L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL; //创建头结点 for(i=0;idata=a[i];s->next=L->next; //将*s插在原表开始结点之前，头结点之后 L->next=s; } }

上面的方法使链表中实际元素顺序为插入顺序的逆序。 b、尾插法建表

void CreateListR(LinkeList* &L, ElemType a[], int n) { LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(LinkList)); L->next=NULL; //创建头结点 r=L; //r始终指向终端结点，开始时指向头结点 for(i=0;idata=a[i];r->next=s; r=s; } }

（2）插入结点