2019-09-10 19:15:19
浏览数 (1)
线性结构【把所有的结点用一根直线穿起来】
连续存储【数组】、离散存储【链表】（不连续的，可分隔开来）
代码语言：javascript
复制 4 #include<stdio.h>
5 #include<malloc.h>//包含malloc函数
6 #include<stdlib.h>//包含exit函数
7 //定义了一个(复合)数据类型，名字叫struct Arr，该数据类型有三个成员:
8 struct Arr{
9 int * pBase; //存储的是数组第一个元素的地址
10 int len; //数组所能容纳的最大元素个数
11 int cnt; //当前数组有效元素的个数
12 };
13
14 void init_arr(struct Arr *pArr,int length); //初始化
15 bool append_arr(struct Arr *pArr,int val); //追加
16 bool insert_arr(struct Arr *pArr,int pos,int val); //插入，pos的值从1开始，表示在第pos个元素上插入
17 bool delete_arr(struct Arr *pArr,int pos,int *pVal); //删除
18 int get(); //获取某下标的值
19 bool is_empty(struct Arr *pArr);//判断数组是否为空
20 bool is_full(struct Arr *pArr); //判断数组是否满
21 void sort_arr(struct Arr *pArr); //排序
22 void show_arr(struct Arr *pArr); //输出
23 void inversion_arr(struct Arr *pArr); //倒置
24
25 int main(){
26 struct Arr arr;//仅仅是用struct Arr数据类型定义了一个arr变量，并未初始化
27 int val;
28
29 init_arr(&arr,6);//不能直接传结构体变量，传实参(结构体变量)给形参赋值，没有联系！
30 show_arr(&arr);//此处可以直接传变量
31 append_arr(&arr,1);
32 insert_arr(&arr,1,99);
33 delete_arr(&arr,1,&val);
34 return 0;
35 }
36
37 void init_arr(struct Arr *pArr,int length){
38 pArr->pBase = (int *)malloc"(sizeof(int)*length);//sizeof(int)*length表示内存大小
39 if (pArr->pBase == NULL){ //检测分配内存是否成功
40 printf("动态内存分配失败");
41 exit(-1);//终止整个程序
42 }
43 else{
44 pArr -> len = length;
45 pArr -> cnt = 0;
46 }
47 return;//函数终止
48 }
49
50 bool is_empty(struct Arr *pArr){
51 if(pArr->cnt == 0){
52 return true;
53 }
54 else{
55 return false;
56 }
57 }
58
59 bool is_full(struct Arr *pArr){
60 if(pArr->cnt == pArr->len){
61 return true;
62 }
63 else{
64 return false;
65 }
66 }
67
68 void show_arr(struct Arr *pArr){
69 if(is_empty(pAarr)){//此处不能传&pArr，因为pArr已经接收了结构体变量的地址
70 printf("数组为空");
71 }
72 else{ //输出数组有效内容
73 for(int i =0;i < pArr->cnt; i ){
74 printf("%d ", pArr->pBase[i]);
75 }
76 }
77 }
78
79 bool append_arr(struct Arr *pArr,int val){
80 if(is_full(pArr)){
81 return false;//数组满时返回false
82 }
83 else{//不满时追加
84 pArr->pBase[pArr->cnt] = val;//追加元素的下标就是pArr->cnt，数组目前的有效长度
85 (pArr->cnt) ;//添加了一个元素，所以有效长度加一
86 return true;
87 }
88 }
89
90 bool insert_arr(struct Arr *pArr,int pos,int val){
91 int i;
92 if(is_full(pArr)){
93 return false;
94 }
95
96 if(pos<1 || pos > pArr->cnt 1 ){
97 return false;
98 }
99
100 for(i = pArr->cnt-1;i>=pos-1;i--){
101 pArr->pBase[i 1] = pArr->pBase[i];
102 }
103 pArr->pBase[pos-1] = val;
104 (pArr->cnt) ;//插入一位元素后，有效长度加一
105 return true;
106 }
107
108 bool delete_arr(struct Arr *pArr,int pos,int *pVal){
109 int i;
110 if(is_empty(pArr)){
111 return false;
112 }
113 if(pos<1 || pos > pArr->cnt){
114 return false;
115 }
116 *pVal=pArr->pBase[pos-1];//等待被删除的元素赋值给形参对应的主函数中的val
117 for(i=pos;i< pAr->cnt;i ){
118 pArr->pBase[i-1] = pArr->pBase[i];
119 }
120 (pArr->cnt)--;
121 }
122
123 void inversion_arr(struct Arr *pArr){
124 int i =0;//第一个元素
125 int j = pArr->cnt-1;//最后一个元素
126 int t;
127 while(i<j){//无论元素个数的奇偶，此算法都可以搞定！
128 t = pArr->pBase[i];
129 pArr->pBase[i]=pArr->pBase[j];
130 pArr->pBase[j] = t;
131 i ;
132 j--;
133 }
134 }
135
136 void sort_arr(struct Arr *pArr){
137 int i,j,t;
138 for(i=0;i < pArr->cnt;i ){ //冒泡排序优化算法，最多进行(pArr->cnt)-1轮比较
139 for(j=i 1;j<pArr->cnt;j ){ //若j=0，那么条件就是j < pArr->cnt-i-1
140 if(pArr->pBase[i]>pArr->pBase[j]){
141 t = pArr->pBase[i];
142 pArr->pBase[i]=pArr->pBase[j];
143 pArr->pBase[j] = t;
144 }
145 }
146 }
147 }
