设计一个算法,通过一趟遍历在单链表中确定值最大的结点。 [题目分析] 假定第一个结点中数据具有最大值,依次与下一个元素比较,若其小于下一个元素,则设其下一个元素为最大值,反复进行比较,直到遍历完该链表。
时间: 2023-06-02 15:02:49 浏览: 113
算法如下:
1.定义一个变量max,存储当前最大值,初值为头结点的数据值。
2.定义一个指针p,指向头结点。
3.while循环,p不为空时执行以下操作:
a.如果p的数据值大于max,则将max更新为p的数据值。
b.将p指向下一个结点。
4.返回max,即为链表中的最大值。
代码实现如下:
```
int findMax(ListNode* head) {
if(head == nullptr) return -1; //链表为空,返回-1
int max = head->val; //存储当前最大值
ListNode* p = head; //指向头结点
while(p != nullptr) {
if(p->val > max) max = p->val; //更新最大值
p = p->next; //指向下一个结点
}
return max;
}
```
相关问题
20. 填空题 下面的算法是通过一趟遍历在单链表中确定值最大的结点。 请在空格处填上对应的代码。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p !=第1个空格 ){//如果下一个结点存在 if(p->data第2个空格 > pmax->data) pmax=第3个空格 ;//如果p的值大于pmax的值,则重新赋值 p=第4个空格;//遍历链表 } return 第5个空格 ->data; }
ElemType Max (LinkList L ){
if(L->next==NULL) return NULL;
pmax=L->next; //假定第一个结点中数据具有最大值
p=L->next->next;
while(p !=NULL){//如果下一个结点存在
if(p->data > pmax->data)
pmax=p;//如果p的值大于pmax的值,则重新赋值
p=p->next;//遍历链表
}
return pmax->data;
}
设s和t是表示成单链表的两个串,试编写一个找出s中第1个不在t中出现的字符(假定每个结点只存放一个字符)的算法。
可以使用哈希表来实现这个算法。
具体步骤如下:
1. 对于字符串t,将其中的每个字符都插入到哈希表中。
2. 遍历字符串s,对于其中的每个字符,查找其是否在哈希表中出现过。如果没有出现过,则找到了第1个不在t中出现的字符。如果遍历完s后仍然没有找到这样的字符,则说明s中的所有字符都在t中出现过。
代码实现如下:
```
char findFirstUniqueChar(ListNode* s, ListNode* t) {
unordered_set<char> hash;
ListNode* p = t;
while (p != nullptr) {
hash.insert(p->val);
p = p->next;
}
p = s;
while (p != nullptr) {
if (hash.find(p->val) == hash.end()) {
return p->val;
}
p = p->next;
}
return '\0';
}
```
其中,ListNode表示单链表结点,val表示结点存储的字符值。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)