线性表课程设计.cpp

数据结构线性链表课程设计

#define null 0
#define OK 1
#define ERROR 0
#include <iostream.h>
#include <stdlib.h>
typedef struct student{
	char name[20];
	int num;
}student;

typedef struct LNode{
	student data;
	
	struct LNode *next;
}LNode,*LinkList;

//创建单链表
void CreateList(LinkList &L,int n);
//显示单链表中结点数据域的值
void ShowList(LinkList L);
//初始化单链表为空链表
void ClearList(LinkList L);
//取单链表L中位序为i的结点,并把结点存放在e中
unsigned GetElem(LinkList L,int i,LNode &e);
//在单链表L的第i个位置之前插入结点e
unsigned ListInsert(LinkList &L,int i,LNode e);
//删除单链表L的第i个位置的结点,并将该结点存入e
unsigned ListDelete(LinkList &L,int i,LNode &e);
//获取结点cur_e的前驱
unsigned PriorElem(LinkList L,LNode cur_e,LNode &pre_e);
//获取结点cur_e的后继
unsigned NextElem(LinkList L,LNode cur_e,LNode &next_e);
//访问函数
void visit(LinkList p);
//单链表的遍历
void ListTraverse(LinkList L,void (*func)(LinkList L));
//按非递减次序定位e在L中的位置
unsigned  LocateElem(LinkList L,LNode e);
//按非递减次序对L中的结点进行排序
unsigned SortList(LinkList &L);
//对L进行逆置
void ReverseList(LinkList &L);
 
void CreateList(LinkList &L,int n){
	LinkList p;

	L=new LNode;
	L->next=null;	
	
	for(int i=0;i<n;i++){
	    p=new LNode;
		if(!p){
			cout<<"Memory allocate error!";
			exit(0);
		}
		
	    cout<<"input name and num:"<<endl;
		cin>>p->data.name>>p->data.num;
		p->next=L->next;
		L->next=p;
	}
}
void ShowList(LinkList L){
	LinkList p;

	p=L->next;
	while(p){
		cout<<p->data.name<<" "<<p->data.num<<"->";
		p=p->next;
	}
	cout<<"null"<<endl;
}
void ClearList(LinkList L){
	LinkList p;
	while(L->next){
		p=L->next;
		L->next=p->next;
		delete p;
	}
}
unsigned GetElem(LinkList L,int i,LNode &e){
    LinkList p;
	int j;

	p=L->next;
	j=1;
	while(p&&j<i){
		p=p->next;
		++j;
	}
	if(!p||j>i)return ERROR;
	e.data=p->data;

	return OK;
}
unsigned ListInsert(LinkList &L,int i,LNode e){

	LinkList p,s;
	int j;

	p=L;
	j=0;
	while(p&&j<i-1){
		p=p->next;
		++j;
	}
	if(!p||j>i-1)return ERROR;
	s=new LNode;
	s->data=e.data;
	
	s->next=p->next;
	p->next=s;
	return OK;
}

unsigned ListDelete(LinkList &L,int i,LNode &e){
	LinkList p,q;
	int j;

	p=L;
	j=0;
	while(p->next&&j<i-1){
		p=p->next;
		++j;
	}
	if(!(p->next)||j>i-1)return ERROR;
	q=p->next;
	p->next=q->next;
	e.data=q->data;
	
	delete q;
	return OK;
}
unsigned PriorElem(LinkList L,LNode cur_e,LNode &pre_e){
	LinkList p,q;

	p=L;
	if(p->next->data.name==cur_e.data.name&&p->next->data.num==cur_e.data.num)return ERROR;//第一个结点无前驱
	while(p->next){
		q=p->next;
		if(q->data.num==cur_e.data.num){
			pre_e.data.num=p->data.num;
			pre_e.data=p->data;
			
			return OK;
		}
		p=p->next;
	}
	return ERROR;
}
unsigned NextElem(LinkList L,LNode cur_e,LNode &next_e){
	LinkList p,q;
	p=L;
	if(p->next==null)return ERROR;//最后一个结点无后继
	while(p->next){
		q=p->next;
	    if(p->data.num==cur_e.data.num){
			next_e.data.num=q->data.num;
			next_e.data=q->data;
			
			return OK;
		}
		p=p->next;
	}
	return ERROR;
}

void visit(LinkList p){
	while(p->next){
		p=p->next;
		cout<<p->data.name<<"->"<<p->data.num<<"->";
	}
	cout<<"null"<<endl;
}
void ListTraverse(LinkList L,void (*func)(LinkList p)){
	func(L);
}
unsigned LocateElem(LinkList L,LNode e){
	LinkList p;
	int position=1;

	p=L->next;
	while(p){
		if(p->data.num>e.data.num)
			return(position);
		else{ 
			++position;
			p=p->next;
		}
	}
	return position;
}

unsigned SortList(LinkList &L){
	LinkList p,newL;
	LNode e;
	int position;

	newL=new LNode;
	if(!newL)return ERROR;
	newL->next=null;
	p=L->next;
	while(p){
		e.data=p->data;
	
		position=LocateElem(newL,e);
		ListInsert(newL,position,e);
		p=p->next;
	}
	L=newL;
	return OK;
}

void ReverseList(LinkList &L){
	LinkList p,q;

	p=L->next;
	L->next=null;
	while(p){
		q=p->next;
		p->next=L->next;
		L->next=p;
		p=q;
	}
}

void main(){
	LinkList L;
	LNode e,pre_e,next_e;
	int n,j;
	
	
	void (*func)(LinkList p);

	//创建单链表
	cout<<"Input the total number of the students:"<<endl;
	cin>>n;
	CreateList(L,n);
	cout<<"By Create:"<<endl;
	ShowList(L);
	cout<<"input the position j:"<<endl;
	cin>>j;
	//获取位序j的结点值
	
	if (j>n) exit(0);
	cout<<"Get position:"<<endl;
	if(!(GetElem(L,j,e))){
		cout<<"Error Position"<<endl;
		exit(0);
	}
	cout<<e.data.name<<" "<<e.data.num<<" "<<endl;
	
	//在位序j的位置插入一个结点
	cout<<"By Insert a new student's name and num before j:"<<endl;
	cin>>e.data.name;
    cin>>e.data.num;
	cout<<"By insert:"<<endl;
	if(!(ListInsert(L,j,e))){
		cout<<"Error Position"<<endl;
		exit(0);
	}
	ShowList(L);
	//删除结点，其位序j
	cout<<"By delete:"<<endl;
	if(!(ListDelete(L,j,e))){
		cout<<"Error Position"<<endl;
		exit(0);
	}
	ShowList(L);
	

	//求元素e的前驱
	cout<<"Get Prior e:"<<endl;
	cin>>e.data.name;
	cin>>e.data.num;
	PriorElem(L,e,pre_e);
	cout<<pre_e.data.name<<" "<<pre_e.data.num<<endl;
	if(!(PriorElem(L,e,pre_e))){
		cout<<"No PriorElem"<<endl;
		exit(0);
	}
	
	cout<<"Get Next:"<<endl;
	NextElem(L,e,next_e);
    cout<<next_e.data.name<<" "<<next_e.data.num<<" "<<endl;
	if(!(NextElem(L,e,next_e))){
		cout<<"No NextElem"<<endl;
		exit(0);
	}
	
	
	//单链表遍历,调用遍历函数visit()
	cout<<"By Traverse:"<<endl;
	func=visit;
	ListTraverse(L,func);
	//单链表结点非递减排序
	cout<<"By sort:"<<endl;
	SortList(L);
	ShowList(L);
	//单链表逆置
	cout<<"By Reverse:"<<endl;
	ReverseList(L);
	ShowList(L);
	//清空单链表
	cout<<"By Clear:"<<endl;
	ClearList(L);
	ShowList(L);
}