创造链表

创建链表

 

#include "iostream.h"
struct node
{
	char data;
	node *next;
};
node *create();
node *search(node *head,char keyWord);
void insert(node * &head,char keyWord,char newdata);
void showList(node *head);
void Delete(node *&head,char keyWord);
int main()
{
	node *head;
	head=create();
//	insert(head,'b','e');
	Delete(head,'b');
	showList(head);
	return 0;
}

node * create()
{
	node *head=NULL;//表头指针，一开始没有任何结点，所以为NULL
	node *pEnd=head;//表为指针，一开始没有任何结点，所以指向表头
	node *pS;//创建新结点时使用的指针
	char temp;//用于存放从键盘输入的字符
	cout <<"Please input a string end with '#':" <<endl;
	do//循环至少运行一次
	{
		cin >>temp;
		if (temp!='#')//如果输入的字符不是结尾符#，则建立新结点
		{
			pS=new node;//创建新结点
			pS->data=temp;//新结点的数据为temp
			pS->next=NULL;//新结点将成为表尾，所以next为NULL
			if (head==NULL)//如果链表还没有任何结点存在
			{
				head=pS;//则表头指针指向这个新结点
			}
			else//否则
			{
				pEnd->next=pS;//把这个新结点连接在表尾
			}
			pEnd=pS;//这个新结点成为了新的表尾
		} 
	}while (temp!='#');//一旦输入了结尾符，则跳出循环
	return head;//返回表头指针
}
void showList(node *head)
{
	node *pRead=head;//访问指针一开始指向表头
	cout <<"The data of the link list are:" <<endl;
	while (pRead!=NULL)//当访问指针存在时（即没有达到表尾之后）
	{
		cout <<pRead->data;//输出当前访问结点的数据
		pRead=pRead->next;//访问指针向后移动
	}
	cout <<endl;
}
void insert(node * &head,char keyWord,char newdata)//keyWord是查找关键字符
{
	node *newnode=new node;//新建结点
	newnode->data=newdata;//newdata是新结点的数据
	node *pGuard=search(head,keyWord);//pGuard是插入位置前的结点指针
	if (head==NULL || pGuard==NULL)//如果链表没有结点或找不到关键字结点
	{//则插入表头位置
		newnode->next=head;//先连
		head=newnode;//后断
	}
	else//否则
	{//插入在pGuard之后
		newnode->next=pGuard->next;//先连
		pGuard->next=newnode;//后断
	}
}

node * search(node *head,char keyWord)//返回结点的指针
{
	node *pRead=head;
	while (pRead!=NULL)//采用与遍历类似的方法，当访问指针没有到达表尾之后
	{
		if (pRead->data==keyWord)//如果当前结点的数据和查找的数据相符
		{
			return pRead;//则返回当前结点的指针
		}
		pRead=pRead->next;//数据不匹配，pRead指针向后移动，准备查找下一个结点
	}
	return NULL;//所有的结点都不匹配，返回NULL
}

void Delete(node * &head,char keyWord)//可能要操作表头指针，所以head是引用
{
	if (head!=NULL)//如果链表没有结点，就直接输出提示
	{
		node *p;
		node *pGuard=head;//初始化pGuard指针
		if (head->data==keyWord)//如果头结点数据符合关键字
		{
			p=head;//头结点是待删除结点
			head=head->next;//先连
			delete p;//后断
			cout <<"The deleted node is " <<keyWord <<endl;
			return;//结束函数运行
		}
		else//否则
		{
			while (pGuard->next!=NULL)//当pGuard没有达到表尾
			{
				if (pGuard->next->data==keyWord)//如果pGuard后继结点数据符合关键字
				{
					p=pGuard->next;//pGuard后继结点是待删除结点 
					pGuard->next=p->next;//先连
					delete p;//后断
					cout <<"The deleted node is " <<keyWord <<endl;
					return;//结束函数运行
				}
				pGuard=pGuard->next;//pGuard指针向后移动
			}
		}
	}
	cout <<"The keyword node is not found or the link list is empty!" <<endl;//输出提示信息
}

 

 

Please input a string end with '#':

Tomato#

The data of the link list are:

Tomato

这个程序的功能是把输入的字符串保存到链表中，然后把它输出。从程序中我们可以看出，create函数的主要工作有：

①做好表头表尾等指针的初始化。

②反复测试输入的数据是否有效，如果有效则新建结点，并做好该结点的赋值工作。将新建结点与原来的链表连接，如果原链表没有结点，则与表头连接。

③返回表头指针。

下图9.6.1给出了create函数创建链表的过程。

初始化

创建第一个结点

 

创建第二个结点

……

创建完成

（图9.6.1）

程序中showList函数的主要工作有： - 103 -

易学 C++

①初始化访问指针。

②如果访问指针不为空，则输出当前结点的数据，否则函数结束。

③访问指针向后移动，并重复第二项工作。

注意，虽然上述程序可以运行，但是它没有将内存释放，严格意义上来说，它是一个不完整的程序。

链表的查

 

 

 

 

delete 在函数中也会影响实参。