计算机保研考研基础题-自己当时保研总结的0基础开始试题

// ConsoleApplication6.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <string> #define LEN 8 using namespace std; #include <stdio.h> struct Node { int val; Node *next; }; class list { Node*head; public: list() { head = NULL; } void insertlist(int aDate, int bDate);//链表结点的插入 void Deletelist(int aDate);//链表结点的删除 void Outputlist();//链表结点的输出 Node*Gethead() { return head; } }; void list::Outputlist() { Node*current = head; while (current != NULL) { cout << current->val << " "; current = current->next; } cout << endl; } void list::insertlist(int aDate, int bDate) //设aDate是结点a中的数据，bDate是结点b中的数据 { Node*p, *q, *s; //p指向结点a，q指向结点a_k，s指向结点b s = (Node*)new(Node); //动态分配一个新结点 s->val = bDate; //设b为此结点 p = head; if (head == NULL) //若是空表，使b作为第一个结点 { head = s; s->next = NULL; } else if (p->val == aDate) //若a是第一个结点 { s->next = p; head = s; } else { while (p->val != aDate&&p->next != NULL)//查找结点a { q = p; p = p->next; } if (p->val == aDate) ///若有结点a { q->next = s; s->next = p; } else //若没有结点a； { p->next = s; s->next = NULL; } } } void list::Deletelist(int aDate) //设aDate是要删除的结点a中的数据成员 { Node*p, *q; //p用于指向结点a,q用于指向结a的前一个结点 pq需要写在外面哦 p = head; if (p == NULL) //若是空表 return; if (p->val == aDate) //若a是第一个结点 { head = p->next; delete p; } else { while (p->val != aDate&&p->next != NULL) //查找结点a { q = p; p = p->next; } if (p->val == aDate) //若有结点a { q->next = p->next; delete p; } } } //判断是否有环 bool isLoop(Node *pHead) { Node * fast = pHead; Node * slow = pHead; //如果无环，则fast先走到终点 //当链表长度为奇数时，fast->Next为空 //当链表长度为偶数时，fast为空 while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; //如果有环，则fast会超过slow一圈 if (fast == slow) { break; } } if (fast == NULL || fast->next == NULL) return false; else return true; } //计算环的长度 int loopLength(Node * pHead) { if (isLoop(pHead) == false) return 0; Node * fast = pHead; Node * slow = pHead; int length = 0; bool begin = false; bool agian = false; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; //超两圈后停止计数，挑出循环 if (fast == slow && agian == true) break; //超一圈后开始计数 if (fast == slow && agian == false) { begin = true; agian = true; } //计数 if (begin == true) ++length; } return length; } //求出环的入口点 Node* findLoopEntrance(Node * pHead) { Node * fast = pHead; Node * slow = pHead; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; //如果有环，则fast会超过slow一圈 if (fast == slow) { break; } } if (fast == NULL || fast->next == NULL) return NULL; slow = pHead; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } //单循环链表创建 Node *CreateListCircle(Node *head1) { Node *p, *q,*head,*tail; p = head1; int i = 0; int n = 10; head = tail = NULL; for (i = 1; i < n; i++) { p = new Node(); p->val = i; if (head == NULL) { head = p; q = p; } else { q->next = p;//尾插法 q = p; } } p->next = head; tail = p; return tail; } int main() { Node *head; head = new Node(); Node* p; p= CreateListCircle(head); if( isLoop(p)) cout<<"有环"; else cout << "wuhuan"; cout<<findLoopEntrance(p)->val; cout << loopLength(p); }