# 数据结构学习系列-----初识数据结构大家好，我是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 #include #include 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; } ``` 感谢阅读本文，下一篇数据结构------链表，敬请期待

narcissulyh