数据结构
参考两个教程：浙大数据结构、数据结构与算法基础-java版（罗召勇）
浙大版链接：
b站
mooc
罗召勇版链接：
b站
使用两种语言实现：C、Java

线性表

由同类数据元素构成有序序列的线性结构

• 表中元素个数为线性表长度
• 没有元素时，称为空表
• 表的起始位置称为表头，结束位置称为表尾
• 实现方式：顺序存储、链式存储

顺序存储

C版

1. 初始化

• 利用数组的连续存储空间存放线性表的元素
• 使用结构体来定义顺序表，成员为一个数组和数组的长度Last
  

.

• 定义结构体之后对它进行初始化，分配内存，建立空的顺序表

#include <stdlib.h>
#include <stdio.h>
#define MAX_SIZE 5 
//给这个结构体类型的指针起名字为List，List：LNode类型的指针，表示顺序表
typedef struct LNode* List;
struct LNode{     //表示顺序表，有两个成员：数组和数组最后一个元素的下标
    int data[MAX_SIZE];
    int last;
};
    
    
//这个函数用来初始化顺序表：①分配内存、长度赋初值  ②返回表指针
List makeEmpty(){
	List L = (List)malloc(sizeof(struct LNode));
	L->last = -1;
	return L;
}

//测试一下，输出长度=-1
int main(){
	List L = Enpty();
	printf("%d",L->last);
}

2. 查找

• 查找：查看一个表中是否含有某个数据

int Find(List Ptrl,int X){
	int i = 0;
	while(Ptrl->data[i]!=X && i<=Ptrl->last)  	//循环遍历表，平均查找（n+1）/2
		i++;
		
	if(Ptrl->data[i]==X)	return i; 	//如果找到了返回下标，否则返回-1
	else	return -1;
}

为方便举例，给表元素赋初值

List Enpty(){
	List L = (List)malloc(sizeof(struct LNode));
	int i=0;
	for(i;i<5;i++){
		L->data[i] = i;
	}
	L->last = 4;
	return L;
}


int main(){
	List L = Enpty();
	printf("%d\n",L->last); // 4
	printf("%d",Find(L,2));  // 2
}

3. 插入

• 插入数据

在第i个位置插入一个数据，它的下标为i-1，需要将a_i-1和它后面的数据往后挪一位，再将这个数据放到a_i-1处

void Insert(List Ptrl,int i,int X){
	int j;
	if(i-1<0 || i-1>Ptrl->last+1)		printf("位置不合法！");   //i-1是下标，下标不能小于0，可以在最后一个位置也可以在最后一个位置的后一个位置插入，但不能在后两个位置插入
	if(Ptrl->last == MAX_SIZE-1)	printf("满了");
	
	for(j = Ptrl->last;j>=i-1;j--){
		Ptrl->data[j+1] = Ptrl->data[j];    //平均移动次数为n/2，时间性能为O（n）
	}
	Ptrl->data[i-1] = X;
	Ptrl->last++;  //每插入一个，多了一个元素last要自增1
	return;
}

测验：

int main(){
	List L = Enpty();
	int i;
	for(i=0;i<MAX_SIZE;i++){
		Insert(L,i+1,3*i);
		printf("%d\n",L->data[i]);
	}
	
}

4. 删除

• 删除数据

删除表的第i个数据，它的下标为i-1，从a_i开始将后面的数据依次往前挪，a_i覆盖掉a_i-1

void Delete(List Ptrl,int i){
	if(i-1<0 || i-1>Ptrl->last)		printf("没有这个元素");
	int j;
	for(j = i;j<=Ptrl->last;j++){
		Ptrl->data[j-1] = Ptrl->data[j];		//平均移动次数（n-1）/2，时间性能O（n）
	}
	Ptrl->last--;   //少一个元素，last自减1
	return;
}

测试：

int main(){
	List L = Enpty();
	int i;
	for(i=0;i<MAX_SIZE;i++){
		Insert(L,i+1,3*i);
		printf("%d\n",L->data[i]);
	}
	
	printf("\n\n");
	Delete(L,2);
	for(i=0;i<=L->last;i++)
		printf("%d\n",L->data[i]);
}

Java版

创建一个面向对象的数组：就是将数组封装到一个类里面，类中还要提供能够操作数组的方法，类似于C里的结构体和那些函数

1. 初始化类

• 定义类，初始化

给出了两个成员：数组和数组大小（也可以通过数组.length获取）
定义构造器来初始化表：它这里给出的初始长度是0，为了后面数组的扩容，也可以给定一个长度

public class MyArray {
    private int[] myList;
    private int size;

    public MyArray() {
        this.myList = new int[0];
        this.size = 0;
    }
}

2. 插入和删除

• 插入元素

如果数组有空余，直接给数组添加元素即可。但是前面定义数组长度为0，容量不够就需要给数组扩容在进行插入

    public void insert(int i,int x){
        if (i<0 || i>this.size)     throw new RuntimeException("位置错误！");
        //扩容
        int[] newArr = new int[this.size + 1];
        for (int j = 0; j < this.size; j++) {   // 先将原数组的内容拷贝到新数组中
            newArr[j] = myList[j];
        }
        for (int j = this.size-1; j >= i; j--) {   //再向新数组插入数据，指定位置元素后移
            newArr[j+1] = newArr[j];
        }
        
        newArr[i] = x;   //插入指定数据
        myList = newArr;   //  记得得将原数组的引用指向扩容后的数组
        this.size++;  //长度+1
    }

    public void show(){
        System.out.println(Arrays.toString(myList));
    }

测试：

class Test{
    public static void main(String[] args) {
        MyArray myArray = new MyArray();
        for (int i = 0; i < 5; i++) {
            myArray.insert(i,i*3);
        }
        myArray.show();
    }
}

• 删除元素同理即可

3. 获取和修改

• 取出某位置元素

  • 直接通过下标来获取：myList[index]

  • 定义一个方法get

    	public int get(int index) {
    		// 判断下标是否越界
    		if (index < 0 || index > elements.length - 1) {
    			throw new RuntimeException("下标越界");
    		}
    		return elements[index];
    	}
    

• 修改某个位置的元素

  • 直接替换：myList[index] = x;

  • 定义一个方法set

    	public void set(int index, int element) {
    		// 判断下标是否越界
    		if (index < 0 || index > elements.length - 1) {
    			throw new RuntimeException("下标越界");
    		}
    		elements[index] = element;
    	}
    

4. 查找

• 查找元素

  • 线性查找

       public int binSearch(int target){
            int begin = 0;
            int end = this.size-1;
            int middle = (begin+end)/2;
    
            while (begin<=end){
                if (myList[middle] == target)      return middle;
                else if (myList[middle] < target)       begin = middle+1;
                else end = middle-1;
                middle = (begin+end)/2;
            }
            return -1;
        }
    }
    

  • 折半查找

      前提：数组有序
      有三个位置：起点、终点、中间
      每次将查找的数和中间的数比较，再挪动索引更改middle处的值
    

        public int binSearch(int target){
            int begin = 0;
            int end = this.size-1;
            int middle = (begin+end)/2;
    
            while (begin<=end){   //不知道比较次数使用while，终止条件：begin不可能比end大
                if (myList[middle] == target)      return middle;	// 表示找到了，返回索引
                else if (myList[middle] < target)       begin = middle+1;
                else end = middle-1;
                
                middle = (begin+end)/2;		// 每次更改后重新给middle赋值
            }
            return -1;
        }