（《数据结构和算法》单链表和循环链表
线性表：线性表是一种有序的序列，序列的数据可以是多种的；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");
}
页:
[1]