c语言描述：数据结构【三.线性表】（连续存储数组算法）

柔情只为你懂 2022-11-01 00:58 169阅读 0赞

### 笔记目录 ###

*  利用结构体的方式
 *  初始化函数init（）
 *  判断是否满和空full（）empty（）
 *  遍历函数show（）
 *  追加函数append（）
 *  插入函数insert（）
 *  删除函数delete（）
 *  倒序函数inversion（）
 *  排序函数sort（）

--------------------

\# 前言 这些代码均为自己在郝斌老师教学的基础下自己的理解与补充，以及一些详细的解释

# 利用结构体的方式 #

#include<stdio.h>
    #include<malloc.h>//包含了malloc函数
    # include <stdlib.h> //包含了exit函数
    struct Arr
    { 
       int *pBase;//储存第一个元素地址
       int len;//（length）所能容纳最大元素个数
       int cnt;//（count）有效元素个数
    };

> cnt有效元素个数这个表示非常妙，学完之后觉得很有味道

# 初始化函数init（） #

void init(struct Arr * pArr, int length) //（initialize）初始化
    { 
      pArr->pBase = (int *)malloc(sizeof(int) * length);//利用malloc函数初始化分配空间
    	if (NULL == pArr->pBase)//判断是否分配出错
    	{ 
    		printf("动态内存分配失败!\n");
    		exit(-1); //终止整个程序
    	}
    	else
    	{ 
    		pArr->len = length;
    		pArr->cnt = 0;
    	}
      return;

# 判断是否满和空full（）empty（） #

int empty(struct Arr * pArr)//判断是否为空
    { 
    	if (0 == pArr->cnt)//有效个数为零
    		return 1;
    	else
    		return 0;		
    }
    int full(struct Arr * pArr)//判断是否为满
    { 
    	if (pArr->cnt == pArr->len)//有效=最大
    		return 1;
    	else
    		return 0;
    }

# 遍历函数show（） #

void show(struct Arr *pArr)
    { 
       if(empty(&pArr)==1)
        { 
            printf("数组为空！\n");
        }
       else
       { 
         for (int i=0;i<pArr->cnt;i++)
             printf("%d",pArr->pBase[i]);
         printf("\n");
       }
    }

# 追加函数append（） #

int append(struct Arr*pArr, int val)//追加函数
    { 
      if(full(&pArr)==1)
        return 0;
      else
      { 
        pArr->pBase[pArr->cnt]=val;/*原理：cnt实际等于要追加下标，因为数组从0开始，而cnt从1 开始所以会有差一，那么可以借cnt来进行追加*/
        (pArr->cnt)++;//追加后则有效数量加一
      }
    }

# 插入函数insert（） #

/*先要理解cnt，pos，与下标的区别：下标从0开始，pos和cnt都是从1开始  
所以，cnt-1表示为该数组里最后一个数的下标为多少；  
该循环里，先将pos前的元素移动到下一个下标；  
然后再将要插入的位置的元素从val中填入；  
而pos-1相当于表示了pos位置的元素下标  
最后因为插入了一个元素，所以该数组有效元素加一*/

int insert(struct Arr *pArr,int pos, int val)//(position)
    { 
       int i;
       if (full(&pArr)==1)
       { 
          printf("插入失败,数组为满\n");
          return 0;
       }
       
       if (pos<1||pos>pArr->len)//保证不超过最长长度
       { 
         printf("插入失败,请检查插入位置\n");
         return 0;  
       }
       /*先要理解cnt，pos，与下标的区别：下标从0开始，pos和cnt都是从1开始 所以，cnt-1表示为该数组里最后一个数的下标为多少； 该循环里，先将pos前的元素移动到下一个下标； 然后再将要插入的位置的元素从val中填入； 而pos-1相当于表示了pos位置的元素下标 最后因为插入了一个元素，所以该数组有效元素加一*/
       for ( i = pArr->cnt-1; i>=pos-1; i--)
       { 
          pArr->pBase[i+1]=pArr->pBase[i];
       }
       pArr->pBase[pos-1]=val;
       (pArr->cnt)++;
       printf("插入成功\n");
       return 1;
    }

# 删除函数delete（） #

int delete(struct Arr *pArr,int pos,int * pVal)
    { 
      int i;
      if ( empty(&pArr)==1 )
    	{ 
        printf("删除出错，该数组为空\n");
        return 0;
      }
    	if (pos<1 || pos>pArr->cnt)
    	{ 
        printf("删除出错，请检查删除位置\n");
        return 0;
      }
    
    	*pVal = pArr->pBase[pos-1];
    	for (i=pos; i<pArr->cnt; ++i)//pos-1要删除位置的下标
    	{ 
    		pArr->pBase[i-1] = pArr->pBase[i];//相当于直接后面覆盖前面了
    	}
    	pArr->cnt--;//总量变小
    	return 1;
    }

# 倒序函数inversion（） #

void inversion (struct Arr * pArr)//倒序
    { 
    	int i = 0;//相当于该数组第一个元素
    	int j = pArr->cnt-1;//相当于该数组最后一个元素
    	int t;//用来暂存
    
    	while (i < j)
    	{ 
    		t = pArr->pBase[i];
    		pArr->pBase[i] = pArr->pBase[j];
    		pArr->pBase[j] = t;
        /*即交换*/
    		++i;
    		--j;
       /* 从两边开始交换*/
    	}
    	return;
    }

# 排序函数sort（） #

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;
    			}
    		}
    	}
    }//冒泡排序