链表操作

// ListOperate.cpp : 定义控制台应用程序的入口点。

//





#include "stdafx.h"

#include "ListData.h"





int _tmain(int argc, _TCHAR* argv[])

{


StudentDataSet StudentSet;


Student* head &＃61; StudentSet.CreateNode();


StudentSet.Print(head);






Student* rever &＃61; StudentSet.Reverse(head);


StudentSet.Print(rever);






Student* sort &＃61; StudentSet.BubbleSort(head);


StudentSet.Print(sort);













return 0;

}

#ifndef LISTDATA_H_
#define LISTDATA_H_
#include
#include
#include
#define  LEN sizeof(Student)


struct Student
{
long num;
char name[20];
float score;
Student *next;


};
class StudentDataSet
{
public:
StudentDataSet();
~StudentDataSet();
public:
Student* CreateNode();
Student* Reverse(Student *head);
void Print(Student *head);
Student* BubbleSort(Student *head);
private:
Student  stu;


};


#endif

#include "ListData.h"


int n &＃61; 0;


StudentDataSet::StudentDataSet()
{


}


StudentDataSet::~StudentDataSet()
{


}


Student* StudentDataSet::CreateNode()
{
Student *head;
Student *p1 ;
Student *p2 ;

p1 &＃61;(Student*) malloc(LEN);
p2 &＃61; p1;

head &＃61; NULL;
printf("Please input %d node -- num,name,score:",n  &＃43; 1);
scanf("%d,%s,%f",&(p1->num),p1->name,&(p1->score));
while (p1->num!&＃61;0)
{
n &＃43;&＃61; 1;
if (n &＃61;&＃61; 1)
{
head &＃61; p1;
p2->next &＃61; NULL;
}
else
{
p2->next &＃61; p1;


}
p2 &＃61; p1;
p1 &＃61; (Student *)malloc(LEN);
printf("Please input %d node -- num,name,score:",n &＃43; 1);
scanf("%ld,%s,%f",&(p1->num),p1->name,&(p1->score));
}
p2->next &＃61; NULL; 
free(p1); 
p1 &＃61; NULL; 


return head;

}


Student* StudentDataSet::Reverse( Student *head )
{


Student *p; 
Student *p1; /*存储返回结果*/
Student *p2; /*源结果节点一个一个取*/


p1 &＃61; NULL; /*开始颠倒时&＃xff0c;已颠倒的部分为空*/
p2 &＃61; head; /*p2指向链表的头节点*/
while (p2 !&＃61; NULL)
{
p &＃61; p2->next;
p2->next &＃61; p1;
p1 &＃61; p2;
p2 &＃61; p;
}
head &＃61; p1;
return head;
}


void StudentDataSet::Print( Student *head )
{


Student *p;
printf("\n Now , These %d records are:\n",n);
p &＃61; head;
if(head !&＃61; NULL) /*只要不是空链表&＃xff0c;就输出链表中所有节点*/
{
 printf("head is %o\n", head); /*输出头指针指向的地址*/
 do 
 { 
 
  printf(" %o %ld %s   %f   %o\n", p, p->num,p->name, p->score, p->next);
  p &＃61; p->next;
/*移到下一个节点*/
 } while (p !&＃61; NULL);
}
}


Student* StudentDataSet::BubbleSort( Student *head )
{
Student *endpt; /*控制循环比较*/
Student *p; /*临时指针变量*/
Student *p1; 
Student *p2; 
p1 &＃61; (Student *)malloc(LEN);
p1->next &＃61; head; /*注意理解&＃xff1a;我们增加一个节点&＃xff0c;放在第一个节点的前面&＃xff0c;主要是为了便于比较。因为第一个节点没有前驱&＃xff0c;我们不能交换地址。*/
head &＃61; p1; /*让head指向p1节点&＃xff0c;排序完成后&＃xff0c;我们再把p1节点释放掉*/
for (endpt&＃61;NULL; endpt!&＃61;head; endpt&＃61;p) /*结合第6点理解*/
{
for (p&＃61;p1&＃61;head; p1->next->next!&＃61;endpt; p1&＃61;p1->next)
{
if (p1->next->num > p1->next->next->num) /*如果前面的节点键值比后面节点的键值大&＃xff0c;则交换*/
{
p2 &＃61; p1->next->next; /*结合第1点理解*/
p1->next->next &＃61; p2->next; /*结合第2点理解*/
p2->next &＃61; p1->next; /*结合第3点理解*/
p1->next &＃61; p2; /*结合第4点理解*/
p &＃61; p1->next->next; /*结合第6点理解*/
}
}


}
p1 &＃61; head; /*把p1的信息去掉*/
head &＃61; head->next; /*让head指向排序后的第一个节点*/
free(p1); /*释放p1*/
p1 &＃61; NULL; /*p1置为NULL&＃xff0c;保证不产生“野指针”&＃xff0c;即地址不确定的指针变量*/
return head;




}