C ++程序实现循环排序的单链接列表
在数据结构中，“链表”是数据元素的线性集合。列表中的每个元素或节点都包含两项-数据和对下一个节点的引用。最后一个节点具有对null的引用。进入链接列表的入口点称为列表的开头。
列表中的每个节点都在一个链接列表中存储内容以及指向列表中下一个节点的指针或引用。单链列表不存储任何指向上一个节点的指针或引用。
由于它是一个排序的单链表，因此链表中的数据项将始终保持排序状态。
这是一个实现循环排序的单链接列表的C++程序
算法
Begin
function createnode() to insert node in the list:
It checks whether the list is empty or not. If the list is empty put the node as first element and update head.
If list is not empty,
It creates a newnode and inserts the number in the data field of the newnode.
Now the newnode will be inserted in such a way that linked list will remain sorted.
If it gets inserted at the last, then the newnode points to the head.
If the newnode inserted at the first, then the linked list starts from there.
End
Begin
function display() to print the list content having n number of nodes:
Initialize c = 0.
Initialize pointer variable with the start address
while (c <= n)
Print the node info
Update pointer variable
Increment c.
End范例程式码
#include<iostream>
using namespace std;
struct nod {
int d;
nod *n;
}
*p = NULL, *head = NULL, *q = NULL, *np = NULL;
int c = 0;
void createnode(int n) {
np = new nod;
np->d = n;
np->n = NULL;
if (c == 0) {
head = np;
p = head;
p->n = head;
c++;
} else if (c == 1) {
p = head;
q = p;
if (np->d < p->d) {
np->n = p;
head = np;
p->n = np;
} else if (np->d > p->d) {
p->n = np;
np->n = head;
}
c++;
} else {
p = head;
q = p;
if (np->d < p->d) {
np->n = p;
head = np;
do {
p = p->n;
}
while (p->n != q);
p->n = head;
} else if (np->d > p->d) {
while (p->n != head && q->d < np->d) {
q = p;
p = p->n;
if (p->n == head) {
p->n = np;
np->n = head;
} else if (np->d< p->d) {
q->n = np;
np->n = p;
break;
}
}
}
}
}
void display(int i) {
nod *t = head;
int c = 0;
while (c <= i ) {
cout<<t->d<<"\t";
t = t->n;
c++;
}
}
int main() {
int i = 0, n, a;
cout<<"enter the no of nodes\n";
cin>>n;
while (i < n) {
cout<<"\nenter value of node\n";
cin>>a;
createnode(a);
i++;
}
cout<<"sorted circularly singly link list"<<endl;
display(n);
}输出结果
enter the no of nodes 5 enter value of node 6 enter value of node 4 enter value of node 7 enter value of node 3 enter value of node 2 sorted circularly singly link list 2 3 4 6 7 2