网站建设运营公司,河南万安建设集团有限公司网站,福州网站设计哪家比较好,微商管理系统实验三链表
一、实验目的与要求
1#xff09;熟悉链表的类型定义#xff1b;
2#xff09;熟悉链表的基本操作#xff1b;
3#xff09;灵活应用链表解决具体应用问题。
二、实验内容
1#xff09;请设计一个单链表的存储结构#xff0c;并实现单链表中基本运算算…实验三链表
一、实验目的与要求
1熟悉链表的类型定义
2熟悉链表的基本操作
3灵活应用链表解决具体应用问题。
二、实验内容
1请设计一个单链表的存储结构并实现单链表中基本运算算法。
编写程序linklist.cpp实现单链表的各种基本运算假设单链表元素类型ElemType为char并在此基础上设计主程序exp.cpp完成以下功能。
§ 初始化单链表。
§ 依次插入a,b,c,d,e元素。
§ 输出单链表的元素和长度。
§ 判断单链表是否为空。
§ 输出单链表的第3个元素。
§ 输出元素a的位置。
§ 在第4个元素位置上插入f元素。
§ 查找单链表的第3个元素如果在则删除如果不在则输出找不到。
§ 释放单链表。
2请设计一个职工文件emp.dat每个职工记录包含职工编号(no)、姓名(name)、部门号(depno)和工资数(salary)信息。设计一个单链表的存储结构完成以下功能
§ 从emp.dat文件中读取职工记录,并建立一个带头结点的单链表L。
§ 输入一个职工记录。
§ 显示所有职工记录。
§ 按职工编号no对所有职工记录进行递增排序。
§ 按部门号depno对所有职工记录进行递增排序。
§ 按工资数salary对所有职工记录进行递增排序。
§ 删除指定职工号的职工记录。
§ 删除职工文件中的全部记录。
§ 将单链表中的所有职工记录存储到职工文件emp.dat中。
3编写程序实现在带头结点的单链表 L 中删除一个最小值结点的算法。请写出算法思想。
三、实验结果
1请将调试通过的源代码粘贴在下面。代码注意书写规范、主要模块要有功能注释
第一题实验代码
#include iostream
#include cstdio
#include cstdlib
#include malloc.h
using namespace std;
typedef char ElemType;//定义单链表结点类型
typedef struct LNode{ElemType data;struct LNode *next;
}LinkList;//初始化单链表
void InitList(LinkList *L){//头节点创建 L(LinkList *)malloc(sizeof(LinkList));L-next NULL;
} //删除单链表
void DestroyList(LinkList *L){LinkList *pL;LinkList *qL-next ;while(q!NULL){free(p);pq;qp-next ;}free(p);
} //判断单链表是否为空
bool ListEmpty(LinkList *L){if(L-next NULL){return 0;//0 代表空 }else{return 1;//1 代表非空 }
}//单链表长度计算
int ListLength(LinkList *L){LinkList *pL;int i0;while(p-next !NULL){pp-next ;i;} return i;
} //输出单链表
void DispList(LinkList *L){LinkList *pL-next ;while(p-next !NULL){coutp-data ;pp-next ;}coutp-dataendl;
} //求某个元素的值 List Location Element
int GetElem(LinkList *L,int i,ElemType e){LinkList *pL;int j0;while(p!NULL ji){j;pp-next ;}if(pNULL){return 0;}else{ep-data;return 1;}
} //查找元素位置 List Element
int LocateElem(LinkList *L,ElemType e){LinkList *pL;int j0;while(p!NULL p-data e){j;pp-next ;}if(pNULL){return 0;}else{return j1; }
} //插入元素 - List Location Element
int ListInsert(LinkList *L,int i,ElemType e){LinkList *pL;LinkList *s;int j0;while(p!NULL ji-1){j;pp-next ;}if(pNULL){return 0;}else{s(LinkList *)malloc(sizeof(LinkList));s-data e;s-next p-next ;p-next s;return 1;}
}//删除元素 - List Location Element
int ListDelete(LinkList *L,int i,ElemType e){LinkList *pL;LinkList *s;int j0;while(p!NULL ji-1){j;pp-next ;}if(pNULL){return 0;}else{sp-next ;if(sNULL){return 0;}es-data ;p-next s-next ;free(s);return 1;}
}int main(){LinkList *h;ElemType e;coutendl初始化单链表endl;InitList(h);coutendl依次插入abcde元素endl;ListInsert(h,1,a);ListInsert(h,2,b); ListInsert(h,3,c); ListInsert(h,4,d); ListInsert(h,5,e); coutendl输出单链表的元素和长度endl;DispList(h);coutLength ListLength(h)endl;coutendl判断单链表是否为空endl;if(ListEmpty(h)1){cout单链表不为空endl;}else{cout单链表为空endl;}coutendl输出单链表的第3个元素endl;GetElem(h,3,e);couteendl;coutendl输出元素a的位置endl;int locationLocateElem(h,a);coutlocationendl;coutendl在第4个元素位置上插入f元素endl;ListInsert(h,4,f);DispList(h);coutLength ListLength(h)endl;coutendl查找单链表的第3个元素endl;int flagListDelete(h,3,e);if(flag1){cout元素存在已经删除endl;} else{cout元素不在无法删除endl;}DispList(h);coutLength ListLength(h)endl;coutendl释放单链表endl;DestroyList(h);return 0;
}第一题输出展示 第二题实验代码
#include cstdio
#include iostream
#include cstdlib
#include iomanip
using namespace std;//每个职工记录的基本信息建立
typedef struct w{int no;//职工编号(no)char name[10];//姓名(name)int depno;//部门号(depno)int salary;//工资数(salary)struct w* next;
}worker;//输入一个职工记录
void input(worker *L){worker *p(worker*)malloc(sizeof(worker));cout请输入该职工的基本信息endl; cin p-no p-name p-depno p-salary ;//头插法 p-nextL-next ;L-next p;cout已完成可输入2进行查询endl;
}//显示所有职工记录
void show(worker *L){worker *pL-next ;for(pL-next;p!NULL;pp-next ){cout nosetw(12)p-no namesetw(12)p-name depnosetw(12)p-depno salarysetw(12)p-salaryendl;}coutendl;
}//按照no排序
void no_sort(worker *L){worker *p,*q,*s;if(L-next NULL){cout当前链表为空endl;return;}qL-next-next;L-next-nextNULL;while(q!NULL){pL;while(p-next !NULL q-no p-next -no){pp-next ;}sq-next ;q-next p-next ;p-next q;qs;}cout已完成可输入2进行查询endl;
} //按照depno排序
void depno_sort(worker *L){worker *p,*q,*s;if(L-nextNULL){cout当前链表为空endl;return ;}qL-next -next;L-next -nextNULL;while(q!NULL){pL;while(p-next !NULL q-depno p-next -depno){pp-next ;}sq-next ;q-next p-next ;p-next q;qs;}cout已完成可输入2进行查询endl;
}//按照salary排序
void salary_sort(worker *L){worker*p,*q,*s; if(L-nextNULL){printf(链表为空\n);return;}qL-next-next;L-next-nextNULL;while(q!NULL){pL;while(p-next!NULL q-salary p-next-salary){pp-next;}sq-next;q-nextp-next;p-nextq;qs;}cout已完成可输入2进行查询endl;
}//删除指定职工号的职工记录
void listdelete(worker *L){worker *p,*temp;int num;cout请输入要删除职工的工号endl;cinnum;for(pL;p-next !NULL;pp-next ){if(p-next -nonum){tempp-next ;p-next temp-next;free(temp);break;}}cout已完成可输入2进行查询endl;
}//删除职工文件中的全部记录
void destroy(worker *L){worker *pL-next;worker *q;while(p!NULL){qp;pp-next;free(q);}L-nextNULL;cout已完成可输入2进行查询endl;
} //生成用户界面
void book(){coutendl;cout本链表可以进行以下操作endl; cout1输入一个职工记录endl; cout2显示所有职工记录endl;cout3按职工编号no对所有职工记录进行递增排序endl;cout4按部门号depno对所有职工记录进行递增排序endl;cout5按照工资数salary对所有职工记录进行递增排序endl;cout6删除制定职工号的职工记录endl;cout7删除职工文件中的全部记录endl;cout8结束本次操作endl;
}int main(){//初始化链表 worker*L(worker*)malloc(sizeof(worker));L-nextNULL;while(1){int opt;book();cout请输入以上数字进行职工信息操作; cinopt;switch(opt){case 1://输入一个职工记录 input(L);break;case 2:show(L);break;case 3:no_sort(L);break;case 4:depno_sort(L);break;case 5:salary_sort(L);break;case 6:listdelete(L);break;case 7:destroy(L);break;case 8:return 0;default:cout输入数字有误请重新输入endl; }}
}第二题输出展示
操作1 操作2 操作3 操作4 操作5 操作6 操作7 操作8 第三题实验代码
void delminnode(LinkNode *L){LinkNode *rL,*pL-next,*qp-next,*sp;//p总是指向最小结点r总是指向p的前驱结点q遍历s指向q的前驱结点while(q!NULL){if(p-data q-data){rs; //pq时r指向p pq; //p总是指向最小结点 qq-next; //q向后遍历 ss-next;}else{qq-next; ss-next;}} r-next p-next;free(p); //删除p结点
}2请分析你程序中每个功能模块的算法时间复杂度。
第一题 p从头结点开始遍历每经过一个非空元素就通过free(p)进行删除同时重置p为其后继结点q重置q为q的后继结点。由此可见时间复杂度为O(n)。 只需要对头结点的后继结点进行判断因为头结点不存放数据所以若后继结点非空则链表非空若后继结点为空则链表为空。由此可见时间复杂度为O(1)。 通过p遍历链表计算链表所存储的元素个数遇到空指针便结束计算。由此可见时间复杂度为O(n)。 通过p遍历链表输出链表所存储的每一个元素遇到空指针便结束输出。由此可见时间复杂度为O(n)。 本段代码是求指定位置的元素通过遍历单链表从头结点摸索到指定位置的结点并输出其对应的元素。由此可见时间复杂度为O(n)。 本段代码是求指定元素的位置通过遍历单链表从头结点摸索每一个位置的元素是否与已知元素等同若等同则输出相应的位置。由于初始化计数变量j是从0开始计数的因此在最后需要进行1操作。由此可见时间复杂度为O(n)。 本段代码是在指定位置插入指定元素通过while循环确定所需要插入的元素的前驱结点再插入指定元素。由此可见时间复杂度为O(n)。 本段代码是在指定位置删除元素思路与在指定位置插入指定元素类似主要是通过while循环确定所需要删除的元素的。由此可见时间复杂度为O(n)。 第二题 本段代码是直接插入一打数据不需要遍历单链表。由此可见时间复杂度为O(1)。 本段代码是通过从头结点遍历单链表找到每一个结点所存储的数据并输出。由此可见时间复杂度为O(n)。 本段代码是按照工号对职工信息进行排序实现过程主要是通过两个while循环。外层循环是从头结点遍历到最后一个结点并假设头结点所存的工号元素为最小值内层循环是比较下一个结点与当前结点所存工号元素的大小若不存在大小突变则继续通过p遍历单链表。由此可见时间复杂度为O(n²)。 本段代码是按照部门号对职工信息进行排序实现过程主要是通过两个while循环。外层循环是从头结点遍历到最后一个结点并假设头结点所存的部门号元素为最小值内层循环是比较下一个结点与当前结点所存部门号元素的大小若不存在大小突变则继续通过p遍历单链表。由此可见时间复杂度为O(n²)。 本段代码是按照工资对职工信息进行排序实现过程主要是通过两个while循环。外层循环是从头结点遍历到最后一个结点并假设头结点所存的工资元素为最小值内层循环是比较下一个结点与当前结点所存工资元素的大小若不存在大小突变则继续通过p遍历单链表。由此可见时间复杂度为O(n²)。 本段代码是删除指定的职工信息主要通过从头结点遍历单链表实现。当for循环中遇到与指定工号相同的工号元素时通过free()进行删除该元素组。由此可见时间复杂度为O(n)。 本段代码是删除指定的职工信息主要通过从头结点遍历单链表实现。通过while循环摸到该单链表的尾部在遇到每一个元素组的时候通过free()进行删除该元素组最后将头指针的后继结点重置为NULL。由此可见时间复杂度为O(n)。 第三题 算法思想q从头结点指向的下一个结点开始遍历直到链表结束每一次寻找到最小值就存入p中遇到更小的值就进行替换。遍历完成后最小值p且r为p的前驱结点然后删除p即可获得最终效果。由此可见时间复杂度为O(n)。 其他参考代码
#includeiostream
#includestdio.h
using namespace std;
#define Elemtype char //最后没有分号
//typedef LNode *LinkList; //LinkList和LNode* 是不同的名字但是他们是同一个指针类型命名的不同是为了概念上更加明确。
//这里的LinkList类型的指针变量L表示它是单链表的头指针LNode* 类型的指针变量表示它是指向某一结点的指针
class LNode{private:Elemtype data;LNode *next;public:LNode(){this-nextNULL;}/*void InitList_L(LNode* L) //链表初始化函数 {Lnew LNode;L-nextNULL; }void DestroyList_L(LNode* L) //对于结构体销毁函数 从 头结点 开始依次释放表中每一个节点所占用的存储空间 {LNode *p;pnew LNode; p-nextNULL; while(L) //如果L存放的东西不为空也即L指向的地方不为空那就接着循环。 这样可以找到最后一个结点 {pL; //p指向的地方和L指向的地方一样
//p仅仅指向现在的L指向的这一个地方即头结点每一次删头结点之前的第一个成为了头结点那就接着删
//确实是可以通过p把L里面的一个一个删除只删p的话就是只删了这一个结点 LL-next; //L是一个指针指向L这个结点也就是头结点。 L-next指的是第L1个结点也就是第一个结点 delete p; p-nextNULL; }}void ClearList_L(LNode* L) //对于结构体清空函数 从单链表 第一个 节点开始依次释放表中每一个节点所占用的存储空间 {LNode *p;LNode *q;pL-next; //L是头结点L存着的就是头结点的物理地址。所以L-next就是第一个节点的物理地址 qnew LNode; //所以用这样的方法new出来的就是这个地址的头结点 while(p){qp;pp-next;delete q;q-nextNULL;} L-nextNULL; } */void pushback(Elemtype t) //在链表最后面添加元素 {LNode *p;pnew LNode; //存放数据的LNode* 指针要new不new会出大问题。只用作遍历可以不new p-nextNULL;p-datat;LNode *pp; ppthis; while(pp-next!NULL){pppp-next;}pp-nextp;}void show() //按顺序输出链表元素 {LNode *p;pthis;while(p-next!NULL){coutp-next-data ;pp-next;//cout!endl;}}int getLength() //输出链表长度 {LNode* p;pthis;int i0;while(p-next!NULL){i;pp-next;}return i;}bool isEmpty() //判断链表是否为空表 {LNode *p;pthis;if(p-nextNULL){return 1;}else{return 0;}}Elemtype threeShow() //输出第三元素所在的位置 {LNode *p;pthis;int i0;for(i0;i3;i){pp-next;}return p-data;}int concernA() //判断字母a是否在链表里面如果在就输出位置 {LNode *p;pthis-next;int i0;while(1){if(p-dataa){break;}else{i;}pp-next;if(i5){break;}}if(i5){return 0;}else{return i1;}}void insert(Elemtype m,int n) //在指定地方插入元素 {int i0;LNode* p;pnew LNode;p-datam;p-nextNULL;LNode *q;qthis;for(i0;in-1;i){qq-next;}p-nextq-next;q-nextp;cout已经按需插入endl; }void Mydelete(int n) //删除指定位置的元素 {LNode *p;pthis;int i0;if((*this).getLength()n1){for(i0;in-1;i){pp-next;}LNode* q;qp-next;p-nextp-next-next;delete q;q-nextNULL;cout删除了第n个元素endl;}else if((*this).getLength()n){for(i0;in-1;i){pp-next;}LNode* q;qp-next;p-nextNULL;delete q;q-nextNULL;cout删除了第n个元素endl;}else{cout长度不足三没有第三个元素endl;}}~LNode() //析构函数 {coutendl析构函数调用endl;}/*~LNode() //析构函数 注意想删除头结点得用头删法从头开始删 {LNode *L;Lthis;LNode *p;pnew LNode;p-nextNULL;int i0;while(L){pL;LL-next;delete p;p-nextNULL;couti;i;} cout析构函数调用endl;}*/
};
int main()
{Elemtype t;LNode a;int i0;while(i5){cint;a.pushback(t); i;}cout链表长度为a.getLength()endl;if(a.isEmpty()1){cout链表为空endl;}else{cout链表不为空endl;}cout链表中第三个元素为a.threeShow()endl;if(a.concernA()0){cout没有字母aendl;} else{cout字母a的位置为a.concernA()endl;} Elemtype ff;a.insert(f,4);int pos3;a.show();coutendl;a.Mydelete(pos);a.show();
} #includeiostream
#includecmath
#includealgorithm
#includecstdio
#includecstring
#includecstdlib
#includefstream
#includevector
using namespace std;
typedef long long ll;
struct emp{int salary; //薪水string name,depno,id; //姓名、部门编号、职工号
};ostream operator (ostream out,const emp p) //输出流
{outp.id p.name p.depno p.salary;return out;
}
bool cmp1(emp a,emp b){return a.salaryb.salary;
}
templatetypename T
class List{private:T data;List *link;public:List();~List();void append(const T val); // 链尾增加一个元素void insertElement(int pos,const T val); // 在指定位置pos后添加一个元素valvoid deleteElement(const string val); // 删除所有值为val的元素 有析构函数时这个delete也可能引起析构函数的调用。 void travalList()const; // 从头节点遍历输出链表并输出长度bool isEmpty() const; //判断是否为空void elementPos(const int pos); //输出第pos1位置 因为从0开始计算void findElement(const T val); //输出b元素为val的位置void findDelete(const int pos); //查找并删除void deletetxt(); //删除文本内容void nwlist(); //读取职工记录void gtin(); //读入一个记录void sortSalary();//以下为排序void sortId();void sortDepno();void writeTxt();//写入文件
};templatetypename T
ListT::List(){linkNULL;
}templatetypename T
void ListT::append(const T val){List* headthis;while((head-link)!NULL){headhead-link;}ListT *a new List();a-dataval;head-linka;
}templatetypename T
void ListT::deleteElement(const string val)
{int flag0;List* headthis;while((head-link)!NULL){if(head-link-data.idval){flag1;List* tmphead-link;head-linktmp-link;tmp-linkNULL;delete tmp;continue;}if(head-linkNULL) break;headhead-link;}if(flag0){cout\nElement val not Found.;}
}templatetypename T
void ListT::travalList()const
{int l0;List* headthis-link;while(head!NULL){l;couthead-dataendl;headhead-link;}cout\nlength: lendl;
}templatetypename T
ListT::~List()
{if(this-link!NULL){delete this-link;this-linkNULL;}
}templatetypename T
void ListT::deletetxt()
{ofstream f(emp.dat,ios::trunc);f.close();
}templatetypename T
void ListT::nwlist()
{FILE* fp;fpfreopen(emp.dat,r,stdin);int l;cinl;for(int i1;il;i){emp tmp;cintmp.idtmp.nametmp.depnotmp.salary;this-append(tmp);}fclose(fp);
}templatetypename T
void ListT::gtin()
{emp tmp;cintmp.idtmp.nametmp.depnotmp.salary;this-append(tmp);
}templatetypename T
void ListT::sortSalary()
{vectoremp q;List* headthis-link;while(head!NULL){q.push_back(head-data);headhead-link;}for(int i0;iq.size()-1;i){for(int j0;jq.size()-1-i;j){if(q[j].salaryq[j1].salary){emp tmpq[j];q[j]q[j1];q[j1]tmp;}}}headthis-link;int l0;while(head!NULL){head-dataq[l];l;headhead-link;}
}templatetypename T
void ListT::sortId()
{vectoremp q;List* headthis-link;while(head!NULL){q.push_back(head-data);headhead-link;}for(int i0;iq.size()-1;i){for(int j0;jq.size()-1-i;j){if(q[j].idq[j1].id){emp tmpq[j];q[j]q[j1];q[j1]tmp;}}}headthis-link;int l0;while(head!NULL) {head-dataq[l];l;headhead-link;}
}templatetypename T
void ListT::sortDepno()
{vectoremp q;List* headthis-link;while(head!NULL){q.push_back(head-data);headhead-link;} for(int i0;iq.size()-1;i){for(int j0;jq.size()-1-i;j){if(q[j].depnoq[j1].depno){emp tmpq[j];q[j]q[j1];q[j1]tmp;}}}headthis-link;int l0;while(head!NULL){head-dataq[l];l;headhead-link;}
}templatetypename T
void ListT::writeTxt()
{FILE* fp;fpfreopen(emp.dat,w,stdout);vectoremp q;List* headthis-link;while(head!NULL){q.push_back(head-data);headhead-link;}coutq.size()endl;for(int i0;iq.size();i){coutq[i].id q[i].name q[i].depno q[i].salaryendl;}fclose(fp);
}int main()
{Listemp list;list.nwlist();list.travalList();list.sortSalary();list.travalList();list.sortDepno();list.travalList();list.deleteElement(001);list.travalList();list.deletetxt();list.writeTxt();return 0;
}//在单链表里面删除一个最小结点的算法
#includeiostream
#includestdio.h
using namespace std;
#define Elemtype double //最后没有分号
//typedef LNode *LinkList; //LinkList和LNode* 是不同的名字但是他们是同一个指针类型命名的不同是为了概念上更加明确。
//这里的LinkList类型的指针变量L表示它是单链表的头指针LNode* 类型的指针变量表示它是指向某一结点的指针
class LNode{private:Elemtype data;LNode *next;public:LNode(){this-nextNULL;}void pushback(Elemtype t) //在链表最后面添加元素 {LNode *p;pnew LNode; //存放数据的LNode* 指针要new不new会出大问题。只用作遍历可以不new p-nextNULL;p-datat;LNode *pp; ppthis; while(pp-next!NULL){pppp-next;}pp-nextp;}void show() //按顺序输出链表元素 {LNode *p;pthis;while(p-next!NULL){coutp-next-data ;pp-next;}}int getLength() //输出链表长度 {LNode* p;pthis;int i0;while(p-next!NULL){i;pp-next;}return i;}void Mydelete(int n,int flag) //删除指定位置的元素 {LNode *p;pthis;int i0;if((*this).getLength()n1){for(i0;in-1;i){pp-next;}LNode* q;qp-next;p-nextp-next-next;delete q;q-nextNULL;cout删除了第n个元素endl;}else if((*this).getLength()n){for(i0;in-1;i){pp-next;}LNode* q;qp-next;p-nextNULL;delete q;q-nextNULL;cout删除了第n个元素endl;}else{cout长度不足三没有第三个元素endl;}}~LNode() //析构函数 {coutendl析构函数调用endl;}void min(){LNode *p;pthis-next;int len(*p).getLength()1; //因为它此时初始位置为this-next而不是this,所以求出来长度少一 Elemtype s[10]{0},temp0;int i0,flag[100]{0},j0;for(i0;ilen;i){s[i]p-data;pp-next;}temps[0];for(i1;ilen;i){if(s[i]temp){temps[i];}}for(i0;ilen;i){if(s[i]temp){flag[j]i;j;}}int k0;for(k0;kj;k){(*this).Mydelete(flag[k]1,k);}}
};
int main()
{Elemtype t;LNode a;int i0;while(i5){cint;a.pushback(t); i;}a.show();a.min();a.show();
} /*LNode *p;pthis;LNode *f;fnew LNode;int i0;if(n1){fp-next;p-nextp-next-next;delete f;f-nextNULL;}if(n2flag1){fp-next;p-nextp-next-next;delete f;f-nextNULL;}for(i0;in-1-flag;i){pp-next;}fp-next;p-nextp-next-next;delete f;f-nextNULL;*/
