设有一个带头节点的单链表 [tex=1.0x1.214]YHs5BX1EMaBNmbX0qd/96w==[/tex]节点的结构为[tex=5.214x1.357]LMOaLQ/68aAbpSy33bsQ/Gyw6fTECDaksqC9UX6i968=[/tex], [tex=2.0x1.0]4UxLfogD9pi/A23ay26F0g==[/tex]为整数元素, [tex=2.0x0.929]7QqODb1IqAMYMAFmGasRTA==[/tex]为后继节点的指针。设计一个算法,按递减次序输出该单链表中各节点的数据元素,并释放节点所占的存储空问,并要求算法的空间复杂度为 [tex=2.071x1.357]4tn8z3a70oWd+Kan/q/D8g==[/tex]。

2022-06-03

设有一个带头节点的单链表 [tex=1.0x1.214]YHs5BX1EMaBNmbX0qd/96w==[/tex]节点的结构为[tex=5.214x1.357]LMOaLQ/68aAbpSy33bsQ/Gyw6fTECDaksqC9UX6i968=[/tex], [tex=2.0x1.0]4UxLfogD9pi/A23ay26F0g==[/tex]为整数元素, [tex=2.0x0.929]7QqODb1IqAMYMAFmGasRTA==[/tex]为后继节点的指针。设计一个算法,按递减次序输出该单链表中各节点的数据元素,并释放节点所占的存储空问,并要求算法的空间复杂度为 [tex=2.071x1.357]4tn8z3a70oWd+Kan/q/D8g==[/tex]。

答案：

解:对应的算法如下:void DispList( LinkList * L)    //输出单链表{    LinkIist * p= T.- > next ; //P指向开始节点    while (p!= NUI.L)    //P不为NULL,输出*P节点的data域    {    printf( “% d ”,p-> data) ;        P= P->next;    //p移向下一个节点    }    printf(“\n”);}void Sort( LinkList * &L)    //对L递减排序{    LinkList  p =L-> next,  4,  pre;    if (p!= NULL){    p- p-> next;    //p指向第2个数据节点    L- > next - > next = NUIL ;    while (p!= NULL)    {    q-p->next;        pre = L.;        while (pre-> next!= NULL && pre-> next->data > p->data)            pre - pre >next;        p- > next = pre-> next;     //在*pre之后插入* p节点            pre-> next = p;        p= q;        }    }}void Release(LinkList * &L)    //释放单链表L{    LinkList * p-L-> next, * pre- L;    while (pl= NUI,L)    {    free(pre) ;        pre- P;        p=p- > next ;    }    free(pre) ;}void fun( LinkIist x &L)    //完成本题的算法{    printf(“排序前单链表L:”); DispList(L);    Sort(L);    printf(“排序后单链表L:”) ;                  DispList(L);    printf(“释放单链表L\n”);    Release( L);}

举一反三

内容

0
设计一个高效算法,将顺序表[tex=0.714x1.0]ravtxd2oof9d0U26ZFAIhw==[/tex]中的所有元素逆置,要求算法的空问复杂度为[tex=2.071x1.357]4tn8z3a70oWd+Kan/q/D8g==[/tex]。
1
一棵具有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个节点的完全二叉树以顺序方式存储在数组[tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex]中,假设每个节点的元素为单个字符,没有对应节点时[tex=0.786x1.0]Yn3GgEZev6SOu2r4v1WnCw==[/tex]中元素取值为“[tex=0.714x1.071]7w98G/k9AtxEbHqkKciLfg==[/tex]”。设计一个算法构造该二叉树的二叉链存储结构。
2
已知单链表[tex=0.714x1.0]ravtxd2oof9d0U26ZFAIhw==[/tex](带头节点)是一个递增有序表，试写一高效算法,删除表中值大于[tex=1.857x1.0]Ve9bEhOtZUXzk+oXeNyN0Q==[/tex]且小于[tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]的节点(若表中有这样的节点),同时释放被删节点的空间,这里[tex=1.857x1.0]Ve9bEhOtZUXzk+oXeNyN0Q==[/tex]和 [tex=2.0x0.786]pey2TtVdqqFqhRAwhigArw==[/tex]是两个给定的参数。请分析你的算法时间复杂度。
3
任意一个有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个节点的二叉树,已知它有[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]个叶子节点,试证明非叶子节点中有[tex=3.0x1.357]6wOxI7kRdeTWx9DEyQ5iyA==[/tex]个节点的度为[tex=0.5x1.0]8C7DKsr6nhrfCdsmGxO88g==[/tex],其余的节点的度为[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex]。
4
给定[tex=3.571x1.357]0jgNZNb5KE0SpRQgBt7oQg==[/tex]，设x=0是4重插值节点，x=1是单重插值节点试求相应的Hermite插值公式，并估计误差[tex=4.071x1.357]ZHsKcW72rLaSaexOsDovRw==[/tex]