网站建设与微信公众号绑定,腾讯广点通广告投放平台,wordpress 一直加载插件,wordpress 火车头采集算法设计题
问题1
已知一个带头结点的单链表head#xff0c;假设结点中的元素为整数#xff0c;试编写算法#xff1a;按递增次序输出单链表中各个结点的数据元素#xff0c;并释放结点所占的存储空间。要求#xff1a;(1)用文字给出你的算法思想#xff1b;(2)不允许使…算法设计题
问题1
已知一个带头结点的单链表head假设结点中的元素为整数试编写算法按递增次序输出单链表中各个结点的数据元素并释放结点所占的存储空间。要求(1)用文字给出你的算法思想(2)不允许使用数组作为辅助空间。
//算法思想冒泡排序
对链表进行遍历在每趟遍历中查找链表的最小值输出并释放空间。再查找次小值输出并释放空间最后释放头节点。算法时间复杂度为O(n^2)//代码实现while(head-next ! null){LNode *pre head;LNode *p head-next;while(p-next ! null){if(p-next-data pre-next-data){pre p;}p p-next;}cout pre-next-data;LNode *q pre-next;pre-next q-next;free(q)}free(head);
}问题2
假设以带头结点的循环单链表表示队列并且只设置一个指针rear指向队尾结点但不设头指针请写出相应的入队列和出队列操作。
//算法思想
本题是链队基本操作的扩展知道尾指针后要实现元素入队则直接用链表的插入操作即可。要实现出队操作则需要根据尾指针找出头结点和开始结点然后进行删除。要注意的是尾指针应始终指向终端结点并且当删除结点后队列为空时必须特殊处理//代码实现
typedef struct QueueNode{int data;struct QueueNode *next;
}QueueNode;typedef struct{QueueNode *rear;
}LinkQueue;bool isEmpty(LinkQueue *Q){return Q-rear-next Q-rear;
}void initQueue(){Q-rear (QueueNode *)malloc(sizeof(QueueNode));Q-rear-next Q-rear;
}void enQueue(LinkQueue *Q, int x){QueueNode *p (QueueNode *)malloc(sizeof(QueueNode));p-data x;p-next Q-rear-next;Q-rear-next p;Q-rear p;//将尾指针移向新节点
}int deQueue(LinkQueue *Q, int x){if(isEmpty(Q)){return 0;}QueueNode *p;p Q-rear-next-next;if(p Q-rear){//队列中除头结点外只有一个结点Q-rear Q-rear-next;Q-rear-next Q-rear;}else{Q-rear-next-next p-next;}x p-data;free(p);return x;
}注意什么时候用. 什么时候用-
typedef struct LNode {int data;struct LNode *next;
}LNode*LinkList;LNode* p;LinkList L;结构体变量用「.」来访问成员而结构体指针用「-」来访问
访问data的两种方式 p-data 等价于 L.data
