数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程序设计
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学C++ 程序来实现已分类循环双向链表
在数据结构中，链表是数据元素的线性集合。列表的每个元素或节点包括两个项目 - 数据和对下一个节点的引用。最后一个节点引用空。在链表中，进入点称为列表的头。
在循环双向链表中，两个连续的元素由先前和下一个指针链接或连接，并且最后一个节点通过下一个指针指向第一个节点，并且第一个节点还通过前一个指针指向最后一个节点。
在分类的循环双向链表中，节点数据字段中的所有数据值都将保持分类。在这样的链表中插入新节点时将处理此事项。
算法
Begin Create a class circulardoublylist within which we have following functions: nod *create_node(int) = To memory allocated for node dynamically. insert_begin() = To Insert elements at beginning of the list. If the list is empty, then insert the node and set next and previous pointer as NULL. If the list is not empty, insert the data and set next and previous pointer and update them. insert_end() = To Insert elements at end of the list. If the list is empty create a node as circular doubly list. Find last node. Create node dynamically. Start going to be the next of new node. Make new node as previous node. Make last previous of new node Make new node next of old last insert_pos() = To insert elements at a specified position of the list. insert the data. Enter the position at which element to be inserted. If the list is empty insert node at first. If list is not empty find node having position and next node. Insert the node between them. delete_pos() = To delete elements from specified position of the list. if list is empty then return. Enter the position from which node need to be deleted. If list has one node delete it and update next and prev pointers. If list has more than one node node then delete the node at particular position and update next and prev pointer. sort() = To sort elements in the list. if the list is empty return. Sort the elements in the list. display() = To display the list. reverse() = To reverse the list. End
示例代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct nod {
int info;
struct nod *n;
struct nod *p;
}*start, *last;
int count = 0;
class circulardoublylist {
public:
nod *create_node(int);
void insert_begin();
void insert_end();
void insert_pos();
void delete_pos();
void sort();
void display();
void reverse();
circulardoublylist() {
start = NULL;
last = NULL;
}
};
int main() {
int c;
circulardoublylist cdl;
while (1) {
cout<<"1.Insert at Beginning"<<endl;
cout<<"2.Insert at End"<<endl;
cout<<"3.Insert at Position"<<endl;
cout<<"4.Delete at Position"<<endl;
cout<<"5.sort the list"<<endl;
cout<<"6.Display List"<<endl;
cout<<"7.Reverse List"<<endl;
cout<<"8.Exit"<<endl;
cout<<"Enter your choice : ";
cin>>c;
switch(c) {
case 1:
cdl.insert_begin();
break;
case 2:
cdl.insert_end();
break;
case 3:
cdl.insert_pos();
break;
case 4:
cdl.delete_pos();
break;
case 5:
cdl.sort();
break;
case 6:
cdl.display();
break;
case 7:
cdl.reverse();
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}
nod* circulardoublylist::create_node(int v) {
count++;
struct nod *t;
t = new(struct nod);
t->info = v;
t->n = NULL;
t->p = NULL;
return t;
}
void circulardoublylist::insert_begin() {
int v;
cout<<endl<<"Enter the element to be inserted: ";
cin>>v;
struct nod *t;
t = create_node(v);
if (start == last && start == NULL) {
cout<<"Element inserted in empty list"<<endl;
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
t->n = start;
start->p = t;
start = t;
start->p = last;
last->n = start;
cout<<"Element inserted"<<endl;
}
}
void circulardoublylist::insert_end() {
int v;
cout<<endl<<"Enter the element to be inserted: ";
cin>>v;
struct nod *t;
t = create_node(v);
if (start == last && start == NULL) {
cout<<"Element inserted in empty list"<<endl;
start = last = t;
start->n= last->n = NULL;
start->p = last->p= NULL;
} else {
last->n= t;
t->p= last;
last = t;
start->p = last;
last->n= start;
}
}
void circulardoublylist::insert_pos() {
int v, pos, i;
cout<<endl<<"Enter the element to be inserted: ";
cin>>v;
cout<<endl<<"Enter the position of element inserted: ";
cin>>pos;
struct nod *t, *s, *ptr;
t = create_node(v);
if (start == last && start == NULL) {
if (pos == 1) {
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
cout<<"Position out of range"<<endl;
count--;
return;
}
} else {
if (count < pos) {
cout<<"Position out of range"<<endl;
count--;
return;
}
s = start;
for (i = 1;i <= count;i++) {
ptr = s;
s = s->n;
if (i == pos - 1) {
ptr->n = t;
t->p= ptr;
t->n= s;
s->p = t;
cout<<"Element inserted"<<endl;
break;
}
}
}
}
void circulardoublylist::delete_pos() {
int pos, i;
nod *ptr, *s;
if (start == last && start == NULL) {
cout<<"List is empty, nothing to delete"<<endl;
return;
}
cout<<endl<<"Enter the position of element to be deleted: ";
cin>>pos;
if (count < pos) {
cout<<"Position out of range"<<endl;
return;
}
s = start;
if(pos == 1) {
count--;
last->n = s->n;
s->n->p = last;
start = s->n;
free(s);
cout<<"Element Deleted"<<endl;
return;
}
for (i = 0;i < pos - 1;i++ ) {
s = s->n;
ptr = s->p;
}
ptr->n = s->n;
s->n->p = ptr;
if (pos == count) {
last = ptr;
}
count--;
free(s);
cout<<"Element Deleted"<<endl;
}
void circulardoublylist::sort() {
struct nod *t, *s;
int v, i;
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to sort"<<endl;
return;
}
s = start;
for (i = 0;i < count;i++) {
t= s->n;
while (t != start) {
if (s->info > t->info) {
v = s->info;
s->info = t->info;
t->info = v;
}
t = t->n;
}
s = s->n;
}
cout<<"List sorted"<<endl;
}
void circulardoublylist::display() {
int i;
struct nod *s;
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to display"<<endl;
return;
}
s = start;
for (i = 0;i < count-1;i++) {
cout<<s->info<<"<->";
s = s->n;
}
cout<<s->info<<endl;
}
void circulardoublylist::reverse() {
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to reverse"<<endl;
return;
}
struct nod *p1, *p2;
p1 = start;
p2 = p1->n;
p1->n = NULL;
p1->p= p2;
while (p2 != start) {
p2->p = p2->n;
p2->n = p1;
p1 = p2;
p2 = p2->p;
}
last = start;
start = p1;
cout<<"List Reversed"<<endl;
}输出
1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 1 Enter the element to be inserted: 7 Element inserted in empty list 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 1 Enter the element to be inserted: 6 Element inserted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 2 Enter the element to be inserted: 4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 2 Enter the element to be inserted: 5 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 6 6<->7<->4<->5 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 5 List sorted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 4 Enter the position of element to be deleted: 3 Element Deleted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 6 4<->5<->7 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 7 List Reversed 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 6 7<->5<->4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 8
更新于: 30-Jul-2019
676 次观看
广告