作为一个计科大学生，没有学好数据结构一直是我的遗憾，博主主攻java web方向，为了不当一个低端码农，决心静下心来学习数据结构，但是和我当初自学java一样，都存在入门难的问题，严蔚敏的数据结构一直是我的噩梦，概念多且抽象，我希望通过敲代码这种实战的方式学习数据结构，也就放弃了课本。
后来在CSDN上看到贺利坚的课程(收费)，和很多人一样，并不想买，后来在贴吧看到免费的观看地址（百度锐聘），就慢慢地开始学，同时写博客记录我的学习过程。
在此十分感谢贺利坚老师，看了他的博客后不止教会了我数据结构，也为我解开了诸多学习上的疑惑

声明

数据结构系列文章时从博主的CSDN中迁移过来的，重新进行排版优化，切莫闹出举报博主自己抄袭自己的笑话(咳咳，我已经授权抄袭自己了)

线性表概述

线性表描述了一种线性的逻辑结构，元素之间是一对一的关系，而在存储结构上分为顺序存储和链式存储，
分别简称为：顺序表和链表
以下是顺序表的定义方式以及操作，运行环境为Eclipse CDT，程序用到少部分C++特性，新建时选择C++ project，在运行main之前，先要右键项目，进行build project

代码实现

sqlist.h

#define MAX_SIZE 50
#define INCREMENT_SIZE 10
/*
ElemType可以表示一个复杂的结构体
	typedef struct {
		int age;
		char name[32];
	}ElemType;
*/
typedef int ElemType;

typedef struct {
	ElemType data[MAX_SIZE];
	int length;
}SqList;

SqList.cpp

#include "sqlist.h"
void initSqList(SqList *&sl); //初始化
bool isEmpty(SqList *sl); //判空
void addCapacity(SqList *&sl); //扩容
void destorySqList(SqList *&sl); //销毁
int getLength(SqList *sl); //获取长度
void printList(SqList *sl); //输出顺序表
void deleteElement(SqList *&sl, int i, ElemType &e); //删除下标为i的元素
void insertElement(SqList *&sl, int i, ElemType e); //在i处插入元素
void getElementByIndex(SqList *sl, int i, ElemType &e); //通过下标i获取元素
int getElementIndex(SqList *&sl, ElemType e);//获取元素的下标
int main(){
	SqList *sl;
	ElemType ele;
	initSqList(sl);
	insertElement(sl, 1, 10);
	insertElement(sl, 2, 20);
	insertElement(sl, 3, 30);
	insertElement(sl, 4, 40);

	deleteElement(sl,4,ele);
	printList(sl);

	printf("元素%d的位置是：%d\n",20, getElementIndex(sl,20));

	getElementByIndex(sl, 2, ele);
	printf("第%d个元素是：%d\n",2, ele);
    return 0;
}

void initSqList(SqList *&sl) {
	sl = (SqList *)malloc(MAX_SIZE*sizeof(SqList));
	sl->length = 0;
}

bool isEmpty(SqList *sl) {
	return (sl->length == 0);
}

void addCapacity(SqList *&sl) {
	sl = (SqList *)realloc(sl,(sl->length + INCREMENT_SIZE));
	if (!sl) {
		printf("扩容失败");
	}
	//注意是length，不是MAX_SIZE,假如这不是第一次扩容
	sl->length += INCREMENT_SIZE;
}

void destorySqList(SqList *&sl) {
	free(sl);
}

int getLength(SqList *sl) {
	return sl->length;
}

void printList(SqList *sl) {
	int i;
	if (isEmpty(sl)) {//是否是空表
		printf("List is empty\n");
	}
	for ( i = 0; i < sl->length; i++){
		printf("%d\t",sl->data[i]);
	}
}

void insertElement(SqList *&sl, int i, ElemType e) {
	//如果list里只有10个元素，你最多能在11的位置上插入，不能大于11
	if (i<1 || i>sl->length+1) {
		printf("插入的位置不合法\n");
		return;
	}
	//如果超过容量，就扩容
	if (sl->length == MAX_SIZE) {
		addCapacity(sl);
	}
	int j;
	//从最后一个元素 到第i-1个元素后移，自己在纸上画出来，很容易理解j>=i-1
	for (j=sl->length-1; j>=i - 1; j--){
		//为什么是j+1 = j,不是j = j-1，想想最后一个元素是怎么移动的就很好理解了
		sl->data[j + 1] = sl->data[j];
	}
	//把元素插入到下标为(i-1)的位置
	sl->data[i - 1] = e;
	//记得length++
	sl->length++;
}

void deleteElement(SqList *&sl, int i, ElemType &e) {
	if (i<1 || i>sl->length) {
		printf("插入的位置不合法\n");
		return;
	}
	e = sl->data[i - 1];
	int j;
	for (j = i; j < sl->length; j++) {
		sl->data[j - 1] = sl->data[j];
	}
	sl->length--;
}

int getElementIndex(SqList *&sl, ElemType e) {
	int i = 0;
	while (i < sl->length && sl->data[i] != e) {
		i++;
	}
	if (i < sl->length) {
		return i + 1; //这个时候的i是从0开始算的，所以要+1
	}else {
		return -1;
	}
}

void getElementByIndex(SqList *sl, int i, ElemType &e) {
	if (i<1 || i>sl->length) {
		printf("访问的位置不合法");
		return;
	}
	e = sl->data[i - 1];
}

/*
	删除元素x，x不止一个
	找到，然后删除, O(n) = n*n
*/
void deleteEle_1(SqList *sl, ElemType x) {
	int i;
	ElemType e;
	while ((i = getElementIndex(sl, x)) > 0) {
		deleteElement(sl, i, e);
	}
}

/*
	删除元素x，x不止一个
	将O(n) 降低到 O(n)
	算法：用复制的思想
	重新从0开始计数，只要第n个元素不等于x，就移动到前面去(同时把以前的覆盖)
*/
void deleteEle_2(SqList *sl, ElemType x) {
	int k = 0, i;
	for (i = 0; i < sl->length; i++) {
		if (sl->data[i] != x) {
			sl->data[k] = sl->data[i];
			k++;
		}
	}
	sl->length = k; //删除x后，k就是长度
}