exam1.cpp

来自「C++语言程序设计题典」· C++ 代码 · 共 162 行

#include <iostream.h>
#include <malloc.h>
typedef int elemtype;     //定义数据域的类型
typedef struct linknode   //定义结点类型
{
    elemtype data;
	struct linknode *next;
} nodetype;
class List
{
	nodetype *head;
public:
	List() { head=NULL; }
    void creatlist();
    void displist();
    int listlen();
    nodetype *findnode(int i);
    void insnode(int i,elemtype x);
    void delnode(int i);
    List::~List();
};
void List::creatlist()
{
	elemtype d;
	nodetype *h=NULL,*s,*t;
	int i=1;
	cout << "创建单链表" << endl;
	while (1)
	{
	   cout << "  输入第" << i << "结点data域:";
	   cin >> d;
	   if (d==0) break;  //以0表示输入结束
	   if (i==1)         //建立第一个结点
	   {
		   h=(nodetype *)malloc(sizeof(nodetype));
		   h->data=d;h->next=NULL;t=h;
	   }
	   else             //建立其余结点
	   {
		   s=(nodetype *)malloc(sizeof(nodetype));
		   s->data=d;s->next=NULL;t->next=s;
		   t=s;          //t始终指向生成的单链表的最后一个结点
	   }
	   i++;
	}
	head=h;
}
void List::displist()
{
	nodetype *p=head;
	cout << "输出单链表:" << endl << "  ";
	if (p==NULL) cout << "空表";
	while (p!=NULL)
	{
		cout << p->data << " ";	p=p->next;
	}
	cout << endl;
}
int List::listlen()
{
	int i=0;
	nodetype *p=head;
	while (p!=NULL)
	{
		p=p->next;i++;
	}
	return i;
}
nodetype *List::findnode(int i)  //返回第i个结点的指针
{
	nodetype *p=head;
	int j=1;
	if (i>listlen() || i<=0) return NULL; //i上溢或下溢
	else
	{
		while (p!=NULL && j<i)        //查找第i个结点,并由p指向该结点
		{
			j++;p=p->next;
		}
		return p;
	}
}
void List::insnode(int i,elemtype x) 
{
	nodetype *h=head,*p,*s;
	s=(nodetype *)malloc(sizeof(nodetype)); //创建结点s
	s->data=x;s->next=NULL;
	if (i==0)                               //i=0:s作为该单链表的第一个结点
	{
		s->next=h;h=s;
	}
	else
	{
		p=findnode(i);            	      //查找第i个结点,并由p指向该结点
		if (p!=NULL)
		{
			s->next=p->next;p->next=s;
		}
		else cout << "输入的i值不正确" << endl;
	}
	head=h;
}
void List::delnode(int i)
{
	nodetype *h=head,*p=head,*s;
	int j=1;
	if (i==1)               //删除第1个结点
	{
		h=h->next;free(p);
	}
	else
	{
		p=findnode(i-1);     //查找第i-1个结点,并由p指向该结点
		if (p!=NULL && p->next!=NULL)
		{
			s=p->next;       //s指向要删除的结点
			p->next=s->next;
			free(s);
		}
		else cout << "输入的i值不正确" << endl;
	}
	head=h;
}
List::~List()  //释放单链表的所有结点占用的空间
{
	nodetype *pa=head,*pb;
	if (pa!=NULL)
	{
		pb=pa->next;
	    if (pb==NULL)          //只有一个结点的情况
			free(pa);
	    else
		{
			while (pb!=NULL)   //有两个及以上结点的情况
			{
				free(pa); pa=pb; pb=pb->next;
			}
	        free(pa);
		}
	}
}
void main()
{
	List L1;
	nodetype *p;
	L1.creatlist();
	L1.displist();
	cout << "单链表长度为:" << L1.listlen() << endl;
	cout << "删除编号为2的结点" << endl;
	L1.delnode(2);
	L1.displist();
	cout << "在编号为3的结点之后插入data为10的结点" << endl;
	L1.insnode(3,10);
	L1.displist();
	cout << "查找data域为2的结点" << endl;
	p=L1.findnode(2);
	if (p!=NULL)
		cout << "  找到了该结点" << endl;
	else
		cout << "  找不到了该结点" << endl;
}