用数组实现线性表各种操作(C语言)完结

排序使用简单的插入排序实现：

void one_sort(int *sqList,int val,int len)
{
     int pos=len;
     int temp=val;
     while(val<sqList[pos-1]&&pos>0)
     {
        sqList[pos]=sqList[pos-1];
        pos--;
        
     } 
     sqList[pos]=temp;
     
}
//直接插入排序实现
void straisort(struct Arr * pArr)
{
     
     for(int i=1;i<pArr->cnt;i++)
     {
        one_sort(pArr->pBase,pArr->pBase[i],i);//调用单步排序
     }
} 

 

直接插入排序通用算法：

void one_sort(int *sqList,int val,int len)
{
     int pos=len;
     int temp=val;
     while(val<sqList[pos-1]&&pos>0)
     {
        sqList[pos]=sqList[pos-1];
        pos--;
        
     } 
     sqList[pos]=temp;
     
}
//直接插入排序实现
void straisort(int *arr,int len)
{
     int i;
     for(i=1;i<len;i++)
     {
        one_sort(arr,arr[i],i);//调用直接插入排序
     }
} 

 

 

 线性表的操作数组实现代码如下，当然功能并不全面，等待以后收集

 

/*
线性结构数组的实现
*/
#include <stdio.h>
#include <malloc.h>  //包含了malloc函数
#include <stdlib.h>  //包含了exit函数 

//首先定义描述数组信息的结构体类型
struct Arr
{
  int * pBase;//存放数组首地址的指针变量
  int len;//数组长度
  int cnt;//数组中元素的个数
};

//定义数组的基本操作的函数声明
void init_arr(struct Arr * pArr,int length);//数组初始化
bool append_arr(struct Arr * pArr,int val);//追加元素
bool insert_arr(struct Arr * pArr,int index ,int val);//插入元素
bool delete_arr(struct Arr * pArr, int pos, int * pVal);//删除元素
int get(struct Arr *pArr,int index); //得到元素
bool is_empty(struct Arr * pArr);//判断是否为空
bool is_full(struct Arr * pArr);//判断是否已满
void show_arr(struct Arr * pArr);//遍历数组
void inversion_arr(struct Arr * pArr);//数组倒置
void one_sort(int *sqList,int val,int len);//单步排序声明
void straisort(struct Arr * pArr);//直接插入排序声明

int main(void)
{
	struct Arr arr;
	init_arr(&arr,6);//初始化函数测试
	//show_arr(&arr);
	append_arr(&arr,3);
	append_arr(&arr,2);
	append_arr(&arr,9);
	insert_arr(&arr,2,7);
	show_arr(&arr);
	return 0;
}

//初始化数组的函数实现  pArr是结构体变量arr的指针
void init_arr(struct Arr * pArr,int length)
{
   pArr->pBase=(int *)malloc(sizeof(int)*length);//malloc()函数头文件声明
   if(NULL==pArr->pBase)
   {
      printf("动态内存分配失败!\n");
	  exit(-1);//要在头文件声明
   }
   else
   {
     pArr->len=length;
	 pArr->cnt=0;
   }

}
//遍历数组函数实现
void show_arr(struct Arr * pArr)
{
	if(is_empty(pArr))
	{
	   printf("数组为空\n");
	}
	else
	{
	  for(int i=0;i<pArr->cnt;i++)
	  {
	    printf("%d",pArr->pBase[i]);
	  }
	}
   
}
//判断数组是否为空
bool is_empty(struct Arr * pArr)
{
   if(pArr->cnt==0)
   
	   return true;
   else
   
	   return false;
   
}
//数组追加元素
bool append_arr(struct Arr * pArr,int val)
{
  if(pArr->cnt < pArr->len)
  {
    pArr->pBase[pArr->cnt]=val;
	(pArr->cnt)++;
	return true;
  }
  else
	 printf("数组已满\n");
    return false;
}
//插入元素
bool insert_arr(struct Arr * pArr,int index ,int val)
{
   if(pArr->cnt<pArr->len&&index<=pArr->cnt)
   {
	   for(int i=pArr->cnt-1;i>=index-1;i--)
	   {
	     pArr->pBase[i+1]=pArr->pBase[i];
		 
		 
	   }
	   pArr->pBase[index-1]=val;
	   (pArr->cnt)++;
	   return true;
   }
   else
   {
	   printf("插入失败\n");
	   return false;
   }


}
//单步直接插入排序实现

void one_sort(int *sqList,int val,int len)
{
     int pos=len;
     int temp=val;
     while(val<sqList[pos-1]&&pos>0)
     {
        sqList[pos]=sqList[pos-1];
        pos--;
        
     } 
     sqList[pos]=temp;
     
}
//直接插入排序实现
void straisort(struct Arr * pArr)
{
     
     for(int i=1;i<pArr->cnt;i++)
     {
        one_sort(pArr->pBase,pArr->pBase[i],i);//调用单步排序
     }
} 
//数组倒置
void inversion_arr(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;
}
//删除元素
bool delete_arr(struct Arr * pArr, int pos, int * pVal)
{
	int i;

	if ( is_empty(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;
}
//判断是否已满
bool is_full(struct Arr * pArr)
{
	if (pArr->cnt == pArr->len)
		return true;
	else
		return false;
}

//查找元素
int get(struct Arr *pArr,int index)
{
   for(int i=0;i<pArr->cnt;i++)
   {
     if(index==i)
	 {
	   return pArr->pBase[i];
	 }
   }
}

 

 

 

评论

1 楼 卑微的去爱你 2011-08-05  

/*      1
         1 1
        1 2 1
       1 3 3 1                一维数组二维数组是一个好算法  切记
      1 4 6 4 1   打印杨辉三角算法      
     
     
      二维数组算法  记住这一题
*/
package day3;
public class Yanghuisanjiao {
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        final int MAX = 8;//经常出现的常数用名称标识
        int mat[][] = new int[MAX][];
        int i = 0, j, n;
        n = MAX;
        for (i = 0; i < n; i++) {
            mat[i] = new int[i + 1];//对每个小数组实例化 ，规律：实例化个数 是下标+1
            mat[i][0] = 1;
            mat[i][i] = 1;
            for (j = 1; j < i; j++)
                mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];//好算法 上面两个数加起来是下面一个数 怎么表示的  学习
        }
       
        for (i = 0; i < n; i++) {
            for (j = n - i; j > 0; j--)
                System.out.print(" ");
            for (j = 0; j <= i; j++)
                System.out.print(mat[i][j] + " ");
            System.out.println();
        }
    }
}