项目实训–把链表结构体改成链表类

现在的位置: 首页 > 综合 > 正文

项目实训–把链表结构体改成链表类

2014年02月06日 ⁄ 综合 ⁄ 共 8800字 ⁄ 字号小中大 ⁄ 评论关闭

/* (程序头部注释开始)
* 程序的版权和版本声明部分
* Copyright (c) 2011, 烟台大学计算机学院学生
* All rights reserved.
* 文件名称：把链表结构体改成链表类

* 作者：雷恒鑫
* 完成日期： 2012 年 08 月 23 日
* 版本号： V1.0
* 对任务及求解方法的描述部分
* 输入描述：
* 问题描述：
* 程序输出：

* 程序头部的注释结束

原来的链表结构体：

#include <stdio.h>
#include <malloc.h>

#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0

struct LNode
{
	int data;
	struct LNode * next;
};

typedef LNode * Link, * Position, Node;

struct LLink
{
	Link head, tail;
	int len;
};

typedef LLink LinkList;

//创建一个结点，其值为value。
int MakeNode(Link &p, int value)
{
	//p = (Link) malloc(sizeof(Node));
	p = (LNode * ) malloc(sizeof(Node));
	if (p == NULL)
	{
		return ERROR;
	}

	p->data = value;
	p->next = NULL;

	return OK;
}

//释放p所指向的结点。
void FreeNode(Link &p)
{
	free(p);
	p = NULL;
}

//构造一个空的线性链表L。
int InitList(LinkList &L)
{
	L.head = NULL;
	L.tail = NULL;
	L.len = 0;
	
	return OK;
}

//已知h指向线性链表L的第一个结点，将s所指结点插入到h之前。
int InsFirst(LinkList &L, Link h, Link s)
{
	if (s == NULL)
	{
		return ERROR;
	}

	s->next = h;
	L.head = s;
	if (L.tail == NULL)
	{
		L.tail = s;
	}
	L.len++;

	return OK;
}

//删除线性链表L中的第一个结点，并以q返回。
int DelFirst(LinkList &L, Link &q)
{
	if (L.head == NULL)
	{
		return ERROR;
	}
	
	q = L.head;
	L.head = q->next;

	if (q == L.tail)
	{
		L.head = NULL;
		L.tail = NULL;
                q->next=NULL;
	}
	L.len--;

	return OK;
}

//将指针s所指的一串结点链接在线性表L的尾部。
int Append(LinkList &L, Link s)
{
	if (s == NULL)
	{
		return ERROR;
	}

	L.tail->next = s;
	L.len++;

	while(s->next != NULL)
	{
		s = s->next;
		L.len++;
	}
	L.tail = s;

	return OK;
}

//删除线性链表L中的尾结点并以q返回。
int Remove(LinkList &L, Link &q)
{
	if (L.len == 0)
	{
		return ERROR;
	}

	Link p;
	p = L.head;
	while (p->next != L.tail)
	{
		p = p->next;
	}
	q = p->next;
	p->next = NULL;
	L.tail = p;
	L.len--;

	return OK;
}

//返回p指示线性链表L中第i个结点的位置，并返回OK,i值不合法时返回ERROR。
int LocatePos(LinkList L, int i, Link &p)
{
	int j;
	if (i < 0 || i > L.len)
	{
		return ERROR;
	}

	p = L.head;
	for (j = 1; j < i; j++)
	{
		p = p->next;
	}

	return OK;
}

//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置。若无直接前驱，则返回NULL。
Position PriorPos(LinkList L, Link p)
{
	if (p == L.head->next)
	{
		return NULL;
	}

	Link q;
	q = L.head->next;
	while (q->next != p)
	{
		q = q->next;
	}

	return q;
}

//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置。若无直接后继，则返回NULL。
Position NextPos(LinkList L, Link p)
{
	if (p->next == NULL)
	{
		return NULL;
	}

	return p->next;
}

//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前。
int InsBefore(LinkList &L, Link &p, Link s)
{
	if (s == NULL || p == NULL)
	{
		return NULL;
	}

	Link q;
	q = PriorPos(L, p);
	if (q == NULL)
	{
		q = L.head;
	}
	q->next = s;
	s->next = p;
	//p = s;
	L.len++;

	return OK;
}

//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后。
int InsAfter(LinkList &L, Link &p, Link s)
{
	if (s == NULL || p == NULL)
	{
		return NULL;
	}

	if (p == L.tail)
	{
		L.tail = s;
	}
	s->next = p->next;
	p->next = s;
	L.len++;

	return OK;
}

//返回线性链表L中头结点的位置。
Position GetHead(LinkList L)
{
	return L.head;
}

//返回线性链表L中尾结点的位置。
Position GetLast(LinkList L)
{
	return L.tail;
}

//释放线性链表L。
int FreeList(LinkList &L)
{
	if (L.len == 0)
	{
		return OK;
	}

	Link p, q;
	p = GetHead(L);
	while (p != NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}

	L.head = NULL;
	L.tail = NULL;
	L.len = 0;

	return OK;
}

//输出线性链表L中的各个结点，并输出头尾指针所指元素值。
int Display(LinkList L)
{
	int i;
	if (L.head == NULL)
	{
		return ERROR;
	}

	Link p = L.head;
	for (i = 1; i <= L.len; i++)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
	printf("head value : %d \n", L.head->data);
	printf("tail value : %d \n", L.tail->data);
	printf("\n");

	return OK;
}

int main()
{
	int i;
	Link p;
	Link q;
	LinkList La, Lb;

	//初始化线性链表La。
	if (!InitList(La))
	{
		return OVERFLOW;
	}

	for (i = 7; i >= 1; i = i -1)
	{
		MakeNode(p, i);
		InsFirst(La, La.head, p);
	}
	printf("链表La为：");
	Display(La);

	//初始化线性链表Lb。
	if (!InitList(Lb))
	{
		return OVERFLOW;
	}

	for (i = 17; i >= 11; i = i -1)
	{
		MakeNode(p, i);
		InsFirst(Lb, Lb.head, p);
	}
	printf("链表Lb为：");
	Display(Lb);

	//将链表Lb链接到链表La之后。
	printf("两个线性链表想链接La + Lb: \n");
	Append(La, Lb.head);
	Display(La);

	//删除首结点。
	DelFirst(La, q);
	printf("被删除的首结点值为：%d\n", q->data);
	FreeNode(q);
	Display(La);

	//删除尾结点。
	Remove(La, q);
	printf("删除链表L中的最后一个结点:%d\n",q->data);
	FreeNode(q);
	Display(La);

	//定位第六个元素结点，并用p指针指向该结点。
	LocatePos(La, 6, p);
	Display(La);
	printf("第六个元素结点数据:%d\n",p->data);

	//p结点的直接前驱。
	q = PriorPos(La, p);
	Display(La);
	printf("第六个元素结点数据:%d\n",p->data);
	printf("第六个元素结点的直接前驱数据是:%d\n",q->data);

	//p结点的直接后继。
	q = NextPos(La, p);
	Display(La);
	printf("第六个元素结点数据:%d\n",p->data);
	printf("第六个元素结点的直接后继数据是:%d\n",q->data);
	printf("\n");
	
	//在第六个结点前插入值为111的新结点。
	printf("在第六个结点前插入值为111的新结点。\n");
	MakeNode(q, 111);
	InsBefore(La, p, q);
	Display(La);

	//在原第六个结点后插入值为222的新结点。
	printf("在原第六个结点后插入值为222的新结点。\n");
	MakeNode(q, 222);
	InsAfter(La, p, q);
	Display(La);

	//输出线性链表La的表头结点。
	q = GetHead(La);
	printf("线性链表La中表头结点的值为:%d\n",q->data);

	//输出线性链表La的表尾结点。
	q = GetLast(La);
	printf("线性链表La中表尾结点的值为:%d\n",q->data);

	FreeList(La);
	Display(La);

	return 0;
}

改成类之后：

LinkList.h

#ifndef HEADER_LINKLIST
#define HEADER_LINKLIST

#include "Node.h"

class LinkList
{
private:
	Node *head;
	int len;
public:
	LinkList();
	~LinkList();
	void set_head(Node *head);
	void set_len(int len);
	Node *get_head();
	int get_len();
	Node *make_node(Record *record);
	void insert_node(Node *node);
	Node *find_node(int number);
	void display_LinkList();
};
#endif

LinkList.cpp

#include "LinkList.h"
#include <iostream>
using namespace std;

LinkList::LinkList()
{
	this->head=NULL;
	this->len=0;
}

LinkList::~LinkList()
{
	Node *p,*q=this->head;
	while (p!=NULL)
	{
		q=p;
		p=p->get_next();
		delete q;
	}
	this->head=NULL;
	this->len=0;
}

void LinkList::set_head(Node *head)
{
	this->head=head;
}

void LinkList::set_len(int len)
{
	this->len=len;
}

Node *LinkList::get_head()
{
	return this->head;
}

int LinkList::get_len()
{
	return this->len;
}

Node *LinkList::make_node(Record *record)
{
	Node *node = new Node();
	node->set_Record(record);
	node->set_next(NULL);
	return node;
}

void LinkList::insert_node(Node *node)
{
	Node *p=this->head;
	if(p==NULL)
	{
		this->head=node;
		this->len++;
		return;
	}
	while(p->get_next()!=NULL)
	{
		p=p->get_next();
	}
	p->set_next(node);
	this->len++;
}

Node *LinkList::find_node(int number)
{
	Node *p=this->head;
	while (p!=NULL)
	{
		Record *r=p->get_Record();
		if(r->get_number()==number)
		{
			return p;
		}
		else
		{
			p=p->get_next();
		}
	}
		return p;
}

void LinkList::display_LinkList()
{
	cout<<"Print LinkList..."<<endl;
	//cout<<"Head:"<<this->head<<endl;
	Node *p=this->head;
	if(p==NULL)
	{
		cout<<"LinkList is NULL..."<<endl;
		cout<<"len:"<<this->len<<endl;
		cout<<"End of LinkList..."<<endl;
		return;
	}
	while (p!=NULL)
	{
		p->display_Node();
		p=p->get_next();
	}
	cout<<"len:"<<this->len<<endl;
	cout<<"End of LinkList..."<<endl;
	return;
}

Node.h

#ifndef HEADER_NODE
#define HEADER_NODE

#include "Record.h"

class Node
{
private:
	Record *record;
	Node *next;
public:
	Node();
	~Node();
	void set_Record(Record *record);
	void set_next(Node *next);
	Record *get_Record();
	Node *get_next();
	void display_Node();
};
#endif

Node.cpp

#include "Node.h"
#include <iostream>
using namespace std;

Node::Node()
{
	this->record=NULL;
	this->next=NULL;
}

Node::~Node()
{
	delete this->record;
	this->record=NULL;
	this->next=NULL;
}

void Node::set_Record(Record *record)
{
	this->record=record;

}

void Node::set_next(Node *next)
{
	this->next=next;

}

Record *Node::get_Record()
{
	return this->record;
}

Node *Node::get_next()
{
	return this->next;
}

void Node::display_Node()
{
	cout<<"Print Node elements..."<<endl;

	if(this->record!=NULL)
	{

	this->record->display_Record();

	cout<<"next*:"<<this->next<<endl;

	}
	else
	{
		cout<<"Record is NULL..."<<endl;
	}

	cout<<"End of Node..."<<endl;
}

/*  void display_Node()为了易于了解也可以改成如下结构
void display_Node()
{
	Record *r=this->record;
	cout<<"Print Node elements..."<<endl;
	if(this->record!=NULL)
	{
		r->display_Record();

		cout<<"next*:"<<this->next<<endl;
	}
	else
	{
		cout<<"Record is NULL..."<<endl;
	}
	cout<<"End of Node..."<<endl;
}
*/

Record.h

#ifndef HEADER_RECORD
#define HEADER_RECORD
#include <string>
using namespace std;

class Record
{
private:
	int number;
	string userName;
	string passWord;
	double balance;
	int flag;
public:
	Record();
	void set_number(int number);
	void set_userName(string userName);
	void set_passWord(string passWord);
	void set_balance(double balance);
	void set_flag(int flag);
	int get_number();
	string get_userName();
	string get_passWord();
	double get_balance();
	int get_flag();
	void display_Record();
};
# endif

Record.cpp

#include "Record.h"
#include <iostream>

using namespace std;

Record::Record()
{
	this->number=0;
	this->userName="";
	this->passWord="";
	this->balance=0;
	this->flag=-1;
}

void Record::set_number(int number)
{
	this->number=number;
}

void Record::set_userName(string userName)
{
	this->userName=userName;
}

void Record::set_passWord(string passWord)
{
	this->passWord=passWord;
}

void Record::set_balance(double balance)
{
	this->balance=balance;
}

void Record::set_flag(int flag)
{
	this->flag=flag;
}

int Record::get_number()
{
	return this->number;
}

string Record::get_userName()
{
	return this->userName;
}

string Record::get_passWord()
{
	return this->passWord;
}

double Record::get_balance()
{
	return this->balance;
}

int Record::get_flag()
{
	return this->flag;
}

void Record::display_Record()
{
	cout<<"Print Record Elements..."<<endl;
	cout<<"Number："<<endl;
	cout<<"UserName："<<this->userName<<endl;
	cout<<"PassWord："<<this->passWord<<endl;
	cout<<"Balance："<<this->balance<<endl;
	cout<<"Flag："<<this->flag<<endl;
	cout<<"End of Record..."<<endl;
}

TestLinkList.cpp

#include "LinkList.h"
#include<iostream>
using namespace std;

int main()
{
	LinkList *list = new LinkList();
	list->display_LinkList();
	cout<<endl;

	Record *r1= new Record();
	r1->display_Record();
	r1->set_number(10001);
	r1->set_userName("zhangsan");
	r1->set_passWord("123456");
	r1->set_balance(10000);
	r1->set_flag(1);

	Node *n1=list->make_node(r1);
	list->insert_node(n1);
	list->display_LinkList();
	cout<<endl;

    Record *r2= new Record();
	r2->display_Record();
	r2->set_number(10002);
	r2->set_userName("lisi");
	r2->set_passWord("123");
	r2->set_balance(20000);
	r2->set_flag(1);

	Node *n2=list->make_node(r2);
	list->insert_node(n2);
	list->display_LinkList();
	cout<<endl;

	Node *n3=list->find_node(10005);
	if(n3==NULL)
	{
		cout<<"Not Found..."<<endl;
	}
	else
	{
		n3->display_Node();
	}
	return 0;
}

运行结果：