当然可以,任何一种算法都是为了解决问题来设计的,只要你的算法可以达到排序单链表的目的,就可以使用。你可以使用类似冒泡法排序的方法,每次是一个最大的或者最小的未排序数沉底,如果你只交换节点的数据域,那么可以通过交换来进行沉底 *** 作。
给你一个我写的完整实例 , 你自己分析吧 ,希望对你有帮助
#include <stdioh>
#include <stringh>
#define null 0
typedef struct node{
char data;//结点的数据域,为一个字符串
struct node next;//结点的指针域
}linkstrnode;//定义单链表结点结构
typedef linkstrnode linkstring;
main(){//建立数据域为字符串类型,且结点无重复的单链表。对单链表做删除结点 *** 作
linkstring head;
char t;
printf("\nplease input the node of the linklist:");
printf("\nnodes data is strings,and end of #\n");
creatlinkstr(&head);//建立单链表
printf("\nthe source linklist is :\n");
printing(head);//输出单链表
printf("\nplease input search string:");
gets(t);//输入要删除的字符串
deletet(&head,t);//在单链表head中找到并删除值与t相同的结点
printf("\nthe final linklist is:\n");
printing(head);//输出做了删除 *** 作后的单链表
}
creatlinkstr(linkstring head){
//建立单链表
char t;
linkstrnode p;
head=(linkstrnode )malloc(sizeof(linkstrnode));
//建立一个只含头结点的空链表,头指针为head
head->next=null;
printf("\nplease input the node data(string),end of #");
gets(t);//输入一个字符串t
while (strcmp(t,"#")!=0){//当t的值不为“#”时,做以下 *** 作
p=head;//在建好的单链表中,以p为扫描指针,从头开始查找有无数据域与t相同的结点
while ((p->next)&&(strcmp(t,p->next->data)))
p=p->next;
if (p->next)//如果存在数据域与t相同的结点,则输出存在信息
printf("\nstring %s existed",t);
else{//若不存在数据域与t相同结点,则做以下 *** 作
p->next=(linkstrnode )malloc(sizeof(linkstrnode));
//在单链表表尾申请一个新结点
p=p->next;//p指针指向新的表尾结点
strcpy(p->data,t);//将t的值复制到p结点的数据域中
p->next=null;//将单链表的表尾结点的next指针置为空
}
printf("\nplease input the node data(string),end of #");
gets(t);//输入下一个字符串
}//end of while
}//end of creatlinkstr
printing(linkstring head){
//输出head单链表
linkstrnode p;
p=head->next;
while(p){
puts(p->data);//输出结点的数据——字符串
p=p->next;
}
}//end of printing
deletet(linkstring head,char t){
//若head单链表中有数据为t的结点,删除之
linkstrnode p,s;
p=head;
while ((p->next)&&(strcmp(p->next->data,t)))
//以p为扫描指针对head链表进行查找数据域值为t结点,
//为了能方便删除 *** 作,p指向待查结点的前趋
p=p->next;
if (p->next){//若查找到有,则做删除 *** 作
s=p->next;
p->next=s->next;
free(s);
printf("\ndelete successful!");
}
else//若head链表中没有数据域的值为t的结点,则输出删除失败的信息
printf("\ndelete failure!");
}
//-----------------ListNodeh-----------------------
#ifndef LISTNODE_H
#define LISTNODE_H
#include <iostream>
using namespace std;
template <class Type> class List;
template <class Type>
class ListNode
{
friend class List<Type>;
private:
Type data;
ListNode<Type> link;
public:
ListNode ();
ListNode (const Type& item);
};
#endif
template <class Type>
ListNode<Type>::ListNode() : link(NULL)
{}
template <class Type>
ListNode<Type>::ListNode(const Type &item) : data(item), link(NULL)
{}
//---------------------Listh------------------------
#ifndef LIST_H
#define LIST_H
#include "ListNodeh"
template <class Type>
class List
{
private:
ListNode<Type> first;
ListNode<Type> last;
public:
List(const Type &value = NULL);
~List();
void MakeEmpty();
int Length() const;
ListNode<Type> Find(Type value);
ListNode<Type> Find(int index);
bool Insert(Type value, int index);
bool Remove(int index);
Type Get(int index);
};
#endif
// 构造函数
template <class Type>
List<Type>::List(const Type &value)
{
first = last = new ListNode<Type>(value);
}
// 析构函数
template <class Type>
List<Type>::~List()
{
MakeEmpty();
delete first;
}
// 链表清空
template <class Type>
void List<Type>::MakeEmpty()
{
ListNode<Type> p;
while (first->link != NULL)
{
p = first->link;
first->link = p->link;
delete p;
}
last = first;
}
// 计算链表长度
template <class Type>
int List<Type>::Length() const
{
ListNode<Type> p = first->link;
int count = 0;
while (p != NULL)
{
p = p->link;
count++;
}
return count;
}
// 按链表中所存储的信息查找
template <class Type>
ListNode<Type> List<Type>::Find(Type value)
{
ListNode<Type> p = first->link;
while (p != NULL && p->data != value)
{
p = p->link;
}
return p;
}
// 按下标查找
template <class Type>
ListNode<Type> List<Type>::Find(int index)
{
if (index < -1)
return NULL;
if (index == -1)
return first;
ListNode<Type> p = first->link;
int i = 0;
while (p != NULL && i < index)
{
p = p->link;
i++;
}
return p;
}
// 在指定
template <class Type>
bool List<Type>::Insert(Type value, int index)
{
ListNode<Type> p = Find(index - 1);
if (p == NULL)
{
return false;
}
ListNode<Type> newnode = new ListNode<Type>(value);
newnode->link = p->link;
if (p->link == NULL)
last = newnode;
p->link = newnode;
return true;
}
// 从链表中删除一个元素,删除index后边的节点
template <class Type>
bool List<Type>::Remove(int index)
{
ListNode<Type> p = Find(index-1);
ListNode<Type> q;
// 如果p为空,或者p的下一个节点为空,没有办法删除
if (p == NULL || p->link == NULL)
return false;
q = p;
p = p->link;
q->link = p->link;
delete p;
if (q->link == NULL)
last = q;
return true;
}
// 得到指定位置的节点data信息
template <class Type>
Type List<Type>::Get(int index)
{
ListNode<Type> p = Find(index);
if (p == NULL || p == first)
return NULL;
else
return p->data;
}
头文件:LinkListh
typedef struct LNode {
int data;
struct LNode next;
}LNode, pLinkList;
class LinkList {
private:
pLinkList m_pList;
int m_listLength;
public:
LinkList();
~LinkList();
bool InitList ();
bool DestroyList ();
bool ClearList();
bool IsEmpty ();
int GetLength ();
bool GetNode(int position, LNode node);
int LocateElem(int elem);
bool SetNodeData(int position, int newData);
bool GetNodeData(int position, int &data);
bool InsertNode(int beforeWhich, int data);
bool DeleteNode(int position);
};
Cpp文件:LinkListcpp
#include <iostreamh>
#include "LinkListh"
LinkList::LinkList() {
m_pList = NULL;
m_listLength = 0;
InitList();
}
LinkList::~LinkList() {
if (!DestroyList()) {
DestroyList();
}
}
//初始化,分配一个头节点。
bool LinkList::InitList() {
if (!(m_pList = new LNode)) {
return false;
}
m_pList->next = NULL;
return true;
}
//销毁链表。
bool LinkList::DestroyList() {
if (!ClearList()) {
return false;
}
delete m_pList;
return true;
}
//判断链表是否为空。若为空,返回true,否则返回false。
bool LinkList::IsEmpty() {
if (m_pList->next == NULL) {
return true;
}
return false;
}
//返回链表的中当前节点数。
int LinkList::GetLength() {
return m_listLength;
}
//将链表清空,释放当前所有节点。
bool LinkList::ClearList() {
if (m_pList == NULL) {
return false;
}
LNode pTemp = NULL;
while (m_pList->next != NULL) {
pTemp = m_pList->next;
m_pList->next = pTemp->next;
delete pTemp;
}
m_listLength = 0;
return true;
}
//将position指定的节点内的数据设置为newData。
//第一个有效节点的position为1。
bool LinkList::SetNodeData(int position, int newData) {
LNode pTemp = NULL;
if (!(GetNode(position, &pTemp))) {
return false;
}
pTemp->data = newData;
return true;
}
//得到指定位置节点的数据。
//节点索引从1到listLength。
bool LinkList::GetNodeData(int position, int &data) {
LNode pTemp = NULL;
if (!(GetNode(position, &pTemp))) {
return false;
}
data = pTemp->data;
return true;
}
//在链表中插入一个节点。
//插入的位置由beforeWhich指定,新节点插入在beforeWhich之前。
//beforeWhich的取值在1到ListLength+1之间。
bool LinkList::InsertNode(int beforeWhich, int data) {
LNode pTemp = NULL;
if (beforeWhich < 1 || beforeWhich > (m_listLength + 1)) {
return false;
}
if (!(GetNode(beforeWhich - 1, &pTemp))) {
return false;
}
LNode newNode = new LNode;
newNode->data = data;
newNode->next = pTemp->next;
pTemp->next = newNode;
m_listLength++;
return true;
}
//删除一个指定的节点。
//节点位置由position指定。
//positon的值从1到listLength。
//若链表为空或指定的节点不存在则返回false。
bool LinkList::DeleteNode(int position) {
if (position < 1 || position > m_listLength) {
return false;
}
LNode pTemp = NULL;
if (!(GetNode(position - 1, &pTemp))) {
return false;
}
LNode pDel = NULL;
pDel = pTemp->next;
pTemp->next = pDel->next;
delete pDel;
m_listLength--;
return true;
}
//得到指定位置节点的指针。
bool LinkList::GetNode(int position, LNode node) {
LNode pTemp = NULL;
int curPos = -1;
pTemp = m_pList;
while (pTemp != NULL) {
curPos++;
if (curPos == position)
break;
pTemp = pTemp->next;
}
if (curPos != position) {
return false;
}
node = pTemp;
return true;
}
//定位与指定数据相等的数据节点。
//如果在当前链表中已经存在该数据则返回该数据节点的索引号。
//若不存在这样的节点则返回0。
//节点索引从0开始到listLength。
int LinkList::LocateElem(int elem) {
LNode pTemp = NULL;
int curIndex = 1;
pTemp = m_pList->next;
while ((pTemp != NULL) && (pTemp->data != elem)) {
pTemp = pTemp->next;
curIndex++;
}
if (pTemp == NULL) {
return 0;
}
return curIndex;
}
/
int main(){
LinkList l;
lInsertNode(1, 10);
lInsertNode(2, 20);
lInsertNode(3, 30);
lInsertNode(4, 40);
cout << lGetLength() << endl;
int dataTemp = 0;
for (int i = 1; i <= lGetLength(); i++) {
lGetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
if (lSetNodeData(3, 50)) {
cout <<"DONE\n";
} else {
cout << "Failed\n";
}
for (i = 1; i <= lGetLength(); i++) {
lGetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
if (lDeleteNode(4)) {
cout <<"DONE\n";
} else {
cout << "Failed\n";
}
for (i = 1; i <= lGetLength(); i++) {
lGetNodeData(i, dataTemp);
cout << dataTemp << endl;
}
cout << lLocateElem(50) << endl;
return 0;
}
/
而顺序表可以直接取相应元素,所以顺序表效率更高;只有第二个,第一个元素后面插入新的元素,单链表不用花费时间查找插入的位置了,只需要修改指针即可,而顺序表要移动从第2个开始的所有元素,所以第二个是正确答案。
先添加;后删除!
node s;
s = (node)malloc(sizeof(node));
s->data = p->data;
/以下是把s往p->next后面插入/
s->next = p->next->next;
s->next->pre = s;//右边插好
s->pre = p->next;
s->pre->next = s;//左边接好
/以下是删除p结点的代码/
p->pre->next = p->next;
p->next->pre = p->pre;
你没说清楚,从这个程序来看应该是把两个已经按升序排列的链表合并,使其依然升序排列。
而且这个程序也不很好啊,试图包括空链的情况了,但是逻辑上有点问题,我修改了一下,你看看是不是清晰了许多。
struct student insert(struct student ah,struct student bh)
{
struct student pa1,pa2,pb1,pb2;
if(ah==NULL)//链表a为空
ah=bh;
else
{
pa2=pa1=ah;
pb2=pb1=bh;
while(pb1!=NULL)//链表b未结束
{
while((pb1->num>pa1->num)&&(pa1->next!=NULL) ) //为pb1指向的节点在链表a中找到合适位置,pa2指向pa1的前一节点
{
pa2=pa1;
pa1=pa1->next;
}
if(pb1->num<=pa1->num) //找到大于pb1的节点pa1,将pb1插到pa1前pa2后
{
pa2->next=pb1;
pb1=pb1->next; //下一次将链表b的下一结点插入链表a
pb2->next=pa1;
pa2=pb2; //pb2的作用是在交换值的时候临时保存变量
pb2=pb1;
}
else //说明pa1->next==NULL,即链表a最后都没有找到大于pb1的,直接把链表b的后面接上即可
{
pa1->next=pb1;
break;
}
}
}
return ah;
}
改好了,去试试吧
list(int a[],int n ) //一维数组a[] 和其中数据长度n
{
node s;
length=n;
first=new node; //先要申请地址,不然不能 *** 作指针变量
first->data=n; //头节点存储数据长度n
rear=first; //尾结点赋值
for(int i=0;i<n;i++) //尾插法建立链表
{
s=new node;
s->data=a[i];
rear->next=s;
s->perior=rear;
rear=s;
}
rear->next=first;
first->perior=rear;
}
~list() //析构函数
{
node p=first;
while( p != rear ) //从头到尾进行释放,因为是循环链表
{
node q=p;
p=p->next;
delete q;
}
}
以上就是关于单链表排序的循环语句中可以只交换结点的数据域吗全部的内容,包括:单链表排序的循环语句中可以只交换结点的数据域吗、c语言 编程 ,链表 改错、交换第一个和第二个元素顺序表和链表哪个效率更高等相关内容解答,如果想了解更多相关内容,可以关注我们,你们的支持是我们更新的动力!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)