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 << "运行结束";
}

数据结构/数据结构与算法实验一线性表的相关算法实现

1.实验题目

2.实验要求

3.算法思路

1(1)

1(2)

1(3)

4(1)

4(2)

6(1)

6(2)

4.演示

5.源代码

1（1） 1（2） 1（3）

seqlist.h

main.cpp

4（1） 4（2） 6（1） 6（2）

linklist.h

main.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构/数据结构与算法实验一 线性表的相关算法实现

1.实验题目

2.实验要求

3.算法思路

1(1)

1(2)

1(3)

4(1)

4(2)

6(1)

6(2)

4.演示

5.源代码

1（1） 1（2） 1（3）

seqlist.h

main.cpp

4（1） 4（2） 6（1） 6（2）

linklist.h

main.cpp

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构/数据结构与算法实验一线性表的相关算法实现