typedef struct node{
int data
struct node *next
}node
node *create()
{
node *head,*p,*q
int i=0
int x
head=(node *)malloc(sizeof(node))
while(1)
{
printf("please input the node:")
scanf("%d",&x)
if(x==0) {break}
p=(node *)malloc(sizeof(node))
p->data=x
if(++i==1)
{
head->next=p
}
else
{
q->next=p
}
q=p
}
q->next=NULL
return head
}
void print(node *head)
{
node *p
int index=0
if(head->next==NULL)
{
printf("Link is empty!\n")
exit(0)
}
p=head->next
while(p!=NULL)
{
printf("the %d node is %d\n",++index,p->data)
p=p->next
}
}
int length(node *head)
{
int len=0
node *p
p=head->next
while(p)
{
len++
p=p->next
}
return len
}
node *search(node *head,int pos)
{
node *p
int len=length(head)
p=head->next
if(pos<0)
{
printf("incorrect position!\n")
return NULL
}
else if(pos>len)
{
printf("incorrect position!\n")
return NULL
}
else if(pos==0)
{
return head
}
if(p==NULL)
{
printf("the link is empty!\n")
return NULL
}
while (--pos)
{
p=p->next
}
return p
}
node *delete(node *head,int pos)
{
node *p,*q
int len=length(head)
p=head->next
if(pos<0)
{
printf("incorrect position!\n")
return NULL
}
else if(pos>len)
{
printf("incorrect position!\n")
return NULL
}
if(p==NULL)
{
printf("link empty!\n")
return NULL
}
p=search(head,pos-1)
if(p!=NULL&&p->next!=NULL)
{
q=p->next
p->next=q->next
free(q)
}
return head
}
node *insert(node *head,int pos,int x)
{
node *p,*q=NULL
q=(node *)malloc(sizeof(node))
q->data=x
if(pos==0)
{
head->next=q
return head
}
p=search(head,pos)
if(p!=NULL)
{
q->next=p->next
p->next=q
}
return head
}
#include<fstream.h>#include<process.h>
#include<iomanip.h>
#include<string.h>
const char*file_name="stuinfo.txt"
class Student
{
public:
Student()
~Student()
void add_info()//添加学生信息
void del_info()//删除学生信息
void search_info_name()//通过学生名字来查找信息
void search_info_Snum()//通过学号来查找信息
void out_all_info()//输出所有学生的信息
void creat_file()//创建文件,学生的信息保存在文件里,即使退出了程序，下次运行还可以找到学生的信息
int get_info()//从文件中获取学生的信息
int search_file()//判断是否存在一个保存学生信息的文件
protected:
char name[10]//学生名字最长为10个字符
long Snum//学号是长整行
int Chinese,English,Math,Computer//语文 英语 数学 计算机 共四门课
Student *head,*next//创建链表使用的指针
}
/**
*构造函数,用来创建对象同时初始化相关指针变量
*/
Student::Student()
{
head=NULL
next=NULL
}
/**
*判断是否存在一个保存学生信息的文件
*/
int Student::search_file()
{
ifstream input_file
input_file.open(file_name)
if(!input_file)//不存在文件
return 0
else
input_file.close()//存在文件
return 1
}
/**
*从文件中获取学生的信息
*/
int Student::get_info()
{
Student *temp,*loop
temp=new Student()
loop=new Student()
ifstream out_file
out_file.open(file_name,ios::beg)//打开文件,设置读指针在文件的开头
if(!out_file)//打开文件失败
{
cout<<"Fail to get information from the file!"
cout<<"\nPress any key to exit."
cin.get()
exit(0)//结束程序
}
while(!out_file.eof())//循环读文件,直到读到了文件的末尾
{
//文件的结构是:文件的一行就是一个学生的信息, 从左到右是:学号 姓名 语文 英语 数学 计算机
//这些信息可以在本程序提供的功能生成并保存到文件里
out_file>>(temp->Snum)>>(temp->name)>>(temp->Chinese)>>(temp->English)>>(temp->Math)>>(temp->Computer)
if(temp->Snum==0) break
//使用链表把学生的信息保存到内存中
if(head==NULL) head=temp
else
{
if(head->Snum>temp->Snum)
{
temp->next=head
head=temp
}
else
{
loop=head
while(loop->next!=NULL)
{
if(loop->next->Snum>temp->Snum)
{
temp->next=loop->next
loop->next=temp
break
}
loop=loop->next
}
if(loop->next==NULL)
{
loop->next=temp
temp->next=NULL
}
}
}
temp=new Student
loop=new Student
}
out_file.close()//关闭文件
if(head==NULL) return 0
else return 1
}
/**
*创建文件,可以增加学生的信息
*/
void Student::creat_file()
{
Student *temp,*loop
temp=new Student
loop=new Student
ofstream creat_file
creat_file.open(file_name,ios::beg)
if(!creat_file)
{
cout<<"Fail to creat stdent information file!"
cout<<"\nPress any key to exit."
cin.get()
exit(0)
}
cout<<"-----------------------------------------------------------"<<endl
cout<<"Now creat file of student information."<<endl
cout<<"Input the number of the student (0 to end):"
cin>>temp->Snum//输入学号
while(temp->Snum!=0)//学号不为0
{
cout<<"Input the name of the student:"
cin>>temp->name//姓名
cout<<"Input the score of Chinese:"
cin>>temp->Chinese//语文
cout<<"Input the score of English:"
cin>>temp->English//英语
cout<<"Input the score of Math:"
cin>>temp->Math//数学
cout<<"Input the score of Computer Science:"
cin>>temp->Computer//计算机
creat_file<<temp->Snum<<" "<<temp->name<<" "<<temp->Chinese<<" "<<temp->English<<" "<<temp->Math<<" "<<temp->Computer<<endl
temp=new Student
loop=new Student
cout<<"\n\nInput the number of the student (0 to end):"
cin>>temp->Snum//输入学号
}
creat_file<<0
creat_file.close()
}
/**
*输出所有学生的信息
*/
void Student::out_all_info()
{
Student*temp
temp=new Student
cout<<"-----------------------------------------------------------"<<endl
cout<<"The flowing is the information of the students."<<endl<<endl
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl
temp=head
while(temp!=NULL)//循环读链表,输出所有学生的信息
{
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl
temp=temp->next
}
}
/**
*通过姓名查找信息
*/
void Student::search_info_name()
{
Student *temp
char name[10]
temp=new Student
cout<<"-----------------------------------------------------------"<<endl
cout<<"Input the name of the student you want to search:"
cin>>name//输入姓名
temp=head
while(temp!=NULL&&strcmp(temp->name,name)!=0)//在链表中逐个的比较姓名
temp=temp->next
if(temp==NULL)//没有找到信息,就是说找不到需要查找姓名的学生的信息
cout<<"Sorry,no such student of the name you input!"<<endl
else//输出学生的信息
{
cout<<"The flowing is the information of the student "<<name<<endl
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl
}
}
/**
*通过学号查找信息
*/
void Student::search_info_Snum()
{
Student*temp
long num
temp=new Student
cout<<"---------------------------------------------------------"<<endl
cout<<"Input the number of the student you want to search:"
cin>>num//输入学号
temp=head
while(temp!=NULL&&temp->Snum!=num)//比较学号
temp=temp->next
if(temp==NULL)//没有找到信息
cout<<"Sorry,no such student of the number you input!"<<endl
else//输出信息
{
cout<<"The flowing is the information of the student "<<num<<endl
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl
}
}
/**
*增加学生的信息
*/
void Student::add_info()
{
Student *temp,*loop,*loop1
temp=new Student
loop=new Student
loop1=new Student
cout<<"-----------------------------------------------------------"<<endl
cout<<"Now add information of student."<<endl
cout<<"Input the number of the student (0 to end):"
cin>>temp->Snum//输入学号
loop1=temp
while(temp->Snum!=0)//学号不为0
{
cout<<"Input the name of the student:"
cin>>temp->name//姓名
cout<<"Input the score of Chinese:"
cin>>temp->Chinese//语文
cout<<"Input the score of English:"
cin>>temp->English//英语
cout<<"Input the score of Math:"
cin>>temp->Math//数学
cout<<"Input the score of Computer Science:"
cin>>temp->Computer//计算机
if(head==NULL) head=temp//将信息添加到链表中
else
{
if(head->Snum>temp->Snum)
{
temp->next=head
head=temp
}
else
{
loop=head
while(loop->next!=NULL)
{
if(loop->next->Snum>temp->Snum)
{
temp->next=loop->next
loop->next=temp
break
}
loop=loop->next
}
if(loop->next==NULL)
{
loop->next=temp
temp->next=NULL
}
}
}
temp=new Student
loop=new Student
cout<<"\n\nInput the number of the student (0 to end):"
cin>>temp->Snum
}
cout<<"\nThe information you input is the flowing."<<endl
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl
while(loop1!=NULL)
{
cout<<(loop1->Snum)<<setw(9)<<(loop1->name)<<setw(9)<<(loop1->Chinese)<<setw(9)<<(loop1->English)
<<setw(9)<<(loop1->Math)<<setw(12)<<(loop1->Computer)<<endl
loop1=loop1->next
}
}
/**
*通过学号删除信息
*/
void Student::del_info()
{
Student *temp,*loop1,*loop2
long snum
temp=new Student
loop1=new Student
loop2=new Student
cout<<"----------------------------------------------------------"<<endl
cout<<"Input the number of the student you want to delete:"
cin>>snum//输入学号
temp=head
while(temp!=NULL&&temp->Snum!=snum)//通过学号查找信息
{
loop1=temp
temp=temp->next
}
if(temp==NULL)//没有相应学号的学生信息
cout<<"Sorry,no such student of the number you input!"<<endl
else
{
loop1->next=temp->next//跳过链表的一个节点temp
cout<<"The information you delete is the flowing."<<endl
cout<<"Snum"<<setw(9)<<"name"<<setw(9)<<"Chinese"<<setw(9)<<"English"<<setw(9)
<<"Math"<<setw(18)<<"Coputer Science"<<endl
cout<<(temp->Snum)<<setw(9)<<(temp->name)<<setw(9)<<(temp->Chinese)<<setw(9)<<(temp->English)
<<setw(9)<<(temp->Math)<<setw(12)<<(temp->Computer)<<endl
if(temp->Snum==head->Snum) head=head->next
delete temp//删除节点
}
}
/**
*析构函数,只用程序的正常结束才会执行改函数,并且把学生的信息保存到文件中
*/
Student::~Student()
{
Student*temp
temp=new Student
ofstream write_file
write_file.open(file_name,ios::beg)
if(!write_file)
{
cout<<"Fail to write the information to the file!"<<endl
cout<<"Press any key to exit."
cin.get()
exit(0)
}
temp=head
while(temp!=NULL)
{
write_file<<temp->Snum<<" "<<temp->name<<" "<<temp->Chinese<<" "<<temp->English<<" "<<temp->Math<<" "<<temp->Computer<<endl
temp=temp->next
}
write_file<<0
write_file.close()
}
/**
*主函数,主要提供一些菜单选项
*/
void main()
{
char select
int selection
Student student
cout<<"\n########################################################"<<endl
if(student.search_file()==0)
{
cout<<"There is no file of student information."<<endl
cout<<"Do you want to creat it?(Y/N):"
cin>>select
if(select=='Y'||select=='y')
student.creat_file()
else
exit(0)
}
if(student.get_info()==0)
{
cout<<"There is no information in the file"<<endl
cout<<"Do you want to add information to the file?(Y/N):"
cin>>select
if(select=='y'||select=='Y')
student.add_info()
else exit(0)
}
cout<<"\n\n##########################################################"<<endl
cout<<"Information of students.Selections are flowing."<<endl
cout<<"Input number 1 to search information by name."<<endl
cout<<"Input number 2 to search information by number."<<endl
cout<<"Input number 3 to add nuw information to the file."<<endl
cout<<"Input number 4 to delete information from the file."<<endl
cout<<"Input number 5 to view all the students' information."<<endl
cout<<"Input other numbers to exit."<<endl
cout<<"Input your selection please:"
cin>>selection
while(selection>=1&&selection<=5)
{
if(selection==1) student.search_info_name()
if(selection==2) student.search_info_Snum()
if(selection==3) student.add_info()
if(selection==4) student.del_info()
if(selection==5) student.out_all_info()
cout<<"\n\n########################################################"<<endl
cout<<"Information of students.Selections are flowing."<<endl
cout<<"Input number 1 to search information by name."<<endl
cout<<"Input number 2 to search information by number."<<endl
cout<<"Input number 3 to add nuw information to the file."<<endl
cout<<"Input number 4 to delete information from the file."<<endl
cout<<"Input number 5 to view all the students' information."<<endl
cout<<"Input other numbers to exit."<<endl
cout<<"Input your selection please:"
cin>>selection
}
}
链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C＋＋语言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言中不能实现链表，其实不然，Java语言比C和C＋＋更容易实现链表结构。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。class Node
{
Object data
Node next//指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。下图是这种链表的示意图：
链表的数据结构
我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。
链表类List的源代码如下：
import java.io.*
public class List
{
/*用变量来实现表头*/
private Node Head=null
private Node Tail=null
private Node Pointer=null
private int Length=0
public void deleteAll()
/*清空整个链表*/
{
Head=null
Tail=null
Pointer=null
Length=0
}
public void reset()
/*链表复位，使第一个结点成为当前结点*/
{
Pointer=null
}
public boolean isEmpty()
/*判断链表是否为空*/
{
return(Length==0)
}
public boolean isEnd()
/*判断当前结点是否为最后一个结点*/
{
if(Length==0)
throw new java.lang.NullPointerException()
else if(Length==1)
return true
else
return(cursor()==Tail)
}
public Object nextNode()
/*返回当前结点的下一个结点的值，并使其成为当前结点*/
{
if(Length==1)
throw new java.util.NoSuchElementException()
else if(Length==0)
throw new java.lang.NullPointerException()
else
{
Node temp=cursor()
Pointer=temp
if(temp!=Tail)
return(temp.next.data)
else
throw new java.util.NoSuchElementException()
}
}
public Object currentNode()
/*返回当前结点的值*/
{
Node temp=cursor()
return temp.data
}
public void insert(Object d)
/*在当前结点前插入一个结点，并使其成为当前结点*/
{
Node e=new Node(d)
if(Length==0)
{
Tail=e
Head=e
}
else
{
Node temp=cursor()
e.next=temp
if(Pointer==null)
Head=e
else
Pointer.next=e
}
Length＋＋
}
public int size()
/*返回链表的大小*/
{
return (Length)
}
public Object remove()
/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点*/
{
Object temp
if(Length==0)
throw new java.util.NoSuchElementException()
else if(Length==1)
{
temp=Head.data
deleteAll()
}
else
{
Node cur=cursor()
temp=cur.data
if(cur==Head)
Head=cur.next
else if(cur==Tail)
{
Pointer.next=null
Tail=Pointer
reset()
}
else
Pointer.next=cur.next
Length－－
}
return temp
}
private Node cursor()
/*返回当前结点的指针*/
{
if(Head==null)
throw new java.lang.NullPointerException()
else if(Pointer==null)
return Head
else
return Pointer.next
}
public static void main(String[] args)
/*链表的简单应用举例*/
{
List a=new List ()
for(int i=1i<=10i＋＋)
a.insert(new Integer(i))
System.out.println(a.currentNode())
while(!a.isEnd())
System.out.println(a.nextNode())
a.reset()
while(!a.isEnd())
{
a.remove()
}
a.remove()
a.reset()
if(a.isEmpty())
System.out.println("There is no Node in List \n")
System.in.println("You can press return to quit\n")
try
{
System.in.read()
//确保用户看清程序运行结果
}
catch(IOException e)
{}
}
}
class Node
/*构成链表的结点定义*/
{
Object data
Node next
Node(Object d)
{
data=d
next=null
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。
可以用这样的代码来实现：
class Node
{
Object data
Node next
Node previous
Node(Object d)
{
data=d
next=null
previous=null
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。
希望对你有帮助。
