数据结构学习笔记(一)



大家好,从今天开始我和你们一起学习数据结构。在这个系列当中,每篇文章是我自己的学习过程和学习总结,并不是教程,有错误一定要在留言区批评和指证。


数据结构

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




END

原文始发于微信公众号(代码墙):数据结构学习笔记(一)