【笔记】数据结构期末复习

​ 2021年数据结构期末复习，经供参考。

数据结构

线性表

数据结构的二元组表示

数据结构的二元组形式为：DS = (D, S)。

其中 D 是数据元素的集合； S 是 D 中数据元素之间的关系集合，并且数据元素之间的关系是使用序偶来表示的。序偶是由两个元素 x 和 y 按一定顺序排列而成的二元组，记作<x , y>， x 是它的第一元素， y 是它的第二元素。

1.如果 D != null，而S == null，则该数据结构为集合结构。
2.如果 D = {01, 02, 03, 04, 05}，S = {<02,04>, <03,05>, <05,02>, <01,03>}，则该数据结构是线性结构。
在这些数据元素中有一个可以被称为“第一个”的数据元素；还有一个可以被称为“最后一个”的数据元素；除第一个元素以外每个数据元素有且仅有一个直接前驱元素，除最后一个元素以外每个数据元素有且仅有一个直接后续元素。这种数据结构的特点是数据元素之间是 1对 1 的联系，即线性关系。
3.D = {01, 02, 03, 04, 05, 06}，S = {<01,02>, <01,03>, <02,04>, <02,05>, <03,06>}
除了一个数据元素（元素 01）以外每个数据元素有且仅有一个直接前驱元素，但是可以有多个直接后续元素。这种数据结构的特点是数据元素之间是 1 对 N 的联系，即树结构。
4.D = {01, 02, 03, 04, 05}
S = {<01,02>, <01,05>, <02,01>, <02,03>, <02,04>, <03,02>,<04,02>, <04,05>, <05,01>, <05,04>}:
每个数据元素可以有多个直接前驱元素，也可以有多个直接后续元素。这种数据结构的特点是数据元素之间是 M 对 N 的联系，即图结构。

单向链表的基本操作

有序顺序表的归并

SqList &la,SqList &lb,SqList &lc
i=j=k=0;lc.n=la.n+lb.n;
while(i<la.n&&j<lb.n)
    if(LT(la.elem[i],lb.elem[j]))
        lc.elem[k++]=la.elem[i++];
	else
        lc.elem[k++]=lb.elem[j++];
while(i<la.n)
    lc.elem[k++] = la.elem[i++];
while(j<lb.n)
    lc.elem[k++] = lb.elem[j++];

创建单向链表

//先入先出法
LinkList ctr1()
{
    //指针last追踪当前最后一个结点
	CreateNode(h);
	last = h;
	while(1){
        scanf("%d, &e");
        if (e==0) break;
        CreateNode(p);
        p->data=e;last->next=p;
        last=p;
	}
	last->neat=NULL;
    return h;
}

//先入后出法
LinkList ctr2(int n)
{
    CreateNode(h);
    h->next=NULL;
    for(i=0;i<n;i++)
    {
        CreateNode(p);
        scanf("%d", &p->data);
        p->next=h->next;
        h->next = p;
    }
    return h;
}

插入删除

//插入
scanf("%d", &e);
q->data = e;
q->next = NULL;
p=h->next;
while(p)
{
    if (插入条件)
    {
        q->next = p->next;
        p->next = q;
    }
}

//删除所有结点
void clear(Linklist h)
{
    p=h->next;
    h->next = NULL;
    while(p)
    {
        q=p;
        p=p->next;
        free(q);
    }
}

归并两个有序单链表

//操作跟线性表差不多，区别在于while(p)
void merge(Linklist ha,Linklist hb,Linklist hc)
{
    pa=ha->next;
    .....
    while(pa&&pb)
    {
        if(LT(pa->data,pb->data))
        {
            p=pa;
            pa=pa->next;
            pc->next=p;
            pc=p;
        }
        else
        {
            p=pb;
            pb=pb->next;
            pc->next=p;
            pc=p;
        }
    }
    if (pa) pc->next =pa;
    if (pb) pc->next =pb;
    ha->next = hb->next = NULL;
}

双向链表

删除结点

//已知某数据结点指针p,删除P

//非循环双向链表
p->prior->next = p->next;
if(p->next) p->next->prior=p->prior;
else h->prior = p->prior;
DeleteNode(p);

//循环双向链表
if(p!=p->next)
{
    p->prior->next = p->next;
    p->next->prior=p->prior;
}

插入结点

//已知结点指针p，在p后面插入结点s

//非循环双向链表
s->next=p->next;
s->prior=p;
p->next=s;
if(s->next)	s->next->prior = s;
else h->prior=s;

//循环双向链表
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;

栈和队列

栈

栈的特点：LIFO(Last in first out)

typedef struct
{
    ElemTp *elem;
    int n;			//栈容量
    int top;		//栈顶指针
}SqSatck;

定义栈顶指针为：top=-1（栈空）

入栈的方向为top+1方向

栈的基本操作

//建栈
int CreateStack(SqStack &s,int n)
{
    if(n<=0) return 0;
    s.n=n;
    s.top=-1;			//初始化
    s.elem = new ElemTp[n];
    if (!s.elem) return 0;
    return 1;
}

//销栈
void destoryStack(SqStack &S)
{
    S.n=0;
    S.top = -1;
    delete s.elem;
}

//判断是否为空
int empty(SqStack &s)
{
    return (s.top==-1);
}

//判断栈满
return s.top>n-1;

//入栈
int push(Sqlist &s,ElemTp e)
{
    if(s.top>=s.n-1) return 0;
    s.elem[++top]=e;
	return 1;
}

//出栈
int pop(SqStack &s,ElemTp &e)
{
    if (s.top==-1) return 0;
    e=s.elem[s.top--];
    return 1;
}

表达式求值

（1）前缀表达式的计算机求值

1. 从右至左扫描表达式
2. 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈
3. 重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

（2）后缀表达式的计算机求值

与前缀表达式类似，只是顺序是从左至右：

1. 从左至右扫描表达式
2. 遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素op 栈顶元素 ），并将结果入栈
3. 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

（3）中缀转后缀和前缀

转化步骤：

1. 按照运算符的优先级对所有的运算单位加括号
2. 将运算符移动到对应括号的前面（前缀表达式）或后面（后缀表达式）
3. 去掉括号，得到前缀或后缀表达式

示例：

中缀表达式：1+(2+3)×4-5

1）加括号
式子变成 ((1+((2+3)×4))-5)

2）移动运算符

对于前缀表达式，变成了 -(+(1×(+(23)4))5)

对于后缀表达式：变成了((1((23)+4)×)+5)-

3）去掉括号
前缀表达式： - + 1 × + 2 3 4 5
后缀表达式：1 2 3 + 4 × + 5 -

队列

队列的特点：FIFO（First in First out)

front队头，rear队尾

init:	f=r=-1;
empty:	f==r;
full:	r-f==n;

循环队列

实现方案：

1.f指向队头元素之前空闲位置；r指向队尾元素

即队头和队尾元素至少间隔一个空闲元素位置

//队满条件：
(q.r+1)%q.n == (q.f+n)%n;

//入队
q.r=(q.r+1)%q.n;
q.elem[q.r] = e;

//队空条件
q.r==q.f;

//出队
q.f=(q.f+1)%q.n;
e=q.elem[q.f];

2.在SqQueue结构体中增设计数变量c，记录队列中当前元素个数

//队空
q,c == 0
    
//队满
q.c == q.n

//入队
q.r=(q.r+1)%q.n;
q.elem[q.r]=e;
q.c++;

//出队
q.f=(q.f+!)%q.n;
e=q.elem[q.f];
q.c--;

串

子串定位基本算法

//BF
//S是主串，t是子串

int index(char *s, char *t)
{
    i=j=0;
    while(s[i]&&t[j])
        if(s[i]==t[j]){i++;j++;}
    	else{i=i-j+1;j=0;}	//失配时，i回溯至主串原出发位置的下一个位置
    if(!t[j]) return i-j;
    return -1;			//没找到
}

KMP算法中的next数组

考察目标字符串ptr：ababaca
这里我们要计算一个长度为m的转移函数next。

next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。

比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。
cbcbc，最长前缀和最长后缀相同是cbc。
abcbc，最长前缀和最长后缀相同是不存在的。

注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。
比如aaaa相同的最长前缀和最长后缀是aaa。
对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。

数组

数组的顺序表示

核心公式：Address=base+offset

详情见课本P92笔记，懒得打了

例题：

已知元素下标求元素地址	已知元素地址求元素下标

数组的压缩存储

//sa[n(n+1)/2]为n阶对称矩阵A的压缩存储

三元组的顺序表表示

typedef struct
{
    int i,j;				//该非零元的行下标和列下标
    ElemType e;
}Triple;
typedef struct
{
    Triple data[MAXSIZE+1];
    int mu,nu,tu;			//矩阵的行数，列数和非零元个数
}TSMatrix;

三元组的顺序表转置

//对矩阵M进行转置存储至N中
void trans(TSMatrix M, TSMatrix &N)
{
	int i, p,k=0;
	N.mu = M.nu;
	N.nu = M.mu;
	N.tu = M.tu;
	for(i=0;i<N.mu;i++)				//遍历矩阵N的行下表
		for(p=0;p<M.tu;p++)
			if (M.data[p].j == i)			//矩阵M的列下标等于矩阵N的行下标
            {
				N.data[k].i = i;
				N.data[k].j = M.data[p].i;
				N.data[k].e = M.data[k].e;
				k++;
			}
}

十字链表

还没看

广义表

广义表常考:

树

孩子兄弟链表表示

二叉树

满二叉树与完全二叉树

完全二叉树的一维数组表示

完全二叉树的性质

习题；

二叉树的存储结构

//二叉链表
typedef struct node
{
    struct node *lchild,
    			*rchild,
}BiTNode,*BiTree;

二叉树的遍历

先序/中序/后序遍历：

//先序
void previsit(BiTree t)
{
    if(t)
    {
        visit(t);
        previsit(t->lchild);
        previsit(t->rchild);
    }
}

//中序
void midvisit(BiTree t)
{
    if (t)
    {
        midvisit(t->lchild);
        visit(t);
        midvisit(t->rchild);
    }
}

//后序
void lastvisit(BiTree t)
{
    if(t)
    {
        lastvisit(t->lchild);
        lastvisit(t->rchild);
        visit(t);
    }
}

层次遍历：

建立二叉树

先序的方式：

//先序遍历建立二叉树
思想还是按照之前先序遍历，将visit的操作更换为存储数据的操作

题型：已知先序遍历序列和中序遍历序列画二叉树

二叉树常见算法

//求二叉树深度
int height(struct node* node)  
{ 
   if (node==NULL)  
       return 0; 
   else 
   { 
       // 计算左子树的高度和右子树的高度 
       int lHeight = height(node->left); 
       int rHeight = height(node->right); 
       // 返回二者较大者加1 
       if (lHeight > rHeight)  
           return(lHeight+1); 
       else return(rHeight+1); 
   } 
} 

//求二叉树中度为1的结点个数
int leaf_1(BiTreeNode *T) {
	if (T==NULL) {
		return 0;
	}
	if ((T->leftchild == NULL && T->rightchild != NULL) || (T->leftchild != NULL && T->rightchild == NULL))
	{
		return 1 + leaf_1(T->leftchild) + leaf_1(T->rightchild);
	}
	return leaf_1(T->leftchild) + leaf_1(T->rightchild);
}
//求二叉树中度为2的结点个数
int Node2(BiTree T)
{
	if(!T)
		return 0;
	else if(T->lchild&&T->rchild)
		return Node2(T->lchild)+Node2(T->rchild)+1;
	else
		return Node2(T->lchild)+Node2(T->rchild);
}

判断二叉树是否为完全二叉树

//n=结点总数	
//if(check(bt,1,n))
bool check(BiT bt,int i,int n)
{
    if(i>n) return true;
    if (!bt) return false;
    return check(bt->lchild,2*i,n)&&check(bt->rchild,2*i+1,n);
}

平衡二叉树

线索二叉树

线索二叉树的遍历

Huffman树

构造

编码，还没看

图

图的存储结构

无向图	有向图

n阶无向完全图边的数目为 n(n-1)/2

n阶有向完全图边的数目为 n(n-1)

DFS

//DFS
void DFStravel(Graph &G)
{
    bool *visited=new bool[G.n];
    for(i=0;i<G.n;i++)	visited[i]=false;
    for(i=0;i<G.n;i++)
        if(!visited[i]) DFS(G,visited,i);
    delete []visited;
}
void DFS(Graph &G,bool visited[],int i)
{
	visit(i);
    visited[i]=true;
    for(j=First_Adj(G,i);j!=-1;j=Next_Adj(G,i,j))
        if(!visited[i])	DFS(G,j);
}

BFS

void BFStravel(Graph &G)
{
	bool *visited=new bool[G.n];
    for(i=0;i<G.n;i++)
        visited[i]=false;
    InitQueue(Q);
    for(i=0;i<G.n;i++)
        if(!visited[i])
        {
            visit(i);	visited[i]=ture;
            enQueue(Q,i);
            while(!Empty(Q))
            {
                u=delQueue(Q);
                for(v=First_Adj(G,u);v!=-1;v=Next_Adj(G,U,V))
                {
                    if(visited[v]){
                        visit(v);
                        visited[i]=true;
                        enQueue(Q,v);
                    }
                }
            }
        }
    delete []visited;
}

拓扑排序

定义

有向无环图（DAG）的排序，对DAG所有顶点的一种排序，若存在一条从顶点A到顶点B的路径，在排序中B排在A后面

算法思想

1.从DAG图中选择一个没有前驱的顶点并输出

2.从图中删除该顶点合所有以它为起点的有向边

3.重复1，2直到当前的DAG图为空或当前图中不存在无前驱的顶点为止，后一种情况说明图中有环

—->>算法结束时没有访问所有顶点，则存在以剩下顶点组成的环

—->>拓扑排序的结果不唯一

—–>>辅助结构：栈S，数组indegree（保存所有顶点当前的入度）

实现代码

bool TopoSort(Graph G)
{
    InitStack(S);
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0)
            Push(S,i);
    int count=0;
    while(!StackEmpty(S)){
        Pop(S,i);
        visit(i);			//遍历
        count++;
        for(p=G.vertex[i].firstarc;p;p=p->nextarc){
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);
        }
    }
    if(count<G.vexnum)
        return false;
    else
        return true;
}

关键路径

AOE网

1.源点，汇点：入度/出度为零的点

2.关键路径：从原点到汇点最大路径长度的路径称为关键路径，关键路径上的活动为关键活动

计算关建路径

1.i->j的最早发生时间：所有从vi到vj的路径走完的时间（理解：开工要求，短板效应），故为最大的路径。计算方法：利用拓扑排序vi->vj的时间，利用入边

2.i->j的最迟发生时间：按照逆拓扑排序的顺序，利用出边

3.活动ai的最早开始时间：其实是看边的关系，1，2看的是点的关系

4.活动ai的最迟开始时间l(i)

5.活动ai的差额

​

最短路径

Prim算法

Kruskal算法

查找

平均查找长度ASL

平均查找长度=总的查找次数/元素数

二叉排序树

排序

直接插入排序

更新集合的思想，前面的序列是有序的，后面的序列是无序的。

void InsertSort(T* array, int n) {               //array待排序数组,n:数组元素数量
	int i, j;                                    //循环变量
	T temp;                                      //存储待排序元素
	for (i = 1; i < n; i++) {
		j = i;
		temp = array[i];                         //待排序元素赋值给临时变量
		while (j > 0 && temp < array[j - 1]) {   //当未达到数组的第一个元素或者待插入元素小于当前元素
			array[j] = array[j - 1];             //就将该元素后移
			j--;                                 //下标减一，继续比较
		}
		array[j] = temp;                         //插入位置已经找到，立即插入
	} 
}

冒泡排序

void BubbleSort(ElemTp R[],int n)
{
	for(i=0;i<n-1;i++)
        for(j=0;j<n-1-i;j++)
            if(R[j].K>R[j+1].K)
                swap(R[j],R[j+1]);
}

快速排序

//一趟快排
int quickpass(int r[],int s,int t)
{
    //s是起点，t是终点
    int i=s,j=t,x=r[s];
    while(i<j)
    {
        while(i<j&&r[j]>X)		//x右边的数一定比他大	
            j--;
        if (i<j){
            r[i]=r[j];
            i++;
        }
        while(i<j&&r[j]<x)
            i++;
        if(i<j){
            r[i]=r[j];
            j--;
        }
        r[i]=x;	
    }
    return i;			//返回支点下标
}
//递归式快排
void quicksort(int r[],int s,int t)
{
    if(s<t){
        i=quickpass(r,s,t);
        quicksort(R,s,i-1);		//先排左边
        quicksort(R,i+1,t);		//再排右边
    }
}

希尔排序

void Shellsort(int r[],int n,int d[],int m)
{
    //r[0..n-1]升序排序
    //d[0..m-1]为增量数组
    for(s=0;s<m;s++){
        for(i=0;i<d[s];i++){
            //小组的数量为d[s]
            for(j=i+d[s];j<n;j+=d[s]){
                //对每个小组进行直接插入排序
                temp=a[j];
                k=j-d[s];
                while(k>=0&&r[k]>temp){
                    r[k+d[s]] = r[k];
                    k -= d[s];			//是从最右边开始排序的。
                }
                a[k+d[s]] = temp;
            }
        }
    }
}

堆排序

思想：

首先根据序列构建一个完全二叉树

在完全二叉树的基础上，从最后一个非叶结点开始调整：比较三个元素的大小–自己，它的左孩子，右孩子。分为三种情况:

• ​ 自己最小，不用调整
• ​ 左孩子最小，交换该非叶结点与其左孩子的值，并考察以左孩子为根的子树是否满足小顶堆的要求，不满足递归向下处理
• ​ 右孩子最小，交换该非叶结点与其右孩子的值，并考察以右孩子为根的子树是否满足小顶堆的要求，不满足递归向下处理

各排序方法对比

时间：

插入>=冒泡>=选择>….>快速

空间：

归并>快速>基数>….

出现过的算法设计题

链式存储求交集

typedef struct node
{
	int data;
	struct node *next;
}linklist;
void inster(linklist *ha, linklist *hb, linklist *&hc)
{
	linklist *p, *q,*t;
	for (p = ha, hc = NULL; p; p = p->next)
	{
		for (q = hb; q; q = q->next)
		{
			if (q->data == p->data)
				break;
		}
		if (q != NULL)
		{
			//元素找到
			t = (linklist *)malloc(sizeof(linklist));
			t->data = p->data;
			t->next = hc;
			hc = t;
		}
	}
}

链表删除值相同的多余结点

typedef int datatype;
typedef struct node { datatype data; struct node *next }lklist;
void del(lklist *head)
{
	lklist *p, *q, *s;
	p = head->next;
	while (p != 0 && p->next != 0)
	{
		s = p;
		q = p->next;
		while (q != 0)
		{
			if (p->data == q->data)
			{
				s->next = q->next;
				free(q);
				q = s->next;
			}
			else {
				s = q;
				q = q->next;
			}
		}
		p = p->next;
	}
}

求一个结点X在二叉树中的双亲结点算法

#include <stdio.h>
#include <stdlib.h>
/*思想是前序遍历，因为前序遍历第i次，其i-1次遍历对应的就是第i次的双亲结点*/
typedef char datatype;
typedef struct tree {
	datatype data;
	struct tree *lchild, *rchild;
}bitree;
/*用队列的思想实现寻找第i-1次遍历*/
bitree *q[20];
int r = 0, f = 0;
int flag = 0;
/*前序遍历并存入队列*/
void preorder(bitree *bt, char x)
{
	if(bt!=NULL&&flag==0)
		if (bt->data == x) {
			flag = 1;
			return;
		}
		else {
			r = (r + 1) % 20;
			q[r] = bt;
			preorder(bt->lchild, x);
			preorder(bt->rchild, x);
		}
}
void findparent(bitree *bt, char x)
{
	int i;
	preorder(bt, x);
	/*得到队列之后只用判断前一次的孩子结点的值与之是否相等就好了*/
	for (i = f + 1; i <= r; i++)
	{
		if (q[i]->lchild->data == x || q[i]->rchild->data == x)
			break;
	}
	if (flag == 0) {
		printf("Not Found!");
	}
	else if (i <= r)
		printf("%c", bt->data);
	else
		printf("Not parent!");
}

交换二叉树所有节点左右子树

typedef struct node{
    int data;
    struct node *lchild,*rchild;
}bitree;
void swap(bitree *bt)
{
    bitree *p;
    if (!bt) return;
    swap(bt->lchild);
    swap(bt->rchild);
    p=bt->lchild;
    bt->lchild=bt->rchild;
    bt->rchild=p;
}

建立二叉排序树

#define n 10		//二叉排序树的结点个数
typedef struct node{
	int key;
    struct node *lchild,*rchild'
}bitree;
void bitreeinsert(bitree *&bt,int key)
{
    if(bt==0){
        bt=(bitree *)malloc(sizeof(bitree));
        bt->key=key;
        bt->lchild=NULL;	bt->rchild=NULL;
    }
    else if(bt->key>key) bitreeinsert(bt->lchild);			//根结点的值大于Key
    else bitreeinsert(bt->rchild,key);
}
void createbsttree(bitree *bt)
{
    int i;
    for(i=0;i<n;i++)
        bitreeinsert(bt,random(100));
}

判断两个二叉树是否相同

int judgebitree(bitree *bt1,bitree *bt2)//判断两个二叉树是否相同。
{
  	if (bt1==0 && bt2==0)//两棵树对应位置都为空返回1
  		return 1;
  	else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) //两棵树的当前节点只有一个为空或者两棵树的当前节点的值不同。
	  	return 0;
  	else 
	  	return judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild);
}