第1页 / 共37页
第2页 / 共37页
第3页 / 共37页
第4页 / 共37页
第5页 / 共37页
第6页 / 共37页
第7页 / 共37页
第8页 / 共37页
东北大学考研数据结构算法汇总.doc
线性结构
一 类型定义
1 顺序表
2 单链表
3双链表
二 基础要点
1单链表
2双链表
三 算法
1 删除顺序表中重复元素
2 给无序表建有序索引表
3 逆置单链表
4拆分单链表
5 删除单链表重复元素
6 合并单链表
7 顺序表和链表的递归输出
8 置逆栈
9 用栈实现队列操作
10共享存储空间的栈的基本操作
11 括号匹配检验
四 查找排序算法
1 折半查找
2 分块查找
3 哈希表的插入
4 哈希表的查找
5 哈希表的删除
6 直接插入排序
7 希尔排序
8 冒泡排序
9 快速排序
10 简单选择排序
11 堆排序
12 两路归并排序
树形结构
一 类型定义
1 二叉链表
2 线索二叉树
二 算法
1 二叉树的遍历（非递归）
a 二叉树的层次遍历
b 二叉树先序（中序）遍历
c 二叉树的后序遍历
2 线索二叉树
a 建立中序线索二叉树（递归）
b中序线索树上查找前驱结点
c中序线索树上查找后继结点
d 先序线索树上查找前驱和后继结点（了解）
e 后序线索树上查找前驱和后继结点（了解）
f 中序线索树中查找父亲结点
g 中序线索树上查找结点在前序序列的后继
I 中序线索树上查找结点在后序序列的前驱
j 中序线索树上查找结点在后序序列的后继
k 中序线索树上查找值为x的结点
l 中序线索树的更新
3 二叉树相关算法
a 统计二叉树总结点数
b 统计二叉树叶子结点数
c 统计二叉树单孩子结点数
d 从根结点到指定结点的路径问题
e 求二叉树的深度
f 求二叉树指定结点的深度
g 释放二叉树所有结点
h 把一棵树拆分成两棵树
i 根据二叉树输出对应的算数表达式
j 根据先序和中序序列确定二叉树
k 求二叉树中最大结点
l 二叉树顺序和链式结构转换
m 求两节点最近的公共祖先
n 每个结点交换左右孩子
4 二叉排序树
a 二叉排序树的插入
b 二叉排序树的建立
c 二叉排序树的查找
d 二叉排序树的删除
5 平衡二叉树
6 树、森林、二叉树的转换
7 哈夫曼树
图形结构
一 存储结构及其创建与转换
1 邻接矩阵
2 邻接表
3 十字链表
二 图的遍历及连通性
1 深度遍历
2 广度遍历
三 拓扑排序及关键路径
四 最小生成树
1 Prim算法
2 Kruskal）算法
五 最短路径(Dijkstra算法)
六 其它算法
13 各种排序算法性能比较
线性结构
typedef struct node
ElemType data;
{
struct node * next;
}SLink;
一 类型定义
1 顺序表
# define MAXSIZE 100
typedef struct
{
ElemType data [MAXSIZE];
int length;
}SqList;
2 单链表
3 双链表
typedef struct node
ElemType data;
{
struct node *prior,*next;
}dlink;
二 基础要点
1 单链表
2 双链表
三 算法
1 删除顺序表中重复元素
void delsame( int A[], int count )
0
{
int i, j, k;
if( N > 1 )
j = 1;
{
for( i =1; i < N; i++ )
{
k = 0;
while( k < j && A[k] != A[i] )
if( k >= j )
k++;
A[j++] == A[i];
}
A[j] == ‘\0’
}
}
2 给无序表建有序索引表
typedef struct indexelem
{
KeyType key;
int
sn;
//关键字
//序号
//索引项
}IndexType;
IndexType idx[1...m];
DataType data[1...m]; //原顺序表
for( i = 1; i <=m; i++ )
{
//索引表
j = i - 1;
while( j > 0 && idx[j].key > data[i].key )
{
idx[j+1] = idx[j];
j--;
//把大于 data[i].key 的所有 idx[j].key 后移
}
idx[j+1].key = data[i].key;
idx[j+1].sn = i;
//插入 data[i].key 至 idx 中，并记下其序号 i
}
3 逆置单链表
void reverse( LinkList H )
{
SNode *p, *temp;
P = H->next;
H->next = NULL;
while( p )
{
temp = p;
p = p->next;
temp->next = H->next;
H->next = temp;
}
}
void reverse( LinkList H )
SNode *p, *q, *temp;
{
P = H->next;
q = NULL;
while( p )
{
temp = p;
p = p->next;
temp->next = q;
q = temp;
1
}
H->next = q;
}
4 拆分单链表
decompese( SNode *L,SNode *ha,SNode *hb,SNode *hc )
{
if( (p->data >= ‘A’ && p->data <= ‘Z’)||(p->data >= ‘a’ && p->data <= ‘z’) )
{
SNode *temp,*p;
p = L;
ha = (SNode*)malloc(sizeof(SNode));
hb = (SNode*)malloc(sizeof(SNode));
hc = (SNode*)malloc(sizeof(SNode));
ha->next = ha;
hb->next = hb;
hc->next = hc;
while( p )
{
temp = p;
p = p->next;
temp->next = ha->next;
ha->next = temp;
}
else if(p->data >= ‘0’ && p->data <= ‘9’ )
{
temp = p;
p = p->next;
temp->next = hb->next;
hb->next = temp;
}
else
{
}
}
temp = p;
p = p->next;
temp->next = hc->next;
hc->next = temp;
}
5 删除单链表重复元素
void delete(LinkList H)
SNode *p,*q,*r;
{
P = H->next;
while( p != NULL )
{
q=p;
while ( q->next )
{
if ( q->next->data == p->data )
{
r = q->next;
q->next = r->next;
free(r);
}
else
q = q->next;
2
}
p = p->next;
}
}
6 合并单链表
LinkList merge(LinkList A,LinkList B)
{
LinkList C;
SNode *p,*q;
P = A->next;
q = B->next;
C = A;
C->next = NULL;
free(B);
while ( p && q )
{
if (p->datadata)
{
s = p;
p = p->next;
}
else
{
}
s = q;
q = q->next;
s->next = C->next;
C->next = s;
}
if ( p == NULL )
if ( q==NULL)
while (r )
r = q;
r=p;
s =r;
r = r->next;
s->next = C->next;
C->next = s;
{
}
/*插入到 C 表的头部*/
/* 将剩余的结点一个个摘下，插入到 C 表的头部*/
}
7 顺序表和链表的递归输出
已知 head 是带头结点的单链表的头指针，试编写逆序/顺序输出表中各元素的递归算法；
有一个整数数组 A[n]，按顺序/逆序递归输出数组中的各元素
output( LinkList *head )
if( head != NULL )
{
{
output( head->next );
printf( “%d”,head->data );
//printf 在 output 下为逆序输出，在上为顺序输出
}
}
8 带访问频度的双向链表的查找
3
8 置逆栈
void reverse( Stack *s )
{
Stack s1, s2;
ElemType x;
InitStack( s1 );
InitStack( s2 );
while( StackEmpty( s ) != 0 )
{
Pop( s, x );
Push( s1, x );
}
while( StackEmpty( s1 ) != 0 )
{
Pop( s1, x );
Push( s2, x );
}
while( StackEmpty( s2 ) != 0 )
{
Pop( s2, x );
Push( s, x );
}
//将 s 栈中的内容转移到 s1 栈中
//将 s1 栈中的内容转移到 s2 栈中
//将 s2 栈中的内容转移到 s 栈中
}
9 用栈实现队列操作
int EnQueue( Stack *s1, Stack *s2, ElemType x )
{
if( s1->top == MaxSize )
//队列上溢
return -1;
Push( s1, x );
return 0;
else
{
}
}
4
int DeQueue( Stack *s1, Stack *s2, ElemType *x )
{
ElemType y;
while( StackEmpty(s1) != 0 )
{
Pop( s1, y );
Push( s2, y );
}
Pop( s2, x );
while( StackEmpty(s2) != 0 )
{
Pop( s2, y );
Push( s1, y );
}
//将 s1 的所有元素退栈进入 s2 中
//将 s2 的栈顶元素退栈并赋给 x
//将 s2 余下的元素退栈后进入 s1 中
}
10 共享存储空间的栈的基本操作
top1 = 1;
top2 = m;
int push( ElemType x, int i )
{
return -1;
if( top1 == top2 - 1 )
else if( i == 1 )
top1++;
{
c[top1] = x;
}
else
{
top2--;
c[top2] = x;
}
return 0;
//上溢出
//对第一个栈进行进栈操作
//对第二个栈进行进栈操作
}
int pop( ElemType *x, int i )
{
if( i == 1 )
{
if( top1 == 0 )
else
{
x = c[top1];
top1--;
//对第一个栈进行出栈操作
return -1;
//栈 1 下溢出
}
}
else
{
if( top2 == m + 1 )
else
{
x = c[top2];
top2++;
}
}
return 0;
}
void setnull( int i )
{
if( i == 1 )
else
}
top1 = 1;
top2 = m;
//对第二个栈进行出栈操作
return -1;
//栈 2 下溢出
5
11 括号匹配检验
#define m 100
Correct(exp,tag)
{
int top=0; i=1; tag=1
while(i<=m&&tag)
{
if(exp[i]==’(‘|| exp[i]==’[‘‘|| exp[i]==’{‘)
st[top++]=exp[i];
if(exp[i]==’)’)
if(st[top]==’(’)
else
tag=0;
if(exp[i]==’]’)
if(st[top]==’(’)
else
tag=0;
if(exp[i]==’}’)
if(st[top]==’(’)
tag=0;
else
top--;
top--;
top--;
i++;
}
If(top>0)
tag=0;
}
四 查找排序算法
1 折半查找
#define MAX 100
typedef struct
{
KeyType key;
ElemType date;
}RecType;
typedef struct
{
RecType r[MAX];
int length;
}sqlist;
int Binary_Search( sqlist R, KeyType k )
{
int mid, low=1, high=r.length；
while( low <= high )
{ mid = ( low + high ) / 2；
if( k < R.r[mid].key )
high = mid - 1；
else if( k > R.r[mid].key )
low = mid + 1；
else
return mid;
}
return -1;
}
6
2 分块查找
3 哈希表的插入
hashinsert( int s[], int m, int key )
{
s[H] = key;
H = hash( key );
if( s[H] == 空 )
else
{
}
s[H1] = key;
H1 = (H+1)%m;
while( s[H1] != 空 )
H1 = (H1+1)%m;
}
4 哈希表的查找
hashsearch( int s[], int m, int key )
{
H = hash( key );
if( s[H] == 空 )
else if( s[H] == key )
else
{
return -1;
return H;
H1 = (H+1)%m;
while( s[H1] != key && s[H1] != 空 && H1 != H )
H1 = (H1+1)%m;
}
7
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
