线性结构——连续存储【数组】的建立与实现

2015-12-09  20:49:18

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>//exit()
  4
  5 struct Arr
  6 {
  7     int * pBase;//数组第一个元素的地址
  8     int len;//长度
  9     int cnt;//当前数组有效元素的个数
 10     int increment;//自动增长因子
 11 };
 12
 13 void init_arr(struct Arr *pArr,int length);
 14 bool append_arr(struct Arr *pArr,int val);//追加
 15 bool insert_arr(struct Arr *pArr,int pos,int val);//pos从一开始
 16 bool delete_arr(struct Arr *pArr,int pos,int *pVal);
 17 get get_arr();
 18 bool is_empty(struct Arr*pArr);
 19 bool is_full(struct Arr *pArr);
 20 void sort_arr(struct Arr *pArr);//排序
 21 void show_arr(struct Arr*pArr);
 22 void inversion_arr(struct Arr*pArr);//倒置
 23
 24
 25
 26 int main ()
 27 {
 28
 29     struct Arr arr;
 30     int val;
 31
 32     init_arr(&arr,6);
 33     show_arr(&arr);
 34     append_arr(&arr,1);
 35     append_arr(&arr,2);
 36     append_arr(&arr,3);
 37     insert_arr(&arr,1,99);
 38     delete_arr(&arr,2,&val)//val返回被删除的值
 39
 40     inversion_arr(&arr);
 41     show_arr(&arr);
 42     sort_arr(&arr);
 43     show_arr(&arr);
 44
 45     retirn 0;
 46 }
 47
 48 void init_arr(struct Arr *pArr,int length)
 49 {
 50     pArr->pBase = (int *)malloc(sizof(int)*length);
 51     if (NULL==pArr->pBase)
 52     {
 53         printf("动态内存分配失败!\n");
 54         exit (-1);//终止整个程序
 55     }
 56     else
 57     {
 58         pArr->len=length;
 59         pArr->cnt=0;
 60     }
 61     return;
 62 }
 63
 64
 65 bool is _empty(struct Arr*pArr)
 66 {
 67     if(0==pArr->cnt)
 68         return true;
 69     else
 70         return false;
 71 }
 72
 73 bool is_full(struct Arr *pArr)
 74 {
 75     if(pArr->cnt == pArr->len)
 76         return true;
 77     else
 78         return false;
 79 }
 80
 81 void show_arr(struct Arr*pArr)
 82 {
 83     if(is_empty(pArr))
 84     {
 85         printf("The arr is Empty!\n");
 86     }
 87     else
 88     {
 89         for(int i=0;i<pArr->cnt;++i)
 90             printf("%d",pArr->pBase[i]);
 91         printf("\n");
 92     }
 93 }
 94
 95 bool append_arr(struct Arr *pArr,int val)
 96 {
 97     if(is_full(pArr))
 98         return false;
 99
100     else
101     {
102         pArr->pBase[pArr->cnt]=val;
103         (pArr->cnt)++;
104         return true;
105     }
106 }
107
108 bool insert_arr(struct Arr *pArr,int pos,int val)
109 {
110     int i ;
111
112     if(is_full(pArr))
113         return false;
114
115     if(pos<1||pos>pArr->cnt+1)
116         return false;
117
118
119     for(i=pArr->cnt-1;i>=pos-1;--i)
120     {
121         pArr->pBase[i+1]=pArr->pBase[i];
122     }
123     pArr->pBase[pos-1]=val;
124     pArr->cnt++;
125     return true;
126 }
127
128 bool delete_arr(struct Arr *pArr,int pos,int *pVal)
129 {
130     int i;
131
132     if(is_empty(pArr))
133         return false;
134
135     if(pos<1||pos>pArr->cnt)
136         return false;
137
138     *pVal=pArr->pBase[pos-1];
139
140     for(i=pos;i<pArr->cnt;++i)
141     {
142         pArr->pBase[i-1]=pArr->pBase[i])
143     }
144
145     pArr->cnt--;
146     return;
147 }
148
149 void inversion_arr(struct Arr*pArr)
150 {
151     int i =0;
152     int j = pArr->cnt-1;
153     int t;
154
155     while(i<j)
156     {
157         t=pArr->pBase[i];
158         pArr->pBase[i]=pArr->pBase[j];
159         pArr->pBase[j]=t;
160         ++i;--j;
161     }
162     return;
163 }
164
165 void sort_arr(struct Arr *pArr)
166 {
167     int i,j;
168
169     for(i=0;i<pArr->cnt;++i)
170     {
171         for(j=i+1;j<pArr->cnt;++j)
172         {
173             if(pArr->pBase[i] > pArr->pBase[j])
174             {
175                 t=pArr->pBase[i];
176                 pArr->pbase[i]=pArr->pBase[j];
177                 pArr->pBase[j]=t;
178             }
179         }
180     }
181 }
时间: 12-08

线性结构——连续存储【数组】的建立与实现的相关文章

数据结构线性存储之连续存储数组的实现

归纳: 线性 连续存储[数组] 优点:存取速度快(元素可以直接定位到) 缺点:插入删除元素慢(因为要移动其他元素),空间通常有限制 离散存储[链表] 优点:空间没有限制,插入删除元素很快 缺点:存取速度很慢(要一个一个遍历,一个一个找) 线性结构的应用: 1. 栈 2. 队列 非线性 树 图 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #define bool int #define false

连续存储——数组的实现

1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <malloc.h> 4 #include <stdbool.h> 5 6 //定义了一个数据类型,该数据类型的名字叫struct Arr,含有三个成员 7 struct Arr{ 8 int * pBase; //存储数组第一个元素的地址 9 int len; //数组所能容纳的最大元素的个数 10 int cnt; //当前数组有效元素的个数 11

郝斌数据结构连续存储数组的算法演示

#include<stdio.h> #include<stdbool.h> #include<stdlib.h> //包含了exit函数 //定义了一个数据类型 struct Arr { int * pBase;//存储的是数组第一个元素的地址 int len;//数组所能容纳 的最大元素的个数 int cnt;//当前数组有效元素的个数 }; void init_arr(struct Arr *, int); bool append_arr(struct Arr *

常见的线性结构

目录 前言 数组 数组介绍 自定义数组 实现数组的增删改查方法 动态数组 时间复杂度分析 栈 栈介绍 定义栈接口 基于数组实现栈的基本操作 使用栈实现"括号匹配"问题 队列 队列介绍 定义队列接口 数组队列 循环队列 数组队列和循环队列的性能比较 链表:最基础的动态数据结构 链表介绍 实现链表的增删改查操作 通过自定义链表实现栈 通过自定义链表实现队列 递归 前言 ??本篇博客主要是记录手写这些这数据结构的底层实现,加深对线性结构的理解,实现自己的一个小型数据结构库,也会进行简单的时间

数据结构入门-线性结构

把所有的节点用一根直线串起来 连续存储[数组] 什么叫做数组:元素类型相同,大小相等 重点看代码吧,需要注意的都在注释里,多敲几遍,当然了,有些功能还没有实现,以后再实现 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 定义了一个数据类型,这个数据类型的名字叫做struct Arr,有三个成员 struct Arr { int * pBase; // 存储的是数组第一个元素的地址 int le

算法--线性结构

一.数据结构 什么是数据结构:数据与数据之间的关系. 数据的存储结构:顺序存储(ArrayList).链式存储(LinkList). 数据的逻辑结构:集合结构.线性结构.树形结构.图形结构. 二.算法 算法:解决问题的方法. 算法的特性:输入.输出.有穷.确定性.可行性. 算法的基本要求:正确性.可读性.健壮性.时间复杂度.空间复杂度. 三.线性结构 1.数组 普通数组:类似Java基本类型数组 对象数组:类似ArrayList在对象里面定义一个数组类型的成员变量. 数组中的算法:线性查找和二分

【Java数据结构学习笔记之一】线性表的存储结构及其代码实现

应用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数据元素之间存在一个对多个关系 图形结构或网状结构:数据元素之间存在多个对多个的关系 对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构 顺序存储结构 链式存储结构 本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素 总存在唯一的最后一个数据元素 除

数据结构 - 线性表链式存储结构

链式存储 链式存储 :用一组任意的存储单元存储线性表中的数据元素.用这种方法存储的线性表简称线性链表. 存储链表中结点的一组任意的存储单元可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的. 链表中结点的逻辑顺序和物理顺序不一定相同.(即不要求逻辑上相邻的元素在物理位置上也相邻) 为了正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其直接后继结点的地址(或位置),称为指针(pointer)或链(link),这两部分组成了数据元素ai的存储映像 链表是通过每个结点

数据结构 线性结构(数组[列表] ,链表 单链表的增删改查**, 线性结构的应用 队列 栈[函数的调用**]),非线性结构 树

数据结构 参考:http://lupython.gitee.io/ 线性结构 就是能够用一根线串起来的数据结构 数组 (列表) 问:申请数组的前提条件是啥? a[12]?内存需要满足的条件? 答:内存必须有一块连续的内存空间 int a[7] : 声明一个数组,这个数组的数组名是 a, 数组的大小是 7, 数组元素的类型是整型. int a[7] = array(1,2,3,4,5,6,7) 问:如何申请内存? 答:C,C++语言,申请:mallco (28).释放:free(28) 问:int