随机输入一个多项式和一个指数，然后求多项式的幂，用链表实现
我在求多项式的积时总是要新建一个链表用于存放结果，然后再释放原来的链表，这样如果指数太大，程序就变得很慢，有没有比较快的算法呢？

代码呢？

码呢？

这个，，，果断抢分

这样的话，你可以利用栈来进行，利用栈的特点进行中间变量的存储，这样最后留在栈中的应该就是指数最高的，我刚学数据结构，懂的不很多

/****************************    list.h       ***************************************************************************************/
typedef double ElementDouble ;
typedef int    ElementInt ;

struct Node ;
typedef struct Node *Position ;
typedef Position List ;

List CreatList ( void ) ;

int IsEmpty ( List L ) ;

void MakeEmpty ( List L ) ;

void Insert ( ElementDouble D, ElementInt Index, List L ) ;

void Print ( List L ) ;

void DisposeList ( List L ) ;



struct Node {
    ElementDouble D ;

    ElementInt    Index ;
    struct Node * Next ;
} ;




/**************************   list.c    ***************************************************/

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
List
CreatList ( void )
{
    List L ;
    L = malloc ( sizeof ( struct Node ) ) ;
    if ( NULL == L )
    {
        fprintf ( stderr, "CreatList :Out of space.\n" ) ;
        exit ( 1 ) ;
    }
    MakeEmpty ( L ) ;
    return L ;
}
int
IsEmpty ( List L )
{
    return NULL == L -> Next ;
}
void
MakeEmpty ( List L )
{
    if ( L != NULL )
    {
        Position p, q ;
        p = L -> Next ;
        while ( p != NULL )
        {
            q = p -> Next ;
            free ( p ) ;
            p = q ;
        }
        L -> Next = NULL ;
    }
}
void
Insert ( ElementDouble D, ElementInt Index, List L )
{
    Position p, q ;
    q = L ;
    if ( 0 == D )
        return ;
    while ( q -> Next != NULL && q -> Next -> Index > Index )
        q = q -> Next ;
  
    if ( q -> Next != NULL && q -> Next -> Index == Index )
        q -> Next -> D += D ; 
    else
    {
        p = malloc ( sizeof ( struct Node ) ) ;
        if ( NULL == p )
        {
            fprintf ( stderr, "Insert :Out of space.\n" ) ;
            exit ( 2 ) ;
        }

        p -> D = D ;
        p -> Index = Index ;
        p -> Next = q -> Next ;
        q -> Next = p ;
    }
}
void
Print ( List L )
{
    Position p ;
    if ( IsEmpty ( L ) )
    {
        fprintf ( stderr, "Print :List is Empty.\n" ) ;
        return ;
    }
    p = L -> Next ;
    printf ( "Polynomial :\n" ) ;
    while ( p != NULL )
    {
        putchar ( p -> D > 0 ? '+' : '-' ) ;
        printf ( " %.1f", p -> D ) ;
        if ( 0 == p -> Index )
        ;
        else
        if ( 1 == p -> Index )
            putchar ( 'x' ) ;
        else
            printf ( "x^%d ", p -> Index ) ;
      
        p = p -> Next ;
    }
    putchar ( '\n' ) ;
}

void
DisposeList ( List L )
{
    MakeEmpty ( L ) ;
    free ( L ) ;
}




/***************     main.c      ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
int IsEven ( int n ) ;
List PowPolynomial ( List L, int n ) ;        //求多项式L的n次幂
List PolyMultiply ( List L1, List L2 ) ;      //求多项式L1与L2的乘积
int
main ( void )
{
    List L ;
    int n ;
    ElementDouble d ;
    ElementInt    index ;
    L = CreatList () ;
    printf ( "Please input a polynomial:\n" ) ;
    scanf ( "%lf%d", &d, &index ) ;
    while ( d != 0 )
    {
        Insert ( d, index, L ) ;  
        scanf ( "%lf%d", &d, &index ) ;
    }
    Print ( L ) ;

    printf ( "Please input polynomial index:" ) ;
    scanf ( "%d", &n ) ;
    if ( 0 == n )
    {
        printf ( "Polynomial : 1\n" ) ;
        return 0 ;
    }
    else
    if ( 1 == n )
        Print ( L ) ;
    else
    {
        L = PowPolynomial ( L, n ) ;
        Print ( L ) ;
    }
    DisposeList ( L ) ;
    return 0 ;
}
List
PowPolynomial ( List L, int n )
{
    if ( 1 == n )
        return L ;
    else
    {
        if ( IsEven ( n ) )
            return PowPolynomial ( PolyMultiply ( L, L ), n / 2 ) ;
        else
            return PolyMultiply ( PowPolynomial ( PolyMultiply ( L, L ), n / 2 ), L ) ;
    }
  
}
List
PolyMultiply ( List L1, List L2 )
{
    List L ;
    Position p1, p2 ;
    p1 = L1 -> Next ;
    p2 = L2 -> Next ;
    if ( NULL == p1 || NULL == p2 )
        return NULL == p1 ? L2 : L1 ;
    L = CreatList () ;
    while ( p1 != NULL )
    {
        p2 = L2 -> Next ;
        while ( p2 != NULL )
        {
            Insert ( p1 -> D * p2 -> D, p1 -> Index + p2 -> Index, L ) ;
            p2 = p2 -> Next ;
        }
        p1 = p1 -> Next ;
    }
    return L ;
}
int
IsEven ( int n )
{
    return 0 == n % 2 ;
}

[ 本帖最后由 Juson 于 2013-4-9 19:15 编辑 ]

太难我不会

代码我全都贴出来的，有木有别的好的算法呢