数据结构与算法课后习题解答
    数据结构与算法课后习题解答
    第一章绪论（参考答案）
    1.3 (1) O(n)
    (2) (2) O(n)
    (3) (3) O(n)
    (4) (4) O(n1/2)
    (5) (5) 执行程序段的过程中，x,y值变化如下：
    循环次数 x y
    0（初始） 91 100
    1 92 100
    2 93 100
    。 。
    9 100 100
    10 101 100
    11 91
    12
    。
    20 99
    21 91 98
    。 。
    30 101 98
    31 91 97
    到y=0时，要执行10*100次，可记为O（10*y）=O（n）
    数据结构与算法课后习题解答
    1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n
    第二章 线性表(参考答案)
    在以下习题解答中，假定使用如下类型定义：
    （1）顺序存储结构：
    #define ***** 1024
    typedef int ElemType;// 实际上，ElemType
    typedef struct
    { ElemType data[*****];
    int last; // last
    }sequenlist;
    （2
    *next；
    }linklist;
    （3）链式存储结构（双链表）
    typedef struct node
    {ElemType data;
    struct node *prior,*next；
    数据结构与算法课后习题解答
    }dlinklist;
    （4）静态链表
    typedef struct
    {ElemType data;
    int next;
    }node;
    node sa[*****];
    2.1 la，往往简称为“链表la”。
    是副产品）
    2.2 23
    void
    elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的
    { int i=0,j;
    while (ielenum  A[i]=x) i++; // 查插入位置
    for (j= elenum-1;jj--) A[j+1]=A[j];// 向后移动元素
    A[i]=x; // 插入元素
    数据结构与算法课后习题解答
    } // 算法结束 24
    void rightrotate(ElemType A[],int n,k)
    // 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
    { int num=0; // 计数，最终应等于n
    int start=0; // 记录开始位置（下标）
    while (numn)
    { temp=A[start]; //暂存起点元素值，temp
    empty=start; //保存空位置下标
    next=(start-K+n) %n; //
    while (next !=start)
    { A[empty]=A[next];//
    num++; 1
    // 计算新右移元素的下标
    // 把一轮右移中最后一个元素放到合适位置
    num++;
    start++; // 起点增1，若numn则开始下一轮右移。 }
    } // 算法结束
    数据结构与算法课后习题解答
    算法二
    算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。
    void rightrotate(ElemType A[],int n,k)
    // 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
    { ElemType temp;
    for(i=0;i(n-k)/2;i++) //左面n-k个元素逆置
    {temp=A[i]; A[i]=A[n-k-1-i]; A[n-k-1-i]=temp; }
    for(i=1;ii++) //右面k个元素逆置
    {temp=A[n-k-i]; A[n-k-i]=A[n-i]; A[n-i]=temp; }
    for(i=0;ii++) //全部n个元素逆置
    {temp=A[i]; A[i]=A[n-1-i]; A[n-1-i]=temp; }
    } // 算法结束 25
    void
    // L递增有序，本算法将x插入到链表中，并保持链表的递增有序。
    ，*s;
    // p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱
    s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出
    s-data=x;
    while (p  p-data=x) {pre=p; p=p-next;} // 查插入位置
    pre-next=s; s-next=p; // 插入元素
    数据结构与算法课后习题解答
    } // 算法结束 26
    void invert(linklist *L)
    // 本算法将带头结点的单链表L逆置。
数据结构与算法题库
    //点的链表中。
    { linklist *p=L-next,*s;
    // p为工作指针，指向当前元素，s为p的后继指针
    L-next=null;//
    while (p)
    {s=p-next; //
    p-next=L-next; // 逆置
    L-next=p;