Question

c++中对链表进行排序，但不改变原始链表

链表中元素为类，根据类中某一成员数据进行排序

Answer 1

#include <stdio.h>

/*
* nodeEntry : 节点数据类型
* nodeADT : 节点结构
* linkADT : 链表结构
*/

typedef int nodeEntry;

typedef struct nodeCDT {
nodeEntry entry;
struct nodeCDT *next;
}*nodeADT;

typedef struct linkCDT {
nodeADT head;
}*linkADT;

/*
* InitLink : 初始化链表
* CreateNode : 创建节点
* AppendLink : 添加数据
*/

void InitLink(linkADT *link) {
*link=(linkADT)malloc(sizeof*(*link));
(*link)->head=0;
}

nodeADT CreateNode(nodeEntry entry) {
nodeADT p=(nodeADT)malloc(sizeof*p);
p->entry=entry,p->next=0;
return p;
}

void AppendLink(linkADT *link,nodeEntry entry) {
nodeADT newNode=CreateNode(entry),p;
if (!*link) InitLink(link);
if (!(*link)->head) (*link)->head=newNode;
else {
for (p=(*link)->head;p->next;p=p->next);
p->next=newNode;
}
}

/*
* SortLink : 排序链表
* -------------------
* 通过移动每个节点的指针来完成排序
*/

void SortLink(linkADT link) {
nodeADT pHead,pRear,p,tp;
if (!link) return;
for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {
for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)
if (pHead->entry>=p->entry)
tp->next=p->next,p->next=pHead,pHead=p,p=tp;
if (!pRear) link->head=pHead;
else pRear->next=pHead;
pRear=pHead;
}
}

/*
* PrintLink : 打印链表
*/

void PrintLink(linkADT link) {
nodeADT p=link->head;
for (;p;printf("%3d",p->entry),p=p->next);
printf("\n");
}

/* 测试 */
void main() {
linkADT link=0;
int a[10]={27,30,42,19,25,28,17,32,14,23},i;

for (i=0;i<10;AppendLink(&link,*(a+i++)));
PrintLink(link);
SortLink(link);
PrintLink(link);

getchar();
}

Answer 2

　　链表中元素为类,根据类中某一成员数据进行排序
　　C++是在C语言的基础上开发的一种面向对象编程语言，应用广泛。C++支持多种编程范式 －－面向对象编程、泛型编程和过程化编程。最新正式标准C++于2014年8月18日公布。 其编程领域众广，常用于系统开发，引擎开发等应用领域，是至今为止最受广大程序员受用的最强大编程语言之一,支持类：类、封装、重载等特性。