C++链表中插入结点 参数的问题

Question

void insert(node * &head,char keyword,char newdata)
{

..........

}

为什么是&head 而不是head
node *&head是什么意思。。

Answer 1

以前做过的实验报告，应该很全，全给你了
1、线性表链式存储结构及基本操作算法实现
[实现提示] （同时可参见教材p64-p73页的ADT描述及算法实现及ppt）函数、类名称等可自定义，部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。
所加载的库函数或常量定义：
（1）单链表存储结构类的定义：
template <class datatype>
class LinkList
{
public:
LinkList( ); //建立只有头结点的空链表
LinkList(datatype a[ ], int n); //建立有n个元素的单链表
~LinkList(); //析构函数,释放整个链表空间
int Length(); //求单链表的长度
int Isempty(void)const;//判断表空，空1否0
datatype Get(int i); //取单链表中第i个结点的元素值
int Locate(datatype x); //求单链表中值为x的元素序号
void Insert(int i, datatype x);
//在单链表中第i个位置插入元素值为x的结点
datatype Delete(int i); //在单链表中删除第i个结点
void PrintList( );
//遍历单链表，按序号依次输出各元素
private:
Node<datatype> *head; //单链表的头指针
};

（2）初始化带头结点空单链表构造函数实现
输入：无
前置条件：无
动作：初始化一个带头结点的空链表
输出：无
后置条件：头指针指向头结点。
template <class datatype>
LinkList<datatype>:: LinkList( )//不带参数的构造函数
{
head=new Node<datatype>; head->next=NULL;
}

（3）利用数组初始化带头结点的单链表构造函数实现
输入：已存储数据的数组及数组中元素的个数
前置条件：无
动作：利用头插或尾插法创建带头结点的单链表
输出：无
后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员。
template <class datatype>
LinkList<datatype>:: LinkList(datatype a[ ], int n)//带参数的构造函数，尾插法
{ Node<datatype> *rear,*s;int i;
head=new Node<datatype>;
rear=head;
for (i=0; i<n; i++)
{
s=new Node<datatype>;
s->data=a[i];
s->next=NULL;
rear->next=s;
rear=rear->next;
}
}

（4）在带头结点单链表的第i个位置前插入元素e算法
输入：插入位置i，待插入元素e
前置条件：i的值要合法
动作：在带头结点的单链表中第i个位置之前插入元素e
输出：无
后置条件：单链表中增加了一个结点
template <class datatype>
void LinkList<datatype>::Insert(int i, datatype e)
{
Node<datatype> *p; int j;
p=head ; j=0;
//指针p初始化
while (p && j<i-1)
{
p=p->next; //指针p后移
j++;
} //找插入点

if (!p) throw "i不合法！";
else {
Node<datatype> *s;
s=new Node<datatype>;
s->data=e;
s->next=p->next;
p->next=s;
}
}

（5）在带头结点单链表中删除第i个元素算法
输入：删除第i个结点，待存放删除结点值变量e
前置条件：单链表不空，i的值要合法
动作：在带头结点的单链表中删除第i个结点，并返回该结点的值（由e传出）。
输出：无
后置条件：单链表中减少了一个结点
template <class datatype>
datatype LinkList<datatype>::Delete(int i)
{
Node<datatype> *p; int j;
p=head ; j=0;
while (p && j<i-1)
{
p=p->next;
j++;
}//找到第i-1个结点

if (!p | | !p->next)
throw “i不合法”;
else {
q=p->next;
e=q->data;
p->next=q->next;
delete q;
return e;
}
}

（6）遍历单链表元素算法
输入：无
前置条件：单链表不空
动作：遍历输出单链表中的各元素。
输出：无
后置条件：无
template <class datatype>
void LinkList<datatype>::PrintList( )
{ Node<datatype> *p;
p=head->next;//指向着结点
while (p)//P不为空时
{
cout<<p->data<<endl;
p=p->next;
}
}

（7）求单链表表长算法。
输入：无
前置条件：无
动作：求单链表中元素个数。
输出：返回元素个数
后置条件：无
template <class datatype>
int LinkList<datatype>::Length( )
{
Node <datatype> *p = head->next;
int i = 0;
while(p)
{
p = p->next;
i++;
}
return i;
}

（8）判单链表表空算法
输入：无
前置条件：无
动作：判表是否为空。
输出：为空时返回1，不为空时返回0
后置条件：无
template <class datatype>
int Linklist<datatype>::Isempty(void)const
{
if(head->next==NULL) return 1;
else return 0;
}
（9）获得单链表中第i个结点的值算法
输入：无
前置条件：i不空，i合法
动作：找到第i个结点。
输出：返回第i个结点的元素值。
后置条件：无
template <class datatype>
datatype LinkList<datatype>::Get(int i)
{
Node<datatype> *p; int j;//计数器
p=head->next; j=1; //或p=head; j=0;
while (p && j<i)
{
p=p->next; //工作指针p后移
j++;
}
if (!p) throw “i值不合法，超过了元素的个数！";
else return p->data;
}

(10)删除链表中所有结点算法（这里不是析构函数，但功能相同）
输入：无
前置条件：单链表存在
动作：清除单链表中所有的结点。
输出：无
后置条件：头指针指向空
template <class datatype>
void LinkList<datatype>:: FreeList()//释放单链表
{
Node<datatype> *p,*q;
p=head->next;
while (p!=NULL)
{q=p;
p=p->next;
delete q;
}
delete head;
}

(11)上机实现以上基本操作，写出main()程序：
参考p72
#include <iostream.h>
#include "LinkList.cpp"

void main()
{
LinkList <int> a;
cout<<"执行插入操作:"<<endl;
a.Insert(1,4);
a.Insert(2,5);
a.Insert(3,6);
a.Insert(4,7);
a.Insert(5,8);
cout<<"插入后的链表为:"<<endl;
a.PrintList();
cout<<endl;
cout<<"查找第1个结点的值为:"<<a.Get(1)<<endl;
cout<<"查找值为7的元素序号为:"<<a.Locate(7)<<endl;
cout<<"删除第2个结点后链表为:"<<endl;
a.Delete(2);
a.PrintList();
cout<<endl;
cout<<"判断此时链表是否为空(空1否0):"<<a.Isempty()<<endl;
int r[]=;
LinkList <int> b(r,5); //根据数组创建单链表
cout<<"根据数组创建单链表b为:"<<endl;
b.PrintList();
}
粘贴测试数据及运行结果：

2、参考单链表操作定义与实现，自行完成单循环链表的类的定义与相操作操作算法。
（1）利用数组初始化带头结点的单循环链表构造函数实现
输入：已存储数据的数组及数组中元素的个数
前置条件：无
动作：利用头插或尾插法创建带头结点的单循环链表
输出：无
后置条件：头指针指向头结点，且数组中的元素为链表中各结点的数据成员，尾指针指向头结点。
template <class T>
CirLinkList<T>::CirLinkList(T a[], int n)
{
head=new Node<T>; //生成头结点
Node<T> *r,*s;
r=head; //尾指针初始化
for (int i=0; i<n; i++)
{
s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点
r->next=s; r=s; //插入到终端结点之后
}
r->next=head; //单链表建立完毕，将终端结点的指针域指向头结点
}

（2）在带头结点单循环链表的第i个位置前插入元素e算法
输入：插入位置i，待插入元素e
前置条件：i的值要合法
动作：在带头结点的单循环链表中第i个位置之前插入元素e
输出：无
后置条件：单循环链表中增加了一个结点
template <class T>
void CirLinkList<T>::Insert(int i, T e)
{
Node<T> *p; int j;
p=head ; j=0; //工作指针p初始化
while (p->next!=head && j<i-1)
{
p=p->next; //工作指针p后移
j++;
}
if (j!=i-1) throw "i不合法";
else {
Node<T> *s;
s=new Node<T>;
s->data=e; //向内存申请一个结点s，其数据域为x
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
}
}

（3）在带头结点单循环链表中删除第i个元素算法
输入：删除第i个结点，待存放删除结点值变量e
前置条件：单循环链表不空，i的值要合法
动作：在带头结点的单循环链表中删除第i个结点，并返回该结点的值（由e传出）。
输出：无
后置条件：单循环链表中减少了一个结点
template <class T>
T CirLinkList<T>::Delete(int i)
{
Node<T> *p; int j;
p=head ; j=0; //工作指针p初始化
while (p->next!=head && j<i-1) //查找第i-1个结点
{
p=p->next;
j++;
}
if (j!=i-1) throw "i不合法"; //结点p不存在或结点p的后继结点不存在
else {
Node<T> *q; int x;
q=p->next; e=q->data; //暂存
p->next=q->next;
delete q;
return e;
}
}
（4）遍历单循环链表元素算法
输入：无
前置条件：单循环链表不空
动作：遍历输出单循环链表中的各元素。
输出：无
后置条件：无
template <class T>
void CirLinkList<T>::PrintList( )
{
Node<T> *p;
p=head->next;
while (p!=head)
{
cout<<p->data<<endl;
p=p->next;
}

}

(5)上机实现以上基本操作，写出main()程序：
#include <iostream.h>
#include "CirLinkList.cpp"
void main( )
{
int r[]=;
CirLinkList <int> a(r,5); //根据数组创建单链表
cout<<"单链表a为:"<<endl;
a.PrintList(); //输出单链表所有元素
cout<<"插入前单链表a的长度为:";
cout<<a.Length()<<endl;
cout<<"在最后插入元素8后单链表a为:"<<endl;
a.Insert(6,8);
a.PrintList();
cout<<"删除第二个元素后单链表a为:"<<endl;
a.Delete(2); //删除a中第二个元素
a.PrintList();
}

粘贴测试数据及运行结果：

3、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。
模板函数：
template <class datatype>
void LinkList<datatype>::MergeList1788(LinkList<datatype> &La,LinkList<datatype> &Lb)
{ Node<datatype> *pa,*pb,*pc;
pa=(La.head)->next; pb=(Lb.head)->next; pc=head=La.head;
while(pa&&pb) //将pa 、pb结点按大小依次插入Lc中
{
if(pa->data<=pb->data)
{
pc->next=pa; pc=pa; pa=pa->next;
}
else
{
pc->next=pb; pc=pb; pb=pb->next;
}
}
pc->next = pa?pa:pb ; //剩余
delete Lb.head; //释放头结点
}

main()
{
int a[7]=,b[8]=;
LinkList<int> S1(a,7),S2(b,8),S3;
cout<<"链表a:";
S1.PrintList();
cout<<"链表b:";
S2.PrintList();
S3.MergeList1788(S1,S2);
cout<<"归并后的链表c:";
S1.PrintList();
}
粘贴测试数据及运行结果：

Answer 2

插入的节点有可能是链表新的首节点，故此时需要改变表首指针的值，故传递参数时要传递其引用（node* &），或其指针（node* *） 。本回答被提问者采纳

Answer 3

int a = 0;
int &b=a;
b=3;
这时a的结果也是3，你可以试试。&表示引用，即变量的一个别名。对于函数参数，它相当于参数的地址传递。
接着上边；
int e =1;
int *c = &a;
int *&d=c;
这时c指向变量e，而不是a。自己思考一下吧