我要评论1.带环链表问题
1.1给定一个链表判断其是否带环
解决思路：利用快慢指针法，快指针一次走两步慢指针一次走一步，从链表起始位置遍历链表，如果链表带环，则快慢指针一定会在环中相遇，否则快指针先到达链表末尾。
代码实现：（链表的实现请跳转☞http://t.csdnimg.cn/jenav）
slnode* islink(slnode* head)
{
slnode* fast = head;
slnode* slow = head;
//让快慢指针先走一步进循环
fast = fast->next->next;
slow = slow->next;
//这里是循环的条件：快慢指针未相遇、快指针未到链表末端
while ((fast != slow) && (fast != null))
{
fast = fast->next->next;
slow = slow->next;
}
if (fast == slow)
{
return fast;
}
if(fast==null)
{
return null;
}
}
void test()
{
//创建一个带环链表
slnode* node1 = slbuynode(1);
slnode* node2 = slbuynode(2);
slnode* node3 = slbuynode(3);
slnode* node4 = slbuynode(4);
slnode* node5 = slbuynode(5);
slnode* node6 = slbuynode(6);
slnode* node7 = slbuynode(7);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7;
node7->next = node4;
//判断是否带环,如果带环打印相遇节点，如果不带环打印"null"
if (islink(node1) == null)
{
printf("null\n");
}
else
{
printf("%d\n", islink(node1)->data);
}
}
int main()
{
test();
return 0;
}1.2给定一个带环链表，返回链表开始入环的第一个节点
解决方案：让一个指针从链表头开始遍历链表，同时另一个指针从判断相遇位置开始绕环运行，两个指针都是一次走一步，最终会在进环的第一个节点相遇。
证明：
代码实现：
//判断是否为带环链表
slnode* islink(slnode* head)
{
slnode* fast = head;
slnode* slow = head;
//让快慢指针先走一步进循环
fast = fast->next->next;
slow = slow->next;
//这里是循环的条件：快慢指针未相遇、快指针未到链表末端
while ((fast != slow) && (fast != null))
{
fast = fast->next->next;
slow = slow->next;
}
if (fast == slow)
{
return fast;
}
if(fast==null)
{
return null;
}
}
//返回带环链表的进环节点
slnode* entrynode(slnode* head, slnode* m)
{
slnode* a = head;
slnode* b = m;
while (a != b)
{
a = a->next;
b = b->next;
}
return a;
}
void test2()
{
//创建一个带环链表：1->2->3->4->5->6->7->4->5...
slnode* node1 = slbuynode(1);
slnode* node2 = slbuynode(2);
slnode* node3 = slbuynode(3);
slnode* node4 = slbuynode(4);
slnode* node5 = slbuynode(5);
slnode* node6 = slbuynode(6);
slnode* node7 = slbuynode(7);
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7;
node7->next = node4;
//返回进环节点
slnode* m = islink(node1);
slnode* e = entrynode(node1, m);
printf("%d\n", e->data);
}
int main()
{
test2();
return 0;
}2.循环队列问题
2.1循环队列
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
2.2代码实现：
circularqueue.h
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<math.h>
typedef int cqdatatype;
typedef struct circularqueue
{
cqdatatype* a; //利用数组实现循环链表
int head; //指向头
int tail; //指向尾的下一个
}cqueue;
//初始化
void cqinit(cqueue* q);
//入队列
void cqpush(cqueue* q, cqdatatype x);
//出队列
void cqpop(cqueue* q);
//查看队头
cqdatatype cqtop(cqueue* q);
//数据有效个数
size_t cqsize(cqueue* q);
//判空
bool cqempty(cqueue* q);
//判满
bool cqfull(cqueue* q);
//销毁
void cqdestroy(cqueue* q);circularqueue.c
#include"circularqueue.h"
//初始化
void cqinit(cqueue* q)
{
assert(q);
//创建一个5+1的数组实现容量为5的循环队列
q->a = (cqdatatype*)malloc(sizeof(cqdatatype)*6);
q->head = q->tail = 0;
}
//判满
bool cqfull(cqueue* q)
{
assert(q);
return (q->tail + 1) % 6 == q->head;
}
//入队列(入队列前需判断是否满)
void cqpush(cqueue* q, cqdatatype x)
{
assert(q);
//判满
if (cqfull(q))
{
perror("cqfull(q) is full");
return;
}
//第一个数据入队列
if (q->head == q->tail == 0)
{
q->a[q->tail] = x;
q->tail++;
}
else
{
q->a[q->tail] = x;
q->tail++;
}
q->tail = q->tail % 6;
}
//判空
bool cqempty(cqueue* q)
{
assert(q);
return q->head == q->tail;
}
//出队列(出队列前判空)
void cqpop(cqueue* q)
{
assert(q);
if (cqempty(q))
{
perror("cqempty(q) is true");
return;
}
q->head++;
q->head = q->head % 6;
}
//查看队头
cqdatatype cqtop(cqueue* q)
{
assert(q);
assert(cqempty(q) != true);
return q->a[q->head];
}
//数据有效个数
size_t cqsize(cqueue* q)
{
assert(q);
if (q->tail < q->head)
{
return 6 - q->head + q->tail - 0;
}
return abs(q->tail - q->head);
}
//销毁
void cqdestroy(cqueue* q)
{
assert(q);
free(q->a);
q->a = null;
q->head = q->tail = 0;
}以上便是本期讨论的两个数据结构问题，欢迎大家评论讨论交流。
发表评论