String

1 字符串分割：

1

"a;b,c:d".split("[;|,|:]");

2 高效分割：

1

new StringTokenizer(String str, String delim);

3 更优化方式：性能远超split()和StringTokenizer()

1
2

str.indexOf(int ch);
subString()

4 charAt()
检查开头结尾字符串比内置函数startWith(),endWith()还快。

String, StringBuilder, StringBuffer

string为不可变对象，添加字符串会copy到新对象，然后添加。效率低！
stringBuilder无法保证线程安全（性能优于stringBuffer，但多线程中不使用）
stringBuffer有同步-synchronized（多线程中使用）

List接口

operations add remove
ArrayList() 尾端插入快 尾部快 每次扩容1.5倍
LinkedList() 任意插入快 头/尾部快

List遍历：
ForEach Iterator ForLoop
最慢 快 最快

Map接口

HashTable():线程安全；有synchronized；k/v不允许用null值
HashMap()：线程不安全； 无synchronized；k/v可以用null值

LinkedHashMap()：增加链表存放元素顺序：1 元素插入顺序； 2 最近访问顺序

TreeMap()：需要对存放元素排序输出时使用；红黑树实现；

Set接口

HashSet()
LinkedHashSet()
TreeSet()

代码设计

消除循环的低效率；
减少过程调用；

改善性能技巧

慎用异常
try…catch用在循环结构内严重影响性能，应放在循环外。

使用局部变量
临时变量存在stack，调用速度快；
静态变量、实例变量存在heap，调用速度慢

位运算代替乘除法

替换switch

提取表达式

展开循环

布尔运算代替位运算

System.arrayCopy(Object src, int srcPros, Object dest, int desPro, int length)
快于for loop7倍。

使用Buffer进行I/O操作
基本方式：
InputStream/OutputStream
Writer/Reader

使用clone()代替new
绕过构造对象，快速赋值一个对象实例。

Backtracking general approach)

7 List and Iterator ADTs

7.1 The List ADT

1
2
3
4
5
6

size();
isEmpty();
get(i);
set(i, e);
add(i, e);
remove(i);

7.2 Array Lists

dynamic array based on List.

7.2.1 Dynamic Arrays

7.2.2 Implementing a Dynamic Array

7.2.3 Amortized Analysis of Dynamic Arrays

7.2.4 Java’s StringBuilder class

7.4 Iterators

1
2
3
4
5

import java.util.Iterator;

hasNext();
next();
remove();

7.5 The Java Collections Framework

7.5.1 List Iterators in Java

1
2
3
4
5
6
7
8
9

add(e);
hasNext();
hasPrevious();
previous();
next();
nextIndex();
previousIndex();
remove();
set(e);

7.5.2 Comparison to Our Positional List ADT

7.5.3 List-Based Algorithms in the Java Collections Framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import java.util.Collections

copy(L_dest, L_src);
disjoint(C, D);
fill(L, e);
frequency(C, e);
max(C);
min(C);
replaceAll(L, e, f);
reverse(L);
rotate(L, d);
shuffle(L);
sort(L);
swap(L, i, j);

Converting Lists into Arrays:

1
2

toArray();
toArray(A);

Converting Arrays into List:

1

asList(A);

7.6 Sorting a Positional List

8 Trees

9 Priority Queues

1
2
3
4
5

insert(k, v);
min();
removeMin();
size();
isEmpty();

java.util.Priority

10 Maps, Hash Tables, and Skip Lists

10.1 Maps

java.util.Map;
Count word frequency

10.2 Hash Tables

Sorted Maps

Applications:
Flight Databases
Maxima Sets;

10.4 Skip Lists

11 Search Trees

12 Sorting and Selection

13 Text Processing

13.2 Pattern-Matching Algorithms

13.2.1 Brute Force

13.2.2 The Boyer-Moore Algorithm

13.2.3 The KMP Algorithm

13.3 Tries

13.3.3 Suffix Tries

13.3.4 Search Engine Indexing

13.4 Text Compression and the Greedy Method

13.4.1 The Huffman Coding Algorithm

13.4.2 The Greedy Method

13.5 Dynamic Programming

Matrix Chain-Product

DNA and Text Sequence Alignment

3 Fundamental Data Structures

3.1 Using Arrays

3.1.1 Storing in an Array

add:插入指定index，index数据与index之后数据整体右移
remove:移除指定index，index之后所有数据整体左移

3.1.2 Sorting an Array

Insert-Sort

3.1.3 java.util Methods for Arrays and Random Numbers

1 Most commonly used methods:
built-in class: java.util.Arrays.
equals(A, B): return true if and only if array A and array B are equal. A and B have the same element values in the same order.
fill(A, x): Stores value x in every cell of array A.
copyOf(A, n): return an array of size n
copyOfRange(A, s, t): returns an array of size t-s. copy array from index s to t-1.
toString(A): returns a String representation of the array A
sort(A): sorts the array A
binarySearch(A, x): searches the Sorted array A for value x, returning the index where it is found.

2 PseudoRandom Number Generation
built-in class: java.util.Random.
Methods of the java.util.Random class:
nextBoolean(): returns the next pseudorandom boolean value
nextDouble(): returns the next pseudorandom double value, between 0.0 to 1.0
nextInt(): returns the next pseudorandom int value
nextInt(n): returns the next pseudorandom int value n the range from 0 up to but not including n
setSeed(s): sets the seed of this pseudorandom number generator to the long s

3.1.4 Simple Cryptography with Character Arrays

1 Converting Between Strings and Character Arrays

1
2
3

String s = "bird";
A = s.toCharArray();  // A = {'b','i','r','d'}
B = new String(A);  // B = "bird"

2 Using Character Arrays as Replacement Codes

3.1.5 2-D Arrays and Positional Games

first index refers as a row number;
second index refers as a column number.

1

int[][] data = new int[8][10];

TicTacToe Game:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public class TicTacToe {
    private static final int X = 1, O = -1;
    private static final int EMPTY = 0;
    private int board[ ][ ] = new int[3][3];
    private int player;

    public TicTacToe( ) { clearBoard( ); }

    public void clearBoard( ) {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                board[i][j] = EMPTY;
        player = X;
    }

    public void putMark(int i, int j) throws IllegalArgumentException {
        if ((i < 0) || (i > 2) || (j < 0) || (j > 2))
            throw new IllegalArgumentException("Invalid board position");
        if (board[i][j] != EMPTY)
            throw new IllegalArgumentException("Board position occupied");
        board[i][j] = player;
        player = -player;
    }

    public boolean isWin(int mark) {
            return ((board[0][0] + board[0][1] + board[0][2] == mark*3)
                    || (board[1][0] + board[1][1] + board[1][2] == mark*3)
                    || (board[2][0] + board[2][1] + board[2][2] == mark*3)
                    || (board[0][0] + board[1][0] + board[2][0] == mark*3)
                    || (board[0][1] + board[1][1] + board[2][1] == mark*3)
                    || (board[0][2] + board[1][2] + board[2][2] == mark*3)
                    || (board[0][0] + board[1][1] + board[2][2] == mark*3)
                    || (board[2][0] + board[1][1] + board[0][2] == mark*3));
    }

    public int winner( ) {
        if (isWin(X)) return(X);
        else if (isWin(O)) return(O);
        else return(0);
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                switch (board[i][j]) {
                    case X: sb.append("X"); break;
                        case O: sb.append("O"); break;
                        case EMPTY: sb.append(" "); break;
                }
                if (j < 2) sb.append("|");
            }
            if (i < 2) sb.append("\n-----\n");
        }
        return sb.toString();
    }

    public static void main(String[ ] args) {
        TicTacToe game = new TicTacToe();
        game.putMark(1,1);  game.putMark(0,2);
        game.putMark(2,2);  game.putMark(0,0);
        game.putMark(0,1);  game.putMark(2,1);
        game.putMark(1,2);  game.putMark(1,0);
        game.putMark(2,0);

        System.out.println(game);
        int winningPlayer = game.winner();
        String[]outcome={"Owins","Tie","Xwins"};
        System.out.println(outcome[1 + winningPlayer]);
    }
}

3.2 Singly Linked Lists

Array:
Cons:fixed capacity;
time-consuming for insertions and deletions
head
tail

Inserting an element
Removing an element

Commonly used methods:

1
2
3
4
5
6
7

size();
isEmpty();
first();
last();
addFirst(e);
addLast(e);
removeFirst();

3.3 Circularly Linked Lists

Linked lists are traditionally viewed as storing a sequence of items in a linear order, from first to last.

3.3.1 Round-Robin Scheduling

To support the responsiveness of an arbitrary number of concurrent processes, most operating systems allow processes to effectively share use of the CPUs, using some form of an algorithm known as Round-Robin Scheduling. A process is given a short turn to execute, known as a time slice, but it is interrupted when the slice ends, even if its job is not yet complete. New Processes can be added to the system, and processes that complete their work can be removed.

3.3.2 Designing and Implementing a Circularly Linked List

3.4 Doubly Linked Lists

Singly Linked List:
Cons:
efficiently add/delete first node but not for last node

1
2
3
4
5
6
7
8

size();
isEmpty();
first();
last();
addFirst(e);
addLast(e);
removeFirst();
removeLast();

3.5 Equivalence Testing

3.5.1 Equivalence Testing with Arrays

a==b: tests if a and b refer to the same underlying array instance
a.equals(b): this is identical to a==b.
Arrays.equals(a, b): return True if the arrays have the same length and all pairs of corresponding elements are “equal” to each other.
Arrays.deepEquals(a, b): for multidimensional arrays

3.5.2 Equivalence Testing with Linked Lists

3.6 Cloning Data Structures

3.6.1 Cloning Arrays

This is not copy. Just have different referred name.

1
2
3

int[] data = {2,3,4,5,6};
int[] backup;
backup = data.clone();

3.6.2 Cloning Linked Lists

5 Recursion

5.1 Illustrative Examples

5.1.1 The Factorial Function

edge case;
base case;
recursive case;

5.1.2 Drawing an English Ruler

5.1.3 Binary Search

5.1.4 File Systems

report disk usage of a file system

1
2
3
4
5
6
7
8
9
10
11

public static long diskUsage(File root) {
  long total = root.length();
  if (root.isDirectory()) {
    for (String childname : root.list()) {
        File child = new File(root, childname);
        total += diskUsage(child);
    }
  }
  System.out.println(total + "\t" + root);
  return total;
}

5.3 Further Examples of Recursion

5.3.1 Linear Recursion

5.3.2 Binary Recursion

5.3.3 Multiple Recursion

5.4 Designing Recursive Algorithms

6 Stacks, Queues, and Deques

6.1 Stacks

LIFO

6.1.1 The Stack Abstract Data Type

1
2
3
4
5
6
7

import java.util.Stack;

push();
pop();
top();
size();
isEmpty();

6.1.2 A Simple Array-Based Stack Implementation

6.1.3 Implementing a Stack with a Singly Linked List

Adapter Pattern

6.1.4 Reversing an Array Using a Stack

6.1.5 Matching Parentheses and HTML Tags

An algorithm for Matching Delimiters;
Matching Tags in a Markup Language;

6.2 Queues

FIFO

6.2.1 The Queue Abstract Data Type

1
2
3
4
5
6
7

import java.util.Queue

enqueue(e);
dequeue();
first();
size();
isEmpty();

6.2.2 Array-Based Queue Implementation

6.2.3 Implementing a Queue with a Singly Linked List

6.2.4 A Circular Queue

6.3 Double-Ended Queues

6.3.1 The Deque Abstract Data Type

1
2
3
4
5
6
7
8
9
10
11

import java.util.Queue;

addFirst();
addLast();
removeFirst();
removeLast();

first();
last();
size();
isEmpty();

6.3.2 Implementing a Deque

1 Java Primer

1.1 Base types

1
2
3
4
5
6
7
8

boolean   
char     16-bit
byte     8-bit
short    16-bit
int      32-bit
long     64-bit
float    32-bit
double   64-bit

1.2 Classes and Objects

Critical members of a class:
Instance variables: must have a type: either a base type or any class type(reference type)
Methods: accept parameters as arguments

1
2
3
4
5
6
7
8

public class Counter {
  private int count;  // a simple integer instance variable
  public Counter() { }  // default constructor (count is 0)
  public Counter(int initial) { count = initial; }  // an alternate constructor
  public int getCount() { return count; }  // an accessor method
  public void increment() { count++; }  // an update method
  public void increment(int delta) { count += delta; }   // an update method
  public void reset() { count = 0; }   // an update method

1.2.1 Dot Operator

1.2.2 Defining a class

1 Modifiers
Access control modifiers: public, protected, private

The static modifier: for any variable or method of a class.
The value of a static variable is associated with the class as a whole. It is used to store “global” information in a class.
When a method of a class is declared as static, it too is associated with the class as a whole, rather than with each individual instance of that class.

The abstract modifier: an advanced feature of OOP to be combined with inheritance.

The final modifier:
a variable that is declared with the final modifier can be initialized as part of that declaration, but can never again be assigned a new value.
a final method cannot be overridden by a subclass, and cannot even be subclassed.

2 Declaring Instance Variables

3 Declaring Methods

4 Declaring Constructors
Constructors cannot be static, abstract, or final.
The name of the constructor must be identical to the name of the class it constructs.
We don’t specify a return type of a constructor.

5 Keyword This

6 main Method

Unit Testing: use framework such as JUnit

1.3 Strings, Wrappers, Arrays, Enum types

1.3.1 String class

Instances are immutable

1
2
3

String title = "Data Structures in Java"; // declared a string
char c = title.charAt(0) // c = 'D';
String term = "over" + "load";  // Concatenation : term = "overload"

1.3.2 StringBuilder Class

Instances are mutable.

setCharAt(k, c): Change the character at index k to character c.
insert(k, s): Insert a copy of string _s_ starting at index _k_ of the sequence, shifting existing characters further back to make room.
append(s): Append string _s_ to the end of the sequence.
reverse(): Reverse the current sequence.
toString(): Return a traditional String instance based on the current character sequence.

1.3.3 Wrapper Types

1.3.4 Arrays

1.3.5 Enum Types

1.4 Expressions

1.4.1 Literals

1
2
3
4
5
6

null;
Boolean: true / false;
Integer: int-32bit, 176L/52l-64bit
Floating Point: default is double.
Character:
  '\n':newline  '\t': tab  '\b': backspace  '\r': return  '\f': form feed  '\\':backslash  '\'': single quote  '\"': double quote

1.4.2 Operators

Arithmetic:

1

String Concatenation:```+

Increment and Decrement Operators:

1
2

Logical Operators:
  for numbers:```< <= == != >= >

for boolean:

1

Bitwise Operators:```~ & | ^异或 << >> >>>

Assignment Operator:

1
2
3
4

![Imgur](https://i.imgur.com/Q10pCkD.png)

### 1.4.3 Type Conversions
**Mutual conversion between int and double**

double d1 = 3.2;
double d2 = 3.9999;
int i1 = (int) d1; // i1 = 3
int i2 = (int) d2; // i2 = 3
double d3 = (double) i2; // d3 =3.0

1

**Mutual conversion between int to String**

String s1 = “2014”;
int i1 = Integer.parseInt(s1); // i1 gets value 2014
int i2 = −35;
String s2 = Integer.toString(i2); // s2 gets value “-35”

1
2
3
4
5
6
7

## 1.5 Control Flow
### if / switch
if...else if... else
switch... case...case...case...default...
### while / for

### control-flow statements

return
break
continue

1
2
3
4

## 1.6 Simple Input and Output
### Simple Output Method
print: String, Object, baseType

import java.io.PrintStream;

System.out.print();
System.out.println();

1
2
3

### Simple Input Method
Create a Scanner object:

new Scanner(System.in);

1
2
3
4
5
6
7
8
9
10
11
12
13
14

```
import java.util.Scanner;   // loads Scanner definition for our use

public class InputExample {
  public static void main(String[ ] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Enter your age in years: ");
    double age = input.nextDouble();
    System.out.print("Enter your maximum heart rate: ");
    double rate = input.nextDouble();
    double fb = (rate − age) ∗ 0.65;
    System.out.println("Your ideal fat-burning heart rate is " + fb);
  }
}

java.util.Scanner Methods
Dealing with tokens:

1
2
3
4

hasNext(): return true/false
next(): return next token string; raise en error if there are no more tokens left
hasNextType():  
nextType():

Processing line by line:

1
2
3

hasNextLine(): return true/false
nextLine(): return next line
findInLine(String s): attempts to find a string matching the pattern s in the current line.

1
2
3
4
5
6
7

Scanner input = new Scanner(System.in);
System.out.print("Please enter an integer: ");
while (!input.hasNextInt()) {
  input.nextLine( );
  System.out.print("Invalid integer; please enter an integer: ");
}
int i = input.nextInt();

1.7 An Example Program

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public class creditCards {
    public static class CreditCard{

        private String customer;
        private String bank;
        private String account;
        private int limit;
        private double balance;

        private CreditCard(String cust, String bk, String acnt, int lim, double initialBal){
            customer = cust;
            bank = bk;
            account = acnt;
            limit = lim;
            balance = initialBal;
        }

        private CreditCard(String cust, String bk, String acnt, int lim){
            this(cust, bk, acnt, lim, 0.0);
        }

        public String getCustomer(){return customer;}
        public String getBank(){return bank;}
        public String getAccount(){return account;}
        public int getLimit(){return limit;}
        private double getBalance(){return balance;}

        private boolean charge(double price){
            if(price + balance > limit) return false;
            balance += price;
            return true;
        }

        private void makePayment(double amount){
            balance -= amount;
        }

        private static void printSummary(CreditCard card){
            System.out.println("Customer = " + card.customer);
            System.out.println("Bank = " + card.bank);
            System.out.println("Account = " + card.account);
            System.out.println("Balance = " + card.balance);
            System.out.println("Limit = " + card.limit);
        }
    }

    public static void main(String[] args){
        CreditCard[] wallet = new CreditCard[3];
        wallet[0] = new CreditCard("John Bowman", "California Savings","5391 0375 9387 5309", 5000);
        wallet[1] = new CreditCard("John Bowman", "California Federal", "3485 0399 3395 1954", 3500);
        wallet[2] = new CreditCard("John Bowman", "California Finance", "5391 0375 9387 5309", 2500, 300);

        for(int val = 1; val <= 16; val++){
            wallet[0].charge(3*val);
            wallet[1].charge(2*val);
            wallet[2].charge(val);
        }
        for(CreditCard card : wallet){
            CreditCard.printSummary(card);  // calling static method
            while (card.getBalance() > 200.0){
                card.makePayment(200);
                System.out.println("New balance = " + card.getBalance());
            }
        }
    }
}

1.8 Packages and Imports

1
2
3

package packageName;
import packageName.className;
import packageName.*;

1.9 Software Development

Three phases: Design, Coding, Testing and Debugging.

1.9.1 Design

For OOP, it is in the design step that we decide how to divide the workings of our program into classes, when we decide how these classes will interact, what data each will store, and what actions each will perform.

Determining how to define classes: Responsibilities; Independence; Behaviors.

UML diagrams to express the organization of a program.
“+”:public visibility
“#”:protected visibility
“-“:private visibility

1.9.2 Pseudocode

1.9.3 Coding

To accelerate the development of this skill, we need to know various design patterns for designing OOP. These patterns provide templates for defining classes and the interactions between these classes.

1.9.4 Documentation and Style

Javadoc

1.9.5 Testing and Debugging

2 Object-Oriented Design

2.1 Goals, Principles, and Patterns

Achieving Robustness, Adaptability, and Reusability.

2.1.2 Object-Oriented Design Principles

Principles of OO approach:
Abstraction: An abstract data type specifies what each operation does, but not how it does.
Encapsulation: hide details of different components.
Modularity:

2.1.3 Design Patterns

Design Patterns fall into two groups:
Patterns for solving algorithm design problems;
Patterns for solving software engineering problems

Algorithms design patterns
Recursion;
Amortization;
Divide-and-Conquer;
Prune-and-Search, also known as Decrease-and-Conquer;
Brute Force;
The greedy method;
Dynamic Programming;

Software design patterns
Template method;
Composition;
Adapter;
Position;
Iterator;
Factory Method;
Comparator;
Locator

2.2 Inheritance

The correspondence between levels is often referred to as an “is a“ relationship, as a house is a building ,and a ranch is a house.

This allows a new class to be defined based upon an existing class as the starting point.

The existing class is described as base class, parent class, or superclass;
Newly defined class is called as subclass, or child class.

2.2.1 Extending the CreditCard Class

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

import creditCards.CreditCard;

public class PredatoryCreditCard extends CreditCard {
    // Additional instance variable
    private double apr; // annual percentage rate

    // Constructor for this class
    public PredatoryCreditCard(String cust, String bk, String acnt, int lim,
                               double initialBal, double rate) {
        super(cust, bk, acnt, lim, initialBal);  // initialize superclass attributes
        apr = rate;
    }

    // A new method for assessing monthly interest charges
    public void processMonth() {
        if (balance > 0) { // only charge interest on a positive balance
            double monthlyFactor = Math.pow(1 + apr, 1.0 / 12); // compute monthly rate
            balance *= monthlyFactor;  // assess interest
        }
    }

    // Overriding the charge method defined in the superclass
    public boolean charge(double price) {
        boolean isSuccess = super.charge(price);
        if (!isSuccess)
            balance += 5;
        return isSuccess;
    }
}

2.2.2 Polymorphism and Dynamic Dispatch

2.2.3 Inheritance Hierarchies

2.3 Interfaces and Abstract Classes

2.3.1 Interfaces in Java

2.3.2 Multiple Inheritance for Interfaces

2.3.3 Abstract Classes

2.4 Exceptions

2.4.1 Catching Exceptions

statements: try...catch...

2.4.2 Throwing Exceptions

2.5 Casting and Generics

2.5.1 Casting

2.5.2 Generics

2.6 Nested Classes

算法基础

1 基本思想

枚举

依次判断，类似于遍历。
三大关键：
解空间；
减少搜索空间；
采用合适搜索顺序。

2 递归思想

三大要点：
递归式；
递归出口；
界函数。

用栈替代递归：

3 动态规划(复习重点)

最长公共子序列

4 DFS

5 BFS

6 Binary Search & Greedy Algorithms

1 数据结构基础

线性结构

线性表（链表）
栈
队列
字符串：substring

非线性结构

1 树
二叉树
二叉搜索树，
Huffman树
min/max heap
priority queue
2 图
强连通分量
最短路径
最小生成树

基本算法分类

1 穷举法：一一枚举数据；顺序找k值
2 回溯，搜索：八皇后，树，图遍历
3 递归分治：二分找k值，快排，merge sort
4 贪心算法：huffman tree， 最短路径dijkstra算法，最小生成树prim算法
5 动态规划：最短路径floyd算法

2 高级数据结构与算法

排序

in-place sort
insert sort; select sort
merge sort;
bucket sort;

out-place sort
优点：价格低，信息不易丢失，portable；
缺点：very slowly r/w speed；

索引

静态索引
倒排索引

B/B+ tree

Red/Black tree，位索引技术

Trie tree-字典树

AVL tree

c程序进阶

1 函数(复习)

类似于y = f(x)，给函数输入，返回输出。

实参是实际输入参数，形参：函数定义参数

执行

开辟空间给主函数，调用函数时开辟新空间，得到返回值后释放函数内存，接着执行主函数程序。主程序执行结束，释放主函数空间。

参数传递

传递变量到函数不改变值；
传数组名到函数会改变值。因为传递的实际是数组的地址，能对数组直接操作。

2 递归

重复调用自身。
程序简明。

递归实现：
–目标解；
–找到n与n-1之间的关系；
–子问题求解；

3 指针(复习)

内存空间有地址
变量三要素：
变量地址 + 变量值 + 变量名
地址运算符“&”

变量地址的作用：利用地资源址访问资源。
通过变量的地址操作变量：利用指针运算符*实现。

1

*&c 等价于 c

指针变量

1
2
3

int icount = 18;
int *iptr = &icount;
*iptr = 58;

icount = 58
iptr = 0028FB10
&icount =0028FB10
&iptr = 58
&iptr = 0028FB04

指针与数组

指针与字符串

结构体-struct

表示普遍存在的变量集合。

结构体变量

将一堆变量写到一个函数中，方便对象调用。

结构体数组-链表

动态申请内存空间。

面向对象入门

计算导论与C语言

1 导论

数学危机与图灵机原理

进制

十进制：逢十进一
二进制：逢二进一
十六进制：逢十六进一

进制转换

二进制布尔运算（复习）

operators：
与：同真异假
或：一真为真，全假为假
非

逻辑电路：
异或门，与门，或门。

计算机历史-从电子管到云计算

摩尔定律挑战：电力消耗，更多热能；
云计算：绿色，能耗相对较少

计算机未来

量子计算机

程序运行基本原理

程序运行：二进制+布尔运算+逻辑电路实现运算

通过某种命令控制计算机（让逻辑电路临时组合实现计算任务），让计算机按照命令来运行。

冯诺伊曼式计算机结构

存储器

1 Byte = 8 bit
1 KB = 1024 B
1 MB = 1024 KB
1 GB = 1024 MB
1 TB = 1024 GB
1 PB = 1024 TB
1 YB = 1024 PB

存储器分类：

1 寄存器与运算器直接连接（极快）
2 cache高速缓存
3 memory内存

存储器原理

RAM: DRAM(动态内存，周期性刷新以保持存储内容), SRAM(不需要周期性刷新)
ROM: ROM; PROM; EPROM; EEPROM; Flash EPROM(快速可擦除编程只读存储器)

CPU指令集

程序执行

2 程序设计语言-C++

关键字（30来个
数据类型（10来种）
操作符号（30来个）
操作句式statements：顺序，分支，循环

所有程序语言的基本组成

数据+运算+控制+传输

数据

1 Byte是一个存储单元，8 bit二进制表示；
每个Byte有一个地址；

变量：可变化的量：x, y…
变量格式：int， double，float…
不同变量分配的内存单元大小不一样；

1 整型
int(最常用): 32 bit = 4 Byte
short int: 16 bit = 2 Byte
long int: 32 bit = 4 Byte
区别：取值范围不同
sizeof：计算某类型对象占用内存的字节数

1

sizeof(short int)

默认sign类型；
unsigned int:都为正数；

1

Max & Min

2 浮点型
float: 32 bit
double: 64 bit
long double: 64 bit
区别： 精度不同
float：前7位有效
double： 前15位有效
long double： 前15位有效

3 字符型
char：1 Byte
最多256个字符

4 布尔型

1

bool

运算

运算符：

1
2
3
4
5
6
7
8
9
10
11
12

求字节数 sizeof
下标运算符 []
赋值运算符 =
算术运算符 +-*/%
关系运算符 < > == >= <=
逻辑运算符 ! && ||
条件运算符 ? :
逗号运算符 ,
位运算符 >> << ~取反 |或 ^异或 &与
指针运算符 * &
强制类型转换运算符 ()
分量运算符 . -->

控制

程序有单入口、单出口特性。
顺序语句；
分支语句：if，switch…case…default
循环语句：for，while, do…while, goto…if

传输-输入缓冲区

输入存入输入缓冲区，然后被程序读取。

一个字符串输入：
1 cin输入：不读取空格与回车
2 cin.get()函数：读取空格与回车
3 cin.get(char）
4 getchar()：不跳过任何字符

一串字符的输出：
cout

一串字符的输入：
1 cin
2 cin.get(ch,10, ‘\n’)
3 cin.getline()

3 总结

计算机基本原理；
计算机发展趋势；
程序运行基本原理；
C程序设计基本认知；

News Recommendation System