线性表应用

一、 线性表的定义和特点

定义: 线性表是具有相同特性的数据元素的一个有限序列，由n(n>=0)个数据元素（结点）a1,a2,a3...an组成的有限序列。

       其中数据元素的个数n定义为表的长度。

       当n=0时称为空表。

       将非空的线性表(n>0)记作：(a1,a2,...an)

       这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。

线性表的逻辑特征：

       在非空的线性表，有且仅有一个开始结点a1,它没有直接前趋，而仅有一个直接后继a2；

      有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；

      其余的内部结点ai(2<=i<=n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

线性表是一种典型的线性结构。

二、 线性表的应用实例

  2.1  稀疏多项式的运算

A = ((7,0),(3,1),(9,8),(5,17))

B = ((8,1),(22,7),(-9,8))

1. 创建一个新数组c
2. 分别从头遍历比较a和b的每一项

             指数相同，对应系数相加，若其和不为零，则在c中增加一个新项

             指数不相同，则将指数较小的项复制到c中

    3.一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

#include <stdio.h>
#include <stdlib.h>
//定义一个结构体来表示多项式的非零项
typedef struct{
     int exponent;//指数
     int coefficient;//系数
}Term;

void addPolynomials(Term poly1[],int size1,Term poly2[],int size2,Term result[]);
int main(){
   //示例多项式1：3x2+5x+2
   Term poly1[] = {{2,3},{1,5},{0,2}};
   int size1 = sizeof(poly1)/sizeof(poly1[0]) ;
   //示例多项式2：2x2+4x1+1
   Term poly2[] = {{2,2},{1,4},{0,1}};
   int size2 = sizeof(poly2)/sizeof(poly2[0]);
   //结果多项式的结果是两个多项式大小的和
   Term result[size1 + size2];
   int resultSize = 0;

   //执行多项式加法
   addPolynomials(poly1,size1,poly2,size2,result);

   //打印结果
   printf("Resulting Polynomial: ");
   for(int i = 0;i < resultSize;i++){
       printf("%dx^%d",result[i].coefficient,result[i].exponent);
       if(i < resultSize - 1 && result[i+1].coefficient >= 0){
           printf("+ ");
       }
   }
   printf("\n");
   return 0;
}
//实现多项式加法
void addPolynomials(Term poly1[],int size1,Term poly2[],int size2,Term result[]){
     int i = 0,j = 0,k = 0;
     //遍历两个多项式
     while(i < size1 && j < size2){
         if(poly1[i].exponent < poly2[j].exponent){
            result[k++] = poly1[i++];}
         else if(poly1[i].exponent > poly2[j].exponent){
            result[k++] = poly2[j++];}
         else{
              //相同指数，系数相加
             int sum = poly1[i].coefficient + poly2[j].coefficient;
             if (sum != 0){//系数不为零，则加到结果中
                 result[k++] = (Term){poly1[i].exponent,sum};
             }
             i++;
             j++;
       }
   }
//添加剩余的项

  while(i < size1){
      result[k++] = poly1[i++];
  }
  while(j < size2){
      result[k++] = poly2[j++];
  }

 //设置结果多项式的大小
  result[k].exponent = -1;
}