数据结构与算法期末复习总结

题型
编程题2题，综合题5题

编程题

链表的遍历，对单链表进行基本操作。

数组实现

//a.线性表储存结构
#include<iostream>
using namespace std;
#define maxlength 100
struct LIST{
   
     Elementtype elements[maxlength];
     int last;};
typedef int position;
//b.插入
void Insert(Elementtype x,position p,LIST &L)
{
   position q;
 if(L.last>maxlength-1)
cout<<"list is full!"<<endl;
 else if((p>L.last+1)||(p<1))
cout<<"position does not exist!"<<endl;
 else{
   
 for(q=L.last;q>=p;q--)
{
      elements[q+1]=L.elements[q];
last=L.last+1;
elements[p]=x;}}}
//c.删除
void Delete(position p,LIST &L)
{
   position q;
 if((p>L.last)||(p<1))
   cout<<"position does not exist!"<<endl;
 else{
   L.last=L.last-1;
      for(q=p;q<=L.last;q++)
L.elementss[q]=L.elements[q+1];}}
//d.定位
position Locate(Elementtype x,LIST L)
{
   position q;
 for(q=1;q<=L.last;q++)
 {
   if(L.elements[q]==x)
return q;
  return(L.last+1);}}

指针实现

#include<iostream>
using namespace std;
//a. 储存结构
struct celltype{
   
     Elementtype element;
     celltype *next;};
typedef celltype *LIST
typedef celltype *position

//b. 插入
void Insert(Elementtype x,position p)

{
   position temp;
 temp=p->next;
P->next=new celltype;
P->next->element=x;
P->next->next=temp;}

//c.删除
void Delete(position p)
{
   position q;
 if(p->next!=NULL){
   
q=p->next;
p->next=q->next;
delete q;}}

//d.定位
postion Locate(Elementtype x,LIST L)
{
   postion p;
 p=L;
 while(p->next!=NULL)
if(p->next->element==x)
   return p;
else p=p->next;
 return p;}

//e.置空
postion MakeNull(LIST &L)
{
   L=new celltype;
L->next=NULL;
return L;} 

二叉树的遍历，判断两个二叉树是否等价。

遍历

//先根遍历DLR
void PreOrder(BTREE BT)
{
   if(!IsEmpty(BT))
 {
   visit(Data(BT));
  PreOrder(Lchild(BT));
  PreOrder(Rchild(BT));}}

//中根遍历LDR
void InOrder(BTREE BT)
{
   if(!IsEmpty(BT))
 {
   InOrder(Lchild(BT));
  visit(Data(BT));
  InOrder(Rchild(BT));}}

//后根遍历LRD
void PostOrder(BTREE BT)
{
   if(!IsEmpty(BT))
 {
   PostOrder(Lchild(BT));
  PostOrder(Rchild(BT));
  visit(Data(BT));}}

//中根遍历非递归函数
void NInOrder(BTREE BT)
{
   STACK S;BTREE T;
 MakeNull(S);
 T=BT;
 while(!IsEmpty(T)||!Empty(S))
if(!IsEmpty(T))
{
   Push(T,S);
 T=Lchild(T);}
else
{
   T=Top(S);Pop(S);
 visit(Data(T));
 T=Rchild(T);}}

//层次遍历（队列）
void LeverOrder(BTREE BT)
{
   Queue Q;BTREE T;
 MakeNull(Q);
 T=BT;
 if(!IsEmpty(T))
EnQueue(T,Q);
 while(!Empty(Q))
 {
   T=Front(Q);
  visit(Data(T));
  DeQueue(T);
  if(!Lchild(T))
     EnQueue(Lchild(T),Q);
  if(!Rchild(T))
     EnQueue(Rchild(T),Q);}}

判断两二叉树是否等价

boolean Equal(BTREE firstbt,BTREE secondbt)
{
   boolean x;
 x=FALSE;
 if(IsEmpty(firstbt)&&IsEmpty(secondbt))
x=TRUE;
 else if(!IsEmpty(firstbt)&&!IsEmpty(secondbt))
if(Data(firstbt）==Data(secondbt))
   if(Equal(Lchild(firstbt),Lchild(secondbt)))
      x=Equal(Rchild(firstbt),Rchild(secondbt));
 return x;}

#include<iostream>
#include <stack>
using namespace std;
struct BTREE {
   
	int data;
	BTREE* lchild;
	BTREE* rchild;
};
BTREE* Lchild(BTREE* BT) {
   
	return BT->lchild;
}
BTREE* Rchild(BTREE* BT) {
   
	return BT->rchild;
}
int Data(BTREE* BT) {
   
	return BT->data;
}
bool IsEmpty(BTREE* BT) {
   
	return BT == NULL;
}
void PreOrder(BTREE* BT) {
   //前序遍历
	if (!IsEmpty(BT)) {
   
		//visit(Data(BT));
		PreOrder(Lchild(BT));
		PreOrder(Rchild(BT));
	}
}
void InOrder(BTREE* BT) {
   //中序遍历
	if (!IsEmpty(BT)) {
   
		InOrder(Lchild(BT));
		//visit(Data(BT));
		InOrder(Rchild(BT));
	}
}
void PostOrder(BTREE* BT) {
   //后序遍历
	if (!IsEmpty(BT)) {
   
		PostOrder(Lchild(BT));
		PostOrder(Rchild(BT));
		//visit(Data(BT));
	}
}
void NINORDER(BTREE* BT) {
   
	stack<BTREE*> S;
	while (!S.empty() || BT != NULL) {
   
		if (BT != NULL) {
   
			S.push(BT);
			BT = BT->lchild;
		}
		else {
   
			BT = S.top();
			S.pop();
			//visit(DATA(BT));
			BT = BT->rchild;
		}
	}
}
bool equal(BTREE* BT1, BTREE* BT2) {
   
	bool x = false;
	if (BT1 == NULL && BT2 == NULL)
		x = true;
	else if (BT1 != NULL && BT2 != NULL) {
   
		if (Data(BT1) == Data(BT2))
			if (equal(Lchild(BT1), Lchild(BT2)))
				x = equal(Rchild(BT1), Rchild(BT2));
	}
	return x;
}
int main() {
   

}

哈夫曼树的构造原理以及构造过程，带权路径长度

//数据结构
#define n 100 //叶子树
#define m 2*(n)-1 //结点总数
typedef struct{
   
double weight;
int lchild;
int rchild;
int parent;}HTNODE;
typedef HTNODE HuffmanT[m];

//构造
void SelectMin(HuffmanT T,int n,int &p1,int &p2)
{
   int i,j;
 for(i=0;i<n;i++)
if(T[i].parent==-1)  {
   p1=i;break;}
 for(j=i+1;j<n;j++)
if(T[j].parent==-1)  {
   p2=j;break;}
 for(i=o;i<n;i++)
if((T[p1].weight>T[i].weight)&&(T[i].parent==-1)&&(p2!=i)) p1=i;
 for(j=0;j<n;j++)
    if((T[p2].weight>T[j].weight)&&(T[j].parent==-1)&&(p1!=j)) p2=j;}
void CreateHT(HuffmanT T)
{
   int i,p1,p2;
 InitHT(T);
 for(i=n;i<=m;i++)
 {
   SelectMin(T,i-1,p1,p2);
  T[p1].parent=T[p2].parent=i;
  T[i].lchild=p1;
  T[i].rchild=p2;
  T[i].weight=T[p1].weight+T[p2.weight];}

#define n 100//叶子数
#define m 2*n-1//节点总数
struct HTNODE
{
   
	double weight;
	int lchild;
	int rchild;
	int parent;
};
typedef HTNODE HuffmanT[m + 1];
void CreateHT(HuffmanT T,int w[],int num) {
   
	int i, p1, p2;
	for (i = 1; i < 2 * num; i++) {
   
		T[i].parent = -1;
		T[i].lchild = -1;
		T[i].rchild = -1;
	}
	for (int i = 1; i <= num; i++) {
   
		T[i].weight = w[i];
	}
	for (int i = num + 1; i <= 2 * num - 1; i++) {
   
		SelectMIN(T, i - 1, p1, p2);
		T[p1].parent = T[p2].parent = i;
		T[i].weight = T[p1].weight + T[p2].weight;
		T[i].lchild = p1;
		T[i].rchild = p2;
	}
}
void SelectMIN(HuffmanT T, int position, int& p1, int& p2) {
   
	int i, j;
	for (i = 1; i <= position; i++) {
   
		if (T[i].parent == -1) {
   
			p1 = i;
			break;
		}
	}
	for (j = i + 1; j <= position; j++) {
   
		if (T[j].parent == -1) {
   
			p2 = j;
			break;
		}
	}
	for (i = 1; i <= position; i++) {
   
		if ((T[p1].weight > T[i].weight) && (T[i].parent == -1) && (i != p2))
			p1 = i;
	}
	for (j = i + 1; j <= position; j++) {
   
		if ((T[p2].weight > T[j].weight) && (T[j].parent == -1) && (j != p1))
			p2 = j;
	}
}
int main() {
   

}

计算图中顶点间最短路径（单源最短路径以及任意顶点之间的最短路径）和最短距离的基本思想。如何计算图的偏心度和中心点。

单源最短路径

void Dijkstra(C)
{
   S={
   1};
 for(i=2;i<=n;i++)
D[i]=C[1][i];
 for(i=1;i<=n-1;i++)
 {
   从V-S中选出一个w，使D[w]的值最小;
  把w加入S;
  for(V-S中的每个顶点v)
     D[v]=min(D[v],D[w]+C[w][v])} //时间复杂度O(n²)

每一对顶点之间的最短路径

//Floyd算法
void Floyd(A,C,n)
{
   for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
   A[i][j]=C[i][j];
 for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
      if(A[i][k]+A[k][j]<A[i][j])
         A[i][j]=A[i][k]+A[k][j];}

//Warshall算法
void Warshall(A,C,n)
{
   for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
   A[i][j]=C[i][j];
 for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
      A[i][j]=A[i][j]∪(A[i][k]∩A[k][j]);}

计算图的偏心度和中心点

偏心度E(k)=max{d[i][k]|i∈V},d[i][j]表示从i到j的最短距离。
求有向图的中心点:
①使用Floyd算法，求每对顶点最短路径的矩阵D.
②对矩阵D的每列j求最大值：E(j)=max{d[i][j]}. //顶点j的偏心度
③求出具有最小偏心度的顶点k：E(k)=min{E(j)}. //即为图G的中心点

综合题

给定树的两种遍历序列，如何确定树

堆的定义以及相关的基本操作

堆的定义

堆即是一棵完全二叉树

//最大堆的类型定义:
#define MaxSize 200
typedef struct{
   
int key;}
Elementtype;
typedef struct{
   
Elementtype elements[MaxSize];
int n;}HEAP;

创建空堆

void MaxHeap(HEAP heap)
{
   heap.n=0;}

判断堆是否为空

bool HeapEmpty(HEAP heap)
{
   return(!Heap.n);}

判断堆是否为满

bool HeapFull(HEAP heap)
{
   return(heap.n==Maxsize-1);}

最大堆heap中插入新元素item

void Insert(HEAP heap,Elementtype item)
{
   int i;
 if(!HeapFull(heap))
 {
   i=heap.n+1;
while((i!=1)&&(item>heap.elements[i/2]))
{
   heap.elements[i]=heap.elements[i/2];
 i/=2;}}
 heap.elements[i]=item;}

最大堆删除最大元素

Elementtype DeleteMax(HEAP heap)
{
   int parent=1,child=2;
 Elementtype item,tmp;
 if(!HeapEmpty(heap))
 {
   item=heap.elements[1];
  tmp=heap.elements[heap.n--];
  while(child<=heap.n)
  {
   if((child<heap.n)&&(heap.elements[child]<heap.elements[child+1]))
      child++;
   if(tmp>=heap.elements[child])  break;
   heap.elements[parent]=heap.elements[child];
   parent=child;
   child*=2;}
  heap.elements[parent]=tmp;
  return item;}}

#include<iostream>
#define MAXSIZE 100
using namespace std;
struct HEAP {
   
	int elements[MAXSIZE];
	int n;
};
void MaxHeap(HEAP& heap) {
   
	heap.n = 0;
}
bool HeapFulls(HEAP& heap) {
   
	return heap.n == MAXSIZE - 1;
}
bool HeapEmpty(HEAP& heap) {
   
	return heap.n == 0;
}
void Insert(HEAP& heap, int element) {
   
	if (!HeapFulls(heap)) {
   
		int i = ++heap.n;
		while (i != 1 && element > heap.elements[i / 2]) {
   
			heap.elements[i] = heap.elements[i / 2];
			i /= 2;
		}
		heap.elements[i] = element;
	}
}
void DeleteMax(HEAP& heap) {
   
	if (!HeapEmpty(heap)) {
   
		int parent = 1, child = 2;
		int temp = heap.elements[heap.n--];
		while (child <= heap.n) {
   
			if (heap.elements[child] < heap.elements[child + 1])
				child++;
			if (temp >= heap.elements[child])break;
			heap.elements[parent] = heap.elements[child];
			parent = child;
			child *= 2;
		}
		heap.elements[parent] = temp;
	}
}
int main() {
   

}

KMP算法中如何计算模式串中的next数组，以及KMP模式匹配的具体步骤

next数组的计算

第1位:0.
第2位:1.
第n位(n>=3):比较前n-1位，得出最长前后缀匹配长度k，填k+1.

void GetNext(char *t,int next[])
{
   int i=0,j=0;
 next[1]=0;
 while(i<t[0])
 {
   if(j==0||t[i]==t[j])
  {
   i++;j++;next[i]=j;}
  else j=next[j];}}

KMP模式匹配具体步骤

若第k-1次比较在j=m处失配，那第k次比较j回溯到j=next[m]处同主串的i比较(主串不回溯),具体可参照p65例2-11

最小生成树（两种方法）的基本原理以及生成过程

最小生成树

生成树是连接V中所有顶点的一棵开放树，生成树中所有边长的总和称为生成树的价，使这个价最小的生成树称为图G的最小生成树

Prim算法

void Prim(costtype C[n+1][n+1])
{
   costtype LOWCOST[n+1];
 int CLOSEST[n+1]；
 int i,j,k;
 costtype min;
 for(i=2;i<=n;i++)
 {
   LOWCOST[i]=C[1][i];
  CLOSEST[i]=1;}
 for(i=2;i<=n;i++)
 {
   min=LOWCOST[i];
  k=i;
  for(j=2;j<=n;j++)
      if(LOWCOST[j]<min)
      {
   min=LOWCOST[i];
       k=j;}
  cout<<〝(〝<<k<<〞,〝<<CLOSEST[k]<<〞)〞<<endl;
 LOWCOST[k]=infinity;
 for(j=2;j<=n;j++)
     if(C[k][j]<LOWCOST[j]&&LOWCOST[j]!=infinity)
     {
   LOWCOST[j]=C[k][j];
      CLOSEST[j]=k;}}}  //O(n²),一般用于顶点不太多的情况

Kruskal算法

void Kruskal(EdgeSet edges,int n,int e)
{
   int bnf,edf;
 MFSET parents;
 Sort(Edges);
 for(int i=1;i<=n;i++)
     Initial(i,parents);
 for(i=1;i<=e;i++)
 {
   bnf=Find(edges[i].begin,parents);
  edf=Find(edges[i].end,parents);
  if(bnf!=edf)
  {
   Union(bnf,edf,parents);
   cout<<ˋ(ˊ<<edges[i].begin<<ˋ,ˊ;
   cout<<edges[i].end<<ˋ,ˊ<<edges[i].cost<<ˋ)ˊ;
   cout<<endl;}}  //O(|E|*log2|E|)，适合于求边稀疏的最小生成树

图的关键路径的基本原理以及生成过程

关键路径

AOE网:V(事件)–E(活动)–W(时间)
AOV网:V(活动)–E(先后关系)
关键路径:起始点–结束点的最大长度路径
事件最早发生时间:v1到vi的最长路径
活动最早开始时间(=事件最早发生时间):E(i)
活动最迟开始时间:L(i)
关键活动:满足E(i)=L(i)
活动可延缓时间=L(i)-E(i)

二叉查找树的定义以及相关基本操作

定义

struct celltype{
   
records data
celltype *lchild,rchild;};
typedef celltype *BST;

基本操作

//a. F所指二叉查找树中查找关键字为K的记录(F为二查找树根节点的指针)
BST Search(keytype k,BSTF)
{
   if(F=NULL)
   return NULL;
 else if(k==F->data.key)
   return F;
 else if(k<F->data.key)
   return(Search(k,F->lchild));
 else(k>F->data.key)
   return(Search(k,F->rchild));}

//b. 插入记录R
Void Insert(records R,BST *F)
{
   if(F==NULL)
 {
   F=new celltype;
F->data=R;
F->lchild=NULL;
F->rchild=NULL;}
 else if(R.key<F->data.key)
   Insert(R,F->lchild);
 else if(R.key>F->data.key)
   Insert(R,F->rchild);}

//c.删除继承结点
Records DeleteMin(BST &F)
{
   records tmp;BST P;
 if(F->lchild==NULL)
 {
   P=F;
  tmp=F->data;
  F=F->rchild;
  delete P;
  return tmp;}
 else return(DeleteMin(F->lchild));}

//d.删除关键字为k的结点
Void delete(keytype k,BST &F)
{
   if(F!=NULL)
   If(k<F->data.key)
     Delete(k,lchild);
   Else if(k>F->data.key)
     Delete(k,rchild);
   Else/*k==F->data.key,删除成功*/
   If(F->rchild==NULL)
     F=F->rchild;
   If(F->lchild==NULL)
     F=F->lchild;
   Else
     F->data=DeleteMin(F->rchild);}

构造AVL树的基本方法，掌握四种平衡处理（旋转）的基本原理，并能够判断何时需要旋转、需要进行哪一种旋转以及如何旋转

类型

int unbanlanced=FALSE;
struct node{
   
records data;
int bf;
node *lchild,rchild;};
typedef node *BST;

LL旋转和LR旋转

void LeftRotation(BST &T,int &unbalanced)
{
   BST gc,lc;
 lc=T->lchild;
 if(lc->bf==1)     //LL旋转
 {
   T->lchild=lc->rchild;
  lc->rchild=T;
T->bf=0;
T=lc;}
 else{
                //LR旋转 
  gc=lc->rchild;
  lc->rchild=gc->lchild;
  gc->lchild=lc;
T->lchild=gc->rchild;
gc->rchild=T;
switch(gc->bf)
{
   case 1:T->bf=-1;
        lc->bf=0;
        break;
 case 0:T->bf=lc->bf=0;
        break;
 case -1:T->bf=0;
         lc->bf=1;}
T=gc;}
T->bf=0;
unbanlanced=FALSE;}

插入新纪录

void AVLInsert(BST &T,records R,int &unbalanced)
{
   if(!T)
 {
   /*向空二叉树插入元素*/
  T=new celltype;
T->data=R;
T->lchild=T->rchild=NULL;
T->bf=0;}
 else if(R.key<T->data.key)
 {
   AVLInsert(T->lchild,R,unbalanced);
  if(unbalanced)
     switch(T->bf)
     {
   case -1:T->bf=0;
              unbalanced=FALSE;
              break;
      case 0:T->bf=1;
             break;
      case 1:LeftRotation(T,unbalanced);}}
 else if(R.key>T->data.key)
 {
   AVLInsert(T->rchild,R,unbalanced);
  if(unbalanced)
     switch(T->bf)
     {
   case -1:T->bf=0;
              unbalanced=FALSE;
              break;
      case 0:T->bf=-1;
             break;
      case 1:RightRotation(T,unbalanced);}}
 else/*查找成功，R已在AVL中*/
   unbalanced=FALSE;}