数据结构上机作业(一)

一.上机内容

1、实现顺序存储结构下线性表的基本操作，数据类型自己确定。 2、输入一组数据，建立带头结点的单链表，实现线性表的基本操作，线性表中数据元素的类型自己确定。 3、试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2…,an）逆置为（an,an-1…,a1）。 4、已知有序表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于 maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你所写的算法的时间复杂度（注意mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 5、删除单链表中重复的元素，即留下单链表中值不相同的结点，并输出删除后单链表中的所有元素。 6*、某百货公司仓库中有一批电视机，试按价格从高到底的次序建立一个循环链表，每个结点有价格)数量和链指针三个域。现新到m台价格为h的电视机，修改原链表并输出修改后链表的所有内容。 7*、在理解一元多项式的加法算法基础上，编程实现一元多项式的减法。

二.代码实现

1.实现顺序存储结构下线性表的基本操作，数据类型自己确定

public class SqList<T> implements Ilist<T>{ // 属性 T[] array; int length; // 构造方法 public SqList(int capacity) { this.array = (T[]) new Object[capacity]; this.length = 0; } /** * 将顺序表置空 */ @Override public void clear() { this.length = 0; } /** * 判断顺序表是否为空 * @return */ @Override public boolean isEmpty() { return this.length==0; } /** * 返回顺序表的长度 * @return */ @Override public int getLength() { return this.length; } /** * 得到第i个元素 * @param i * @return */ @Override public T get(int i) throws Exception{ if (i<0 || i>=this.length){ throw new Exception("第 " + i +" 元素不存在"); } return this.array[i]; } /** * 在末尾插入元素 * @param t */ public void insert(T t) throws Exception { insert(this.length,t); } /** * 插入元素 * @param i * @param t */ @Override public void insert(int i, T t) throws Exception { // 这个length不是线性表的length,而是底层数组的length,因为不能超过底层数组的长度 if (i == this.array.length){ throw new Exception("长度已满,无法插入"); } if (i<0 || i > this.length){ throw new Exception("插入位置不合法,无法插入"); } // 能运行到这,表示能够进行插入 // 第i个元素及其后面的元素都要往后移动一位 for (int j = this.length; j > i ; j--) { // 后一位等于前一位 this.array[j] = this.array[j-1]; } // 插入 this.array[i] = t; // 长度加一 this.length++; } /** * 删除第i位的元素 * @param i */ @Override public void remove(int i) throws Exception { if (i < 0 || i > this.length){ throw new Exception("删除位置不合法,无法删除"); } // 第i处后面的元素都往前一位 for (; i < this.length - 1; i++) { this.array[i] = this.array[i+1]; } // 长度减一 this.length--; } /** * 返回下标首次出现t元素的下标,如果没有则返回-1 * @param t * @return */ @Override public int indexOf(T t) { for (int i = 0; i < this.length; i++) { if (t.equals(this.array[i])){ return i; } } return -1; } }

2、输入一组数据，建立带头结点的单链表，实现线性表的基本操作，线性表中数据元素的类型自己确定。

public class LinkList<T extends Comparable> implements Ilist<T>{ // 属性 Node head; // 头节点 int length; // 长度 // 内部节点类 private class Node{ // 数据 T item; // 下一节点 Node next; // 构造方法 public Node(Node next,T item) { this.item = item; this.next = next; } } // 构造方法 public LinkList() { this.head = new Node(null,null); this.length = 0; } /** * 将顺序表置空 */ @Override public void clear() { this.head = new Node(null,null); this.length = 0; } /** * 判断链表是否为空 * @return */ @Override public boolean isEmpty() { return this.length==0; } @Override public int getLength() { return this.length; } /** * 获得第i个元素 * @param i * @return * @throws Exception */ @Override public T get(int i) throws Exception { if (i<0 || i>=this.length){ throw new Exception("第 " + i +" 元素不存在"); } Node current = head; for (int j = 0;j <= i ;j++){ current = current.next; } return current.item; } /** * 在末尾插入新的节点 * @param t */ public void insert(T t) throws Exception { insert(this.length,t); } /** * 向指定位置,插入元素t * @param i * @param t * @throws Exception */ @Override public void insert(int i, T t) throws Exception { if (i<0 || i > this.length){ throw new Exception("插入位置不合法,无法插入"); } Node pre = head; // 找到第i个元素的前驱元素 for (int j = 0; j <= i-1 ; j++) { pre = pre.next; } // 创建新的节点 Node newNode = new Node(pre.next,t); // 让前驱元素指向节点 pre.next = newNode; // 长度加一 this.length++; } /** * 删除指定位置的元素 * @param i * @throws Exception */ @Override public void remove(int i) throws Exception { if (i < 0 || i > this.length){ throw new Exception("删除位置不合法,无法插入"); } // 找到前驱元素 Node pre = head; for (int j = 0; j < i ; j++) { pre = pre.next; } // 如果是最后一个节点 if (i == this.length){ pre.next = null; }else { // 前驱元素指向要删除的节点的下一节点 pre.next = pre.next.next; } // 长度减一 this.length--; } /** * 返回下标首次出现t元素的下标,如果没有则返回-1 * @param t * @return */ @Override public int indexOf(T t) { int count = -1; Node current = head; while(current.next !=null){ if (t.equals(current.item)){ return count; } count++; current = current.next; } return -1; } @Override public void display() { Node current = head.next; while (current != null){ System.out.print(current.item + " "); current = current.next; } System.out.println(); } }

3.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2…,an）逆置为（an,an-1…,a1）

/** * 实现顺序表的就地逆置 */ public void reverse(){ for (int i = 0, j = this.length-1; i < j; i++,j--) { T temp = this.array[i]; this.array[i] = this.array[j]; this.array[j] = temp; } }

4、已知有序表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于 maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你所写的算法的时间复杂度（注意mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

/** * 删除表中所有值大于mink且小于 maxk的元素 * @param mink * @param maxk */ public void remove(T mink,T maxk){ // 遍历 Node current = head.next; Node firstNodePre = head; Node lastNodeNext = null; boolean flag = true; while(current.next!=null){ // 找到第一个比mink大的节点的前驱 if (flag){ // 找到比mink大的节点 if (mink.compareTo(current.item) < 0){ flag = false; }else { firstNodePre = firstNodePre.next; } } if (maxk.compareTo(current.item) < 0){ lastNodeNext = current; break; } current = current.next; } // 找到这两个节点后 firstNodePre.next = lastNodeNext; }

5、删除单链表中重复的元素，即留下单链表中值不相同的结点，并输出删除后单链表中的所有元素。

/** * 删除单链表中重复的元素，即留下单链表中值不相同的结点，并输出删除后单链表中的所有元素 * @return */ public void removeSame() throws Exception { ArrayList<Node> arrayList = new ArrayList<>(); Node currentNode = head.next; while(currentNode != null){ int i = indexOf(currentNode.item); Node nextNode = currentNode.next; while (nextNode != null){ if (nextNode.item.equals(currentNode.item)){ arrayList.add(nextNode); // 通过下标来删除,函数解决,别总想着自己再实现一遍删除 remove(i); }else { i++; } nextNode = nextNode.next; } currentNode = currentNode.next; } // 遍历 for (Node node : arrayList){ System.out.println(node.item); } }

6*、某百货公司仓库中有一批电视机，试按价格从高到底的次序建立一个循环链表，每个结点有价格)数量和链指针三个域。现新到m台价格为h的电视机，修改原链表并输出修改后链表的所有内容。

7*、在理解一元多项式的加法算法基础上，编程实现一元多项式的减法。

/** * 多项式减法 * @param LA * @param LB * @return */ public PolynList minusPolyn(PolynList LA,PolynList LB){ Node ha = LA.head; // ha指向新形成链表的尾结点 Node qa = LA.head.next; // qa指向LA中需要计算的当前项 Node qb = LB.head.next; // qb指向LB中需要计算的当前项 while (qa != null && qb != null){ // 取出节点的数据域 PolynNode a = (PolynNode) qa.data; PolynNode b = (PolynNode) qb.data; // 比较a,b的指数大小 switch (cmp(a,b)){ case -1: // LA当前项的指数小 ha.next = qa; // 新链表当前节点指向qa ha = qa; // ha往后移 qa = qa.next; // qa往后移 break; case 0: // 两项指数相等,求和 double sum = a.coef - b.coef; // 求系数的和 if(sum != 0.0){ a.coef = sum; ha.next = qa; ha = qa; qa = qa.next; qb = qb.next; }else { qa = qa.next; qb = qb.next; } break; case 1: // LB当前项的指数小 ha.next = qb; ha = qb; qb = qb.next; break; } } ha.next = (qa == null? qb:qa); return LA; }