数据结构 C语言版|第2版-复习

第1章 绪论

1.2基本概念和术语

1.2.1数据、数据元素、数据项和数据对象

数据是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位。数据元素通常用于完整地描述一个对象。例如一名学生记录。

数据项是组成数据元素的、有独立含义的、不可分割的最小单位。例如学生基本信息表中的学号、姓名、性别等。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

1.2.2数据结构

数据结构是相互之间存在一种或多种特定关系（“结构”）的数据元素的集合。

数据结构包括逻辑结构和存储结构两个层次。

1.逻辑结构

（1） 集合结构

（2） 线性结构

（3） 树结构

（4） 图结构或网状结构

其中集合结构、树结构和图结构都属于非线性结构。

线性结构包括线性表、栈和队列、字符串、数组、广义表。

非线性结构包括树和二叉树、有向图和无向图。

2.存储结构

（1） 顺序存储结构

（2） 链式存储结构

1.4.1算法的定义及特性

算法是为了解决某类问题而规定的一个有限长的操作序列。

一个算法必须满足一下五个重要特性：

（1） 有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。

（2） 确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。

（3） 可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

（4） 输入。一个算法有零个或多个输入。

（5） 输出。一个算法有一个或多个输出。

1.4.3算法的时间复杂度

算法的时间复杂度取决于问题的规模和待处理数据的初态。

一般情况下，算法中基本语句重复执行的次数是时间规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。

若f(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则T(n)=O(nm)。

1.4.4算法的空间复杂度

关于算法的存储空间需求，类似于算法的时间复杂度，我们采用渐进空间复杂度作为算法所需存储空间的量度，简称空间复杂度，它也是问题规模n的函数，记作：S(n)=O(f(n))。

若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)。

第2章 线性表

线性表特征：线性结构的基本特点是除第一个元素无直接前驱，最后一个元素无直接后继外，其他每个数据元素都有一个前驱和后继。

2.1线性表的定义和特点

由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表（同一性、有穷性、有序性）。

线性表中元素的个数 n(n>=0)定义为线性表的长度，n=0时称为空表。

2.4线性表的顺序表示和实现

2.4.1线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构。

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址（基地址）作为数据元素的存储起始位置。

线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l

第i+1个数据元素的存储位置和第i个数据元素的存储位置满足：LOC(ai+1)=LOC(ai)+l。

只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

2.4.2顺序表中基本操作的实现

1.初始化

Status InitList(SqList &L) {     L.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间 if(!L.elem) exit(OVERFLOW);     L.length=0; //当前长度为0，为空表 return OK; } 

2.取值

elem[i-1]单元存储第i个数据元素。

Status GetElem(SqList L,int I,ElemType &e) { if(i<1||i>L.length) return ERROR;     e=L.elem[i-1]; return OK; } 

取值算法的时间复杂度为O(l)。

3.查找

int LocateElem(SqList L,ElemType e) { for(i=0;i<L.length;i++) if(L.elem[i]==e) return i+1; //查找成功，返回序号i+1 return 0; //查找失败，返回0 } 

平均查找长度ASL=(n+1)/2,平均时间复杂度为O(n)。

4.插入

Status ListInsert(SqList &L,int i,ElemType e) { if((i<1)||(i>L.length+1)) return ERROR; //i不合法 if(L.length==MAXSZIE) return ERROR; //存储空间已满 for(j=L.length-1;j>=i-1;j--)        L.elem[j+1]=L.elem[j]; //插入位置后的元素后移     L.elem[i-1]=e; //新元素e放入第i个位置 ++L.length; //表长加1 return OK; } 

所需移动元素次数的期望值Eins=n/2，插入算法的平均时间复杂度为O(n)。

5.删除

Status ListDelete(SqList &L,int i) { if((i<1)||(i>L.length)) return ERROR; //i不合法 for(j=i;j<L.length-1;j++)        L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK; } 

所移动元素的期望值Edel=(n-1)/2,删除算法的平均时间复杂度O(n)。

2.5线性表的链式表示和实现

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。元素本身的信息和指示其直接后继的信息组成数据元素ai的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

链表增加头节点的作用：（1）便于首元结点的处理（2）便于空表和非空表的统一处理。

2.5.2单链表基本操作的实现

操作特点：顺链操作，指针保留

1.初始化

Status InitList(LinkList &L) {     L=new LNode;     L->next=NULL; return OK; } 

2.取值

Status GetElem(LinkList L,int i,ElemType &e) //取序号为i的元素的值 {     p=L->next;     j=1; while(p&&j<i) //p为空或p指向第i个元素跳出循环  {        p=p->next; ++j; } if(!p||j>i) return ERROR; //i>n或i<=0，不合法     e=p->data; return OK; } 

平均查找长度ASL=(n-1)/2，平均时间复杂度为O(n)。

3.查找

分为按序号查找和按值查找，从链表的首元结点出发（只能顺链查找）。

按值查找：

LNode *LocateElem(LinkList L,ElemType e) {     p=L->next; while(p&&p->data!=e) //p为空或p结点的数据域等于e跳出循环        p=p->next; return p; } 

平均时间复杂度为O(n)。

4.插入

Status ListInsert(LinkList &L,int i,ElemType e) {     p=L;     j=0; while(p&&(j<i-1)) {p=p->next;++j;} if(!p||j>i-1) return ERROR;     s=new LNode;     s->data=e;     s->next=p->next;     p->next=s; return OK; } 

平均时间复杂度为O(n)。

5.删除

Status ListDelete(LinkList &L,int i) {     p=L;     j=0; while((p->next)&&(j<i-1)) //查找第i-1个结点 {p=p->next;++j;} if(!(p->next)||(j>i-1)) return ERROR; //i>n或i<1删除位置不合法     q=p->next;     p->next=q->next; // p->next=p->next->next     delete q; return OK; } 

平均时间复杂度为O(n)。

6.创建单链表

（1）前插法/头插法

void CreateList_H(LinkList &L,int n) {     L=new LNode;     L->next=NULL; for(i=0;i<n;++i) {  p=new LNode;  cin>>p->data;  p->next=L->next;  L->next=p; //p插入到头结点之后 } } 

时间复杂度为O(n)。

（2）后插法/尾插法

Void CreateList_R(LinkList &L,int n) {     L=new LNode;     L->next=NULL;     r=L; //尾指针r指向头结点 for(i=0;i<n;++i) {  p=new LNode;  cin>>p->data;  p->next=NULL;  r->next=p; //新节点p插入尾结点r之后  r=p; //r指向新的尾结点p } } 

时间复杂度为O(n)。

2.5.3循环链表

其特点是表中最后一个结点的指针域指向头结点（首尾相接）。

判别当前指针p是否指向表尾结点的终止条件为p!=L或p->next!=L。

2.5.4双向链表

在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

插入：

Status ListInsert_Dul(DuLinkList &L,int i,ElemType e) { //在第i个位置之前插入元素e if(!(p=GetElem_Dul(L,i))) return ERROR; //第i个元素不存在     s=new DulNode;     s->data=e;     s->prior=p->prior;     p->prior->next=s;     s->next=p;     p->prior=s; return OK; } 

删除：

Status ListDelete_Dul(DuLinkList &L,int i) { //删除第i个元素 if(!(p=GetElem_Dul(L,i))) return ERROR; //第i个元素不存在     p->prior->next=p->next;     p->next->prior=p->prior;     delete p; return OK; } 

2.6顺序表和链表的比较

2.6.1空间性能的比较

（1）存储空间的分配

当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。

（2）存储密度的大小

存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比。存储密度越大，存储空间的利用率就越高。顺序表的存储密度为1，而链表的存储密度小于1。

当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表为存储结构。

2.6.2时间性能比较

（1）存取元素的效率

若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。

（2）插入和删除操作的效率

对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。

第3章 栈和队列

运算的位置限定在表的端点。数据元素可是任意类型，但必须属于同一个数据对象，数据之间是线性关系。

3.1.1栈的定义和特点

栈是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈。栈又称为后进先出的线性表。

3.1.2队列的定义和特点

队列是一种先进先出的线性表。只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。

3.3栈的表示和操作的实现

3.3.2顺序栈的表示和实现

顺序栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。指针top指示栈顶元素（top=0/-1表示空栈），指针base指示栈底元素。当top和base的值相等时，表示空栈。

栈空时，top和base的值相等；栈非空时，top始终指向栈顶元素的上一个位置。

1.初始化

Status InitStack(SqStack &S) {     S.base=new SElemType[MAXSIZE]; if(!S.base) exit(OVERFLOW);     S.top=S.base;     S.stacksize=MAXSIZE; return OK; } 

2.入栈

Status Push(SqStack &S,SElemType e) { if(S.top-S.base==S.stacksize) return ERROR; //栈满 *S.top++=e; //*S.top=e; S.top++; e压入栈顶，栈顶指针加1 return OK; } 

3.出栈

Status Pop(SqStack &S,SElemType &e) { if(S.top==S.base) return ERROR; //栈空     e=*--S.top; //S.top--;e=*S.top; 栈顶指针减1，栈顶元素赋给e return OK; } 

4.取栈顶元素

SElmType GetTop(SqStack &S) { if(S.top！=S.base) //栈非空 return *(S.top-1); //返回栈顶元素的值，栈顶指针不变 } 

3.3.3链栈的表示和实现

以链表的头部作为栈顶，无需附加头结点。

1. 链栈的初始化

Status InitStack(LinkStack &S) {     S=NULL; return OK; } 

2. 链栈的入栈

Status Push(LinkStack &S,SElemType e) {     p=new StackNode;     p->data=e;     p->next=S; //新节点插入栈顶     S=p; //栈顶指针指向p return OK; } 

3. 链栈的出栈

Status Pop(LinkStack &S,SElemType &e) { if(S==NULL) return ERROR; //栈空     e=S->data; //栈顶元素赋给e     p=S;     S=S->next; //修改栈顶指针     delete p; return OK; } 

4.取链栈的栈顶元素

SElmType GetTop(LinkStack S) { if(S!=NULL) return S->data; //返回栈顶元素的值，栈顶指针不变 } 

两栈共享技术：两栈共享栈空间。

3.4栈与递归

3.4.1采用递归算法解决的问题

若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称它们是递归的。

一个递归算法必须包括终止条件和递归部分。

3.5队列的表示和操作的实现

3.5.2循环队列——队列的顺序表示和实现

附设两个整型变量front和rear分别指示队列头元素及队列尾元素的位置。

约定：初始化创建空队列时，令front=rear=0，每当插入新的队列尾元素时，尾指针rear增1；每当删除队列头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

为解决上述约定的“假溢出”问题，将顺序队列变为一个环状的空间，称之为循环队列。头、尾指针 “依环状增1”的操作可用“模”运算来实现。

循环队列不能以头、尾指针的值是否相同来判断队列空间是“满”还是“空”，如何区分队满还是队空，通常有以下两种处理方法：

（1）少用一个元素空间，即队列空间大小为m时，有m-1个元素就认为是队满；当头、尾指针的值相同时，则认为队空。

队空的条件：Q.front==Q.rear

队满的条件：(Q.rear+1)%MAXSIZE==Q.front

(2)另设一个标志位以区别队列是“空”还是“满”。

1.循环队列的初始化

Status InitQueue(SqQueue &Q) {     Q.base=new QElemType[MAXSIZE]; if(!Q.base) exit(OVERFLOW);     Q.front=Q.rear=0; return OK; } 

2.求循环队列的长度

int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } 

3.循环队列的入队

Status EnQueue(SqQueue &Q,QElemType e) { if((Q.rear+1)%MAXSIZE==Q.front) //队满 return ERROR;     Q.base[Q.rear]=e; //e入队尾     Q.rear=(Q.rear+1)%MAXSIZE; //队尾指针加1 return OK; } 

4.循环队列的出队

Status DeQueue(SqQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; //队空     e=Q.base[Q.front]; //取队头元素     Q.front=(Q.front+1)%MAXSIZE; //队头指针加1 return OK; } 

5.取循环队列的队头元素

SElemType GetHead(SqQueue Q) { if(Q.front!=Q.rear) //队非空 return Q.base[Q.front]; //取队头元素的值，队头指针不变 } 

3.5.3链队——队列的链式表示和实现

一个链队需要两个分别指向队头和队尾的指针才能唯一确定，给链队天骄一个头结点，并令头指针始终指向头结点。

1.链队的初始化

Status InitQueue(LinkQueue &Q) {     Q.front=Q.rear=new QNode; //队头和队尾的指针指向头结点     Q.front->next=NULL; return OK; } 

2.链队的入队

Status EnQueue(LinkQueue &Q,QElemType e) {     p=new QNode;     p->data=e;     p->next=NULL;     Q.rear->next=p; //新节点插到队尾     Q.rear=p; //修改队尾指针 return OK: } 

3.链队的出队

Status DeQueue(LinkQueue &Q,QElemType &e) { if(Q.front==Q.rear) return ERROR; //队空     p=Q.front->next;     e=p->data; //取队头元素     Q.front->next=p->next; //修改头结点的指针域 if(Q.rear==p) Q.rear=Q.front; //最后一个元素被删，队尾指针指向头结点     delete p; return OK; } 

4.取链队的队头元素

SElemType GetHead(LinkQueue Q) { if(Q.front!=Q.rear) //队非空 return Q.front->next->data; //返回队头元素，队头指针不变 } 

第4章 串、数组和广义表

4.1串的定义

串（或字符串）是由零个或多个字符组成的有限序列。一般记为

s=“a1a2…an” (n>=0)

其中，s是串的名，用双引号括起来的字符序列是串的值；ai(1<=i<=n)（单字符）可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串，其长度为零。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。

称两个串是相等的，当且仅当这两个串的值相等。只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。

4.3串的类型定义、存储结构及其运算

4.3.2串的存储结构（顺序串，堆串，块链串）

1.串的顺序存储

#define MAXLEN 255  //串的最大长度 typedef struct{ char ch[MAXLEN+1]; //存储串的一维数组 int length; //串的当前长度 }SString; 

2.串的堆式顺序存储

typedef struct{ char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL int length; //串的当前长度 }HString; 

3.串的链式存储

#define CHUNKSIZE 80  //可由用户定义的块大小 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; typedef struct{ Chunk *head,*tail; //串的头和尾指针 int length; //串的当前长度 }LString; 

存储密度小，运算处理方便，然而存储占用量大。

4.3.3串的模式匹配算法

子串的定位运算通常称为串的模式匹配或串匹配。

1.BF算法

int Index_BF(SString S,SString T,int pos) { //返回子串T在主串S中从第pos个字符开始第一次出现的位置     i=pos;     j=1; while(i<=S.length&&j<=T.length) { if(S.ch[i]==T.ch[j]) {++i;++j;} else {i=i-j+2;j=1;} } if(j>T.length) return i-T.length; else return 0; } 

设主串长度为n，子串的长度为m，最好的情况下匹配成功的平均比较次数为(n+m)/2，时间复杂度为O(n+m)；最坏的情况下匹配成功的平均比较次数为m*(n-m+2)/2，时间复杂度为O(n*m)。

2.KMP算法

int Index_KMP(SString S,SString T,int pos) { //利用模式串T的next函数求T在主串S中从第pos个字符之后的位置     i=pos;     j=1; while(i<=S.length&&j<=T.length) { if(j==0&&S.ch[i]==T.ch[j]) {++i;++j;} else {j=next[j]}; } if(j>T.length) return i-T.length; else return 0; } 

计算next函数值：

void get_next(SString T,int next[]) {     i=1;     next[1]=0;     j=0; while(i<T.length) { if(j==0||T.ch[i]==T.ch[j]) {++i;++j;next[i]=j;} else j=next[j]; } } 

计算next函数修正值：

void get_nextval(SString T,int nextval[]) {     i=1;     nextval[1]=0;     j=0; while(i<T.length) { if(j==0||T.ch[i]==T.ch[j]) { ++i; ++j; if(T.ch[i]!=T.ch[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } } 

next数组计算：

next[1]=-1:next[i]为模式串第i-1个字符前与前缀匹配的字符串长度。

Next[1]=0:Next[i]=next[i]+1。

nextval数组计算：

nextval[1]=-1/0。

当T.ch[i]==T.ch[next[i]]时，nextval[i]=nextval[next[i]];

当T.ch[i]!=T.ch[next[i]]时，nextval[i]= next[i]。

4.4数组

数组时由类型相同的数据元素构成的有序集合。数组是线性表的原因：ai是单元素或者ai是带有结构信息的元素。

4.4.2数组的顺序存储

采用顺序存储结构表示数组比较合适。

对二维数组可有两种存储方式：一种是以列序为主序的存储方式；一种是以行序为主序的存储方式。

以行序为主序的存储结构：每个数据元素占L个存储单元，二维数组A[0…m-1,0…n-1]中任一元素aij的存储位置LOC(i,j)=LOC(0,0)+(n*i+j)L。

n维数组A[0…b1-1,0…b2-1,…,0…bn-1]的数据元素存储位置的计算公式：LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(b2*…bnj1+b3*…bnj2+…+bn*jn-1+jn)L。

4.4.3特殊矩阵的压缩存储

1.对称矩阵(aij=aji)

以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在一一对应的关系：

2.三角矩阵

（1）上三角矩阵

sa[k]和矩阵元aij之间的对应关系为：

（2）下三角矩阵

sa[k]和矩阵元aij之间的对应关系为：

3.对称矩阵（带状矩阵）

按某个原则（或以行为主，或以对角线的顺序）将其压缩存储到一维数组上。

4.稀疏矩阵

其非零元较零元少，且分布没有一定规律，称之为稀疏矩阵。（三元组表示法或十字链表）

4.5广义表

4.5.1广义表的定义

广义表是线性表的推广，也成为列表。一般记作LS=(a1,a2,…,an).

其中，LS是广义表的名称，n是其长度。线性表中ai只限于是单个元素。而在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。用大写字母表示广义表的名称，用小写字母表示原子。

广义表的定义是一个递归的定义。

A=()——A是一个空表，其长度为零 B=(e)——B只有一个原子e，其长度为1 C=(a,(b,c,d))——C的长度为2，两个元素分别为原子a和子表(b,c,d) D=(A,B,C)——D的长度为3，3个元素都是广义表，D=((),(e), (a,(b,c,d))) E=(a,E)——这是一个递归的表 

广义表的运算：

（1）取表头GetHead(LS)：取出的表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表。

（2）取表尾GetTail(LS)：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。

4.5.2广义表的存储结构

1.头尾链表的存储结构

表结点：

tag=1	hp	tp

原子结点：

tag=0	atom

（1）除空表的表头指针为空外，对任意非空广义表，其表头指针均指向一个表结点，且该结点中hp域指示广义表表头（或为原子结点，或为表结点），tp域指向广义表表尾（除非表尾为空，则指针为空，否则必为表结点）。

（2）容易分清列表中原子和子表所在层次。

（3）最高层的表结点个数即为广义表的长度。

2.扩展线性链表的存储结构

表结点：

tag=1	hp	tp

原子结点：

tag=0	atom	tp

（1）tp指向同层的下一个

广义表的长度：n

广义表的深度：最多的括号层数