链表长度

struct node {

int data;

struct node next;

} ;

创建单链表后，最后一个结点的next是NULL，据此来遍历表，获得长度。

void get_len( struct node head )

{

struct node p=head->next ;

int len=0;

while ( p )

{

len++;

p=p->next;

}

head->data=len ; //存储长度到头结点

}

请采纳答案，支持我一下。

如果不是循环链表要做以下规定的：

表头的prev指针必须初始化为NULL

表尾的next指针必须初始化为NULL

于是计算链表长度可以从表头开始迭代，每次迭代计数加一，当遇到next为NULL时结束迭代，结束之后链表的长度就计算出来了。

新建节点时要养成习惯，prev和next未链接的要赋值为NULL

以前做过的实验报告，应该很全，全给你了

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 <iostreamh>

#include "LinkListcpp"

void main()

{

LinkList <int> a;

cout<<"执行插入 *** 作:"<<endl;

aInsert(1,4);

aInsert(2,5);

aInsert(3,6);

aInsert(4,7);

aInsert(5,8);

cout<<"插入后的链表为:"<<endl;

aPrintList();

cout<<endl;

cout<<"查找第1个结点的值为:"<<aGet(1)<<endl;

cout<<"查找值为7的元素序号为:"<<aLocate(7)<<endl;

cout<<"删除第2个结点后链表为:"<<endl;

aDelete(2);

aPrintList();

cout<<endl;

cout<<"判断此时链表是否为空(空1否0):"<<aIsempty()<<endl;

int r[]={1,2,3,4,5};

LinkList <int> b(r,5); //根据数组创建单链表

cout<<"根据数组创建单链表b为:"<<endl;

bPrintList();

}

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

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 <iostreamh>

#include "CirLinkListcpp"

void main( )

{

int r[]={3,4,5,6,7};

CirLinkList <int> a(r,5); //根据数组创建单链表

cout<<"单链表a为:"<<endl;

aPrintList(); //输出单链表所有元素

cout<<"插入前单链表a的长度为:";

cout<<aLength()<<endl;

cout<<"在最后插入元素8后单链表a为:"<<endl;

aInsert(6,8);

aPrintList();

cout<<"删除第二个元素后单链表a为:"<<endl;

aDelete(2); //删除a中第二个元素

aPrintList();

}

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

3、采用链式存储方式，并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表，将其归并为新线性表Lc，该线性表仍有序（未考虑相同时删除一重复值）的算法。

模板函数：

template <class datatype>

void LinkList<datatype>::MergeList1788(LinkList<datatype> &La,LinkList<datatype> &Lb)

{ Node<datatype> pa,pb,pc;

pa=(Lahead)->next; pb=(Lbhead)->next; pc=head=Lahead;

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 = papa:pb ; //剩余

delete Lbhead; //释放头结点

}

main()

{

int a[7]={1,2,3,4,5,6,7},b[8]={2,3,6,7,8,9,11,12};

LinkList<int> S1(a,7),S2(b,8),S3;

cout<<"链表a:";

S1PrintList();

cout<<"链表b:";

S2PrintList();

S3MergeList1788(S1,S2);

cout<<"归并后的链表c:";

S1PrintList();

}

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

以上就是关于链表长度全部的内容，包括:链表长度、如何用函数获取双向链表长度、求c++链表程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！