数据结构习题（单链表）

昨天写的CSDN不知道怎么了，记得已经发出去了，竟然没有发出去

针对带头节点的单链表，编写以下函数//默认为程序内的函数

其实我觉得用外部传入的更严谨，而且使用范围更广

结点类LinkNode

单链表类List

头结点first

下一指针域 link

数据域data

（1）定位函数 Locate:在单链表中遍历在单链表中寻找第i个结点，若找到，则函数返回第i个结点的地址，找不到返回NULL；

template

LinkNode*List::Search(int i)//返回类型

{

if(i<0)//条件判断

{

cout<<"请检查i的输入"<

return NULL;

}

LinkNode*p=first;

int k=0;

while(p->link！=NULL&&k

k++

p=p->link;//移动

}

return  p;//返回结点的地址，如果没有的话当然返回NULL

}

2 求最大值函数max,通过一趟遍历在单链表中确定值最大的结点

template //类模板

 LinkNode *LIst::max()//找到则返回地址，所以返回类型为结点类型

{

LinkNode* p=first->link;//从第一个结点对结点进行赋值，因为有头结点，所以为link

LinkNode*m=first->link;//假设第一个结点为最大的值

while(p->link!=NULL)

{

p=p->link;

if(p->data>m->data)//在遍历中每次与最大的结点进行比较

{

m=p;//记录下最大的结点

}

}

return m;//循环结束，m即为找到的最大值，返回即可

}

（3）统计函数number:统计单链表中所有与给定值x相同的元素的个数

template

int List::number( T x)//返回类型为int,因为为元素个数

{

LinkNode *p=first->link;//从头节点开始

int k=0;//计数变量

while(p->link!=NULL)

{

p=p->link;//移动

if（p->data==x)

k++；//统计元素加1

}

return k;//返回元素个数

}

（4）建立函数create;根据一维数组a[n]建立一个单链表，使得链表中各元素的次序与a[n]中各元素的次序相同要求该程序的时间复杂度为O(n).（外部传入）

template

LinkNode *create(T a[],int n)//以数组作为参数传入函数

{

if(n==0)

return NULL;//条件判断

LinkNode* first =new LinkNode;//开辟头结点空间，返回头节点

LinkNode*p=first;//建立工作指针

for(int i=0;i

{

p=p->link=new LinkNode(a[i));//这一步是关键
 

}

return first;//返回头节点

}

5

整理函数tidyup:在非递减的有序的单链表中删除值相同的多余结点

template

LinkNode *tidyup(List&L)//传入参数

{

if（L->next==NULL)

return NULL;//空链表

LinNode*q;//用于删除

LinkNode*p=L->link;//用于遍历

T same=p->data;//记录下当前的值

while(p->link!=NULL)//结束条件

{

if（p->next->data==same)//找到就删除

{

q=p->next;//保存

p->next==q->next;//移动

delete p；

}

else

{

p=p->next;//移动

same=p->data;//记录下当前的值  这句是关键

}

}

}