关知识来解决具体问题。
二.实验内容1.建立一个由n 个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。1) 用顺序表来实现。2) 用单链表来实现。3) 用双链表实现。4) 用静态链表实现。
5) 用间接寻址实现。
1）顺序表：
#include<iostream> using namespace std; const int MaxSize=100; class Student { int data[MaxSize];//建立数组 int length;//线性表长度 public: Student(){length=0;} //建立空表 Student(int a[],int n); //建立长度为n顺序表 ~Student(){}//析构函数 int Get(int i);//按位查找，第i个 void Input (int i,int x);//插入 int Delete(int i);//删除 void Print();//输出 }; Student::Student(int a[],int n) { int i; if(n>MaxSize)throw"参数非法"; for(i=0;i<n;i++) data[i]=a[i]; length=n; } int Student::Get(int i) { if(i<1&&i>length) throw"查找位置非法"; return data[i-1]; } void Student::Input(int i,int x) //插入 { int j; if(length>=MaxSize)throw"上溢"; if(i<1||i>length+1)throw"位置"; for(j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++; } int Student::Delete(int i) //删除 { int x,j; if(length==0)throw"下溢"; if(i<1||i>length)throw"位置"; x=data[i-1]; for(j=i;j<length;j++) data[j-1]=data[j]; length--; return x; } void Student::Print() //输出 { int i; for(i=1;i<length;i++) cout<<"第"<<i<<"位学生成绩："<<data[i-1]<<endl; cout<<endl; } void main() { int a[5]={50,60,70,80,90}; Student L(a,5); cout<<"录入学生信息:"<<endl; L.Print(); cout<<"在第2个位置插入85"<<endl; L.Input(2,85); cout<<"插入后学生成绩为:"<<endl; L.Print(); cout<<"第三位学生成绩为："<<endl; cout<<L.Get(3)<<endl; cout<<"删除第一个学生成绩"<<endl; L.Delete(1); cout<<"删除后学生成绩为："<<endl; L.Print(); }2）单链表
#include <iostream> using namespace std; struct Std{ int data; Std *next; }*p,*q; class Student { private: Std *first; public: Student(); Student(int a[],int n); ~Student(); int Get(int i); int Locate(int x); void Insert(int i,int x); int Delete(int i); void Print(); }; Student::Student()//无参构造 { first =new Std; first->next=NULL; } Student::Student(int a[],int n)//初始化 { first=new Std; first->next=NULL; for (int i=0;i<n;i++) { p=new Std; p->data=a[i]; p->next=first->next; first->next=p; } } Student::~Student()//析构函数 { while(first!=NULL) { p=first; first=first->next; delete p; } } int Student::Get(int i) //按位查找 { p=first->next; int count=1; while (p != NULL && count<i) { p = p->next; count++; } if (p == NULL) throw "位置非法"; else return p->data; } int Student::Locate(int x)//按值查找 { p=first->next; int count=1; while (p!=NULL) { if(p->data==x) return count; p=p->next; count++; } return 0; } void Student::Insert(int i,int x)//插入 { p=first; int count=0; while(p!=NULL&&count<i-1) { p=p->next; count++; } if(p==NULL)throw"位置"; else { q=new Std; q->data=x; q->next=p->next; p->next=q; } } int Student::Delete(int i)//删除 { p=first; int count=0; while (p!=NULL&&count<i-1) { p=p->next; count++; } if (p==NULL||p->next==NULL) throw "位置非法"; else { int x; q=p->next; x=q->data; p->next=q->next; delete q; return x; } } void Student::Print() { p = first->next; while (p!= NULL) { cout << p->data<< ' '; p= p->next; } cout<<endl; } void main() { int a[5]={50,60,70,80,90}; Student L(a,5); cout<<"录入学生信息:"<<endl; L.Print(); cout<<"在第2个位置插入85"<<endl; L.Insert(2,85); cout<<"插入后学生成绩为:"<<endl; L.Print(); cout<<"第三位学生成绩为："<<endl; cout<<L.Get(3)<<endl; cout<<"删除第一个学生成绩"<<endl; L.Delete(1); cout<<"删除后学生成绩为："<<endl; L.Print(); }3）双链表
#include <iostream> using namespace std; struct Std { int data; Std *next; Std *prior; }*p,*q; class Student { private: Std *first; public: Student(); //无参构造 Student(int a[],int n); //初始化 ~Student(); //析构函数 int Get(int i); //按位查找 int Locate(int x); //按值查找 int Before(int x); //前元素查找 void Insert(int i,int x); //插入 void Delete(int i); //删除 void Print(); //输出 }; Student::Student()//无参构造 { first =new Std; first->next=NULL; first->prior=NULL; } Student::Student(int a[],int n)//初始化 { first=new Std; first->next=NULL; first->prior=NULL; q=first; for (int i=0;i<n;i++) { p=new Std; p->data=a[i]; p->prior=q; p->next=q->next; q->next=p; q=p; } } Student::~Student(){}//析构函数 int Student::Get(int x) //按位查找 { p=first->next; int count=1; while (p != NULL && count<x) { p = p->next; count++; } if (p == NULL) throw "位置非法"; else return p->data; } int Student::Locate(int x)//按值查找 { p=first->next; int count=1; while (p!=NULL) { if(p->data==x) return count; p=p->next; count++; } return 0; } int Student::Before(int x) //前元素查找 { for(p=first->next;p!=NULL&&p->data!=x;) { p=p->next; } if (p==NULL) throw "位置非法"; else return p->prior->data; return 0; } void Student::Insert(int i,int x)//插入 { p=first; int count=0; while(p!=NULL&&count<i-1) { p=p->next; count++; } if(p==NULL)throw"位置"; else { q=new Std; q->data=x; q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; } } void Student::Delete(int i)//删除 { p=first->next; int count=0; while (p!=NULL&&count<i-1) { p=p->next; count++; } if (p==NULL) throw "位置非法"; else { (p->prior)->next=p->next; (p->next)->prior=p->prior; delete p; } } void Student::Print() //输出 { p = first->next; while (p!= NULL) { cout << p->data<< ' '; p= p->next; } cout<<endl; } void main() { int a[5]={50,60,70,80,90}; Student L(a,5); cout<<"录入学生信息:"<<endl; L.Print(); cout<<"在第2个位置插入85"<<endl; L.Insert(2,85); cout<<"插入后学生成绩为:"<<endl; L.Print(); cout<<"85的前一个学生成绩为："<<endl; cout<<L.Before(85)<<endl; cout<<"第三位学生成绩为："<<endl; cout<<L.Get(3)<<endl; cout<<"删除第一个学生成绩"<<endl; L.Delete(1); cout<<"删除后学生成绩为："<<endl; L.Print(); }4）静态链表
#include <iostream> using namespace std; const int N=100; struct Std { int data; int next; }score[N]; class Student { private: static int first; static int avail; int lenght; public: Student(); Student(int a[],int n); ~Student(){} void Insert(int i,int x); int Delete(int i); int Get(int i); int Locate(int x); void Show(); }; int Student::first=0; int Student::avail=1; Student::Student() { score[first].next=-1; for (int i=avail;i<N-1;i++) score[i].next=i+1; score[i].next=-1; } Student::Student(int a[],int n) { int s;cout<<first; score[first].next=avail; for (int i=0;i<n;i++) { s=avail; avail=score[avail].next; score[s].data=a[i]; score[s].next=avail; } lenght=n; } void Student::Insert(int i,int x) { if (i>lenght) throw "位置非法"; int s; s=avail; avail=score[avail].next; score[s].data=x; score[s].next=score[i-1].next; score[i-1].next=s; lenght++; } int Student::Delete(int i) { if (i>lenght) throw "位置非法"; int r=first; while (score[r].next<i) r=score[r].next; score[r].next=score[i].next; score[i].next=avail; avail=i; lenght--; return score[i].data; } int Student::Get(int i) { if (i>lenght) throw "位置非法"; int r=first; while (r<i) r=score[r].next; return score[r].data; } int Student::Locate(int x) { int r=first; while (score[r].data!=x) r=score[r].next; return r; } void Student::Show() { int r=first; for (int j=0;j<lenght;j++) { r=score[r].next; cout<<score[r].data<<' '; } cout<<endl; } void main() { int a[5]={50,60,70,80,90}; Student L(a,5); cout<<"录入学生信息:"<<endl; L.Show(); cout<<"在第2个位置插入85"<<endl; L.Insert(2,85); cout<<"插入后学生成绩为:"<<endl; L.Show(); cout<<"第三位学生成绩为："<<endl; cout<<L.Get(3)<<endl; cout<<"删除第一个学生成绩"<<endl; L.Delete(1); cout<<"删除后学生成绩为："<<endl; L.Show(); }5）间接寻址
#include <iostream> using namespace std; const int N=100; class Student { private: int *scores[N]; int lenght; public: Student(int score[],int n); ~Student(){} void Insert(int i,int *x); int Delete(int i); int Get(int i); int Locate(int x); void Show(); }; Student::Student(int score[],int n) { if (n>N) throw "参数非法"; for (int i=0;i<n;i++) scores[i]=&score[i]; lenght=n; } void Student::Insert(int i,int *x) { if (lenght>N) throw "上溢"; if (i<0||i>lenght+1) throw "位置非法"; for (int j=lenght;j>=i;j--) scores[j]=scores[j-1]; scores[i-1]=x; lenght++; } int Student::Delete(int i) { if (lenght<0) throw "下溢"; if (i<0||i>lenght+1) throw "位置非法"; int x=*scores[i-1]; for (int j=i-1;j<lenght-1;j++) scores[j]=scores[j+1]; lenght--; return x; } int Student::Get(int i) { return *scores[i-1]; } int Student::Locate(int x) { int n; for (int i=0;i<lenght;i++) if (*scores[i]==x) n=i+1; return n; } void Student::Show() { for (int i=0;i<lenght;i++) cout<<*scores[i]<<' '; cout<<endl; } void main() { int a[5]={50,60,70,80,90}; Student L(a,5); cout<<"录入学生信息:"<<endl; L.Show(); cout<<"在第2个位置插入85"<<endl; int x=85; L.Insert(2,&x); cout<<"插入后学生成绩为:"<<endl; L.Show(); cout<<"第三位学生成绩为："<<endl; cout<<L.Get(3)<<endl; cout<<"删除第一个学生成绩"<<endl; L.Delete(1); cout<<"删除后学生成绩为："<<endl; L.Show(); }