建站小程序快速上线,研发个app需要多少钱,撰写网站建设规划设计任务书,软件设计包括哪些内容题1#xff1a;
某带头结点的非空单链表L中所有元素为整数#xff0c;结点类型定义如下#xff1a;
typedef struct node
{ int data; struct node *next;
} LinkNode;
设计一个尽可能高效的算法#xff0c;将所有小于零的结点移到所有大于等于零的结点的前面。
分…题1
某带头结点的非空单链表L中所有元素为整数结点类型定义如下
typedef struct node
{ int data; struct node *next;
} LinkNode;
设计一个尽可能高效的算法将所有小于零的结点移到所有大于等于零的结点的前面。
分析
定义一个p指针指向L-next一个pre指向头结点也就是p指针的前驱。
该题可以使用while循环先找到第一个小于0的数其实这一步也可以不要因为后面那个while也可以做到不过这里为了方便理解所以就加上了然后再使用while循环将该小于0的结点在原位置删除将其插入到头结点后面其实这里就有点像单链表的头插法然后指针指回pre的next,进行比较大于0就跳过往后查找小于0就按上面的规则进行删除然后使用头插法插入头结点后面直到所有结点都处理完毕。
void Move(LinkNode *L)
{ LinkNode *pL-next,*preL;while (p!NULL p-data0) //跳过小于0的结点{ prep;ppre-next;}while (p!NULL){ if (p-data0) //若*p结点值小于0{ pre-nextp-next; //从链表中删除*p结点p-nextL-next; //将*p结点插入到头结点之后L-nextp;ppre-next; //p指向*pre之后结点pre不变}else //若*p结点值不小于0{ prep; //pre、p同步后移一个结点pp-next;}}
}题2
假设二叉树中有n个结点每个结点值为单个字符而且所有结点值均不相同采用二叉链存储结构存储其结点类型定义如下
typedef struct node
{ char data; struct node *lchild,*rchild;
} BTNode;
请完成以下任务
1设计一个算法在二叉树b中查找x结点指结点值为x的结点若找到该结点返回其地址否则返回NULL。 BTNode *Findx(BTNode *b,char x) //在二叉树b中查找x结点
{ BTNode *p;if (bNULL) return NULL;else{ if (b-datax)return b;pFindx(b-lchild,x);if (p!NULL)return p;return Findx(b-rchild,x);}
}题3
2设计一个算法利用1小题设计的算法输出二叉树b中x结点的所有子孙结点值。
void Sons(BTNode *b,char x) //输出x结点的子孙初始时b指向x结点
{ if (b!NULL){ if (b-data!x)printf(%c ,b-data);Sons(b-lchild,x);Sons(b-rchild,x);}
}
void OutSons(BTNode *b,char x) //输出二叉树b中x结点的所有子孙结点值
{ BNode *p Findx(b,x);if (p!NULL)Sons(p,x);
}
