数据结构

发表于

序言

  1. 数据结构是一门研究非数值性程序设计中计算机操作的对象以及它们之间的关系和操作的学科。
    算法好坏的区分标准：
    运行速度（时间），所占空间，精确度等．
  2. 数据(data)
    描述客观事物的数，字符，以及所有能输入计算机的，并被计算机程序识别和处理的符号集合．或者说数据是计算机化的信息．
  3. 数据结构(data structure)
    由某一数据对象及该对象中所有数据成员之间的关系组成，记为：
    Data_Structure={D,R}　
    Ｄ是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合．
    数据的逻辑结构—–从用户视图看是面向问题的．
    数据的物理结构—–从具体实现视图看，是面向计算机的．(顺序，拉链)
  4. 抽象数据类型(ADTs: Abstract Data Types)
    抽象：是一种信息隐蔽的方法．
    抽象数据类型：提供组织和设计程序的一种新方法．
    思想：将数据类型的使用与它的内部表示（机内存储），实现（机内操作的实现）分开．更确切地说：把一个数据类型的内部表示及在这个类型上的操作实现封装到一个程序模块中，用户不必知道细节．
    抽象数据类型的特征是使用和实现分离，实行封装 和信息隐蔽
    优点：
    从使用者来看，只要了解该抽象数据类型的规格说明，就可以利用其公共界面中的服务来使用这个类型，而不必关心其物理实现．
    从实现者的角度看：把抽象数据类型的物理实现封装起来，有利于编码、测试，也有利于扩充、修改．
  5. 面向对象的概念
    面向对象＝对象＋类＋继承＋通信
    面向对象＝对象＋类＋继承＋通信
    对象：
    指各种实体，事件，规格说明，由一组属性值（确定对象的状态）和在这组值上的一组操作构成．
    例如：定义一个矩形对象：
    属性：左上角坐标, 右下角坐标, 边线颜色, 内部颜色．
    操作：move(x,y); SetEdgeColor(c); SetInnerColor(c);
    类：具有相同属性和操作的对象构成同一个类．
    对类而言，其中的每一个对象称为该类的一个实
    例(instance)，不同的实例具有不同的属性值．

  6. 把n个整数用选择排序的方法由小到大排列．

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void SelectSort(int a[], const int n)
    {    for (int i=0; i<n-1; i++)
    	{
    	　int k = i;　//k中存放每趟比较最小元素的下标
    	　for (int j=i+1; j<n; j ++)
    		if (a[j] < a[k]) k = j;
    	　int temp=a[i]; a[i]=a[k]; a[k]=temp;
    	}
    }

  7. 性能分析与度量
    １)算法的性能标准
    　①．正确性　　②．可使用性　　③．可读性
    　④．效率　　时间代价（主要讨论的）
    　　　　　　　空间代价
    ２)时间复杂度度量
    　⑴．程序步(program step)
    　是指在语法上或语义上有意义的一段指令序列．

链表

编程题

求数组a的最大值

1
2
3
4
5
6
7
8
9
int max(int a[], int n) {
	if (n == 1) return a[0];
	int m = max(a, n - 1);
	if (m > a[n - 1]) {
		return m;
	} else {
		return a[n - 1];
	}
}

求数组a的平均值

1
2
3
4
5
6
7
8
9
10
11
12
float average(int a[], int n) {
	if (n == 1) {
		return a[0];
	} else {
		return (average(a, n - 1) * (n - 1) + a[n - 1]) / n;
	}
}

float average(ListNode f, int n) {
	if (f.link == NULL) return false;
	else return (average(f.link, n - 1) * (n - 1) + f.data) / n;
}

统计叶子结点个数

1
2
3
4
5
6
7
int leafNum(BinTreeNode <Type> * root) {
	if (root == NULL) return 0;
	if (root->leftChild == NULL && root->rightChild == NULL) return 1;
	else {
		return leafNum(root->leftChild) + leafNum(root->rightChild);
	}
}

交换左右子数

1
2
3
4
5
6
7
8
void swapChild(BinTreeNode * p) {
	if (p == NULL) return;
	BinTreeNode *temp = p->left;
	p->left = p->right;
	p->right = temp;
	swapChild(p->left);
	swapChild(p->right);
}

如果用链表来实现表求链表中的最大值

1
2
3
4
5
6
7
8
int getMaxNum(ListNode f) {
	if (f.link == NULL) return f.data;
	else [
		int i = getMaxNum(f.link);
		if (i > f.data) return i;
		else return f.data;
	]
}

逆转链表

1
2
3
4
5
6
7
8
9
10
11
12
void inverse(ListNode f) {
	if (f == NULL) return;
	ListNode p = f.link; 
	ListNode pr = NULL;
	while (p != NULL) {
		f.link = pr;
		pr = f;
		f = p;
		p = p.link;
	}
	f.link = pr;
}

作业

编写一个递归方法，它返回数N的二进制表示中1的个数。

1
2
3
4
5
6
7
public static int count(int n) {
	if (n == 0) {
		return 0;
	} else {
		return n % 2 + count(n / 2);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void permute(char[] str, int low, int high) {
	if (low == high) { // low = 0, high = str.lengh
		System.out.println(str);
	} else {
		for (int i = low; i <= high; i++) {
			char temp;
			temp = str[i];
			str[i] = str[low];
			str[low] = temp;
			permute(str, low + 1, high);
			temp = str[i];
			str[i] = str[low];
			str[low] = temp;
		}
	}
}

求数组A中的最大整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int max(int[] num, int n) {
	if (n == 1) return num[0];
	else {
		int temp = max(num, n - 1);
		if (temp > num[n - 1]) {
			return temp;
		} else {
			return num[n - 1];
		}
	}
}

public int max_(int[] num, int left, int right) {
	if (left == right) {
		return num[left];
	} else {
		int x = max_(num, left, (left + right) / 2);
		int y = max_(num, (left + right) / 2 + 1, right);
		return (x > y) ? x : y;
	}
}

// low = 0, n = hight = num.length;

求n个整数的平均值

1
2
3
4
5
6
7
double average(int[] num, int n) {
	if (n == 1) {
		return (double)num[0];
	} else {
		return (double)(average(num, n - 1) * (n - 1) + num[n - 1]) / n;
	}
}

递归求解链表的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Length {
	public static int length = 0;
	public static int GetLength(Iterator it) {
		if (!it.hasNext()) {
			return 0;
		} else {
			it.next();
			return 1 + GetLength(it);
		}
	}
}

public int caculate(ListNode p) {
	if (p == null) return 0;
	else return 1 + caculate(p.nest);
}

class ListNode {
	Object content = null;
	ListNode nest = null;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean palinedromes(String word) {
	if (word == null) return false;
	else if (word.length() <= 1) return true;
	else if (word.charAt(0) == word.charAt(word.length() - 1)) {
		return palinedromes(word.substring(1, word.length() - 1));
	}
	else return false;
}

public boolean sentence(String sentence) {
	String one = sentence.toLowerCase();
	String two = "";
	for (int i = 0; i < sentence.length(); i++) {
		if (one.charAt(i) >= 'a' && one.charAt(i) <= 'z') {
			two += one.charAt(i);
		}
	}
	return palinedromes(two);
}

求下面函数的复杂度，这个函数是用来在一个未排序的整数数组中查找第k个整数的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 从一个数组里找到第K小的数
// k次，每次都找第i小的数，找到后，放到i位
int selectKth(int a[], int k, int n) {
	int i, j, mini, temp;
	for (i = 0; i < k; i++) {
		mini = i; // 1
		for (j = i + 1; j < n; j++) {
			if (a[j] < a[mini]); // 1
			mini = j; // 1
		}
		temp = a[i]; // 1
		a[i] = a[mini]; // 1
		a[mini] = temp; // 1
	}
	return a[k - 1];
}


sum++被执行的次数

1
2
3
4
5
sum=0;
for(i=0; i<n; i++)
     for(j=0; j<i*i; j++)
          for(k=0; k<j; k++)
                sum++;


i的从0到n-1，因为当i为0时候，内层循环并不会被执行，所以是n-1次
j是从0到ii-1，也就是ii次
k是从0到j-1。
来看一次内层循环，当i=1，j是从0，k取0，0次
当i=2，j从0到3，j=0，k 0 0次，j = 1，k0 1次，j=2，k01二次，j=3，k012三次
j从0到ii-1用ii项，而内层循环是从0到i*i-1次 用等差数列求和可得以上公式

1
2
3
4
5
6
sum=0;
for(i=0; i<n; i++)
     for(j=0; j<i*i; j++)
          if(j%i==0) //注意
              for(k=0; k<j; k++)
                    sum++;

分析（了解%运算符）
运行时间f(n)取决于sum++的执行次数，
sum++只在j=i、2i、3i、…(i-1)i时才会执行

1
2
3
4
5
6
7
8
设n为正整数，分析下列各程序段中加下划线的语句的执行次数。
1）
 for (int i = 1; i <= n;  i++)
     for (int j = 1; j<=n; j++){  
           c[i][j] = 0.0;
           for ( int k = 1; k <= n; k++)
           	c[i][j] = c[i][j]+a[i][k]*b[k][j];
     }

1
2
3
4
5
x = 0; y = 0;
for (int i = 1; i <= n; i++)
      for (int j = 1; j <= i; j++)
            for (int k = 1; k <= j; k++)
                 x = x+y;


是k(k+1),i从i到n的一半。n个1到i的等差数列和。

负数放在非负数前

1
2
int[] num = new int[10];
int len = num.length;
1
int n[ 10 ];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void sort(int[] num) {
	int len = num.length;
	int temp, i = 0, j = len - 1;
	while (i != j) {
		if (i < len && num[i] < 0) {
			i++;
		}
		if (j >= 0 && num[j] >= 0) {
			j--;
		}
		temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
}

循环数组实现循环队列 c++

假设以数组Q[m]存放循环队列中的元素，同时以rear和length 分别指示环形队列中的队尾位置和队列中所含元素的个数：
1）求队列中第一个元素的实际位置。
2）给出该循环队列的队空条件和队满条件，并写出相应的插入(enqueue)和删除(dlqueue)元素的操作算法。

1
2
3
4
front=rear-length+1
front=rear+m-length+1

front=(rear-length+1+m)%m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 队空条件
public boolean isEmpty() {return  length==0;}
public boolean  isFull() {return  length==m;}
//入队函数
public  void  enqueue(Object  x)  throw  Overflow {
       if (isFull())
             throw new Overflow();

       length++;
       rear = (rear+1)%m;
      Q[rear] = x;
}
//出队函数
public Object dequeue()  throw  Underflow {
       if (isEmpty())
             throws new Underflow();

       length--;
       return Q[(rear-length+m)%m];
}


## 不带表头的链表求平均值递归
```java
public class ListNode {
    int data;
    ListNode link;
    ListNode(int x) { data = x; }
}
public float average(ListNode f, int n) {
	if (f.link == null) return f.data;
	else {
		return (average(f.link, n - 1) * (n - 1) + f.data) / n;
	}
}

输出不小于k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class BinaryNode {
    int data;
    BinaryNode left;
    BinaryNode right;
}

public class BST {
    private BSTNode root;
    public BST() {
        this.root = null;
    }
}

public void BSTfind(BSTNode root, int k) {
	if (root == null) return;
	BSTfind(root.right, k);
	if(root.data >= k) {
		System.out.println(root.data);
	}
	BSTfind(root.left, k);
}

最小堆调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void pereUp(Comparable[] a, int start) {
	int j = start;
	int i = j / 2;
	Comparable temp = a[j];
	while (j > 1) {
		if (a[i] <= temp) break;
		else {
			a[j] = a[i];
			j = i;
			i = i / 2;
		}
	}
	a[j] = temp;
}

名词解释

二叉搜索树
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
图的最小生成树
堆
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

线性结构
一个数据元素的有序集合
算法的时间复杂度
法在编写成可执行程序后，对运行时所需要的时间资源的度量。
散列表的线性探查法

快速排序的最坏时间浮渣度
“在哈夫曼树(也叫最优树)中,只有两种类型的结点:度为0或N,即最优二叉树中只有度为0或2的结点,最优三叉树中只有度为0或3的结点,所以有2N-1个节点 。”
用最小堆排序

5阶B树 添加删除
Dijkstra方法计算1到其他顶点的最短路劲

key

二、
//策略接口
public interface Description {
public String getDescription(String applicatioName, float avarageRate, ArrayList newFeatureItems);
}
//实现策略
public class DescriptionForAndroid implements Description{
public String getDescription(String applicatioName, float avarageRate, ArrayList newFeatureItems) {
StringBuffer result = new StringBuffer();
result.append(“This is “+ applicatioName + “ for Android platform\n”);
for(int i =0; i< newFeatureItems.size(); i++) {
result.append(newFeatureItems.get(i).getDescription());
}
result.append(“Avarage Rate from Google Play\n”);
result.append(String.valueOf(avarageRate));
return result.toString();
}
}
public class DescriptionForiOS implements Description{
public String getDescription(String applicatioName, float avarageRate, ArrayList newFeatureItems) {
StringBuffer result = new StringBuffer();
result.append(“This is “+ applicatioName + “ for iOS platform\n”);
for(int i =0; i< newFeatureItems.size(); i++) {
result.append(newFeatureItems.get(i).getDescription());
}
result.append(“Avarage Rate from App Store\n”);
result.append(String.valueOf(avarageRate));
return result.toString();
}

}
//context
class Application {
prative String applicatioName;
prative float avarageRate;
prative ArrayList newFeatureItems = new ArrayList();
Description description;
void setDescription(Description description) {
this.description = description;
}
String getDescription() {
return description.getDescription();
}

}

三

答：

违反了迪米特法则
public class Customer {
Rental rental;
int getNewRentPoint(){
return rental.getNewRentPoint();
}
}
public class Rental {
private int daysRented;
private Movie movieRented;
public int getDaysRented(){
return daysRented;
}
public Movie getMovieRented(){
return movieRented;
}
public Movie getNewRentPoint(){
if((movieRented.getPriceCode() == Movie.NEW_RELEASE) && daysRented > 1) {
return 2;
}
else
return 1;
}
}
public class Movie {
private int priceCode;
public static final int CHILDRENS = 2;
public static final int REGULAR = 0;
public static final int NEW_RELEASE = 1;
public int getPriceCode(){
return priceCode;
}
}

四

答

1) 第一段程序违反了里氏替换原则。第二段程序设计合理，因为能用Person的地方也能用Employee替代。
2) 里氏替换：子类型必须能够替换掉基类型而起相同的作用。
public class MyStack extends Vector {
Vector v = new Vector();
public void push(Object element) {
v.insertElementAt(element,0);
}
public Object pop() {
Object result = v.firstElement();
v.removeElementAt(0);
return result;
}
}

五

答案

1) 数据耦合，不用修改。
2) 控制耦合，改为1) 的形式。

六

答案

1)
2) 性能需求、质量属性、对外接口、约束。

七

答案

八

答案

1.用户输入错误的信息，系统会标注出来，而不是叫用户重写整段代码。体现了人机交互的低出错率设计。
2.使用逐层递进的方式展示信息、并且小功能使用直截了当的图像快捷方式。体现了人机交互的易记性设计。
3.编不出来了。。。

九

答

这题感觉是用策略模式来定义各个挡位的税收，然后定义一个工厂来根据实际的taxable_income，来返回相应的策略对象。