Exercise DS

#include <iostream>
using namespace std; typedef struct Node
{
Node *next;
int data;
}Node, *List; typedef struct DNode
{
DNode *prior;
DNode *next;
int data;
}DNode, *DList; void creatList(List &l)
{
l = new Node;
Node *p = l;
int data;
while ((cin>>data) && data != -)
{
Node *q= new Node;
q ->data = data;
p ->next = q;
p = p->next;
}
p ->next = nullptr;
} void printList(List &l)
{
Node *p = l->next;
while (p)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
} void reversePrint(List &l)
{
Node *p =l;
if (p->next != nullptr)
reversePrint(p->next);
cout<<p->data<<" ";
} void removeMin(List &l)
{
Node *p = l->next;
int min = p->data;
Node *flag = nullptr;
while (p)
{
if (p->next ==nullptr) break ;
if (p->next->data < min)
{
min = p->next->data;
flag = p;
}
p = p->next;
} Node *q = flag ->next;
flag ->next = q->next;
free(q);
} void reverseList (List &l)
{
Node *p = l->next;
l->next = nullptr;
Node *q;
while (p)
{
q = p->next;
p->next = l->next;
l->next = p;
p = q;
}
} void selectSort(List &l)
{
Node * p = l->next;
while (p)
{
Node *q = p->next;
Node *flag = p;
while (q)
{
if (q->data < flag->data)
flag = q;
q = q->next;
}
swap (p->data,flag->data);
p = p->next;
}
} void removeMM(List &l)
{
Node* p = l->next;
Node* min = p;
Node* max = p;
while (p)
{
if (p->data > max->data)
max = p;
if (p->data < min->data)
min = p;
p = p->next;
} Node* q = l; while (q)
{
Node * s = q->next;
if ((s->data>min->data) && (s->data<max->data ))
{
q ->next = s->next;
free(s);
}
q = q->next;
}
} int length(List &l)
{
int i = ;
if (!l || !l->next)
return ;
Node *p = l->next;
while (p)
{
i++;
p = p->next;
}
return i;
} Node* Search_1st_common(List &l1,List &l2)
{
int len1 = length(l1);
int len2 = length(l2); List longList = (len1>len2)?l1:l2;
List shortList = (len1<len2)?l1:l2;
int dist = (len1>len2)?(len1-len2):(len2-len1); while (dist--) longList = longList->next; while (longList)
{
if (longList->data == shortList->data)
return longList;
else
{
longList = longList->next;
shortList = shortList->next;
}
}
return nullptr;
} void freeALL(List &l)
{
while (l->next)
{
Node* pre = l;
Node*p = pre->next; while (p->next)
{
if (p->next->data<pre->next->data)
pre = p;
p = p->next;
}
printf("%d ",pre->next->data);
Node *u = pre->next;
pre->next =u->next;
free (u);
}
free(l);
} void divideList(List &l,List &r1)
{
Node *p = l->next;
r1 = new Node;
Node *r = r1;
while (p->next)
{
Node* s = new Node;
s->data = p->next->data;
Node* t = p->next;
p ->next = t->next;
r->next = s;
r = r-> next;
free(t);
p = p->next;
}
r->next = nullptr;
} void removeCF(List &l)
{
Node *p = l->next;
while (p->next)
{
Node *q = p->next;
if (q->data == p->data)
{
p->next = q->next;
free(q);
}
else
p = p->next;
}
} void MergeList(List &l1,List &l2)
{
Node *p = l1->next;
Node *q = l2->next;
l1->next = nullptr;
Node *s;
while (p && q)
{
if (p->data<q->data)
{
s = p->next;
p->next = l1->next;
l1->next = p;
p = s;
}
else {
s = q->next;
q->next = l1->next;
l1->next = q;
q = s;
}
} if (p) q = p; while (q)
{
s = q->next;
q->next = l1->next;
l1->next = q;
q = s;
}
} void inserthead(List &l)
{
l = new Node;
l ->next =nullptr; Node *s;
int data;
while (cin>>data && data != -)
{
s = new Node;
s ->data = data;
s ->next = l->next;
l ->next = s;
}
} List getCommon(List &l1,List &l2)
{
List l3 = new Node;
Node *p = l1->next;
Node *q = l2->next;
Node *t = l3;
while (p && q)
{
if (p->data == q->data)
{
Node* s = new Node;
s->data = p->data;
t ->next = s;
t = t->next;
p = p->next;
q = q->next;
}
else if (p->data > q->data)
q = q->next;
else p = p->next;
}
t->next = nullptr;
return l3;
} void UnionList(List &l1,List &l2)
{
Node *p = l1->next;
Node *q = l2->next;
Node *s = l1, *u; while (p && q)
{
if (p->data == q->data)
{
s->next = p;
s = p;
u = q;
q = q->next;
p = p->next;
free (u);
}
else if (p->data > q->data)
{
u = q;
q = q->next;
free (u);
}
else { u = p ; p = p->next ; free (u);}
}
while (p) { u = p; p = p->next; free (u);}
while (q) { u = q; q = q->next; free (u);}
s ->next = nullptr;
free (l2);
} bool isSubseq(List &l1,List &l2)
{
Node *p = l1->next;
Node *q = l2->next; Node *s = p;
while (p && q)
{
if (p->data == q->data)
{
p = p->next;
q = q->next;
}
else
{
s = s->next;
p = s;
q = l2->next;
}
}
if (!q) return true;
else return false;
} void crtDbCirList(DList &l)
{
l = new DNode;
DNode*p = l; int data;
while (cin>>data && data != -)
{
DNode* q = new DNode;
q ->data = data;
p ->next = q;
q ->prior = p;
p = p->next;
}
p ->next = l->next;
l ->next ->prior = p;
} bool isSymmetry(DList &dl)
{
DNode *p = dl->next;
DNode *q = dl->next->prior; while ( p != q && (p->next != q->prior))
{
//printf ("fuck");
if (p->data == q->data)
{
p = p->next;
q = q->prior;
}
else return false;
} return true;
} int main()
{
/*List s;
List s2;
creatList(s);
creatList(s2);
*/
//printList(s);
//printList(s2);
//reversePrint(s);
//removeMin(s);
//reverseList(s);
//selectSort(s);
//printList(s);
//cout<<length(s)<<endl<<length(s2)<<endl;
//cout<<Search_1st_common(s, s2)->data<<endl; /*List s2;
divideList(s, s2);
printList(s);
printList(s2);
*/ //removeCF(s);
//MergeList(s,s2);
//List s3 = getCommon(s, s2);
//printList(s3); //UnionList(s, s2);
//printList(s);
//cout<<isSubseq(s, s2)<<endl; DList dl;
crtDbCirList(dl);
DNode *q = dl->next;
DNode *f = dl->next->prior; cout<<q->data<<" "<<f->prior->data<<endl; if (isSymmetry(dl)) cout<<"success"<<endl;
else cout<<"fail"<<endl; return ;
}
上一篇:Linux -- Centos6 yum安装相关问题与处理


下一篇:CodeBlocks卸载后重装 编译c文件提示错误信息“No such file or directory”