单链表的基本操作与排序

统计字符串中各字母出现的次数，并按照规定格式和 自然顺序 输出给定字符串。如：输入”asdfdfdassssddf” ，输出：a:2 d:5 f:3 s:5 。

题目的层次分析

分析题目可得，目标程序需要实现字符串的输入、遍历、排序、输出四项基本操作。其中字符串的输入与输出都很基础，则重心放在遍历与排序上。

字符串的遍历

在给定字符串进行遍历的情况下，我们有两个选择进行遍历：数组与链表。但链表更容易实现动态插入，所以在这个题目中我们选择用链表来实现其操作。

定义结构体，分别存放字母和频次用以输出。在遍历时，第一次检测到某个字母时将其插入链表，同时令其频次+1，之后的遍历也在此基础上进行。 其中字母的抓取就是单纯的对字符串进行遍历，根据字母出现的先后顺序构建链表。 代码如下：

struct Node *getNodeByKey(char key) { struct Node *node; node = list_head; while (node != NULL) { if (node->data.key == key) return node; node = node->next; } return NULL; } void insert(char key) { struct Node *node = (Node*)malloc(sizeof(struct Node)); node->data.key = key; node->data.num = 1; node->next = NULL; if (list_head == NULL) { list_head = node; } if (list_tail == NULL) { list_tail = node; } else { list_tail->next = node; list_tail = node; } }

链表的排序

排序是此题中的一个难点。最终选择的方法是冒泡排序，来实现顺序输出。 基本思想：改变链表指针的指向，字符两两进行比较（ASCLL码），将较大的一方“冒”到最后，和数组的冒泡排序基本方法类似，只是过程稍稍麻烦一些。指针的指向很容易搞错，是其中很需要注意的一个问题。 建立四个指针，分别是current，prevent，temporary，last，我们通过这四个指针来改变链表的顺序。 current和prevent开始时都指向头结点（prevent作为current的父结点，指向其前一个位置），temporary用来作为缓存位置记录指针指向，last则是指向尾结点。 需要注意的是在交换结束时我们还需要注意让prevent和current的重新指回头结点。 尾结点和头结点都是循环中非常需要重要的部分，倘若情况考虑不全面，很容易进入死循环。 在搞懂了基本思想之后我们需要考虑边界问题——也就是字符串的输入情况。 1、字符串只有一个字母； 2、遍历到尾节点和NULL比较的情况 3、第一次比较就发生交换 这次写代码就在“当第一次比较就发生交换后，进入死循环”的情况下卡了好久，最后再单独设定条件当循环次数i=1时单独对prev节点的位置进行改变。 代码如下：

/* 交换指针域，冒泡排序单链表 */ void sortList() { struct Node *cur, *prev, *tmp, *last; cur = list_head; prev = list_head; last = NULL; int i, j; j = 0; while (cur != last) { i = 0; while (cur != NULL && cur->next != last) { if (cur->data.key > cur->next->data.key) { /* cur, cur->next 交换位置 */ tmp = cur->next; cur->next = cur->next->next; tmp->next = cur; if (i > 0) prev->next = tmp; // 第一次交换: prev == cur /* 移动 prev, cur 节点，这里cur已经是下一个 */ prev = tmp; /* 维护头结点 */ if (i == 0) list_head = prev; } else { /* 节点不交换位置 */ prev = cur; cur = cur->next; } i++; } /* 维护尾节点 */ if (j == 0) { list_tail = cur; list_tail->next = NULL; } j++; last = cur; cur = list_head; prev = list_head; } }

完整代码

最后的拼接倒是问题不大，最容易出现的错误还是冒泡排序那里，双重循环的嵌套，以及边界情况的考虑是这个试题的难点，不过冒泡排序算是比较复杂的一种方式，有更为简单的方法但我还并未写出来，下面把完整的代码贴出来作为参考：

// ConsoleApplication1.cpp: 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<stdio.h> #include<stdlib.h> struct Data { char key; int num; }; struct Node { struct Data data; struct Node *next; }; const char *testString = "z"; struct Node *list_head = NULL; struct Node *list_tail = NULL; struct Node *getNodeByKey(char key) { struct Node *node; node = list_head; while (node != NULL) { if (node->data.key == key) return node; node = node->next; } return NULL; } void insert(char key) { struct Node *node = (Node*)malloc(sizeof(struct Node)); node->data.key = key; node->data.num = 1; node->next = NULL; if (list_head == NULL) { list_head = node; } if (list_tail == NULL) { list_tail = node; } else { list_tail->next = node; list_tail = node; } } void printList() { struct Node *node; node = list_head; while (node != NULL) { printf("%c:%d ", node->data.key, node->data.num); node = node->next; } printf("\n"); } /* 交换指针域，冒泡排序单链表 */ void sortList() { struct Node *cur, *prev, *tmp, *last; cur = list_head; prev = list_head; last = NULL; int i, j; j = 0; while (cur != last) { i = 0; while (cur != NULL && cur->next != last) { if (cur->data.key > cur->next->data.key) { /* cur, cur->next 交换位置 */ tmp = cur->next; cur->next = cur->next->next; tmp->next = cur; if (i > 0) prev->next = tmp; // 第一次交换: prev == cur /* 移动 prev, cur 节点，这里cur已经是下一个 */ prev = tmp; /* 维护头结点 */ if (i == 0) list_head = prev; } else { /* 节点不交换位置 */ prev = cur; cur = cur->next; } i++; } /* 维护尾节点 */ if (j == 0) { list_tail = cur; list_tail->next = NULL; } j++; last = cur; cur = list_head; prev = list_head; } } int main() { const char *input = testString; struct Node *node; while (*input != '\0') { node = getNodeByKey(*input); if (node == NULL) { insert(*input); } else { node->data.num++; } input++; } sortList(); printList(); return 0; }

其他方法

另外一种方式比起这种稍微简单一些：建立数组，直接把字母的ASCLL值作为数组的下标，把频次作为数组存放的值。遍历字符串后正序输出数组（只输出>0的部分）。不过这种方法与链表关系不大，就不再写出具体代码。