一、实验目的
深入掌握单链表应用的算法设计。
二、实验内容及要求
内容:设有一个职工文件emp.dat,每个职工记录包含职工编号(no)、姓名(name)、部门号(depno)和工资数(salary)信息。设计一个程序exp2-11.cpp完成以下功能:
(1)从emp. dat文件中读出职工记录,并建立一个带头结点的单链表L。
(2)输人一个职工记录。v
(3)显示所有职工记录。√
(4)按编号no对所有职工记录进行递增排序
(5)按部门号depno对所有职工记录进行递增排序。
(6)按工资数salary对所有职工记录进行递增排序。
(7)删除指定职工号的职工记录。
(8)删除职工文件中的全部记录。
(9)将单链表L中的所有职工记录存储到职工文件emp. dat中。
三、算法设计
（1）职工信息的综合运算功能
建立为职工创建相应的类，再通过单链表对职工信息进行存储。将职工信息单链表进行封装，实现对职工信息的文件读入和文件写入、职工信息的删除和添加、职工信息的查询和显示。并通过相应的gui程序实现对职工信息操作的可视化。
（2）算法思想
?????? 顺序表：
?????? 将线性表中的所有元素按照其逻辑顺序依次存储到计算存储器中指定存储位置开始的一块连续的存储空间中。
?????? 链表：
?????? 链表的每个存储节点不仅包含元素本身的信息（数据域），还包含表示元素之间逻辑关系的信息（指针域）。数据域用于存储数据，指针域来存储其逻辑相邻元素的物理存储地址。
（3）算法描述：
?????? 顺序表：
?????? 创建顺序表：将需要初始化值依依对应的复制到顺序表中。
?????? 输出顺序表：从前往后遍历顺序表的每一个位置，并将其位置上的元素输出。
?????? 获取某一位置元素值：直接通过位置下标获取这一位置的值并返回。
?????? 获取某一元素值的位置：从前往后遍历顺序表并比对，相同则返回这一位置 下标。
?????? 在某一位置插入元素：将这一位置后面的元素对应后移，然后将需要添加的元素加入这一位置。
?????? 删除某一位置的元素：将这一位置的元素值返回，然后将这一位置后的元素依依前移一个位置。
?????? 链表：
?????? 头插法：将第一个有数据的节点保存到需要添加的节点的地址域中，然后将需要添加节点地址保存到头节点的地址域中。
?????? 尾插法：从头节点遍历找到尾节点的地址，然后将需要添加节点的位置保存到尾节点的地址域中，并将需要添加节点的地址域置为NULL。
?????? 输出链表所有元素：从第一个有数据的节点开始，遍历所有节点，并输出其数据域的数据。
?????? 按元素值查询：从第一个有数据的节点开始，将查询元素值与节点数据域中对应的数据值进行比对，相同则返回，否者继续。重复此操作直到尾节点。
?????? 按元素值删除：从第一个有数据的节点开始，将查询元素值与节点数据域中对应的数据值进行比对，相同则删除。重复此操作直到尾节点，。
?????? 排序：遍历链表，将所有节点中的数据保存到数组中，然后对数组进行排序，最后利用数组中有序的数据进行连接成 新的逻辑顺序的链表。
四、算法实现
//从文件读入职工信息
void ListWorker::ReadToList()
{
??? ??? QFile infile;
??? ??? Worker *p,*pnew;
??? ??? int newNo,newDepno;
??? ??? double newSalary;
??? ??? QString newName;
??? ??? p=H;
??? ??? infile.setFileName("data/worker1.dat");
??? ??? infile.open(QIODevice::ReadOnly);
??? ??? if(!infile.isOpen())
??? ??? {
??????? ?????? qDebug()<<QString("open file failure");
??????? ?????? return;
??? ??? }
??? ??? QDataStream stream(&infile);
??? ??? stream>>length;
??? ??? pnew=Q_NULLPTR;
??? ??? for(int i=0;i<length;i++)
??? ??? {
??????? ??????? stream>>newNo>>newName>>newSalary>>newDepno;
???? ????????? pnew=new Worker;
??????? ?????? pnew->SetNo(newNo);
??????? ?????? pnew->SetName(newName);
??????? ?????? pnew->SetDepno(newDepno);
??????? ?????? pnew->SetSalary(newSalary);
??????? ?????? pnew->SetPnext(Q_NULLPTR);
??????? ?????? p->SetPnext(pnew);
??????? ?????? p=pnew;
??? ??? }
??? ??? head=H->GetPnext();
??? ??? tail=pnew;
??? ??? infile.close();
}
//插入职工信息
??? bool ListWorker::Insert(Worker a)
{
?? ???? Worker *p;
?? ???? p=new Worker;
??? ??? p->SetNo(a.GetNo());
??? ??? p->SetName(a.GetName());
??? ??? p->SetDepno(a.GetDepno() );
??? ??? p->SetSalary(a.GetSalary() );
??? ??? p->SetPnext(Q_NULLPTR);
??? ??? if(tail==Q_NULLPTR)
??? ??? {
?????? ??????? H->SetPnext(p);
?????? ??????? head=tail=p;
??? ??? }
??? ??? else
??? ??? {
??????? ?????? tail->SetPnext(p);
??????? ?????? tail=p;
??? ??? }
??????? length++;
??? ??? return true;
}
//按职工编号增序排序
bool ListWorker::SortNo()
{
??? struct data no[length];
??? Worker *p=head;
??? if(head==Q_NULLPTR) return false;
??? for(int i=0;i<length;i++)
??? {
??????? no[i].n=p->GetNo();
??????? no[i].p=p;
??????? p=p->GetPnext();
??? }
??? sort(no,no+length,cmp);
??? p=H;
??? for(int i=0;i<length;i++)
??? {
??????? p->SetPnext(no[i].p);
??????? p=p->GetPnext();
??? }
??? p->SetPnext(Q_NULLPTR);
??? head=H->GetPnext();
??? tail=p;
??? return true;
}
。。。。。。
五、程序运行截图
?
?
?
?
?
?
?
?