基础数据结构和算法——2、顺序表

基础数据结构和算法——2、顺序表

0. 线性结构

数据结构中最常用最简单的结构是线性结构。
线性结构，又称线性表。逻辑结构上数据元素之间存在一个对一个的相邻关系。线性结构是n个数据元素的有序（次序）集合，它有下列几个特征：

1. 集合中必存在唯一的一个"第一个元素"；
2. 集合中必存在唯一的一个"最后的元素"；
3. 除最后元素之外，其它数据元素均有唯一的"后继"；
4. 除第一元素之外，其它数据元素均有唯一的"前驱"。

1. 顺序表是什么？

顺序表是用一组地址连续的存储单元依次存储线性表中的各个元素，使线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

数组的缺点：大小(元素个数)不能改变，不能适用元素个数变化的情况。
数组可以看作无法改变大小的顺序表。

2. 顺序表怎么用？

顺序表通过一个结构体和结构体对应的接口使用。

3. 顺序表怎么实现？

3.1 定义结构

typedef int SeqType; //存储单元类型

typedef struct{
    SeqType *elem;  //存储空间基地址
    int size;       //当前长度
} List;

定义一个存储单元类型SeqType是为了使顺序表适和更多数据类型，使用的时候修改SeqType类型即可。

3.2 定义操作

1. 初始化顺序表
   为什么要初始化？因为局部变量默认初始化为随机值。
   怎么初始化？把结构体变量成员赋值为合法的初始值。

bool sqlist_init(SqList* plist);

2. 添加元素

int sqlist_append(SqList* plist,SeqType value);
int sqlist_prepend(SqList* plist,SeqType value);

3. 获取元素

SeqType sqlist_get(SqList* plist,int index);

4. 获取元素个数

int sqlist_size(SqList* plist);

为什么不直接从结构体获取？

5. 插入元素

int sqlist_insert(SqList* plist,int index,SeqType value);

6. 删除元素

SeqType sqlist_remove(SqList* plist,int index);

7. 销毁顺序表

bool sqlist_destroy(SqList* plist);

4. 优化

1. 容量
   每次增加一个元素，都要重复释放申请内存。可以预先申请一部分备用。

int capacity;   //当前分配的存储容量

每次预先申请多少？

2. 创建
   用户使用SeqType忘记初始化，可以把结构体定义和初始化合二为一。

SeqType sqlist_create(int size);

3. 随机访问元素
   获取元素sqlist_get()，只能获取到顺序表中的元素的副本，如果需要改变顺序表中的元素，可以提供如下函数。

SeqType* sqlist_at(SqList* plist,int index);

4. 遍历
   提供一个对顺序表的整体操作的接口。

typedef void (*SqList_Traversal)(const SeqType* value);
void sqlist_traverse(SqList* plist,SqList_Traversal fp);

• 完整代码

#include <stdio.h>
#include <stdlib.h>  //malloc()  realloc()
#include "SeqList.h"
#include <assert.h>  //assert()
#include <string.h>  //memcpy()

//创建
List list_create(){
	List l = {NULL,0};
	return l;
}


//初始化
bool list_init(List* seq){
	assert(NULL != seq);
	seq->data = NULL;
	seq->size = 0;
}

//销毁
void list_destroy(List* seq){
	assert(NULL != seq);
	free(seq->data);
	seq->data = NULL;
	seq->size = 0;
}

//基本操作
//添加数据
void list_append(List* seq,SeqType val){
	assert(NULL != seq);
	/*if(NULL == seq->data){
		seq->data = malloc(sizeof(SeqType));
		seq->data[0] = val;
	}else{
		seq->data = realloc(seq->data,(seq->size+1)*sizeof(SeqType));
		seq->data[seq->size] = val;
	}
	seq->size++;
	*/
	seq->size++;
	seq->data = realloc(seq->data,seq->size*sizeof(SeqType));
	seq->data[seq->size-1] = val;
}
void list_prepend(List* seq,SeqType val){
	assert(NULL != seq);
	seq->size++;
	seq->data = realloc(seq->data,seq->size*sizeof(SeqType));
	/*
	for(int i=seq->size-1;i>0;--i){
		seq->data[i] = seq->data[i-1];
	}
	 */
	memcpy(seq->data+1,seq->data,(seq->size-1)*sizeof(SeqType));
	seq->data[0] = val;

}
//插入数据
void list_insert(List* seq,int index,SeqType val){
	assert(NULL != seq);
	assert(index >= 0 && seq->size >= index);
	seq->size++;
	seq->data = realloc(seq->data,seq->size*sizeof(SeqType));
	memcpy(seq->data+1+index,seq->data+index,(seq->size-1-index)*sizeof(SeqType));
	seq->data[index] = val;
	
}
//删除数据
void list_delete(List* seq,int index){	
	assert(NULL != seq);
	assert(index >= 0 && seq->size > index);
	memcpy(seq->data+index,seq->data+index+1,(seq->size-index)*sizeof(SeqType));
	seq->size--;
}
//获取数据
SeqType list_get(List* seq,int index){	
	assert(NULL != seq);
	assert(index >= 0 && seq->size > index);
	return seq->data[index];
}
SeqType* list_at(List* seq,int index){
	assert(NULL != seq);
	assert(index >= 0 && seq->size > index);
	return seq->data+index;

}
//获取元素个数
int list_size(List* seq){
	assert(NULL != seq);
	return seq->size;
}
//打印
void list_print(List* seq){
	assert(NULL != seq);
	printf("size = %dn",seq->size);
	for(int i=0;i<seq->size;++i){
		printf("%d ",seq->data[i]);
	}
	printf("n");
}
//遍历
typedef void(*traval_t)(SeqType* val);
void list_traval(List* seq,traval_t func){
	assert(NULL != seq);
	assert(NULL != func);
	for(int i=0;i<seq->size;++i){
		(*func)(seq->data+i);
	}
}
//排序
static int list_cmp_element(const void* a,const void* b){
//	return *(SeqType*)a > *(SeqType*)b;
	return ((SeqType*)a)->age > ((SeqType*)b)->age;
}
void list_sort(List* seq){
	qsort(seq->data,seq->size,sizeof(SeqType),list_cmp_element);
}

//清空
void list_clear(List* seq){
	
}
//判断
bool list_empty(List* seq){

}
//查找
int list_find(List* seq,SeqType val){

}
SeqType* list_search(List* seq,SeqType val){

}

最后

以上就是酷炫小伙为你收集整理的基础数据结构和算法——2、顺序表的全部内容，希望文章能够帮你解决基础数据结构和算法——2、顺序表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。