excise1.cpp

用链表存贮结构实现线性表的基本操作。（包括各种操作）

//函数结果状态代码
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;

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

Status InitList(LinkList &L)//构造一个空的链表L
{ 
	L=(LinkList)malloc(sizeof(LNode));
	if (!L) exit(OVERFLOW);
	return OK;
}

Status DestroyList(LinkList &L)//销毁链表L
{ 
	free(L);
	L=NULL;
	return OK;
}

Status ClearList(LinkList &L)//将表置为空表
{ 
	LNode *p;
	p=L->next;
	while(p)
	{
	   L->next=p->next;
	   free(p);
	   p=L->next;
	}
	return OK;
}
 
Status ListEmpty(LinkList L)//若为空表返回真，否则返回假
{
	if(!(L->next)) 
		return TRUE;
	else 
		return FALSE;
}

Status ListLength(LinkList L)//求表的长度
{
	LNode *p;
	p=L;
	int j=0;
	while(p->next)
	{
		p=p->next;
		j++;
	}

	return j;
}

Status GetElem(LinkList L,int i,int &e)//用e返回链表中的第i个元素
{
	int j;
	LNode *p;
	if(i<1||i>ListLength(L))
		return ERROR;
	p=L->next;
	for(j=1;j<i;j++)
		p=p->next;
	e=p->data;
	return e;
}

/*Status LocateElem(LinkList L,int e,Status(*compare)(int,int))
{
	LNode *p;
	p=L;
	int j=0;
	if(p)
	{
		p=p->next;
		j++;
		if((*compare)(p->data,e))
			return j;
	}
	else return ERROR;
}*/

Status PriorElem(LinkList L,int cur_e,int &pre_e)//返回当前元素的前驱
{
	LNode *p;
	p=L; 
	if(L->next->data==cur_e)
		return ERROR;
	while(p->next->data!=cur_e&&p->next)
		p=p->next;
	if(p->next->data==cur_e)
	{
		pre_e=p->data;
	    return pre_e;
	}
	else
		return ERROR;
}

Status NextElem(LinkList L,int cur_e,int &next_e)//返回当前元素的后继
{
	LNode *p;
	p=L->next;
	while(p->data!=cur_e&&p->next)
		p=p->next;
	if(p->data==cur_e&&p->next)
	{
		next_e=p->next->data;
	    return next_e;
	}
	else
		return ERROR;
}

Status ListInsert(LinkList &L,int i,int e)//在第i个元素前插入e
{
	LNode *p,*s;
	int j;
    p=L;
	if(i<1||i>ListLength(L)+1)
		return ERROR;
	for(j=0;j<i-1;j++)
		p=p->next;
	s=(LinkList)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return OK;
}

Status ListDelete(LinkList &L,int i,int &e)//删除第i个元素
{
	LNode *p;
	LNode *q;
	int j;

	if(i<1||i>ListLength(L))
		return ERROR;
	p=L;
	for(j=0;j<i-1;j++)
		p=p->next;
	q=p->next;
	p->next=q->next;
	q->next=NULL;
    e=q->data;
	free(q);
	return e;
}

/*Status ListTraverse(LinkList L,Status((*visit)(int)))
{
	LNode *p;
	p=L;
	while(p&&(*visit)(p->next))
		p=p->next;
	if(!(*visit)(p->next))
		return ERROR;
}*/

main()
{
	LinkList L;
	InitList(L);
	LNode *p;
	p=L;
	int i;
	for(i=0;i<10;i++)
	{
		LNode *s;
		s=(LinkList)malloc(sizeof(LNode));
		s->next=NULL;
        p->next=s;
		p=p->next;
		cout<<"请输入第"<<i+1<<"个数据:";
	    cin>>p->data;		
		cout<<endl;
	}
	p=L;
	i=1;
	while(p->next!=NULL)
	{
		p=p->next;
		cout<<"第"<<i<<"个数是:"<<p->data<<endl;
		i++;
	}
	cout<<"线性表的长度是:"<<ListLength(L)<<endl;
	int e;
	cout<<"第5个元素是:"<<GetElem(L,5,e)<<endl;

    int pre_e;
	int next_e;
	cout<<"元素8的前驱是:"<<PriorElem(L,8,pre_e)<<endl;
	
	cout<<"元素8的后继是:"<<NextElem(L,8,next_e)<<endl;
    i=3;
	while(!ListEmpty(L)&&i<4)
	{
		cout<<"你删除了第"<<i<<"个元素:"<<ListDelete(L,i,e)<<endl;
		i++;
	}
	p=L;
	i=1;
    while(p->next!=NULL)
	{
       p=p->next;
       cout<<"删除后第"<<i<<"个元素是:"<<p->data<<endl;
	   i++;
	}
	cout<<"下面将在第3个元素前插入“123!”"<<endl;
	ListInsert(L,3,123);
	p=L;
	i=1;
    while(p->next!=NULL)
	{
       p=p->next;
       cout<<"插入后第"<<i<<"个元素是:"<<p->data<<endl;
	   i++;
	}

	cout<<"下面将清空链表!"<<endl;
	ClearList(L);
	if(L->next)
	     cout<<"该链表不为空,清空链表操作失败!"<<endl;
	else 
		 cout<<"该链表为空,清空链表成功!"<<endl;
	cout<<"下面将销毁链表!"<<endl;
	DestroyList(L);
	if(!L)
		cout<<"销毁链表成功!"<<endl;
	else 
		cout<<"销毁链表失败!"<<endl;

	cout<<"程序结束!"<<endl;
	return OK;
}

/*程序结果
请输入第1个数据:1

请输入第2个数据:2

请输入第3个数据:3

请输入第4个数据:4

请输入第5个数据:5

请输入第6个数据:6

请输入第7个数据:7

请输入第8个数据:8

请输入第9个数据:9

请输入第10个数据:10

第1个数是:1
第2个数是:2
第3个数是:3
第4个数是:4
第5个数是:5
第6个数是:6
第7个数是:7
第8个数是:8
第9个数是:9
第10个数是:10
线性表的长度是:10
第5个元素是:5
元素8的前驱是:7
元素8的后继是:9
你删除了第3个元素:3
删除后第1个元素是:1
删除后第2个元素是:2
删除后第3个元素是:4
删除后第4个元素是:5
删除后第5个元素是:6
删除后第6个元素是:7
删除后第7个元素是:8
删除后第8个元素是:9
删除后第9个元素是:10
下面将在第3个元素前插入“123!”
插入后第1个元素是:1
插入后第2个元素是:2
插入后第3个元素是:123
插入后第4个元素是:4
插入后第5个元素是:5
插入后第6个元素是:6
插入后第7个元素是:7
插入后第8个元素是:8
插入后第9个元素是:9
插入后第10个元素是:10
下面将清空链表!
该链表为空,清空链表成功!
下面将销毁链表!
销毁链表成功!
程序结束!
Press any key to continue*/