计算机科学与技术学院
课程设计说明书
题目：双向循环链表操作的实现
哈夫曼树
课程：数据结构
院（部）：计算机科学与技术学院专业：
班级：
学生姓名：
学号：
指导教师：
完成日期： 2016/12/29
目录
课程设计任务书一................................................ I 课程设计任务书二............................................... I I 双向循环链表操作的实现 (3)
一、问题描述 (3)
二、数据结构 (4)
三、逻辑设计 (6)
四、编码 (6)
五、测试数据 (7)
六、测试情况 (10)
所选题目........................................ 错误!未定义书签。
一、问题描述 (11)
二、数据结构 (11)
三、逻辑设计 (11)
四、编码 (12)
五、测试数据 (15)
六、测试情况 (16)
结论 (18)
参考文献 (23)
课程设计指导教师评语 (24)
课程设计任务书一
课程设计任务书二
指导教师（签字）：教研室主任（签字）
双向循环链表操作的实现
一、问题描述
1、建表
Head
2、插入
3、删除
4、就地逆置
二、数据结构
建表
public Create(int n) throws Exception {
this();
Scanner sc = new Scanner(System.in);
for (int j = 0; j < n; j++)
insert(n, sc.next());
}
插入
public void insert(int i, Object x) throws Exception { Node p = head.next;
int j = 0;
while (!p.equals(head) && j < i) {
p = p.next;
j++;
}
if (j != i && !p.equals(head))
throw new Exception("插入位置不对");
Node s = new Node(x);
p.pr.next=s;
s.pr=p.pr;
s.next=p;
p.pr=s;
}
删除
public void remove(int i) throws Exception {
Node p = head.next;
int j = 0;
while (!p.equals(head) && j < i) {
p = p.next;
++j;
}
if (j != i)
throw new Exception("删除位置不对");
p.pr.next=p.next;
p.next.pr=p.pr;
}
返回元素
public Object get(int i) throws Exception {
Node p = head.next;
int j = 0;
while (!p.equals(head) && j < i) {
p = p.next;
++j;
}
if (j > i || p.equals(head)) {
throw new Exception("第" + i + "个元素不在");
}
return p.data;
}
计算长度
public int length() {
Node p = head.next;
int length = 0;
while (!p.equals(head)) {
p = p.next;
++length;
}
return length;
}
查找位置
public int indexOf(Object x) {
Node p = head.next;
int j = 0;
while (!p.equals(head) && !p.data.equals(x)) { p = p.next;
++j;
}
if (!p.equals(head))
return j;
else
return -1;
}
遍历
public void display() {
Node node = head.next;
while (!node.equals(head)) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
就地逆置
public void trs(){
Node p=head.next;
while(p!=head){
