静态链表为什么实现不了数据反转,哪里错了,具体的代码如何实现?
//vc6.0实现的C++版
//功能:静态链表实现线性表的基本功能
#include <iostream.h>//读入必须包含的头文件
#include <windows.h>//清屏和颜色设置需要
#include <iomanip.h>

enum returninfo{success,fail,overflow,underflow,range_error};//定义返回信息清单
#define NULLP -1//静态链表的空地址模拟
const int MAXSIZE=10;//静态链表的总空间大小

class node
{
public:
    int data;//数据域
    int next;//指针域
};

/*
定义一个线性表类staticlinklist
*/
class staticlinklist
{
private:
    node dataarray[MAXSIZE];//定义静态链表的数组
    int freep,headp;//freep管理空闲空间,headp管理实际线性表空间
    int count;//计数器 统计结点个数即线性表的长度
public:
    staticlinklist();//构造函数
    ~staticlinklist();//析构函数
    int getnewnode(void);//申请一个新的可用空间
    returninfo create(int number);//静态链表的初始化
    bool empty(void) const;//判断是否空链
    int size(void) const;//求静态链表的长度
    void deletenode(int position);//把某个空间地址归还给空闲空间
    returninfo traverse(void);//遍历静态链表所有元素
    returninfo retrieve(int position,int &item) const;//读取一个结点
    returninfo replace(int position,const int &item);//修改一个结点
    returninfo insert(int position,const int &item);//插入一个结点
    returninfo remove(int position);//删除一个结点
    returninfo invertlist(void);//静态链表所有数据反转
    void showinfo(void);//显示静态链表相关信息
};

staticlinklist::staticlinklist()//构造函数
{
    //静态链表初始化,约定开始时地址域为从小到大顺序挂链,最后一个为NULLP(即-1)
    int i;
    for(i=0;i<MAXSIZE;i++)
        dataarray[i].next=i+1;
    dataarray[MAXSIZE-1].next=-1;
    freep=0;//设置空闲区的指针
    count=0;//计数器清零,表明开始时没有实际数据
    headp=NULLP;
}

staticlinklist::~staticlinklist()//析构函数
{
}

staticlinklist::getnewnode(void)
{
    int tempaddress;//定义一个临时地址指针
    tempaddress=freep;//保存目前可用空间的第一个地址
    freep=dataarray[freep].next;//可用空间头指针后移
    return tempaddress;
}

returninfo staticlinklist::create(int number)//静态链表的初始化
{
    int tempaddress,tempp;
    cout<<"请依次输入数据(用空格隔开):";
    for(int i=1;i<=number;i++)
    {
        tempaddress=getnewnode();
        cin>>dataarray[tempaddress].data;
        dataarray[tempaddress].next=NULLP;
        count++;
        if(i==1)//挂第一个结点
        {
            headp=tempaddress;
            tempp=headp;
        }
        else//挂其他结点
        {
            dataarray[tempp].next=tempaddress;
            tempp=tempaddress;
        }
    }
    return success;
}

bool staticlinklist::empty(void) const//判断是否空链
{
    if(headp==NULLP)
        return true;
    else
        return false;
}

int staticlinklist::size(void) const//求静态链表的长度
{
    return count;
}

void staticlinklist::deletenode(int position)
{
    dataarray[position].next=freep;
    freep=position;
}

returninfo staticlinklist::traverse(void)//遍历静态链表中的所有元素
{
    int searchp;//启用搜索指针
    if(empty())
        return underflow;//空表的处理
    searchp=headp;
    cout<<"静态链表中的全部数据为:Headp->";//提示显示数据开始
    while(searchp!=NULLP)//循环显示所有数据
    {
        cout<<"["<<dataarray[searchp].data;
        if(dataarray[searchp].next==NULLP)
            cout<<"|^]";
        else
            cout<<"|-]->";
        searchp=dataarray[searchp].next;
    }
    cout<<endl;//最后有一个回车的控制
    return success;//本次操作成功
}

returninfo staticlinklist::retrieve(int position,int &item) const//读取一个结点
{
    if(empty())//处理意外,空表
        return underflow;   
    if(position<=0||position>=count+1)       //处理意外,范围不正确
        return range_error;
    int searchp=headp;//定义搜索指针,初始化
    for(int i=1;i<position&&searchp!=NULLP;i++)//提示:注意小于号
        searchp=dataarray[searchp].next;//顺序访问方式,用循环,算法复杂度是O(n)
    item=dataarray[searchp].data;//返回读取的数据
    return success;//本次操作成功
}

returninfo staticlinklist::replace(int position,const int &item)//修改一个结点
{
    if(empty())//处理意外,空表
        return underflow;   
    if(position<=0||position>=count+1)       //处理意外,范围不正确
        return range_error;
    int searchp=headp;//定义搜索指针,初始化
    for(int i=1;i<position&&searchp!=NULLP;i++)//提示:注意小于号
        searchp=dataarray[searchp].next;//顺序访问方式,用循环,算法复杂度是O(n)
    dataarray[searchp].data=item;//实际修改数据的语句
    return success;//本次操作成功
}

returninfo staticlinklist::insert(int position,const int &item)//插入一个结点
{
    if(position<=0||position>=count+2)       //处理意外,范围不正确
        return range_error;
    int newnodep,searchp=headp,followp=NULLP;
    newnodep=getnewnode();//此处需要申请新的一个可用空间,地址赋给newnodep
    if(newnodep==NULLP)
        return overflow;
    dataarray[newnodep].data=item;//给数据赋值
    if(position==1)
    {
        dataarray[newnodep].next=headp;
        headp=newnodep;
        count++;
        return success;
    }
    for(int i=1;i<position&&searchp!=NULLP;i++)//以下为查找插入位置
    {
        followp=searchp;
        searchp=dataarray[searchp].next;
    }
    //以下开始修改链表,完成插入数据
    dataarray[newnodep].next=dataarray[followp].next;//注意此处的次序相关性
    dataarray[followp].next=newnodep;
    count++;//计数器加1
    return success;
}

returninfo staticlinklist::remove(int position)//删除一个结点
{
    if(empty())//处理意外,空表
        return underflow;   
    if(position<=0||position>=count+1)       //处理意外,范围不正确
        return range_error;
    int searchp=headp,followp=NULLP;//这里两个指针的初始值设计一前一后
    if(position==1)
    {
        searchp=headp;
        headp=dataarray[headp].next;
        deletenode(searchp);//释放该结点空间
        count--;//计数器减1
        return success;
    }
    for(int i=1;i<position&&searchp!=NULLP;i++)
    {
        followp=searchp;
        searchp=dataarray[searchp].next;
    }
    dataarray[followp].next=dataarray[searchp].next;//删除结点的实际语句
    deletenode(searchp);//释放该结点
    count--;//计数器减1
    return success;
}

returninfo staticlinklist::invertlist(void)//静态链表所有数据反转
{
    int nowp,midp,lastp;//启用多个辅助指针
    if(empty())
        return underflow;
    nowp=dataarray[headp].next;
    midp=NULLP;
    while(nowp!=NULLP)
    {
        lastp=midp;
        midp=nowp;
        nowp=dataarray[nowp].next;
        dataarray[midp].next=lastp;
    }
    dataarray[headp].next=midp;
    return success;
}

void staticlinklist::showinfo(void)//显示静态链表相关信息
{
    int searchp;
    cout<<"目前静态链表总空间:"<<setw(3)<<MAXSIZE<<"地址为(0--"<<MAXSIZE-1<<")"<<endl;
    cout<<"其中自由空间大小为:"<<setw(3)<<MAXSIZE-count<<"编号为:";
    searchp=freep;
    while(searchp!=NULLP)
    {
        cout<<" "<<searchp;
        searchp=dataarray[searchp].next;
    }
    cout<<endl;
    cout<<"线性表的已用空间为:"<<setw(3)<<count<<"编号为:";
    searchp=headp;
    while(searchp!=NULLP)
    {
        cout<<" "<<searchp;
        searchp=dataarray[searchp].next;
    }
    cout<<endl;
}

/*
定义一个实现静态链表功能的菜单处理类interfacebase 
*/
class interfacebase
{
private:
    staticlinklist listonface;
public:
    void clearscreen(void);//清屏
    void showmenu(void);//显示菜单函数
    int userchoice(void);//用户的选项
    returninfo processmenu(int menuchoice);//菜单函数
};

void interfacebase::clearscreen(void)
{
    system("cls");
}

void interfacebase::showmenu(void)
{
    cout<<"静态链表基本功能菜单"<<endl;
    cout<<"=================="<<endl;
    cout<<"1.输入数据(键盘输入)"<<endl;
    cout<<"2.显示数据(遍历全部数据)"<<endl;
    cout<<"3.修改数据(要提供位置和新值)"<<endl;
    cout<<"4.插入数据(要提供位置和新值)"<<endl;
    cout<<"5.删除数据(要提供位置)"<<endl;
    cout<<"6.读取数据(要提供位置)"<<endl;
    cout<<"7.求表长度"<<endl;
    cout<<"8.数据反转(全部数据逆序存储)"<<endl;
    cout<<"9.静态链表相关信息"<<endl;
    cout<<"0.退出程序"<<endl;
    cout<<"=================="<<endl;
}

int interfacebase::userchoice(void)
{
    int menuchoice;
    cout<<"请输入您的选择:";
    cin>>menuchoice;
    return menuchoice;
}

returninfo interfacebase::processmenu(int menuchoice)
{
    int position,item,returnvalue;
    switch(menuchoice)//根据用户的选择进行相应的操作
    {
    case 1:
        cout<<"请问你要输入数据的个数,注意要在"<<MAXSIZE<<"个以内:";
        cin>>item;
        if(item>MAXSIZE)
            cout<<"对不起,输入数据超限,操作已取消!请按任意键继续..."<<endl;
        else
        {
            returnvalue=listonface.create(item);
            if(returnvalue==success)
                cout<<"建立静态链表操作成功!请按任意键继续..."<<endl;
        }
        break;
    case 2:
        returnvalue=listonface.traverse();
        if(returnvalue==underflow)
            cout<<"静态链表目前为空,没有数据可以显示!请按任意键继续..."<<endl;
        else
            cout<<"静态链表遍历操作成功!请按任意键继续..."<<endl;
        break;
    case 3:
        cout<<"请输入要修改数据的位置:";
        cin>>position;
        cout<<"请输入要修改的新数据:";
        cin>>item;
        returnvalue=listonface.replace(position,item);
        if(returnvalue==underflow)
            cout<<"对不起,静态链表已空!请按任意键继续..."<<endl;
        else if(returnvalue==range_error)
            cout<<"对不起,修改的位置超出了范围!请按任意键继续..."<<endl;
        else
            cout<<"修改操作成功!请按任意键继续..."<<endl;
        break;
    case 4:
        cout<<"请输入要插入数据的位置:";
        cin>>position;
        cout<<"请输入要插入的新数据:";
        cin>>item;
        returnvalue=listonface.insert(position,item);//注意这个位置的参数
        if(returnvalue==overflow)
            cout<<"对不起,静态链表溢出,无法插入新数据!请按任意键继续..."<<endl;
        else if(returnvalue==range_error)
            cout<<"对不起,插入的位置超出了范围!请按任意键继续..."<<endl;
        else
            cout<<"插入操作成功!请按任意键继续..."<<endl;
        break;
    case 5:
        cout<<"请输入要删除数据的位置:";
        cin>>position;
        returnvalue=listonface.remove(position);//注意这个位置的参数
        if(returnvalue==underflow)
            cout<<"对不起,静态链表已空!请按任意键继续......"<<endl;
        else if(returnvalue==range_error)
            cout<<"对不起,删除的位置超出了范围!请按任意键继续..."<<endl;
        else
            cout<<"删除操作成功!请按任意键继续..."<<endl;
        break;
    case 6:
        cout<<"请输入要读取数据的位置:";
        cin>>position;
        returnvalue=listonface.retrieve(position,item);
        if(returnvalue==underflow)
            cout<<"对不起,静态链表已空!请按任意键继续......"<<endl;
        else if(returnvalue==range_error)
            cout<<"对不起,读取的位置超出了范围!请按任意键继续..."<<endl;
        else
            cout<<"读取的数据为:"<<item<<endl<<"读取操作成功!请按任意键继续..."<<endl;
        break;
    case 7:
        cout<<"静态链表目前的长度为:"<<listonface.size()<<endl;
        cout<<"求静态链表长度操作成功!请按任意键继续..."<<endl;
        break;
    case 8:
        returnvalue=listonface.invertlist();
        if(returnvalue==underflow)
            cout<<"对不起,链表已空!请按任意键继续......"<<endl;
        else
            cout<<"链表所有元素反转操作成功!请按任意键继续..."<<endl;
        break;
    case 9:
        listonface.showinfo();
        break;
    case 0:
        exit(0);
    default:
        cout<<"对不起,您输入的功能编号有错!请重新输入!!!"<<endl;
        break;
    }
    return success;
}

/*
程序主入口
*/
void main(void)
{
    int menuchoice;//定义变量,菜单选单项的选择
    interfacebase interfacenow;
    staticlinklist linklistnow;
    system("color f0");//修改屏幕的背景色和字的颜色
    interfacenow.clearscreen();//清屏
    while(1)//永真循环
    {
        interfacenow.showmenu();//显示菜单
        menuchoice=interfacenow.userchoice();//获取用户的选择
        interfacenow.processmenu(menuchoice);//处理用户的选择
        system("pause");//暂停
        interfacenow.clearscreen();//清屏
    }
}//主函数结束
c++

2个回答

returninfo staticlinklist::invertlist(void)//静态链表所有数据反转
{
    int nowp,midp,lastp;//启用多个辅助指针
    if(empty())
        return underflow;
    nowp=dataarray[headp].next;
    midp=NULLP;
    int num=0;
    while(nowp!=NULLP)
    {
        lastp=midp;
        midp=nowp;
        nowp=dataarray[nowp].next;
        if(num==0)
        {
            dataarray[midp].next=headp;
            dataarray[headp].next=NULLP;
        }
        else
            dataarray[midp].next=lastp;
        num++;
    }
    headp=midp;
    return success;
}

一个for循环解决了,数据翻转把类内data翻转一下就行了

returninfo staticlinklist::invertlist(void)//静态链表所有数据反转
{
    if (empty())
        return underflow;

    for (int i = 0; i < count / 2; i++)
    {
        int swap = dataarray[i].data;
        dataarray[i].data = dataarray[count-i-1].data;
        dataarray[count - i - 1].data = swap;
    }
    return success;

    //int nowp, midp, lastp;//启用多个辅助指针
    //if (empty())
    //  return underflow;
    //nowp = dataarray[headp].next;
    //midp = NULLP;
    //while (nowp != NULLP)
    //{
    //  lastp = midp;
    //  midp = nowp;
    //  nowp = dataarray[nowp].next;
    //  dataarray[midp].next = lastp;
    //}
    //dataarray[headp].next = midp;
    //return success;
}
qq_42660156
追忆~似水年华 谢谢,但是进行了插入和删除操作后,数据反转后顺序还是乱的
4 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!