编写算法，实现带头结点单链表的逆置算法。

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法: ① 求链表中的最大整数; ② 求链表的结点个数; ③ 求所有整数的平均值。

参考答案：
　　[算法描述]
　　①
　　int GetMax(LinkList p)
　　{
　　if(!p->next)
　　return p->data;
　　else
　　{
　　int max=GetMax(p->next);
　　return p->data>=max ? p->data:max;
　　}
　　}
　　②
　　int GetLength(LinkList p)
　　{
　　if(!p->next)
　　return 1;
　　else
　　{
　　return GetLength(p->next)+1;
　　}
　　}
　　③
　　double GetAverage(LinkList p , int n)
　　{
　　if(!p->next)
　　return p->data;
　　else
　　{
　　double ave=GetAverage(p->next,n-1);
　　return (ave*(n-1)+p->data)/n;
　　}
　　}

第2题：

假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空、入队和出队等算法。

参考答案：
　　置空队就是建立一个头节点，并把头尾指针都指向头节点，头节点是不存放数据的;判队空就是当头指针等于尾指针时，队空;入队时，将新的节点插入到链队列的尾部，同时将尾指针指向这个节点;出队时，删除的是队头节点，要注意队列的长度大于1还是等于1的情况，这个时候要注意尾指针的修改，如果等于1，则要删除尾指针指向的节点。
　　[算法描述]
　　//先定义链队结构:
　　typedef struct queuenode
　　{Datatype data;
　　struct queuenode *next;
　　}QueueNode; //以上是结点类型的定义
　　typedef struct
　　{queuenode *rear;
　　}LinkQueue; //只设一个指向队尾元素的指针
　　(1) 置空队
　　void InitQueue( LinkQueue *Q)
　　{ //置空队：就是使头结点成为队尾元素
　　QueueNode *s;
　　Q->rear = Q->rear->next;//将队尾指针指向头结点
　　while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队
　　{s=Q->rear->next;
　　Q->rear->next=s->next;
　　delete s;
　　}//回收结点空间
　　}
　　(2) 判队空
　　int EmptyQueue( LinkQueue *Q)
　　{ //判队空。当头结点的next指针指向自己时为空队
　　return Q->rear->next->next==Q->rear->next;
　　}
　　(3) 入队
　　void EnQueue( LinkQueue *Q, Datatype x)
　　{ //入队。也就是在尾结点处插入元素
　　QueueNode *p=new QueueNode;//申请新结点
　　p->data=x; p->next=Q->rear->next;//初始化新结点并链入
　　Q-rear->next=p;
　　Q->rear=p;//将尾指针移至新结点
　　}
　　(4) 出队
　　Datatype DeQueue( LinkQueue *Q)
　　{//出队,把头结点之后的元素摘下
　　Datatype t;
　　QueueNode *p;
　　if(EmptyQueue( Q ))
　　Error("Queue underflow");
　　p=Q->rear->next->next; //p指向将要摘下的结点
　　x=p->data; //保存结点中数据
　　if (p==Q->rear)
　　{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点
　　Q->rear = Q->rear->next;
　　Q->rear->next=p->next;
　　}
　　else
　　Q->rear->next->next=p->next;//摘下结点p
　　delete p;//释放被删结点
　　return x;
　　}

第3题：

带头结点的单链表Head为空的条件是____________。

参考答案：Head->next==null

第4题：

试写一算法,实现单链表的就地逆置(要求在原链表上进行)

参考答案：void Inverse(LinkList L->next;L->next NULL;while p->next;q->next L->next;L->next

第5题：

在具有n个结点的单链表中,实现()的操作，其算法的时间复杂度是O。

A.求链表的第i个结点

B.在地址为P的结点之后插入一个结点

C.删除表头结点

D.删除地址为P的结点的后继结点

正确答案：A

第6题：

设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。

参考答案：
　　B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表。
　　[算法描述]
　　void DisCompose(LinkedList A)
　　{ B=A;
　　B->next= NULL; ∥B表初始化
　　C=new LNode;∥为C申请结点空间
　　C->next=NULL; ∥C初始化为空表
　　p=A->next; ∥p为工作指针
　　while(p!= NULL)
　　{ r=p->next; ∥暂存p的后继
　　if(p->data<0)
　　{p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法
　　else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表,前插法
　　p=r;∥p指向新的待处理结点。
　　}
　　}

第7题：

设计一个算法,通过一趟遍历在单链表中确定值最大的结点。

参考答案：
　　假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则设其下一个元素为最大值，反复进行比较，直到遍历完该链表。
　　[算法描述]
　　ElemType Max (LinkList L ){
　　if(L->next==NULL) return NULL;
　　pmax=L->next; //假定第一个结点中数据具有最大值
　　p=L->next->next;
　　while(p != NULL ){//如果下一个结点存在
　　if(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值，则重新赋值
　　p=p->next;//遍历链表
　　}
　　return pmax->data;

第8题：

带头结点的单链表L为空的判定条件是()。

参考答案：L->next==NULL

第9题：

完善算法：已知单链表结点类型为：

函数create建立以head为头指针的单链表。

正确答案：

第10题：

在长度为n的()上删除第一个元素,其算法的时间复杂度为O(n)。

A.只有表头指针的不带表头结点的循环单链表

B.只有表尾指针的不带表头结点的循环单链表

C.只有表尾指针的带表头结点的循环单链表

D.只有表头指针的带表头结点的循环单链表

参考答案：A

编写算法，实现带头结点单链表的逆置算法。

题目

相似问题和答案

更多相关问题

相关内容