（《数据结构和算法》单链表和循环链表

luciferzf

线性表：线性表是一种有序的序列，序列的数据可以是多种的；
1.c++中最常用的一种线性表就是数组，数组通过存储的地址连接在一起，进而可以通过存储地址来遍历、增减等操作。
2.单向链表，在C语言中通过指针将元素连接在一起，通过每个节点的指针指向下一个节点，从而进行遍历等操作
3.循环链表，与单向链表相似，但是最后一个元素的指针不再为空，而是指向头节点，形成循环。
4.有环链表的判断：1）步数比较法，其中一个指针不断的从头指针走到另一个指针的位置，比较二者步数，如果是无环链表，步数一定相同（2）快慢指针法，快指针的速度是慢指针的两倍，如果是有环链表，快指针总会在一定的循环后与慢指针指在同一位置，而无环则不可能。

#include<cstdlib>
#include<cstdio>
#include<time.h>
#include<iostream>
using namespace std;

struct node
{
        int value;
        struct node *nextptr;
}*r,*h;

void create1(int n)
{
        int i;
        srand(time(NULL));
        struct node *p;
        h = new struct node;
        r = h;
        for (i = 0; i < n; i++)
        {
                p = new struct node;
                p->value = rand() % 100 + 1;
                r->nextptr = p;
                r = p;
        }
        h->value = rand() % 100 + 1;
        r->nextptr = h->nextptr->nextptr->nextptr;
}

void create2(int n)
{
        srand(time(NULL));
        h = NULL;
        for (int i = 0; i < n; i++)
        {
                if (h == NULL)
                {
                        h = new struct node;
                        r = h;
                }
                else
                {
                        r->nextptr = new struct node;
                        r = r->nextptr;
                }
                r->value = rand() % 100 + 1;
        }
        r->nextptr = NULL;
}

void proof1()
{
        struct node *p1, *p2;
        p1 = h, p2 = h;
        int pos1 = 0, pos2 = 0;
        while (p1 != NULL&&p2 != NULL&&p2->nextptr != NULL)
        {
                p1 = p1->nextptr;
                pos1++;
                p2 = h;
                while (p2 != p1)
                {
                        p2 = p2->nextptr;
                        pos2++;
                        if (p1 == p2)
                        {
                                if (pos1 != pos2)
                                {
                                        printf("在第%d个节点存在环\n",pos1);
                                        return;
                                }
                                else
                                {
                                        pos2 = 0;
                                        break;
                                }
                        }
                }
        }
        cout << "不存在环" << endl;
}

void proof2()
{
        struct node *fp=h, *sp=h;
        while (fp != NULL&&sp != NULL&&fp->nextptr != NULL)
        {
                fp = fp->nextptr->nextptr;
                sp = sp->nextptr;
                if (fp == sp)
                {
                        cout << "存在环" << endl;
                        return;
                }
        }
        cout << "不存在环" << endl;
}
int main()
{
        int i, s;
        cout << "创建有环链表——》1" << endl << "创建无环链表——》2" << endl;
        cout << "用法一验证链表——》3" << endl << "用法二验证链表——》4" <<"结束程序——》5"<< endl;
        cout << "input:";
        cin >> s;
        while (1)
        {
                if (s == 1)
                {
                        cout << "链表元素个数n:";
                        int n;
                        cin >> n;
                        create1(n);
                }
                else if (s == 2)
                {
                        cout << "链表元素个数n:";
                        int n;
                        cin >> n;
                        create2(n);
                }
                else if (s == 3)proof1();
                else if (s == 4)proof2();
                else if (s == 0)break;
                else cout << "wrong!" << endl;
                cout << "input:";
                cin >> s;
        }
        system("PAUSE");
}