数据结构——顺序表

摘要：由于太久没有复习数据结构了，导致该忘的都忘了，所以在这里记录重新学习数据结构的笔记，以备以后查看。

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

构建一个简单的顺序表

#include <stdio.h>
#include <stdlib.h>
#define max_size 128
//采取动态分配的方式创建顺序表
typedef struct LinkList(){
	int *data;
	int length;
}Link;

这就很简单的构建了一个顺序表的结构了。

初始化顺序表

Link *create_link(int len){
	Link *ret = (Link*)malloc(sizeof(Link));
	ret->data = (int*)malloc(sizeof(Link)*len);
	ret->length = 0;
	return ret;
}

这样就可以很简单的初始化顺序表了，其中初始化data空间，以及将length(表长)置为0。

寻找对应元素的下标

int find_elem_p(Link *L,int x){
	int i;
	for(i = 0;i < L->length;i++){
		if(x <= L->data[i])
			return i;
	}
	return i;
}

这句话中，从头开始寻找，当length == 0 时，会直接返回0，否则就是查找返回一个比x大的值的下标，若没有找到则返回最后一个元素下标+1。

插入元素

int insert_elem(Link *L, int x){
	int p,i;
	p = find_elem_p(L,x);
	if(L->length ==0){
		L->data[0] = x;
		++(L->length);
		return 1;
	}
	
	for(i = L->length-1;i > p ; i--)
		L->data[i+1] = L->data[i];
	L->data[p] = x;
	++(L->length);
	return 1;
}

插入元素体现的是如果顺序表长度为0，则对data[0]赋值，若长度不为0，则将查询到需要插入的下标之后的元素整体向后位移一位，接着再将该元素插入。

tips:

切记边界的判断，我在这卡壳一天就是因为没有理解好边界值的正确取法。

删除元素

int delete_elem(Link *L,int p,int *e){
	int i;
	if(p<0 || p > L->length -1)
		return 0;
	*e = L->data[p];
	
	for(i = p; i < L->length-1;i++)
		L->data[i]=L->data[i+1];
	
	--(L->length);
	return 1;
}

删除元素即把原来的元素取出到e中，并把所有后面一个元素向前位移一位，最后将length减去一即可。

（这里有个疑问，最后一位向前移位后需要将原来的最后一位释放掉（free(L->data[i])，会对以后的程序产生错误嘛，留待大家给我解答）

获取下标对应的元素

int get_elem_p(Link *L,int p,int* e){
    if(p < 0 || p > L->length-1)
        return 0;
    *e = L->data[p];
    return 1;
}

打印顺序表

void print_link(Link* L){
    int i;
    for(i=0;i<L->length;i++)
        printf("%3d",L->data[i]);
        printf("\n");
}

释放表

void free_link(Link* L) {
	free(L->data);
	free(L);
}

主函数部分

int main(int argc, char** argv)
{
	Link  *link1 = 0;
	link1 = create_link_list(max_size);
	//初始以及创建的方式，很简单
}

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max_size 100

//动态分配空间
typedef struct LinkList {
	int *data;
	int length;
}Link;

//创建顺序表
Link * create_link_list(int len) {
	Link* ret = (Link*)malloc(sizeof(Link));
	ret->data = (int*)malloc(sizeof(Link)*len);
	ret->length = 0;
	return ret;
}
//寻找元素对应的下标
int find_elem(Link* L, int x) {
	int i;
	for (i = 0; i < L->length; i++) {
		if (x <= L->data[i])
			return i;
	}
	return i;
}
//插入元素
int insert_elem(Link *L, int x) {
	int p, i;
	p = find_elem(L, x);
	if (L->length == 0) {
		L->data[0] = x;
		++(L->length);
		return 1;
	}

	for (i = L->length-1 ; i > p; --i) {
		L->data[i + 1] = L->data[i];
	}
	L->data[p] = x;
	++(L->length);
	return 1;
}

//删除元素
int delete_elem(Link *L,int p,int* e){
    int i;
    if(p < 0 || p > L->length-1)
        return 0;

    *e = L->data[p];

    for(i = p;i < L->length-1;i++)
        L->data[i]=L->data[i+1];

    //free(L->data[i]);
    --(L->length);
    return 1;
}

//取下标的元素
int get_elem_p(Link *L,int p,int* e){
    if(p < 0 || p > L->length-1)
        return 0;
    *e = L->data[p];
    return 1;
}

//打印
void print_link(Link* L){
    int i;
    for(i=0;i<L->length;i++)
        printf("%3d",L->data[i]);
        printf("\n");
}
//释放表
void free_link(Link* L) {
	free(L->data);
	free(L);

}
int main(int argc, char** argv)
{
	int i;
	int e;
	Link* link1 = NULL;
	link1 = create_link_list(max_size);
	for (i = 0; i < 10; i++) {
	insert_elem(link1, i);
	}
	print_link(link1);

	delete_elem(link1,2,&e);
	printf("被删除的元素：%d\n",e);
    print_link(link1);

	free_link(link1);
	return 0;
}