脚本宝典收集整理的这篇文章主要介绍了数据结构 : 链表,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
双链表操作(不带头结点)
struct Node {
int val;
struct Node* prior, *next;
Node(int v) : val(v) { prior = NULL; next = NULL; }
};
构建双链表
struct Node* build() {
struct Node* head = NULL;
struct Node* ptr = NULL;
int val;
while (cin >> val) {
if (head == NULL) {
head = new Node(val);
head->next = head;
ptr = head;
}
else {
ptr->next = new Node(val);
ptr->next->prior = ptr;
ptr = ptr->next;
}
}
if (head != NULL) {
head->prior = ptr;
ptr->next = head;
}
return head;
}
遍历
//升序遍历
void ascendingTraverse(struct Node* head) {
if (head == NULL)
return;
auto ptr = head;
do {
cout << ptr->val;
ptr = ptr->next;
if (ptr == head) {
cout << endl;
}
else {
cout << " ";
}
} while (ptr != head);
}
// 逆序遍历
void descendingTraverse(struct Node* head) {
if (head == NULL)
return;
auto ptr = head->prior;
do {
cout << ptr->val;
ptr = ptr->prior;
if (ptr == head->prior) {
cout << endl;
}
else {
cout << " ";
}
} while (ptr != head->prior);
}
插入排序
重点
/*移动结点内的元素,而不是结点本身*/
/*注意head会发生变化*/
void sort(struct Node*& head) {
if (!head)
return;
for (auto ptr = head->next; ptr != head; ptr = ptr->next) {
int tmp = ptr->val;
struct Node* pri;
/* 注意该条件:pri != head->prior */
for (pri = ptr->prior; pri != head->prior && pri->val > tmp ; pri = pri->prior){
pri->next->val = pri->val;
}
pri->next->val = tmp;
}
int minNum = head->val;
auto newHead = head;
for (auto ptr = head->next; ptr != head; ptr = ptr->next) {
if (minNum > ptr->val) {
newHead = ptr;
minNum = ptr->val;
}
}
head = newHead;
}
删除
void destroy(struct Node* head) {
if (!head)
return;
for (auto ptr = head->next; ptr != head; ) {
auto tmp = ptr->next;
delete ptr;
ptr = tmp;
}
delete head;
}
以上是脚本宝典为你收集整理的数据结构 : 链表全部内容,希望文章能够帮你解决数据结构 : 链表所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。