专业课数据结构笔记.docx

资源描述

专业课数据结构笔记.docx

《专业课数据结构笔记.docx》由会员分享，可在线阅读，更多相关《专业课数据结构笔记.docx（26页珍藏版）》请在冰点文库上搜索。

专业课数据结构笔记.docx

专业课数据结构笔记

（页面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）voidexam1（）{

n=2;

while（n%2==0）

n=n+2;

printf（“%d\n”,n）;

}

（2）voidexam2（）{

y=0;

x=5/y;

printf（“%d,%d”,x,y）;

}

违背了哪些特点：

答：

算法

（1）违反了有穷性，算法

（2）违反了可行性。

1.2.2算法描述

要求采用C/C++描述。

注意C++中的引用&。

eg1.inta=4;

int&b=a;

此时两个变量同步改变

eg2.voidswap（int&x,int&y）

{inttemp=x;

x=y;

y=temp;

}

执行swap（a,b）后，a、b值发生交换

如果将函数声明改成voidswap1（intx,inty），则swap1（a,b）不交换a、b的值。

在C语言中为了支持引用类型，采用指针方式回传行参的值：

voidswap（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，分析时间复杂度

voidMatrixAdd（intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]）

{inti,j;

for（i=0;i

for（j=0;j

C[i][j]=A[i][j]+B[i][j];

}

T（n）=O（n2）（不会输公式，省去了步骤）

eg3.分析时间复杂度

intfun（intn）{

inti,j,k,s;

s=0;

for（i=0;i<=n;i++）

for（j=0;j<=i;j++）

for（k=0;k<=j;k++）

s++;

}

T（n）=O（n3）

eg4.包含递归的情况（考研中最难的算法分析题，武大应该不会出）

voidfun（inta[],intn,intk）//a中有n个元素

{inti;

if（k==n-1）{

for（i=0;i

printf（“%d\n”,a[i]）;

else{

for（i=k;i

a[i]=a[i]+i*i;

fun（a,n,k+1）l

}

fun（a,n,0）调度，求时间复杂度。

设fun（a,n,0）执行时间T（n）,fun（a,n,k）执行时间T1（n,k）

T1（n,k）=nk=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个。

typedefstruct

{

ElemTypeelem[MaxSize];/*存放顺序表元素*/

intlength;/*存放顺序表的长度*/

}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单链表

每个结点只设一个指针域，指向后继结点。

typedefstructLNode

{

ElemTypedata;

structLNode*next;/*指向后继结点*/

}LinkList;

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

（图见p28）

题目没有特别声明，你设计时可以带或不带头结点（推荐带）

2.3.2单链表基本运算的实现

（1）建立单链表很重要！

a、头插法建表

voidCreateListF（LinkeList*&L,ElemTypea[],intn）

{LinkList*s,inti;

L=（LinkList*）malloc（sizeof（LinkList））;

L->next=NULL;//创建头结点

for（i=0;i

{s=（LinkList*）malloc（sizeof（LinkList））;

//创建新结点

s->data=a[i];s->next=L->next;

//将*s插在原表开始结点之前，头结点之后

L->next=s;

}

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

b、尾插法建表

voidCreateListR（LinkeList*&L,ElemTypea[],intn）

{LinkList*s,*r;inti;

L=（LinkList*）malloc（sizeof（LinkList））;

L->next=NULL;//创建头结点

r=L;//r始终指向终端结点，开始时指向头结点

for（i=0;i

{s=（LinkList*）malloc（sizeof（LinkList））;

//创建新结点

s->data=a[i];r->next=s;

r=s;

}

（2）插入结点

eg.设C={a1,b1,a2,b2,…,an,bn}为一线性表，采用带头结点hc单链表存放，编写一算法，拆分成两线性表（链表）

A={a1,a2,…,an}B={b1,b2,…,bn}

A、B下标均从1到n，采用尾插法建表

voidfun（LinkList*hc,LinkList*&ha,LinkList&hb）

{LinkList*p=hc->next,*ra,*rb;

ha=hc;//ha头结点利用hc头结点

ra=ha;//ra始终指向ha末尾结点

hb=（LinkList*）malloc（sizeof（LinkList））;

//创建hb头结点

rb=hb;//rb始终指向hb末尾结点

while（p!

=NULL）

{ra->next=p;ra=p;//将p链到ha单链表的末尾

p=p->next;

if（p!

=NULL）

{rb->next=p;//将p链到ha单链表的末尾

rb=p;

p=p->next;

}

ra->next=rb->next->NULL;//两个尾结点next域置空

}

2.3.3双链表

2.3.4循环链表

（以上两种链表均为单链表的转换，方法类似，老师没有细讲）

eg.编写出判断带头结点的双向循环链表L是否对称的算法（这块过的比较快，没有细记）

2.3.4有序表（只作了解）

所有元素以递增或递减的方式排列，有序表种不存在元素值相同的情况。

第三章栈和队列

3.1栈的定义……p44

3.1.1栈是一种只能在一端进行插入或删除操作的线性表。

eg.栈输入序列A、B、C、D，则借助一个栈所得的输出序列不可能是（D）

A、A,B,C,DB、D,C,B,AC、A,C,B,DD、D,A,B,C

eg.已知一个栈进栈序列1，2，3，……，n，其输出序列p1,p2,…,pn，若p1=n，则pi的值（C）

A、iB、n-iC、n-i+1D、不确定

3.1.2栈的顺序存储结构及其基本运算实现

结构：

typedefstructlinknode

{ElemTypedata;/*数据域*/

structlinknode*next;/*指针域*/

}LiStack;

（1）初始化栈initStack（&s）

voidInitStack（SqStack*&s）

{

s=（SqStack*）malloc（sizeof（SqStack））;

s->top=-1;//注意与书上的s->top=0;不同（这是老师的方法）

}

（2）销毁栈

（3）判栈为空

（4）进栈先移动栈指针

（5）出栈先取元素再减一

3.1.3栈的链式存储结构及其基本运算的实现

带头结点链栈（不存在栈满上溢的情况）

eg.设表达式允许包含圆括号、大括号，判断表达式括号是否配对。

p49

3.2队列……p58

（1）队列通常采用循环队列（数组）

rear指向队尾元素，front指队列元素前一位置。

队空条件front==rear

队满条件（rear+1）%MaxSize==front（只有进队时才判断队满，所以前面是rear后面是front）

队首指针进1：

front=（front+1）%MaxSize

rear=（rear+1）%MaxSize

eg.对顺序循环队列而言，若知道队首元素位置和队列中元素个数，队尾位置不知，求队列的基本运算（判空、判满、进队、出队）。

考点：

栈的概念（如求出栈序列），不考算法!

第四章串

4.1串基本概念……p70

串相等：

元素个数相同、对应位置元素相同。

子串：

任意个连续字符的子序列（含空，不包含自己）

eg.“abcde”有多少子串

解：

空串：

1个字符：

2个字符：

3个字符：

4个字符：

共1+2+3+4+5=15个子串

4.2串存储结构……p73

4.3串模式匹配……p79（不考KMP!

）

第五章数字和稀疏矩阵

5.1数组……p90

5.1.1数组的基本概念

5.1.2数组的存储结构

二维数组（行序/列序）方式存储

5.1.3特殊矩阵压缩存储

（1）对称矩阵（重点掌握下标对应关系及推导过程）

将a[1…n][1…n]映射到B[1…n（n+1）/2]（注意从1开始还是从0开始）

将a[i][j]映射到B[k]

对于aij，前面有i-1行，第i行在aij前有j-1个元素

k=1+2+…+i-1+j-1=（1+i-1）*（i-1）/2+j-1=i（i-1）/2+（j-1）

（2）稀疏矩阵

第七章树形结构（肯定有二叉树（非线索）算法题，在卷子里不会低于30%）

7.1树的基本概念……p118

7.1.1树的定义

（1）形式化定义T={K,R}

（2）递归定义

n（n>=0）个结点组成有限集合（T）

如果n=0，它是一棵空树，这是树的特例；

如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点，简称为根（root），其余结点可分为m（m>0）个互不相交的有限集T1,，T2，…，Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

7.1.2表示

7.1.3树的术语

掌握路径与路径长度，树中不是任意结点间都有路径（边有方向）

7.1.4基本运算

7.1.5遍历

先根遍历，后根遍历

7.1.6树的存储结构……p136

（1）双亲存储结构

（2）孩子存储结构

（3）孩子兄弟表示法

7.2二叉树概念和性质……p121

7.2.1概念

可以为空或由根结点和左右子树构成，子树有左右之分。

7.2.2五种基本形态……p123

7.2.3满二叉树叶子结点全在最下一层

注意：

二叉树与度为二的树不一样：

（1）二叉树左右子树不能颠倒

（2）度为2的树至少有一个结点度为2，而二叉树可以为空或只有一个结点。

7.2.4完全二叉树按满二叉树的结点顺序编号

7.2.5性质1～性质5注意推导过程

7.3二叉树存储结构……p126

7.3.1完全二叉树

可以采用顺序存储结构

非完全二叉树采用顺序存储结构，则对应的完全二叉树结点不存在，数组中用0代替

7.3.2二叉树链式存储结构

typedefstructnode

{ElemTypedata;/*数据元素*/

structnode*lchild;/*指向左孩子*/

structnode*rchild;/*指向右孩子*/

}BTNode;

7.4二叉树的遍历……p128（至关重要，算法题可能就有与遍历结合的综合题）

（1）、先序遍历

（2）、中序遍历

（3）、后序遍历

主要看递归实现

eg1.假设二叉树采用二叉链存储结构存储，试设计一个算法，输出一给定二叉树的所有叶子结点。

解：

所有叶子结点递归模型

f（b）：

不做任何事，b=NULL

f（b）：

输出*b的data域，*b为叶子结点

f（b）：

f（b->lchild）;f（b->rchild）*b为叶子结点

voidDispLeaf（BTNode*b）

{

if（b!

=NULL）

{//即将先根遍历中的处理函数改写

if（b->lchild==NULL&&b->rchild==NULL）

printf（“%c”,b->data）;

else

{

DispLeaf（b->lchild）;

DispLeaf（b->rchild）;

}

eg2编写BTNodeDepth（*b），求一二叉树的高度

递归模型：

f（NULL）=0

f（b）=MAX{f（b->lchild）,f（b->rchild）}+1

eg3.假设二叉树采用二叉链存储，判断两二叉树是否相似（即形状是否相同）

递归模型：

f（t1,t2）=true;t1=t2=NULL;

f（t1,t2）=false;t1、t2之一为NULL，另一个非NULL

f（t1,t2）=f（t1->lchild,t2->lchild）&f（t1->rchild,t2->rchild）;

注：

以上两题老师讲的比较快，没有记下程序，应该在他编的习题集上有这两个题。

eg.设二叉树二叉链存储，编写Level（），求p结点的层数

voidLevel（BTNode*b,BTNode*p,int&h,intlh）

//找到*p后，h为层次，否则为0

{if（b==NULL）h=0;//空树返回0

elseif（p==b）h=lh;//找到结点p

else

{Level（b->lchild,p,h,lh+1）;//左子树找

if（h==0）

Level（b->rchild,p,h,lh+1）;

}

eg4.输出从每个叶子结点到根结点路径

解法1：

层次遍历法

设计的队列为非循环顺序队列将所有已扫描过的结点指针进队，并在队列中保有双亲的位置。

voidAllPath（BTNode*b）

{structsnode

{BTNode*node;//存放当前结点指针

intparent;//存放双亲结点

}q[MaxSize];

intfront,rear,p;

front=rear=-1;

rear++;

q[rear].parent=1;

while（front

{front++;

b=q[front].node;//队头出队列

if（b->lchild==NULL&b->rchild==NULL）

p=front;

while（q[p].parent!

=-1）

{printf（“%c->”,q[p].node->data）;

p=q[p].parent;

}

printf（“%c\n”,q[p].node->data）;

}

if（b->lchild!

=NULL）//左孩子入队列

{rear++;q[rear].node=b->lchild;

q[rear].parent=front;}

if（b->rchild!

=NULL）//右孩子入队列

{rear++;q[rear].node=b->child;

q[rear].parent=front;

}

对于右图，队列结构为：

队列

node

parent

-1

输出：

DBA

解法2：

递归方法

path数组存放路径，pathlen存放路径长度。

调用f（b,path,pathlen）;b为叶子：

输出path值（b为叶子）。

调用f（b,path,pathlen）;b为其他情况：

将b->data放入path，pathlen++;调用f（b->lchild,path,pathlen）;f（b->rchild,path,pathlen）

7.5线索二叉树……p132

7.6哈夫曼树

定义：

构造过程：

p144～p146（注意没有度为1的结点）

通过哈夫曼编码画出哈夫曼树（或判断是否可以构成哈夫曼树）

第八章广义表（比较基本，老师没有讲）

第九章图（没有算法题，但是要注意概念）

9.1存储结构：

p160～p164

9.1.1邻接矩阵

（1）邻接矩阵表示唯一

（2）无向图邻接矩阵对称

9.1.2邻接表

（1）不唯一

（2）对于n个结点e条边，邻接表n个顶点2e条边

9.2图的遍历（核心内容，可能考简答或问题）

深度优先：

递归p168～p169

eg.对某个图的邻接表调用DFS（）函数，写出DFS的执行序列（即遍历的结点序列）

广度优先：

第十章查找

10.1线性表的查找……p216

（1）顺序查找有序

（2）二分查找不要求有序，掌握判定树

（3）分块查找

eg.对11个元素{2,3,10,15,20,25,28,29,30,35,40}进行二分查找

（1）查找20，依次与哪些元素比较？

（2）查找26，依次与哪些元素比较？

（3）成功平均查找长度？

不成功平均查找长度？

二分查找判定树

（1）比较25、10、15、20，共4次

（2）比较25、30、28，共3次

（3）ASLsucc=（1*1+2*2+4*3+4*4）/11=3

ASLunsucc=（4*3+8*4）/11=3.67

10.2树表的查找……p226（不考具体算法）

10.2.1平衡二叉树

（1）调整方法LL,LR,RL,RRp233～p236

eg.输入{16,3,7,11,9,26,18,14,15}，给出构造AVL的过程。

（图太多，不好画，习题集上应该有这道题）

10.3哈希表查找……p251

第十一章内排序（没有算法题，主要考基本题，注意算法间的比较）

比较表（里面的内容太多，没有时间抄）

时间复杂度

空间复杂度

稳定性

复杂性

直接插入

希尔

冒泡

快速

直接选择

堆

归并

基数

同时要了解算法的基本思路。

比如给定一个序列，判断是不是堆。

文件外排序，基本不考。

（随便看看就行了吧）

我的总结：

数据结构这块应该不难，算法题（即设计程序）主要在二叉树遍历、链表操作（涉及建表）等方面，把递归这样的设计方法掌握，关键要弄清楚概念，看书的时候仔细一些，像上面的一些概念题要注意。

老师说基本按自己的书（春保版数据结构）出题目，有他的教材、习题集最好。

他课件里面的“复习”要看看。

由于上课老师放幻灯，而且时间很紧，有些地方记得不太清楚、例子没记全，但绝大多数地方都没有漏，他强调的考点与不考的地方都没少。

他说不考的地方就不用看了，没有说的地方还是看一下（范围应该与“复习”差不多），强调的地方（特别是树）一定要熟练掌握。

后面时间比较紧，他说的比较少，但并不表示不重要，还是要仔细看看。

祝大家都能考出好成绩。

专业课计算机组成原理笔记

考3、4、5、6、7、10章，会达到2002年期末考试的水平。

一、数据编码与数据校验（就几分的题目）

1、数据编码

机器数：

一串二进制数……p64

真值：

机器数数值

1、机器原码……p64

定义

特性：

1、原码最高位符号位

[x]=x0<=x<1

=1-x-1<=x<=0

2、有正负0

3、取值范围：

字长有关

2、机器反码……p67

定义

特性：

1、反码最高位符号位

2、有正负0

3、取值范围

4、反码作运算循环进位

3、机器补码……p65

定义

展开阅读全文