1.实验题目
教材P77，习题三的“四、应用题”的第1、4、6题。
1.在顺序表中设计函数实现以下操作：
（1）从顺序表中删除具有最小值的元素（假设顺序表中元素都不相同），并由函数返回被删元素的值，空出的位置由最后一个元素填补。
（2）从顺序表中删除具有给定值e的所有元素。
（3）在一个顺序表中如果一个数据值有重复出现，则留下第一个这样的数据值，并删除其他所有重复的元素，使表中所有元素的值均不相同。
4．针对带头结点的单链表，试编写下列函数：
（1）定位函数：在单链表中寻找第i个结点。若找到，则返回第i个结点的 地址，否则返回空指针。
（2）统计函数：统计单链表中等于给定值e的元素个数。
6．设计一个带头结点的有序单链表类。实现以下函数：
（1）插入函数：把元素值e作为数据元素插入表中。
（2）删除函数：删除数据元素等于e的结点。
2.实验要求
1.对于第1、4题可以直接使用教材上定义的顺序表类和单链表类。
2.对于第6题也可以直接使用教材上定义的单链表类，并假设定义的对象中的数据是有序的。
3.可以在教材定义的基础上，增加你的算法为成员函数。也可以设计成类外部的模板函数，可以通过调用已定义的顺序表类和单链表类中的成员函数来实现。
3.算法思路
1(1)
从顺序表中删除具有最小值的元素（假设顺序表中元素都不相同），并由函数返回被删元素的值，空出的位置由最后一个元素填补。
先假设具有最小值的元素在顺序表第0位，记录下最小值的元素的位置pos。遍历顺序表，遍历时将顺序表每个元素与当前记录下的最小值比较。若当前元素比当前最小值元素更小，则将记录下的具有最小值的元素更新为该位置。
将顺序表遍历完成后，我们已经找到了具有最小值的元素所在的位置pos。用min存储elems[pos]即该最小值。而我们还得知顺序表长度为length，因此，顺序表最后一个元素为elems[length-1]。将该元素的值赋给elems[pos]，将顺序表长度-1，此时我们可以认为该最小值已经被删除。最后，用min变量将被删元素带出。
1(2)
从顺序表中删除具有给定值e的所有元素。
先定义一个变量mlen记录数组原来的长度。遍历顺序表，若找到具有给定值e的元素，便从该元素开始，后面所有元素往前移一格，将顺序表长度-1。遍历时使用i指针。在删除一格具有给定值e的元素后，若后继元素的值仍为e，我们也需要将它删除。因此，我们将i指针退回一格，并重复以上过程。
在该过程结束后，若顺序表长度没有改变，则顺序表中原本没有具有值为e的元素，删除失败。若长度减小，则删除成功。
1(3)
在一个顺序表中如果有一个数据值重复出现，则留下第一个这样的数据值，并删除其他所有重复的元素，使表中所有元素的值均不相同。
先定义一个指针i从0开始遍历数组中的元素。在遍历元素过程中，定义一个指针j从i+1开始遍历数组中i之后的元素，若找到第j个元素与第i个元素具有相同的值，则将其删除。删除时也是使用指针k从j开始，j后面所有元素往前移一个，数组的长度length减一。不断重复这一过程直到指针i访问了数组中每一个元素。通过这一个时间复杂度为的算法，可以实现去重，只保留数组中第一次出现的元素而删除后面重复出现的元素。
4(1)
定位函数：在单链表中寻找第i个结点。若找到，则返回第i个结点的地址；否则返回空指针。
先判断i的值。若i的值比1小或者比链表的长度length还大，则直接退出，返回空指针。若i的值正确，则定义一个计数器和一个指针，先将指针定位到头结点的next，后将指针不断指向该结点的next结点，重复i次，找到第i个结点后便能将该结点地址返回。
4(2)
统计函数：统计单链表中等于给定值e的元素个数。
先找到链表头结点。设置一个计数器sum初始为0.遍历链表，找到值为e的元素后将sum的值加一。在遍历完链表后，便可返回sum值。
6(1)
插入函数：把元素值e作为数据元素插入表中。
可分三种情况：头插入、中间插入、尾插入。生成一个元素值为e的结点。若e小于第一个元素，则直接进行头插入。否则，设置两个工作指针，p指针从头结点后的第一个结点开始，pre结点在p指针之前。若元素e大于等于pre指针指向的结点的数据而又小于等于p指针指向的结点的数据，则将该元素值为e的结点插入。若e值比最后一个元素还大，则将该结点插入末尾。
6(2)
删除函数：删除数据元素等于e的结点。
定义一个p指针，从头结点开始。若p指针为非空结点且p指向的结点的数据比e小，则将p指向下一个元素。直到p为空或p指向的元素不小于e。若p指向的元素大于e或p为空，则说明链表内不存在数据等于e的结点，删除失败。若找到了元素为e的结点，则从该结点开始删除所有元素值都是e的结点。
4.演示
数组管理系统进入页面
在数组录入完成后可以选择功能：
1（1）的实现
1（2）的实现
1（3）的实现
链表管理系统进入页面
定位函数。定位失败的情况
定位函数，定位成功的情况
统计函数：对5 5 3 2 5这一链表，正确地统计出有3个重复的5
在有序链表中插入一个数：对1 2 3 4 6这个有序链表，成功将5插入在正确位置
删除函数：对于1 2 2 3 3 这个有序链表，成功删除所有的3
5.源代码
1（1） 1（2） 1（3）
seqlist.h
#pragma once #define SUCCESS 1 #define DEFAULT_SIZE 100 #define ERROR 0 #include<iostream> using namespace std; typedef int status; template <class ElemType> class seqlist { protected: int length; int maxsize; ElemType * elems; public: seqlist(int size = DEFAULT_SIZE)//构造空顺序表 { elems = new ElemType[size]; maxsize = size; length = 0; } seqlist(ElemType v[], int n, int size = DEFAULT_SIZE)//根据已知数组构造顺序表 { elems = new ElemType[size]; maxsize = size; length = n; for (int i = 0; i < n; i++) elems[i] = v[i]; } void show() { for (int i = 0; i < length; i++) cout << elems[i] << " "; cout << endl; } virtual ~seqlist(){ delete []elems; } int getLength(){ return length; } bool isEmpty() { return (length == 0); } void Clear() { length = 0; } ElemType findmin() { //1(1) int pos = 0; for (int i = 0; i < length; i++) { if (elems[i] < elems[pos]) pos = i; }//找出哪个位置具有最小值 ElemType min = elems[pos]; elems[pos] = elems[length - 1];//将该位置的值由最后一个元素代替 length--; return min; } status deleteE(ElemType e) {//1(2) int mlen = length;//记录初始的数组长度 for (int i = 0; i < length; i++) { if (e == elems[i]) { for (int j = i; j < length - 1; j++) elems[j] = elems[j + 1]; length--; i--; } } if (mlen == length)//如果初始的数组长度没有变化，则没删掉数，退出 return ERROR; else return SUCCESS; } status deleteRepeated() {//1(3) int maxlen = length; for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if (elems[j] == elems[i]) {//找到重复元素后删去 for (int k = j; k < length - 1; k++) elems[k] = elems[k + 1]; length--; j--; } } } if (length == maxlen) return ERROR; else return SUCCESS; } };
main.cpp
#include<iostream> #include"seqlist.h" #define SUCCESS 1 #define DEFAULT_SIZE 100 #define ERROR 0 typedef int status; using namespace std; int main() { cout << "请输入数组长度:"; int len; cin >> len; int a[100]; cout << "请输入数组:"; for (int i = 0; i < len; i++) cin >> a[i]; seqlist<int> seq1(a, len, DEFAULT_SIZE); int func; int num; do { cout << "1.删除具有最小值的元素" << endl; cout << "2.删除具有给定值e的所有元素" << endl; cout << "3.去重" << endl; cout << "4.输出" << endl; cout << "5.退出" << endl; cin >> func; switch (func) { case 1: cout<<"最小值是"<<seq1.findmin()<<endl; break; case 2: cin >> num; seq1.deleteE(num); break; case 3: seq1.deleteRepeated(); break; case 4: seq1.show(); break; case 5:break; default:cout << "输入错误！" << endl; break; } } while (func != 5); }
4（1） 4（2） 6（1） 6（2）
linklist.h
#pragma once #include"node.h" #include<iostream> #include<Windows.h> #define SUCCESS 1 #define ERROR 0 typedef int Status; using namespace std; template<class ElemType> class linklist { protected: node<ElemType>* head; int length; public: linklist() { head = new node<ElemType>; // assert(head); length = 0; } linklist(ElemType v[], int n) { node<ElemType>* p; length = n; p = head = new node<ElemType>; for (int i = 0; i < n; i++) { p->next = new node<ElemType>(v[i], NULL); // assert(p->next); p = p->next; } } ~linklist() { clear(); delete head; } void clear(){ node<ElemType>* p = head->next; while (p != NULL) { head->next = p->next; delete p; p = head->next; } length = 0; } void show() { node<ElemType>* p = head->next; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << endl; } node<ElemType>* seek(int i) {//4(1) if (i<1 || i>length) { return NULL; } else { node<ElemType>* p = head->next; int count; for (count = 1; count < i; count++) { p = p->next; } return p; } } int counting(ElemType val) {//4(2) int sum = 0; node<ElemType>* p = head->next; for (int i = 0; i < length; i++) { if (p->data == val) sum++; p = p->next; } return sum; } Status insert(ElemType e) {//6(1) node<ElemType>* p = head->next; node<ElemType>* ptemp = new node<ElemType>(e, NULL); if (e <= p->data) { ptemp->next = p; head->next = ptemp; length++; return SUCCESS; } p = p->next; node<ElemType>* pre = head->next; while (p != NULL) { if ((e >= pre->data)&&(e<=p->data)) { ptemp->next=pre->next; pre->next=ptemp; length++; return SUCCESS; } p=p->next; pre=pre->next; } length++; pre->next = ptemp; return SUCCESS; } Status deleteVal(ElemType e) {//6(2) node<ElemType>* p = head->next,*pre=head; while (p != NULL&&p->data<e) { p = p->next; pre = pre->next; } if (p == NULL) { return ERROR; } if (p->data > e) { return ERROR; } while((p!=NULL)&&(p->data == e)) { pre->next = p->next; delete p; p = pre->next; } return SUCCESS; } }; node.h #pragma once template <class ElemType> struct node { ElemType data; node<ElemType>* next; node() { next = NULL; } node(ElemType e,node<ElemType> *link=NULL) { data = e; next = link; } };
main.cpp
#include<iostream> #include"linklist.h" #include"node.h" #define SUCCESS 1 #define ERROR 0 using namespace std; typedef int Status; int main() { int n,a[100]; cout << "请输入链表长度:"; cin >> n; int num; cout << "请输入您的链表:"; for (int i = 0; i < n; i++) cin >> a[i]; linklist<int> link1(a, n); node<int>* p = NULL; int func; do { cout << "1.定位函数，寻找第i个结点地址" << endl; cout << "2.统计函数，统计单链表中等于给定值e的元素个数" << endl; cout << "3.插入函数，把元素e插入链表中。仅限有序链表" << endl; cout << "4.删除函数，删除数据元素等于e的结点。仅限有序链表" << endl; cout << "5.输出链表" << endl; cout << "6.退出" << endl; cin >> func; switch (func) { case 1: cin >> num; p = link1.seek(num); cout << p << endl; break; case 2: cin >> num; cout << link1.counting(num)<<endl; break; case 3: cin >> num; link1.insert(num); break; case 4: cin >> num; link1.deleteVal(num); break; case 5: link1.show(); break; case 6:break; default:cout << "输入错误！"<<endl; break; } } while (func!=6); cout << "运行结束"; }
