#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
typedef struct _Node
{
int data;
struct _Node *left;
struct _Node *right;
}node;
node *CreatNode_Head(int n)
{
node *head,*p;
head=(node*)malloc(sizeof(node));
if(head==NULL)
return NULL;
head->left=NULL;
head->right=NULL;
srand(time(0));
for(int i=0;i<n;++i)
{
p=(node*)malloc(sizeof(node));
p->data=rand()0+1;
printf("p->data:%d\t",p->data);
/*
if(i==0)
{
p->right=head->right;
p->left=head;
head->right=p;
}
else
{
head->right->left=p;
p->right=head->right;
p->left=head;
head->right=p;
}*/
if(head->right)
head->right->left=p;
p->right=head->right;
p->left=head;
head->right=p;
}
return head;
}
node *CreatNode_Tail(int n)
{
int i=0;
node *head,*p,*q;
head=(node*)malloc(sizeof(node));
if(head==NULL)
return NULL;
head->left=NULL;
head->right=NULL;
q=head;
srand(time(0));
for(int i=0;i<n;++i)
{
p=(node*)malloc(sizeof(node));
p->data=rand()0+1;
p->right=NULL;
p->left=q;
printf("p->data:%d\t",p->data);
q->right=p;
q=p;
}
return head;
}
bool isempty(node *head)
{
if(head->right==NULL)
{
printf("此链表是空的!!!：\n");
return true;
}
else
{
printf("此链表不是空的：\n");
return false;
}
}
int length(node *head)
{
if(head==NULL)
return -1;
int len=0;
node *p=head;
while(p->right!=NULL)
{
len++;
p=p->right;
}
return len;
}
void printnode(node *p)
{
if(p==NULL)
return;
node *q;
if(isempty(p))
return;
else
{
q=p->right;
while(q!=NULL)
{
printf("%d\t",q->data);
q=q->right;
}
}
printf("\n");
printf("print over:\n");
}
void printnode_left(node *p)
{
if(p==NULL)
return;
node *q,*tmp;
if(isempty(p))
return;
else
{
q=p->right;
while(q!=NULL)
{
tmp=q;
q=q->right;
}
}
while(tmp!=p)
{
printf("%d\t",tmp->data);
tmp=tmp->left;
}
printf("\n");
printf("print over:\n");
}
int SearchNode(node *head,int pos)
{
if(head==NULL)
{
printf("the node is NULL\n");
return -1;
}
if(pos<=0)
{
printf("the pos can not smaller than 0\n");
return -1;
}
else if(head->right==NULL)
{
printf("the node is empty\n");
return -1;
}
else if(pos>length(head))
{
printf("the pos over the length of the node\n");
return -1;
}
else
{
while(pos--)
{
head=head->right;
}
}
return head->data;
}
node * SearchNode1(node *head,int pos)
{
if(pos<0)
{
printf("the pos can not smaller than 0\n");
return NULL;
}
else if(head->right==NULL)
{
printf("the node is empty\n");
return NULL;
}
else if(pos>length(head))
{
printf("the pos over the length of the node\n");
return NULL;
}
else
{
while(pos--)
{
head=head->right;
}
}
return head;
}
bool DeleteNode(node *head,int pos,int &data)
{
if(head==NULL)
return false;
node *item=NULL;
node *p=head;
node *q=SearchNode1(head,pos-1);
if((!q)||(!q->right))
{
printf("delete failed:\n");
return false;
}
item=q->right;
data=item->data;
q->right=item->right;
free(item);
item=NULL;
printf("Delete success:\n");
return true;
}
bool InsertNode(node *head,int pos,int data)
{
if(head==NULL)
return false;
node *item=NULL;
node *p=head;
node *q=SearchNode1(head,pos-1);
if(!q)
{
printf("Insert failed:\n");
return false;
}
item=(node*)malloc(sizeof(node));
item->data=data;
item->right=q->right;
item->left=q;
q->right=item;
printf("Insert success:\n");
return true;
}
int main()
{
int len=0;
node *head,*head1;
node *head2=NULL;
printf("please input some date and creat a node\n");
head=CreatNode_Head(10);
printnode(head);
printnode_left(head);
printf("the length of the list is:%d\n",length(head));
head1=CreatNode_Tail(10);
printnode(head1);
printnode_left(head1);
printf("the length of the list is:%d\n",length(head1));
for(int i=0;i<length(head1);i++)
{
printf("SearchNode:index:%d,data:%d\n",i+1,SearchNode(head1,i+1));
//printnode(SearchNode1(head1,i+1));//这里打印就有问题
}
InsertNode(head1,1,101);
printnode(head1);
InsertNode(head1,12,102);
printnode(head1);
InsertNode(head1,14,103);
printnode(head1);
int data=0;
DeleteNode(head1,1,data);
printf("the data is:%d\n",data);
printnode(head1);
DeleteNode(head1,12,data);
printf("the data is:%d\n",data);
printnode(head1);
printnode_left(head1);
return 0;
}
