北大夜大数据结构期末考试重点整理

2）集合的顺序存储结构：

? 静态分配的数组存放: struct Set { ElemType set[MaxSize]; int len; };

? 动态分配的数组存放: struct Set { ElemType *set; int len; int MaxSize; };

集合顺序存储结构示意图： 1 2 0(下标) A1 A2 A3 …. n-1 An n .. Maxsize-1 3）集合的链式存储结构

集合的顺序存储结构是通过数组实现的，链式存储结构是通过链接实现的。 Struct SNode {

ElemType data; //存储元素值得结点值域 SNode * next;//存储下一结点地址的指针 }

集合链接存储结构示意图：

HT A1 A2 An ^

2.稀疏矩阵的定义和三元组线性表表示。

1）矩阵(Matrix)是一个具有m行n列的数表，共包含m×n个元素。

当m＝n时，称之为n阶方阵

稀疏矩阵(SparseMatrix)：其非零元素的个数远远小于零元素的个数。 2）稀疏矩阵的三元组表示： （行号，列号，元素值）

稀疏矩阵所对应的三元组线性表表示： （（1,1,3），（1,4,5），（2,3,-2），（3,1,1），（3,3,4），（3,5,6）….） 3.广义表的定义和表示，广义表长度和深度的计算。

1）广义表：是线性表的推广，一个广义表是n个元素的优先序列，n=0时为空表。 广义表是一种递归的数据结构。动态链接存储。

表示：LS=（a1,a2,a3,a4…an）,ai为单元素或表元素，n为长度，及为含元素的个数。 2）广义表的长度：所含元素的个数。

广义表的深度：括号嵌套的最大次数，（注意空表的深度为1）。

4.广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法。 1） 广义表的链接存储结构中结点类型定义： 单元素：包括值域和指向其后续结点的指针域

子表：包括指向子表中第一个结点的表头指针域和指向其后续结点的指针域 标志域：区分单元素结点和子表结点 struct GLNode { Boolean tag; union { ElemType data; GLNode *sublist; };

GLNode *next; };

2）广义表长度的递归算法 int Lenth (GLNode* GL) {

if (GL!= NULL) return 1+Lenth(GL->next); else return 0 ; }

3）广义表深度的递归算法

广义表的深度=MAX（子表的深度）+1

int Depth (GLNode* GL) {

int max=0;

while (GL!= NULL) { if (GL->tag= =True) { int dep=Depth(GL->sublist); if (dep>max) max=dep; } GL= GL->next; }

return max+1; }

第四章 栈和队列

1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能。

1）栈：又称堆栈，其限制是仅允许在表的一端进行插入和删除运算。（后进先出） 2）栈的抽象数据类型描述： ADT STACK is Data： 采用顺序或链接方式存储的栈，其存储类型 为StackType。 Operation：

Void InitStack(StackType& S); //构造一个空栈S

Void ClearStack(StackType& S); //将S清为空栈

int StackEmpty(StackType& S);

//若S为空栈，则返回1，否则返回0 ElemType Peek(StackType& S); //返回栈元素，但不移动栈顶指针

Void Push(StackType& S, const ElemType& item);

//元素item进栈

ElemType Pop(StackType& S); //栈顶元素出栈 int StackFull(StackType& S);

//若栈满，返回1 ，否则返回0，顺序存储特有 End STACK

2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。 1）静态分配空间 Struct Stack {

ElemType stack[Maxsize];//顺序存储栈中所有元素 Int top; //栈顶位置 }

top值为-1表示栈空。 top值为StackMaxSize -1表示栈满。 2） 动态分配空间 Struct Stack {

ElemType *stack; //栈元素 Int top; //存栈顶元素的位置

Int MaxSize;//存Stack数组长度，即所能存储栈的最大长度 }

3.栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 1）初始化栈

void InitStack(Stack& S) { S.MaxSize=10; S.Stack=new ElemType[S.MaxSize]; if(!S.stack) { cerr<<“动态存储分配失败!”<

2）清空栈

void ClearStack(Stack& S) { if(S.stack ){

delete []S.stack; S.stack=0; } S.top = -1; S.MaxSize=0; }

3）判断栈是否为空

int StackEmpty(Stack& S) { return S.top==-1; }

4）读取栈顶元素

ElemType Peek(Stack& S) { if(S.top==-1) { cerr<<\ exit(1); } return S.stack[S.top]; }

5）数据元素进栈

void Push(Stack& S,const ElemType& item) { if(S.top==StackMaxSize-1) { int k=sizeof(ElemenType); S.stack=(ElemType*)realloc(S.stack, 2*S.MaxSize*k); SmMaxSize=2*S.MaxSize; } S.top++; S.stack[S.top]=item; }

6）数据元素出栈(删除栈顶元素并返回) ElemType Pop(Stack& S) { if(S.top==-1) { cerr<<\ exit(1); } ElemType temp=S.stack[S.top]; S.top--; return temp; }

7）检查栈是否已满 int StackFull(Stack& S) { return S.top==StackMaxSize-1;