线性表的连接存储(数组)

1.数据结构中之数据类型?

本身总了转,数据结构将现实生活中的类分为两好像,一好像是线性结构(也叫线性表)还闹一致像样是非线性结构。

 

2.什么是线性结构与非线性结构?

线性结构,顾名思义,就是诸如线同样的构造,数据元素以逻辑上一个搭一个,可以经时底岗位找到下一个,甚至是随后的备职位的因素。

 

非线性结构:和线性结构相反,用这种组织存储的数额元素于逻辑上是免总是的,也就算是无法通过时职务找到下一个素。

 

3.线性结构的少数单分类?

线性结构分为数组和链表:

1º率先勤组大家一定还为此过,底层封装了成百上千先定义好之代码可供使用。它的结构为是扎眼的,1)它不仅于逻辑上是接连的,在物理及呢是连接的,一个继一个.2)我定义一个屡次组,必须先行让他分配好几独长的内存空间。(静态存储)

2º1)链表只是当逻辑上市连续的(满足线性结构),但是以情理及它们并无是连,它好经每个节点的指针找到下一个元素。2)定义链表的还要,并不需要事先分配好内存空间可以在程序运行的时分配内存(动态储存)。

 

总结:假如要存储班级之丁,有或每个班级的食指不平等,这个时要因此数组存储,你不能不先定义好累组的长,但鉴于班级人数不一样,你要依据绝要命之班级数定义长度这样尽管会促成空间浪费,这种事先分配长度的静态存储很糟糕。这个时段可选择链表(动态储存)。

4.数组常用智实现

这边自己是用C语言实现的。java等也得,但是绝不用因此。

//反转数组元素

void inversion_arr(pArr arr);

//升序排序

void sort_arr(pArr arr);

//获得指定下标的素

int get(pArr arr,int pos);

//修改指定下标的因素

bool update_arr(pArr arr,int pos,int val);

//删除指定下标的要素

bool delete_arr(pArr arr,int pos,int *val);

//向指定下标插入一个累

bool insert_arr(pArr arr,int pos,int val);

//追加数组一个素

bool append_arr(pArr arr,int val);

//初始化数组

void init_arr(pArr arr,int len);

//显示数组的相干消息

void show_arr(pArr arr);

//判断数组是否也空

bool is_empty(pArr arr);

//判断数组是否已经满

bool is_full(pArr arr);

 

 1 //测试数据结构中线性表中的顺序表
 2  #include <stdio.h>
 3  #include <malloc.h>
 4  #include <stdlib.h> 
 5  typedef struct Arr{
 6      int *pBase;
 7      int length;
 8      int cnt;
 9  }*pArr; //pArr=struct Arr *
10  void inversion_arr(pArr arr);
11  void sort_arr(pArr arr);
12  int get(pArr arr,int pos);
13  bool update_arr(pArr arr,int pos,int val);
14  bool delete_arr(pArr arr,int pos,int *val);
15  bool insert_arr(pArr arr,int pos,int val);
16  bool append_arr(pArr arr,int val);
17  void init_arr(pArr arr,int len);
18  void show_arr(pArr arr);
19  bool is_empty(pArr arr);
20  bool is_full(pArr arr);
21  int main(){
22      struct Arr arr;
23      int len,delVal;
24      printf("请输入你想要分配的内存空间长度len=");
25      scanf("%d",&len);
26      init_arr(&arr,len);
27      append_arr(&arr,12);
28      append_arr(&arr,2);
29      append_arr(&arr,3);
30      append_arr(&arr,11);
31      append_arr(&arr,4);
32      append_arr(&arr,19);
33      append_arr(&arr,103);
34      append_arr(&arr,41);
35      append_arr(&arr,9);
36      show_arr(&arr);
37      inversion_arr(&arr);
38      show_arr(&arr);
39  //    printf("%d",get(&arr,2));
40      /*
41      if(update_arr(&arr,2,111)){
42          show_arr(&arr);
43      }
44     //show_arr(&arr);
45      //insert_arr(&arr,1,18);
46      //bool flag = delete_arr(&arr,1,&delVal);
47      //if(flag){
48          //printf("删除成功,删除的数为%d\n",delVal);
49      //}
50      */
51  }

 1  //反转数组元素
 2  void inversion_arr(pArr arr){
 3      if(is_empty(arr)){
 4          printf("该数组为空,退出程序!\n");
 5          exit(-1);
 6      }
 7      int i,j;
 8      for(i=0;i<arr->cnt/2;i++){
 9          int temp=arr->pBase[i];
10          arr->pBase[i]=arr->pBase[arr->cnt-1-i];
11          arr->pBase[arr->cnt-1-i]=temp;
12      }
13  }

 1 //选择法升序排序 
 2  void sort_arr(pArr arr){
 3      int i,j;
 4      if(is_empty(arr)){
 5          printf("该数组为空,退出程序!\n");
 6          exit(-1);
 7      }
 8      for(i=0;i<arr->cnt;i++){
 9          for(j=i+1;j<arr->cnt;j++){
10              if(arr->pBase[i]>arr->pBase[j])
11              {
12                  int temp=arr->pBase[i];
13                  arr->pBase[i]=arr->pBase[j];
14                  arr->pBase[j]=temp;
15               }
16         }
17      }
18  }

 1 //获得指定元素的下标,pos表示第几个数 
 2  int get(pArr arr,int pos){
 3      if(is_empty(arr)){
 4          printf("该数组为空,退出程序!");
 5          return false;
 6      }
 7      if(pos<1||pos>arr->cnt){
 8          printf("输入下标不合法");
 9          return false;
10      }
11      return arr->pBase[pos-1];
12  }

 1 //修改指定下标的元素
 2 bool update_arr(pArr arr,int pos,int val){
 3      if(is_empty(arr)){
 4          printf("该数组为空,退出程序!\n");
 5          return false;
 6      }
 7      if(pos<1||pos>arr->cnt){
 8          printf("修改下标不符合!\n");
 9          return false;
10      }
11      arr->pBase[pos-1]=val;
12      return true;
13  }

 1 //删除指定下标的元素
 2   bool delete_arr(pArr arr,int pos,int *val){
 3      int i;
 4      if(is_empty(arr)){
 5          printf("数组为空,没得删除了!\n");
 6          return false;
 7      }
 8      if(pos<1||pos>arr->cnt){
 9          printf("删除的下标不合法!\n");
10          return false;
11      }
12      *val = arr->pBase[pos-1];
13      for(i=pos-1;i<arr->cnt;i++){
14          arr->pBase[i-1]=arr->pBase[i];
15      }
16      arr->cnt--;
17      return true;
18  }

 1 //指定位置下标插入元素 
 2  bool insert_arr(pArr arr,int pos,int val){//pos从1开始,表示在第几个数插入 
 3      int i;
 4      if(is_full(arr)){
 5          printf("数组已满,不能再插入了!\n");
 6          return false;
 7      }
 8      if(pos<1||pos>arr->cnt+1){
 9          printf("数组插入下标不合法!\n");
10          return false;
11      }
12      for(i=arr->cnt-1;i>=pos-1;i--){
13          arr->pBase[i+1]=arr->pBase[i];
14      }
15      arr->pBase[pos-1]=val;
16      arr->cnt++;
17      return true;
18  }

1  //追加元素到数组的后面 
2  bool append_arr(pArr arr,int val){
3      if(is_full(arr)){
4          printf("数组已满,不能在添加了,退出程序\n");
5          return false;
6      }
7      arr->pBase[arr->cnt++]=val;
8      return true;
9  }

 1 //打印数组的基本信息 
 2  void show_arr(pArr arr){
 3      int i;
 4      if(arr==NULL){
 5          printf("数组分配空间失败,退出程序\n");
 6          exit(-1);
 7      }
 8      printf("数组的最大长度为%d,实际长度为%d",arr->length,arr->cnt);
 9      if(arr->cnt>0){
10          printf(",数组元素有:");
11          for(i=0;i<arr->cnt;i++){
12              printf("%d,",arr->pBase[i]);
13          }
14          printf("\n");
15      }else{
16          printf(",没有有效元素\n");
17      }
18  }

 1 //初始化数组
 2  void init_arr(pArr arr,int len){
 3      arr->pBase = (int *)malloc(sizeof(int)*len);
 4      if(arr==NULL){
 5          printf("分配空间失败,退出程序!\n");
 6          exit(-1);
 7      }
 8      arr->length=len;
 9      arr->cnt=0;
10  } 

1 //判断数组是否为空
2  bool is_empty(pArr arr){
3      if(arr->cnt==0)
4          return true;
5      return false;
6  } 

1 //判断数组是否满
2  bool is_full(pArr arr){
3      if(arr->length==arr->cnt)
4          return true;
5      return false;
6  } 

 

至这结束,数组的主干方法还实现了,因为是故C语言实现之,所以涉及到了指针,动态内存分配(malloc),以及C结构体,所以看无顶明了的校友可以先押有有关这些情节之素材。写的不得了,还伸手多多指教。

 

切切实实源码参考:http://download.csdn.net/download/qq\_31308883/10141495