910数据结构（2014年真题）

算法设计题

问题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