1 import java.util.Scanner;  2   3 class DATA2 {  4     String key; // 结点的关键字  5     String name;  6     int age;  7 }  8   9 class CLType // 定义链表结构 10 { 11     DATA2 nodeData = new DATA2(); 12     CLType nextNode; 13  14     // 追加结点 15     CLType CLAddEnd(CLType head, DATA2 nodeData) { 16         CLType node, htemp; 17         if ((node = new CLType()) == null) { 18             System.out.print("申请内存失败！\n"); 19             return null; // 分配内存失败 20         } else { 21             node.nodeData = nodeData; // 保存数据 22             node.nextNode = null; // 设置结点指针为空，即为表尾 23             if (head == null) // 头指针 24             { 25                 head = node; 26                 return head; 27             } 28             htemp = head; 29             while (htemp.nextNode != null) // 查找链表的末尾 30             { 31                 htemp = htemp.nextNode; 32             } 33             htemp.nextNode = node; 34             return head; 35         } 36     } 37  38     // 添加头结点 39     CLType CLAddFirst(CLType head, DATA2 nodeData) { 40         CLType node; 41         if ((node = new CLType()) == null) { 42             System.out.print("申请内存失败！\n"); 43             return null; // 分配内存失败 44         } else { 45             node.nodeData = nodeData; // 保存数据 46             node.nextNode = head; // 指向头指针所指结点 47             head = node; // 头指针指向新增结点 48             return head; 49         } 50     } 51  52     // 查找结点 53     CLType CLFindNode(CLType head, String key) { 54         CLType htemp; 55         htemp = head; // 保存链表头指针 56         while (htemp != null) // 若结点有效，则进行查找 57         { 58             if (htemp.nodeData.key.compareTo(key) == 0) // 若结点关键字与传入关键字相同 59             { 60                 return htemp; // 返回该结点指针 61             } 62             htemp = htemp.nextNode; // 处理下一结点 63         } 64         return null; // 返回空指针 65     } 66  67     // 插入结点 68     CLType CLInsertNode(CLType head, String findkey, DATA2 nodeData) { 69         CLType node, nodetemp; 70         if ((node = new CLType()) == null) // 分配保存结点的内容 71         { 72             System.out.print("申请内存失败！\n"); 73             return null; // 分配内存失败 74         } 75         node.nodeData = nodeData; // 保存结点中的数据 76         nodetemp = CLFindNode(head, findkey); 77         if (nodetemp != null) // 若找到要插入的结点 78         { 79             node.nextNode = nodetemp.nextNode; // 新插入结点指向关键结点的下一结点 80             nodetemp.nextNode = node; // 设置关键结点指向新插入结点 81         } else { 82             System.out.print("未找到正确的插入位置！\n"); 83             // free(node); //释放内存 84         } 85         return head; // 返回头指针 86     } 87  88     int CLDeleteNode(CLType head, String key) { 89         CLType node, htemp; // node保存删除结点的前一结点 90         htemp = head; 91         node = head; 92         while (htemp != null) { 93             if (htemp.nodeData.key.compareTo(key) == 0) // 找到关键字，执行删除操作 94             { 95                 node.nextNode = htemp.nextNode; // 使前一结点指向当前结点的下一结点 96                 // free(htemp); //释放内存 97                 return 1; 98             } else { 99                 node = htemp; // 指向当前结点100                 htemp = htemp.nextNode; // 指向下一结点101             }102         }103         return 0; // 未删除104     }105 106     int CLLength(CLType head) // 计算链表长度107     {108         CLType htemp;109         int Len = 0;110         htemp = head;111         while (htemp != null) // 遍历整个链表112         {113             Len++; // 累加结点数量114             htemp = htemp.nextNode; // 处理下一结点115         }116         return Len; // 返回结点数量117     }118 119     void CLAllNode(CLType head) // 遍历链表120     {121         CLType htemp;122         DATA2 nodeData;123         htemp = head;124         System.out.printf("当前链表共有%d个结点。链表所有数据如下：\n", CLLength(head));125         while (htemp != null) // 循环处理链表每个结点126         {127             nodeData = htemp.nodeData; // 获取结点数据128             System.out.printf("结点(%s,%s,%d)\n", nodeData.key, nodeData.name,129                     nodeData.age);130             htemp = htemp.nextNode; // 处理下一结点131         }132     }133 134 }135 136 public class LinkedList {137 138     public static void main(String[] args) {139         CLType node, head = null;140         CLType CL = new CLType();141         String key, findkey;142         Scanner input = new Scanner(System.in);143 144         System.out.print("链表测试。先输入链表中的数据，格式为：关键字 姓名 年龄\n");145         do {146             DATA2 nodeData = new DATA2();147             nodeData.key = input.next();148             if (nodeData.key.equals("0")) {149                 break; // 若输入0，则退出150             } else {151                 nodeData.name = input.next();152                 nodeData.age = input.nextInt();153                 head = CL.CLAddEnd(head, nodeData);// 在链表尾部添加结点154             }155         } while (true);156         CL.CLAllNode(head); // 显示所有结点157 158         System.out.printf("\n演示插入结点，输入插入位置的关键字：");159         findkey = input.next(); // 输入插入位置关键字160         System.out.print("输入插入结点的数据(关键字 姓名 年龄):");161         DATA2 nodeData = new DATA2();162         nodeData.key = input.next();163         nodeData.name = input.next();164         nodeData.age = input.nextInt();// 输入插入结点数据165         head = CL.CLInsertNode(head, findkey, nodeData); // 调用插入函数166         CL.CLAllNode(head); // 显示所有结点167 168         System.out.print("\n演示删除结点，输入要删除的关键字:");169 170         key = input.next(); // 输入删除结点关键字171         CL.CLDeleteNode(head, key); // 调用删除结点函数172         CL.CLAllNode(head); // 显示所有结点173 174         System.out.printf("\n演示在链表中查找，输入查找关键字:");175         key = input.next(); // 输入查找关键字176         node = CL.CLFindNode(head, key); // 调用查找函数，返回结点指针177         if (node != null) // 若返回结点指针有效178         {179             nodeData = node.nodeData; // 获取结点的数据180             System.out.printf("关键字%s对应的结点为(%s,%s,%d)\n", key, nodeData.key,181                     nodeData.name, nodeData.age);182         } else // 若结点指针无效183         {184             System.out.printf("在链表中未找到关键字为%s的结点！\n", key);185         }186     }187 }