撰写
大家好，从今天开始我和你们一起学习数据结构。在这个系列当中，每篇文章是我自己的学习过程和学习总结，并不是教程，有错误一定要在留言区批评和指证。
数据结构(Data Structure)指的是数据元素之间的相互关系，即数据的组织形式。
它的逻辑结构主要分为线性结构、树形结构、图状结构。存储结构可以用顺序存储方法、链式存储方法、索引存储方法，和散列存储方法这4种方法得到。
概念上的东西了解即可，接下来直接进入实战。
把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。顺序存储结构通常是借助于程序语言的数组来描述的。
在本文中均用C语言来描述，我们用结构体来表示一个结点：
struct Arr {
int * pBase; //存储数组的首元素的地址
int len; //数组的长度
int cnt; //有效元素的个数
};首先，封装一个初始化数组的函数：
/*
1.用malloc函数根据传入的length计算出需要分配的空间转换成int * 类型赋值给pArr->pBase
2.判断pArr->pBase是否为空
3.如果不为空将数组长度和有效元素个数进行赋值
*/
void init(struct Arr * pArr, int length) {
pArr->pBase = (int *)malloc(sizeof(int) * length);
if(NULL == pArr->pBase) {
printf("动态分配失败!n");
exit(-1); //终止整个程序
}else {
pArr->len = length;
pArr->cnt = 0;
}
return;
}接下来完成打印数组所有元素的功能：
void showArray(struct Arr * pArr) {
if(pArr->cnt == 0) {
printf("数组为空！n");
}else {
for(int i = 0; i < pArr->cnt; i++ ) {
printf("%d ",pArr->pBase[i]);
}
printf("n");
}
}在数组末尾追加一个值：
/***
在数组不满的状态下，把传进来的value赋值给pArr->pBase[pArr->cnt]，而后pArr->cnt自加
*/
bool append(struct Arr * pArr, int value) {
if(isFull(pArr)) {
return false;
}else {
pArr->pBase[pArr->cnt] = value;
(pArr->cnt)++;
return true;
}
}在此基础上，完成其他功能：
void init(struct Arr * pArr, int length); // 初始化
bool isEmpty(struct Arr * pArr); // 判断是否为空
void showArray(struct Arr * pArr); // 打印数组所有元素
bool append(struct Arr * pArr, int value); // 末尾追加元素
bool isFull(struct Arr * pArr); // 判断是否满
bool insert(struct Arr * pArr, int pos, int value); // 插入元素
bool deleteValue(struct Arr * pArr, int pos, int * pVal); // 删除元素
void inversion(struct Arr * pArr); // 将数组倒置
void sort(struct Arr * pArr); // 排序全部代码如下：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct Arr {
int * pBase; //存储数组的首元素的地址
int len; //数组的长度
int cnt; //有效元素的个数
};
void init(struct Arr * pArr, int length);
bool isEmpty(struct Arr * pArr);
void showArray(struct Arr * pArr);
bool append(struct Arr * pArr, int value);
bool isFull(struct Arr * pArr);
bool insert(struct Arr * pArr, int pos, int value);
bool deleteValue(struct Arr * pArr, int pos, int * pVal);
void inversion(struct Arr * pArr);
void sort(struct Arr * pArr);
int main() {
struct Arr arr;
int val;
init(&arr,7);
append(&arr,1);
append(&arr,454);
append(&arr,-12);
append(&arr,15742);
append(&arr,2);
showArray(&arr);
inversion(&arr);
showArray(&arr);
sort(&arr);
showArray(&arr);
return 0;
}
/*
排序
升序
*/
void sort(struct Arr * pArr) {
int i,j,t;
for(i = 0; i < pArr->cnt; ++i) {
for(j = i + 1; j < pArr->cnt; ++j) {
if(pArr->pBase[i] > pArr->pBase[j]) {
t = pArr->pBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = t;
}
}
}
}
/*
将数组倒置
*/
void inversion(struct Arr * pArr) {
int i = 0;
int j = pArr->cnt - 1;
int t = 0;
while(i < j) {
t = pArr->pBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = t;
i++;
j--;
}
return;
}
/*
插入在pos的位置前面插入一个数值
pos从1开始
*/
bool insert(struct Arr * pArr, int pos, int value) {
int i;
if(isFull(pArr)) {
return false;
}
if(pos < 1 || pos>pArr->cnt + 1) {
return false;
}
for(i = pArr->cnt - 1; i >= pos - 1; --i) {
pArr->pBase[i+1] = pArr->pBase[i];
}
pArr->pBase[pos-1] = value;
(pArr->cnt)++;
return true;
}
/*
删除指定元素
成功返回true，失败返回false
*/
bool deleteValue(struct Arr * pArr, int pos, int * pVal) {
int i;
if(isEmpty(pArr)) {
return false;
}
if(pos < 1 || pos > pArr->cnt) {
return false;
}
* pVal = pArr->pBase[pos-1];
for(i = pos; i < pArr->cnt; ++i) {
pArr->pBase[i-1] = pArr->pBase[i];
}
pArr->cnt--;
return true;
}
/*
判断数组是否满
满返回true，不满返回false
*/
bool isFull(struct Arr * pArr) {
if(pArr->cnt == pArr->len) {
return true;
}else {
return false;
}
}
/*
在数组的末尾追加一个值
*/
bool append(struct Arr * pArr, int value) {
if(isFull(pArr)) {
return false;
}else {
pArr->pBase[pArr->cnt] = value;
(pArr->cnt)++;
return true;
}
}
/*
显示数组
*/
void showArray(struct Arr * pArr) {
if(pArr->cnt == 0) {
printf("数组为空！n");
}else {
for(int i = 0; i < pArr->cnt; i++ ) {
printf("%d ",pArr->pBase[i]);
}
printf("n");
}
}
/*
判断数组是否为空
为空返回true，不为空返回false
*/
bool isEmpty(struct Arr * pArr) {
if(pArr->cnt == 0) {
return true;
}else {
return false;
}
}
/*
建立一个数组，并指定长度
*/
void init(struct Arr * pArr, int length) {
pArr->pBase = (int *)malloc(sizeof(int) * length);
if(NULL == pArr->pBase) {
printf("动态分配失败!n");
exit(-1); //终止整个程序
}else {
pArr->len = length;
pArr->cnt = 0;
}
return;
}原文始发于微信公众号（代码墙）：数据结构学习笔记(一)