线性表

从顺序表中删除具有最小值的元素假设唯一并由函数返回被删函数的值空出的位置由最后一个元素填补若顺序表为空则显示出错信息并退出运行。

思路

搜索整个顺序表查找最小值元素并记住其位置搜索结束后用最后一个元素填补空出的原最小值元素的位置。

【注意】别忘了边界条件和线性表长度要1因为属于改变线性表内容所以传进去的是地址

bool

该步可以不用要不需要太注意题目未提的边界L.data[pos]

true;

用cnt统计值不为x的数字的个数当遍历到某数值不为x时将其移动到线性表中表cnt-1的位置。

*/void

初始时视第一个数为不重复的数从左向右移动若该数与前一个数不相同则可视为不重复的数。

若该数为第cnt个不重复的数则将其插入到数组中的第cnt个位置上

*/void

(LNode*)malloc(sizeof(LNode));q-data

x;q-next

算法思想设置两个指针p和q,指针p每次走一步指针q每次走两步当指针q到达链尾时指针p恰好在链表的中间结点

void

指针p先向前走k步走到第k个结点时令指针q指向头结点随后让指针p和指针q同时向后走

*/bool

//p指向链表的第一个结点同时也是逆转后的最后一个结点if(p

NULL)

指针p、q分别指向两个单词所在链表的头节点遍历一遍链表分别得到两个链表的长度

假设一个链表比另一个链表的长度长k,那么指向该链表的指针先向前移动k步之后同步遍历两个链表

*//*

该算法使用空间换时间的思想开一个大小为n1的数组a;各元素的初值为0.从头一次扫描链表

中的各结点。

同时检查a[|data|]的值若为0则保留该结点并令a[|data|]1否则将该结点

从链表中删除

1先找出算法L的中间结点为此设置两个指针p和q,指针p每次走一步指针q每次走两步当指针q到达链尾时指针p恰好在链表的中间结点

void

//p为中间结点q为后半段头结点//开始逆置while(q-next

NULL){r

NULL){visit(T);PreOrder(T-lchild);PreOrder(T-rchild);}

void

NULL){PreOrder(T-lchild);visit(T);PreOrder(T-rchild);}

void

NULL){PreOrder(T-lchild);PreOrder(T-rchild);visit(T);}

非递归遍历

p-lchild;}else{//此时已经遍历完左子树了才能访问根节点Pop(s,

p);visit(p);

//用来接收队头InitQueue(Q);EnQueue(Q,

T);while(!IsEmpty(Q)){DeQueue(Q,

NULL)

算法思想利用原有的层次遍历算法出队的同时将各结点指针入栈在所有的结点入栈后再从栈顶开始依次访问结点

void

{InitQueue(Q);InitStack(S);EnQueue(Q,

T);BiTree

p-lchild);if(p-rchild)EnQueue(Q,

p-rchild);}//自下而上从右到左的层次遍历while(IsEmpty(S)

false){Pop(S,

算法思想采用层次遍历算法设置变量level来记录当前结点所在的层数设置变量last指向当前层的最右结点每次层次遍历出队时队头指针与last比较若相等则lever加一并让last指向下一层的最右结点即当前的队尾结点直到遍历完成level即为二叉树的高度

注意事项

算法思想采用层次遍历算法遇到空节点时查看其后是否有非空节点不需要遍历完所有结点,当某层结点都为空时自然没有后代若有则二叉树不是完全二叉树

void

算法思想采用后序递归算法对于b结点先交换b结点左孩子的左右子树再交换b结点右孩子的左右子树最后再交换b结点的左右孩子

void

NULL){Work(T-lchild);Work(T-rchild);//交换三部曲BiTree

temp

方法使用全局变量来记录是否已经找到该值并将该值记录在全局变量中

int

题目对于树中每个元素值为x的结点删除以它为根的子树并释放相应的空间

释放内存用free();

值为x的结点的父亲在删完子树后需要指向NULL,所以通过父亲来判断孩子的值是否为x;

void

{if(bt){Delete(bt-lchild);Delete(bt-rchild);free(bt);}

}void

x)Delete(T);else{if(T-lchild-data

//孩子值为x删掉并将孩子位置换成NULL{Delete(T-lchild);T-lchild

x);if(T-rchild-data

题目设有一棵满二叉树已知其先序序列为pre(字符串)设计一个算法求其后序序列post。

对于一般二叉树而言仅根据先序或后序序列不能确定另一个遍历序列。

但对于满二叉树可以确定

#includestdio.hvoid

题目将二叉树的结点按从左到右的顺序连成一个单链表表头指针为head,二叉树按二叉链表方式存储链接时用叶结点的右指针域来存放单链表指针

算法思想使用先序遍历遍历到的叶节点的顺序就是从左到右的故用pre指针记录前一个叶节点即可。

LinkList

T;}}Work(T-lchild);Work(T-rchild);}return

head;

对于默认图即不带权在邻接矩阵中如两点之间存在边则g[a][b]1.否则为0

算法思想在邻接矩阵中对于每个顶点其所在行中1的个数为该顶点对应的出度其所在列1的个数为该顶点对应的入度。

因此可以枚举每个顶点用count1记录出度用count2记录入度用ans来记录K顶点的个数当count1count2时输入该顶点ans加一。

最后返回ans的值。

int

算法思想从矩阵A的右上角即第一行的最后一列的那个元素开始比较若当前元素小于目标值则向下移动一行若当前元素大于目标值则向左移动一列

若当前元素等于目标值则返回true,如果移动的过程越界了说明矩阵中不存在该目标值返回false。

并查集