VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 203|回复: 2

[已解决]问一下这道链表的题目,谢谢大家!

[复制链接]
41_avatar_middle
最佳答案
0 
在线会员 发表于 2020-4-17 07:31:08 | 显示全部楼层 |阅读模式
15驿站币
#include<iostream>
using namespace std;
#include "LinkList.h"

#define N 10

LinkList<int> L;

void Insert()        //生成关键字有重复的链表
{       
        for(int i=1;i<=N;i++)
        {
                L.Insert(2*i-1,i);
                L.Insert(2*i,2*i);
        }
        for(int j=1;j<=N;j++)
                L.Insert(1,1);
}

void Distinct()        //请完成将关键字有重复的结点删除
{

}
int main()
{
        Insert();        //调用函数生成关键字有重复的链表
        //输出关键字有重复的链表
        cout<<"当前链表为:\n"<<L<<endl;
        Distinct();
        //输出关键字无重复的链表
        cout<<"删除关键字后当前链表为:\n"<<L<<endl;
        return 0;
}
其中linklist头文件为
#ifndef LINKLIST
#define LINKLIST
//存储结点类
template<class T>
class LinkNode    //结点类
{
template<class T>
friend class LinkList; //将链式表类声明为友类
public:
  LinkNode()//构造函数
  {
   next=NULL;
  }
  T data;    //结点元素
  LinkNode<T> *next;  //指向下一个结点的指针
};
//单向链表类
template<class T>
class LinkList
{
public:
  LinkList();  //构造函数
  ~LinkList();  //析构函数
  LinkList<T>& Insert(int k,const T& x);
  bool IsEmpty() const;  
  int GetLength() const;  
  bool GetData(int k,T& x);
  bool ModifyData(int k,const T& x);
  int Find(const T& x);
  LinkList<T>& DeleteByIndex(int k, T& x);
  LinkList<T>& DeleteByKey(const T& x,T& y);
  void OutPut(ostream& out);
public:
  LinkNode<T> *head;//指向链表的第一个头结点的指针
};
//构造函数的实现
template <class T>
LinkList<T>::LinkList()
{ //创建空单向链表
head=new LinkNode<T>();//创建头结点
}
//析构函数的实现
template <class T>
LinkList<T>::~LinkList()
{ //空单向链表
T x;
int len=GetLength();
for (int i=len;i>=1;i--)
  DeleteByIndex(i,x);     //释放所有结点
}
//实现插入新数据元素
template<class T>
LinkList<T>& LinkList<T>::Insert(int k,const T& x)
{
LinkNode<T> *p=head;      //p指向头结点
LinkNode<T> *newNode=new LinkNode<T>; //创建待插入的新结点
newNode->data =x;
int len=GetLength();
if ( k<1 || k>len+1 )       //插入新元素的位置错误
  cout<<"元素下标越界,添加元素失败";
else
{
  for( int i=1;i<k;i++)  
   p=p->next;      //将p移动到第k-1个结点
  newNode->next=p->next;    //在k处插入新结点
  p->next =newNode;
}
return *this;
}
//实现判断是否为空表
template<class T>
bool LinkList<T>::IsEmpty() const
{
return head->next==NULL;
}
//实现求当前表的长度
template<class T>
int LinkList<T>::GetLength() const
{
int length=0;
LinkNode<T> *p=head->next;
while(p)
{
  length++;
  p=p->next;
}
return length;
}
//实现按位置取元素
template<class T>
bool  LinkList<T>::GetData(int k,T& x)
{
LinkNode<T> *p=head->next;
int index=1;
if (k<0||k>GetLength())
  return false;
while (p!=NULL && index<k)
{
  index++;
  p=p->next;
}
if (p==NULL)
  return false;
else
{
  x=p->data;
  return true;
};
}
//实现按位置修改元素
template<class T>
bool LinkList<T>::ModifyData(int k,const T& x)
{
LinkNode<T> *p=head->next;
int index=1;
if (k<0||k>GetLength())
  return false;
while (p!=NULL && index<k)
{
  index++;
  p=p->next;
}
if (p==NULL)
  return false;
else
{
  p->data=x;
  return true;
};
}
//实现按关键字查找
template<class T>
int LinkList<T>::Find(const T& x)
{
LinkNode<T> * p=head->next;
int index=1;
while (p!=NULL && p->data !=x )
{
  p=p->next  ;
  index++;
}
if(p!=NULL)
  return index;
else
  return 0;
}
//实现按位置删除
template<class T>
LinkList<T>& LinkList<T>::DeleteByIndex(int k, T& x)
{
if (GetData(k,x))
   //判断是否有此元素,若果存在,则将该元素值放入x中,并返回true
{
  LinkNode<T> *p=head;   //p指向头结点
  LinkNode<T> *q=NULL;  //q指向空地址
  //删除中间或最后的结点
  for (int i=1;i<k;i++)
    p=p->next;   //将p指针移动到第k-1个结点
  q=p->next;     //q指向待删除的第k个结点
  p->next =q->next;    //将第k个结点从链表中移出
  delete q;      //物理删除该结点
}
else        //没有第k个结点,删除失败
  cout<<"元素下标越界,删除失败\n";
return *this;
}
//实现按关键字删除
template<class T>
LinkList<T>& LinkList<T>::DeleteByKey(const T& x,T& y)
{
int index=Find(x);     //得到要删除元素的位置
if (index!=0)
  return DeleteByIndex(index, y);
else
{
  cout<<"没有此元素,删除失败\n";
  return *this;
}
}
//实现单向链表的输出
template<class T>
void LinkList<T>:: OutPut(ostream& out)
{
LinkNode<T>* p=head->next;
while(p!=NULL)
{
  out<<p->data <<endl;
  p=p->next;
}
}
//重载插入运算符<<
template<class T>
ostream& operator<<(ostream& out, LinkList<T>& x)
{
x.OutPut(out);
return out;
}
#endif
请问一下怎么去写那个Distinct函数呢?这种题的方法是什么呢?
最佳答案
57_avatar_small
2020-4-17 07:31:09
本人表示有个疑问:
为什么楼主链表的头指针会指向一个节点。这样设计的原因是?head = new LinkNode<T>();
以下代码是Distinct的实现。
  1. void Distinct()        //请完成将关键字有重复的结点删除
  2. {
  3.         for (int i = 1; i <= L.GetLength(); )
  4.         {
  5.                 bool bDelete = false;
  6.                 int nValue = 0;
  7.                 bool bFlag = L.GetData(i,nValue);
  8.                 if (bFlag)
  9.                 {
  10.                         for (int j = i+1; j <= L.GetLength(); )
  11.                         {
  12.                                 int nTmp = 0;
  13.                                 bool bFlag = L.GetData(j, nTmp);
  14.                                 if (bFlag)
  15.                                 {
  16.                                         if (nTmp == nValue)
  17.                                         {
  18.                                                 L.DeleteByIndex(j, nTmp);
  19.                                                 bDelete = true;
  20.                                         }
  21.                                         else
  22.                                         {
  23.                                                 j++;
  24.                                         }
  25.                                 }
  26.                                 else
  27.                                 {
  28.                                         break;
  29.                                 }
  30.                         }
  31.                 }
  32.                 else
  33.                 {
  34.                         break;
  35.                 }

  36.                 if (bDelete)
  37.                 {
  38.                         L.DeleteByIndex(i, nValue);
  39.                 }
  40.                 else
  41.                 {
  42.                         ++i;
  43.                 }
  44.         }
  45. }
复制代码

最佳答案

查看完整内容

本人表示有个疑问: 为什么楼主链表的头指针会指向一个节点。这样设计的原因是?head = new LinkNode(); 以下代码是Distinct的实现。




上一篇:ReadString读取文本为什么只读了一行就退出不读了?
下一篇:小白对api函数有多个头文件的疑问
57_avatar_middle
最佳答案
22 
在线会员 发表于 2020-4-17 07:31:09 | 显示全部楼层    本楼为最佳答案   
bestAnswer
本人表示有个疑问:
为什么楼主链表的头指针会指向一个节点。这样设计的原因是?head = new LinkNode<T>();
以下代码是Distinct的实现。
  1. void Distinct()        //请完成将关键字有重复的结点删除
  2. {
  3.         for (int i = 1; i <= L.GetLength(); )
  4.         {
  5.                 bool bDelete = false;
  6.                 int nValue = 0;
  7.                 bool bFlag = L.GetData(i,nValue);
  8.                 if (bFlag)
  9.                 {
  10.                         for (int j = i+1; j <= L.GetLength(); )
  11.                         {
  12.                                 int nTmp = 0;
  13.                                 bool bFlag = L.GetData(j, nTmp);
  14.                                 if (bFlag)
  15.                                 {
  16.                                         if (nTmp == nValue)
  17.                                         {
  18.                                                 L.DeleteByIndex(j, nTmp);
  19.                                                 bDelete = true;
  20.                                         }
  21.                                         else
  22.                                         {
  23.                                                 j++;
  24.                                         }
  25.                                 }
  26.                                 else
  27.                                 {
  28.                                         break;
  29.                                 }
  30.                         }
  31.                 }
  32.                 else
  33.                 {
  34.                         break;
  35.                 }

  36.                 if (bDelete)
  37.                 {
  38.                         L.DeleteByIndex(i, nValue);
  39.                 }
  40.                 else
  41.                 {
  42.                         ++i;
  43.                 }
  44.         }
  45. }
复制代码

test.png
41_avatar_middle
最佳答案
0 
ico_lz  楼主| 发表于 2020-4-18 08:55:26 | 显示全部楼层
JLDawson 发表于 2020-4-17 13:51
本人表示有个疑问:
为什么楼主链表的头指针会指向一个节点。这样设计的原因是?head = new LinkNode();
...

保证不丢失头指针的值
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

×【发帖 友情提示】
1、请回复有意义的内容,请勿恶意灌水;
2、纯数字、字母、表情等无意义的内容系统将自动删除;
3、若正常回复后帖子被自动删除,为系统误删的情况,请重新回复其他正常内容或等待管理员审核通过后会自动发布;
4、感谢您对VC驿站一如既往的支持,谢谢合作!

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号 )|网站地图wx_jqr

GMT+8, 2020-10-24 22:24

Powered by CcTry.CoM

© 2009-2020 cctry.com

快速回复 返回顶部 返回列表