数据结构学习系列-----初识数据结构

大家好，我是NarcissuLyh。从今天开始定期分享关于数据结构的知识。在这个系列当中，每篇文章都是一些总结，有错误大家一定要在steemit留言区批评和指证。

数据结构

数据结构(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;
}

感谢阅读本文，下一篇数据结构------链表，敬请期待