第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
数据结构算法伪码汇总.pdf
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
数据结构算法汇总
目录
专题一 线性表 ..............................................................................................................................................1
1.线性表基本操作 ..............................................................................................................................1
2.顺序表 ................................................................................................................................................2
3.链表 ....................................................................................................................................................2
4.线性表应用 .......................................................................................................................................2
专题二 栈 ......................................................................................................................................................6
1.栈基本操作 .......................................................................................................................................6
2.顺序栈 ................................................................................................................................................6
3.链栈 ....................................................................................................................................................6
专题三 队列 ..................................................................................................................................................7
1.队列基本操作 ...................................................................................................................................7
2.顺序队列 ...........................................................................................................................................7
3.链式队列 ...........................................................................................................................................7
专题四 树 ......................................................................................................................................................7
1.树.........................................................................................................................................................7
2.二叉树 ................................................................................................................................................8
3.线索二叉树 .................................................................................................................................... 10
4.二叉排序树 .................................................................................................................................... 13
5.二叉树应用 .................................................................................................................................... 14
专题五 广义表 ........................................................................................................................................... 25
专题六 图 ................................................................................................................................................... 26
1.图的存储结构 ................................................................................................................................ 26
2.邻接表相关 .................................................................................................................................... 26
专题七 排序与查找 .................................................................................................................................. 27
专题一 线性表
1.线性表基本操作
InitList(&L)
Length(L)
LocateElem(L, e)
GetElem(L, i)
ListInsert(&L, i, e)
ListDelete(&L, i, &e)
//初始化表
//求表长
//按值查找操作
//按位查找操作
//插入操作
//删除操作
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
PrintList(L)
Empty(L)
DestroyList(&L)
//输出操作
//判空操作
//销毁操作
2.顺序表
ElemType data[MaxSize];
int length;
//静态分配
#define MaxSize 50
typedef struct{
}SqList;
//动态分配
#define InitSize 100
typedef struct{
}SeqList;
//动态分配语句：
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
ElemType *data;
int MaxSize, length;
3.链表
ElemType data;
struct LNode *next;
ElemType data;
struct DNode *prior, *next;
//单链表：
typedef struct LNode{
}LNode, *LinkList;
//双链表：
typedef struct DNode{
}DNode, *DLinklist;
//静态链表：
#define MaxSize 50
typedef struct{
}SLinkList[MaxSize];
ElemType data;
int next;
4.线性表应用
1.删除不带头结点单链表 L 中所有值为 x 结点
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
//用于指向待删除结点
//递归出口
//若L所指结点值为x
//L指向下一结点
return;
void Delete_x(LinkList &L, int x){
}
LinkList p;
if (L == NULL)
if (L->data==x){
}
else Delete_x(L->next, x);
p = L;
L = L->next;
free(p);
Delete_x(L, x);
2.删除带头结点单链表 L 中所有值为 x 结点
法一:设置前驱指针，扫描
q = p;
p = p->next;
pre->next = p;
free(q);
void Delete_x(LinkList &L, int x){
}
LinkList pre, p, q;
pre = L;p = L->next;
while (p!=NULL){
}
if (p->data == x){
}
else {
}
pre = p;
p = p->next;
法二:尾插法建立单链表
void Delete_x1(LinkList &L, int x){
LinkList p, r, q;
p = L->next;r = L;
while (p != NULL){
if (p->data != x){
}
else {
r->next = p;
r = p;
p = p->next;
q = p;
p = p->next;
free(q);
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
}
}
r->next = NULL;
}
3.反向输出带头结点单链表 L 中所有结点值
void R_Print(LinkList L){
if (L->next != NULL){
R_Print(L->next);
cout << L->next->data << " ";
}
}
4.删除带头结点单链表 L 中最小值结点
//p为工作指针，pre指向其前驱
void Delete_min(LinkList &L){
}
LinkList p, pre;
LinkList minP, minPre; //minP指向候选最小值，minPre指向其前驱
p = minP = L->next;
pre = minPre = L;
while (p!=NULL){
}
minPre->next = minP->next;//删除最小值结点
free(minP);
if (p->datadata){
}
pre = p;
p = p->next;
minP = p;
minPre = pre;
5.就地逆置带头结点单链表 L
法一:头插法
void Reverse_L(LinkList &L){
}
LinkList p, q;
p = L->next;
L->next = NULL;
while (p!=NULL){
}
q = p;
p = p->next;
q->next = L->next;
L->next = q;
法二:指针反转
void Reverse_L(LinkList L){
LinkList pre, p, r;
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
p = L->next;
r = p->next;
p->next = NULL;
while (r != NULL){
}
L->next = p;
pre = p;
p = r;
r = r->next;
p->next = pre; //指针反转
//表头指向最后结点
}
6.带头结点单链表 L 升序排列
//开始插入排序
//r指向p后继结点，保证不断链
//构造只含一个结点的链表
直接插入排序
void sort(LinkList &L){
LinkList pre, p, r;
p = L->next;
r = p->next;
p->next = NULL;
p = r;
while (p!=NULL){
r = p->next;
pre = L;
//从表头开始扫描p的插入位置
while (pre->next != NULL&&pre->next->data < p->data)
p->next = pre->next;//将p结点插入pre后
pre->next = p;
p = r;
}
}
pre = pre->next;
7.删除带头结点单链表 L 中介于给定的两个值之间元素
//p为工作指针，pre指向其前驱
void RangeDelete(LinkList &L,int min,int max){
if (min < p->data&&p->data < max){
}
else{
}
LinkList p, pre;
p = L->next;pre = L;
while (p!=NULL){
pre->next = p->next;
free(p);
p = pre->next;
pre = p;
p = p->next;
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
}
}
专题二 栈
1.栈基本操作
InitStack(&S)
StackEmpty(S)
Push(&S, x)
Pop(&S, &x)
GetTop(S, &x)
ClearStack(&S)
//初始化操作
//判空操作
//进栈操作
//出栈操作
//读栈顶元素
//销毁操作
2.顺序栈
ElemType data[MaxSize];
int top;
#define MaxSize 50
typedef struct{
}SqStack;
//栈顶指针：初始时设置S.top = -1
//栈顶元素：S.data[S.top]
//进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素
//出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1
//栈空条件：S.top == -1
//栈满条件：S.top == MaxSize – 1
//栈长：S.top + 1
3.链栈
typedef struct SNode{
}SNode, *LiStack;
ElemType data;
struct SNode *next;
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
专题三 队列
1.队列基本操作
InitQueue(&Q)
QueueEmpty(Q)
EnQueue(&Q, x)
DeQueue(&Q, &x)
GetHead(Q, &x)
//初始化操作
//判空操作
//入队操作
//出队操作
//读队头元素
2.顺序队列
ElemType data[MaxSize];
int front, rear;
#define MaxSize 50
typedef struct{
}SqQueue;
//初始条件：Q.front = Q.rear = 0
//队空条件：Q.front == Q.rear
//进队操作：队不满时，++Q.rear；Q.data[Q.rear] = x；
//出队操作：队不空时，++Q.front；x = Q.data[Q.front]；
3.链式队列
ElemType data;
struct QNode *next;
typedef struct QNode{//链式队列结点
}QNode;
typedef struct{ //链式队列
}LiQueue;
//当 Q.front == NULL 且 Q.rear == NULL 时，链式队列为空。
QNode *front, *rear;
专题四 树
1.树
1.树存储结构
1.树双亲存储结构
#define MAX_TREE_SIZE 100
电子科大计算机考研免费提供 群号：367060756 ——by HarvestWu
ElemType data;
int parent;
typedef struct{
}PTNode;
typedef struct{
}PTree;
PTNode nodes[MAX_TREE_SIZE];
int n;
2.树孩子兄弟存储结构
typedef struct CSNode{
}CSNode,*CSTree;
ElemType data;
struct CSNode *firstchild,*nextsibling;
2.二叉树
1.二叉树链式存储结构
#define ElemType int
#define MaxSize 1000
typedef struct BiTNode{
}BiTNode,*BiTree;
ElemType data;
struct BiTNode *lchild, *rchild;
//数据域
//左、右孩子指针
2.二叉树的遍历
1.递归先序遍历
void PreOrder(BiTree T){
}
if (T != NULL){
}
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
2.非递归先序遍历
//访问结点
//递归遍历左子树
//递归遍历右子树
void PreOrder(BiTree T){
InitStack(S); BiTree p = T;
if (p != NULL)
{
Push(S, p);
while (!IsEmpty(S))
{
//初始化栈；p是遍历指针
//p不空继续执行
//指针进栈
//栈不空时循环
Pop(S, p);
visit(p);
if (p->rchild != NULL) //右子树不为空
Push(S,p->rchild); //右子树进栈
//指针退栈
//访问结点
相关推荐
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
