数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究实现排序双向链表的 C++ 程序
在数据结构中链接列表是一个线性的数据元素集合。列表的每个元素或节点都包含两个项目 - 数据和指向下一个节点的引用。最后一个节点引用 null。在链接列表中，进入点被称为列表头。
双向链接列表包含一组称为节点的顺序链接记录。每个节点包含三个字段：一个数据字段和两个链接字段; 引用节点字段序列中之前和之后的节点。
对于排序的双向链接列表，根据已排序数据字段值，链接列表将保持排序。
算法
Begin function createnode() to insert node in the list: it creates a newnode and inserts the number in the data field of the newnode. It checks whether the list is empty or not. If the list is empty put the node as first element and update head. Both prev and next pointers will be initialized with NULL. If list is not empty, then this newnode will be inserted into the existing linked list in such a way that ultimately the linked list will remain sorted. Prev and next pointers will be updated accordingly. End Begin function display_head() to display the list from the head: Initialize c=0. Initialize pointer variable with the head node address while (c <= i ) Print the node info Update pointer variable Increment c. End Begin function dispslay_tail() to display the list from the tail: Initialize m=0. Initialize pointer variable with the tail node address while (m <= i ) Print the node info Update pointer variable Increment m. End
示例代码
#include<iostream>
using namespace std;
struct nod {
int d;
nod *n, *p;
}
*p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL;
int c = 0;
void createnode(int n) {
np = new nod;
np->d = n;
np->n = NULL;
np->p = NULL;
if (c == 0) {
tail = np;
head = np;
p = head;
p->n = head;
p->p = head;
c++;
} else if (c == 1) {
p = head;
r = p;
if (np->d < p->d) {
np->n = p;
p->p = np;
head = np;
p->n = np;
np->p = p;
tail = p;
} else if (np->d > p->d) {
p->n = np;
np->p = p;
np->n= head;
p->p = np;
}
c++;
} else {
p = head;
r = p;
if (np->d < p->d) {
np->n = p;
p->p = np;
head = np;
do {
p = p->n;
}
while (p->n != r);
tail = p;
p->n = np;
np->p = p;
} else if (np->d > p->d) {
while (p->n != head && np->d > p->d) {
r = p;
p = p->n;
if (p->n == head && (p->d < np->d)) {
p->n = np;
np->p = p;
np->n = head;
tail = np;
head->p = np;
break;
} else if (np->d< p->d) {
r->n= np;
np->p = r;
np->n= p;
p->p= np;
if (p->n != head) {
do {
p = p->n;
}
while (p->n != head);
}
tail = p;
break;
}
}
}
}
}
void display_head(int i) {
nod *t = head;
int c = 0;
while (c <= i) {
cout<<t->d<<"\t";
t = t->n;
c++;
}
cout<<endl;
}
void display_tail(int i) {
nod *t = tail;
int m = 0;
while (m <= i) {
cout<<t->d<<"\t";
t = t->p;
m++;
}
cout<<endl;
}
int main() {
int i = 0, n, a, ch;
cout<<"enter the no of nodes\n";
cin>>n;
while (i < n) {
cout<<"\nenter value of node\n";
cin>>a;
createnode(a);
i++;
}
cout<<"\nsorting Doubly Linked List head first\n";
display_head(n);
cout<<"\nsorting Doubly Linked List tail first\n";
display_tail(n);
}输出
enter the no of nodes 5 enter value of node 7 enter value of node 4 enter value of node 6 enter value of node 2 enter value of node 1 sorting Doubly Linked List head first 1 2 4 6 7 1 sorting Doubly Linked List tail first 7 6 4 2 1 7
更新于：30-Jul-2019
1K+ 次浏览
广告