建立频度链表统计字符频度
时间: 2024-05-26 12:06:51 浏览: 17
频度链表是一种用于统计字符频度的数据结构,它可以有效地记录每个字符出现的次数,并且可以按照频度进行排序。下面是建立频度链表统计字符频度的步骤:
1. 创建一个空的频度链表,链表中的每个节点包含字符和对应的频度。
2. 遍历待统计的字符串,对于每个字符:
- 如果该字符在频度链表中已经存在,则将对应节点的频度加1。
- 如果该字符在频度链表中不存在,则创建一个新节点,并将其插入到合适的位置,使得链表按照频度从小到大排序。
3. 遍历完所有字符后,频度链表中的节点就是按照频度排序的字符及其对应的频度。
以下是建立频度链表统计字符频度的示例代码:
```python
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.next = None
def insert_node(head, new_node):
if head is None:
return new_node
if new_node.freq < head.freq:
new_node.next = head
return new_node
curr = head
while curr.next and new_node.freq >= curr.next.freq:
curr = curr.next
new_node.next = curr.next
curr.next = new_node
return head
def build_frequency_list(string):
freq_dict = {}
for char in string:
if char in freq_dict:
freq_dict[char] += 1
else:
freq_dict[char] = 1
head = None
for char, freq in freq_dict.items():
new_node = Node(char, freq)
head = insert_node(head, new_node)
return head
# 示例用法
string = "abracadabra"
frequency_list = build_frequency_list(string)
curr = frequency_list
while curr:
print(f"Character: {curr.char}, Frequency: {curr.freq}")
curr = curr.next
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)