資料結構
網路
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+ 次瀏覽
廣告