信管117116李可欣数据结构实验三
1、建立一个包含n个学生成绩信息的程序
（1）用顺序表实现
# include <iostream>
# include <fstream>
# include <string.h>
#define MAX 100
int i,n;
using namespace std;
struct Student{
charid[20];
charname[20];
intLnum;
intGnum;
intEnum;
float sum;
voidMenu();
voidFind();
voidRemoveItem();
voidDisplay();
voidshow();
voidAddItem();
voidInput();
}Stu[MAX+1];
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌主菜单﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
void Menu(){
cout<<" "<<endl;
cout<<"\t 学 生 成 绩 管 理 系 统\t\t"<<endl;
cout<<" "<<endl;
cout<<"\t\t1.录入\t\t"<<endl;
cout<<"\t\t2.显示\t\t"<<endl;
cout<<"\t\t3.查找\t\t"<<endl;
cout<<"\t\t4.插入\t\t"<<endl;
cout<<"\t\t5.删除\t\t"<<endl;
cout<<"\t\t0.退出\t\t "<<endl;
cout<<"\n\t\t\n\t\t请选择："<<endl;
}
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌录入信息﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
void Input()
{
cout<<"\t\t你要录入几位学生：";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"位";
cout<<"\t\t请输入学生姓名："<<endl; cin>> Stu[i].name;
cout<<"\t\t请输入学生学号："<<endl; cin>>Stu[i].id;
cout<<"\t\t请输入离散成绩："<<endl; cin>>Stu[i].Lnum;
cout<<"\t\t请输入管理成绩："<<endl; cin>>Stu[i].Gnum;
cout<<"\t\t请输入英语成绩："<<endl; cin>>Stu[i].Enum;
Stu[i].sum=Stu[i].Lnum+Stu[i].Gnum+Stu[i].Enum;
}
}
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌显示所有信息﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
void Display()
{
cout<<"序号"<<"\t"<<"姓名"<<"\t\t"<<"学号"<<"\t"<<"离散"<<"\t"<<"管理"<<"\t"<<"英语"<<"\t"<<"总分"<<endl;
for(i=1;i<=n;i++)
{
cout<<i<<"\t"<<Stu[i].name<<"\t"<<Stu[i].id<<"\t"<<Stu[i].Lnum<<"\t"<<Stu[i].Gnum<<"\t"<<Stu[i].Enum<<"\t"<<Stu[i].sum<<"\t"<<"\n";
}
}
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌选择信息﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
void Student::show()
{
cout<<"序号"<<"\t"<<"姓名"<<"\t\t"<<"学号"<<"\t"<<"离散"<<"\t"<<"管理"<<"\t"<<"英语"<<"\t"<<"总分"<<endl;
cout<<i<<"\t"<<Stu[i].name<<"\t"<<Stu[i].id<<"\t"<<Stu[i].Lnum<<"\t"<<Stu[i].Gnum<<"\t"<<Stu[i].Enum<<"\t"<<Stu[i].sum<<"\t"<<"\n";
}
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌查找信息﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
void Find()
{
charna[20] ,I[10];
intx,a,z;
cout<<"\n\t\t*********************************\n";
cout<<"\t \t 1.按姓名 2.按学号3.按序号";
cout<<"\n\t\t*********************************\n请选择：";
cin>>x;
switch(x)
{
case 1:{
cout<<"\t\t请输入要查找的姓名：";cin>>na;
bool flag=false;
for(i=1;i<=n;i++)
{
if(strcmp(Stu[i].name, na) == 0)
{
Stu[i].show();
flag=true;
}
}
if(!flag){
cout<<"无此人";
}
}break;
case 2:{
cout<<"\t\t请输入要查找的学号：";cin>>I;
bool flag=false;
for(i=1;i<=n;i++)
{
if(strcmp(Stu[i].id, I) == 0)
{
Stu[i].show();
flag=true;}
}
if(!flag){
cout<<"无此人";}
}break;
case 3:{
cout<<"\t\t请输入要查找的序号：";cin>>i;
if(i<1||i>n) throw "position error";
else Stu[i].show();
}break;
}
}
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌插入信息﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
voidAddItem()
{
int i,j;
n++;
if(n>MAX) throw"overflow";
cout<<"which position do youwant to insert?";
cin>>i;
if(i<1||i>n) throw"position";
for(j=n;j>=i;j--)
{
Stu[j]=Stu[j-1];
}
cout<<"第"<<i<<"位";
cout<<"\t\t请输入学生姓名："<<endl; cin>> Stu[i].name;
cout<<"\t\t请输入学生学号："<<endl; cin>>Stu[i].id;
cout<<"\t\t请输入离散成绩："<<endl; cin>>Stu[i].Lnum;
cout<<"\t\t请输入管理成绩："<<endl; cin>>Stu[i].Gnum;
cout<<"\t\t请输入英语成绩："<<endl; cin>>Stu[i].Enum;
Stu[i].sum=Stu[i].Lnum+Stu[i].Gnum+Stu[i].Enum;
cout<<"Thenew list is:";
Display();
}
//﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌删除信息﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌﹌
voidRemoveItem()
{
intj;
if(n==0) throw "underflow";
cout<<"which sequence number doyou want to delete?";
cin>>i;
if(i<1||i>n) throw"position";
for(j=i+1;j<=n;j++)
{
Stu[j-1]=Stu[j];
}
cout<<"The new list is:";
n--;
Display();
}
int main()
{
int x,i=0;
boolquit=false;
while(!quit)
{
system("cls");
Menu();
cin>>x;
switch(x)
{
case 0:quit=true;break;
case 1:Input();system("pause");break;
case 2:Display();system("pause");break;
case 3:Find();system("pause");break;
case 4:AddItem();system("pause");break;
case 5:RemoveItem();system("pause");break;
}
}
return 0;
}
（2）用单链表实现
#ifndef LinkList_H
#define LinkList_H
template<class DataType>
struct Node
{
DataTypedata;
Node<DataType>* next;
};
template<class DataType>
class LinkList
{
public:
LinkList();
LinkList(DataType a[],int n);
~LinkList();
int Locate(DataType x);
voidInsert(int i,DataType x);
DataType Delete(int i);
voidPrintList();
private:
Node<DataType>* first;
};
#endif
#include<iostream>
using namespace std;
#include "LinkList.h"
template<class DataType>
LinkList<DataType>::LinkList()
{
first=newNode<DataType>;
first->next=NULL;
}
template<class DataType>
LinkList<DataType>::LinkList(DataTypea[],int n)
{
Node<DataType>* r, * s;
first=newNode<DataType>;
r=first;
for(inti=0;i<n;i++)
{
s=newNode<DataType>;
s->data=a[i];
r->next=s;r=s;
}
r->next=NULL;
}
template<class DataType>
LinkList<DataType>::~LinkList()
{
Node<DataType>* q=NULL;
while(first!=NULL)
{
q=first;
first=first->next;
deleteq;
}
}
template<class DataType>
void LinkList<DataType>::Insert(inti,DataType x)
{
Node<DataType>*p =first, *s =NULL;
intcount=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL)throw"位置";
else{
s=newNode<DataType>;s->data=x;
s->next=p->next;p->next=s;
}
}
template<class DataType>
DataTypeLinkList<DataType>::Delete(int i)
{
Node<DataType>* p=first, * q=NULL;
DataTypex;
intcount=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL||p->next==NULL)
throw"位置";
else{
q=p->next;x=q->data;
p->next=q->next;
deleteq;
returnx;
}
}
template<class DataType>
intLinkList<DataType>::Locate(DataType x)
{
Node<DataType>* p=first->next;
intcount=1;
while(p!=NULL)
{
if(p->data==x)returncount;
p=p->next;
count++;
}
return0;
}
template<class DataType>
void LinkList<DataType>::PrintList()
{
Node<DataType>* p=first->next;
while(p!=NULL)
{
count<<p->data<<"";
p=p->next;
}
cout<<endl;
}
#include<iostream>
using namespace std;
#include "LinkList.cpp"
void main()
{
intr[5]={1,2,3,4,5};
LinkList<int>L(r,5);
cout<<"执行插入成绩操作前数据为："<<endl;
L.PrintList();
try
{
L.Insert(2,3);
}
catch(char* s)
{
cout<<s<<endl;
}
cout<<"执行插入成绩操作后数据为："<<endl;
L.PrintList();
cout<<"值为5的元素位置为：";
cout<<L.Locate(5)<<endl;
cout<<"执行删除成绩操作前数据为："<<endl;
L.PrintList();
try
{
L.Delete(1);
}
catch(char* s)
{
cout<<s<<endl;
}
cout<<"执行删除成绩操作后数据为："<<endl;
L.PrintList();
}
（3）用双链表实现
#include<iostream>
using namespace std;
template <class T>
class Node
{
public:
Tdata;
Node<T> *prior;
Node<T> *next;
};
template <class T>
class DoubleLinkList {
public:
DoubleLinkList();
DoubleLinkList(T score[], int n);
~DoubleLinkList();
int Length();
void insert(int i, T x);
Tget(int i);
int locate(T x);
TDelete(int i);
void print();
private:
Node<T> *first;
int length;
};
template <class T>
DoubleLinkList<T>::DoubleLinkList(Tscore[], int n)
{
length = 0;
first = new Node<T>;
first->next = NULL;
first->prior = NULL;
for (int i = n-1; i>=0; i--)
{
Node<T> *s = new Node<T>;
s->data = score[i];
s->next = first->next;
first->next = s;
}
}
template <class T>
DoubleLinkList<T>::~DoubleLinkList()
{
while (first->next != first->prior)
{
Node<T> *temp = first;
first->prior->next = first->next;
first->next->prior = first->prior;
first = first->next;
delete temp;
}
delete first;
}
template<class T>
int DoubleLinkList<T>::Length()
{
Node<T> *p; int count;
p= first->next;
count = 0;
while (p != NULL)
{
p = p->next;
count++;
}
return length;
}
template <class T>
void DoubleLinkList<T>::insert(int i,T x)
{
Node<T>*p, *s; int count;
p= first;
count = 0;
while (p != NULL&&count<i - 1)
{
p = p->next;
count++;
}
if (p == NULL) throw"位置";
else
{
s = new Node<T>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
template <class T>
T DoubleLinkList<T>::get(int i)
{
Node<T> *p; int count; count = 1;
p= first->next;
while (p != NULL&&count<i)
{
p = p->next; count++;
}
if (p == NULL)throw"位置非法";
else return p->data;
}
template <class T>
int DoubleLinkList<T>::locate(Tx)
{
Node<T> *p; int count;
p= first->next; count = 1;
while (p != NULL)
{
if (p->data == x) return count;
p = p->next;
count++;
}
return 0;
}
template <class T>
T DoubleLinkList<T>::Delete(inti)
{
Node<T> *p, *q;
p= first->next; int count, x; count = 1;
while (p != NULL&&count<i - 1)
{
p = p->next; count++;
}
if (p == NULL || p->next == NULL) throw"位置非法";
else
{
q = p->next;
x = q->data;
if (p->next != NULL)
{
if (q->next != NULL)
q->next->prior = p;
else
{
p->next = NULL;
p->next = q->next;
delete q;
q = NULL;
return x;
}
}
p->next = q->next;
delete q;
q = NULL;
return x;
}
}
template <class T>
void DoubleLinkList<T>::print()
{
Node<T> *p;
p= first->next;
while (p->next != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << p->data << endl;
}
void main()
{
int score[5] = { 66,77,88,99,55 };
DoubleLinkList<int>student(score,5);
cout << "学生成绩" << endl;
student.print();
cout << endl << "在位置3插入成绩44，插入后结果如下：" ;
student.insert(3,44);
student.print();
cout<< endl << "在位置2删除成绩为："<< student.Delete(2);
cout << "删除后结果如下:"; student.print();
cout<< endl << "位置3的成绩为："<< student.get(3);
cout<< endl << "成绩99所在位置为："<< student.locate(99) ;
}
（4）用静态链表实现
#include<iostream>
#include<string>
using namespace std;
const int Maxsize = 100;
template<typename T>
class Node {
public:
Tdata;
int next;
};
template <typename T>
class SLL {
public:
SLL();
SLL(T score[],int n);
virtual ~SLL();
void print();
Tget(int i);
int Locate(T x);
void insert(int i, T x);
void Delete(int i);
private:
Node<T> node[Maxsize];
int first;
int avail;
int length;
};
template<typename T>
SLL<T>::SLL(T score[],int n)
{
length = 0;
for(int i = 0; i<Maxsize; i++)
{
node[i].next=i+1;
}
node[Maxsize - 1].next = -1;
avail = 2;
first = 1;
node[first].next = -1;
for (int j = n-1; j >=0; j--)
{
if (avail == -1)
{
break;
}
int s = avail;
avail = node[avail].next;
node[s].data = score[j];
node[s].next = node[first].next;
node[first].next = s;
length++;
}
}
template<class T>
SLL<T>::~SLL()
{
}
template<typename T>
void SLL<T>::print()
{
int s = node[first].next;
for (int i = 1; i <= length; i++)
{
cout << node[s].data << " ";
s = node[s].next;
}
}
template<typename T>
T SLL<T>::get(int i)
{
if(i<=0 || i>length) throw"位置非法";
int p = first;
for(int j = 0; j<i; j++)
{
p=node[p].next;
}
return node[p].data;
}
template<typename T>
int SLL<T>::Locate(T x)
{
int count=0;
int p = first;
while(node[p].next != -1)
{
p=node[p].next;
if(node[p].data == x) return count+1;
count++;
}
return -1;
}
template<typename T>
void SLL<T>::insert(int i, T x)
{
if(i<0||i>length) throw"位置非法";
int p = first;
for(int j = 1; j<i; j++)
{ p=node[p].next; /*或者p=node[p].next*/}
int s = node[avail].next;
node[avail].data = x;
node[avail].next = node[p].next;
node[p].next = avail;
avail = s;
length++;
}
template<typename T>
void SLL<T>::Delete(int i)
{
if(i<0||i>length+1) throw"位置非法";
int p = first;
for(int j = 1;j<=i; j++)
{ p=node[p].next; }
int q = node[p].next;
Te = node[p].data;
node[p].next = node[q].next;
node[q].next = avail;
avail = q;
length--;
}
void main()
{
float score[6]={55,68,97,84,76,60};
SLL<float> student(score,6);
cout<<" 学生离散数学成绩"<<endl;
student.print();
cout<<endl<<endl<<"在位置3插入成绩88，结果如下："<<endl;
student.insert(3,88);
student.print();
cout<<endl<<endl<<"在位置4删除成绩 删除后结果如下："<<endl;
student.Delete(3);
student.print();
cout<<endl<<endl<<"位置2的成绩为："<<student.get(2)<<endl;
cout<<endl<<endl<<"成绩60所在位置为："<<student.Locate(60)<<endl;
}
（5）用间接寻址实现
#include<iostream>
using namespace std;
const int Maxsize = 100;
template<class T>
struct Node
{
Tdata;
Node<T> *next;
};
template<class T>
class D{
public:
D();
D(T score[],int n);
virtual ~D();
void print();
T get(int i);
int locate(T x);
void insert(int i,T x);
T Delete(int i);
bool changeList(int i, T x);
private:
Node<T> *first;
int length;
Node<T> *address[Maxsize];
};
template<class T>
D<T>::D()
{
first=new Node<T>;
first->next=NULL;
}
template<class T>
D<T>::D(T score[],int n)
{
if (n > Maxsize) throw("溢出");
Node<T> *s;
first = new Node<T>;first->next=NULL;
for(int i=n-1;i>=0;i--)
{
s=new Node<T>;s->data=score[i];
s->next=first->next;first->next=s;
}
}
template<class T>
D<T>::~D()
{
Node<T> *q;
while(first!=NULL)
{
q=first;
first=first->next;
delete q;
}
}
template<class T>
void D<T>::insert(int i,T x)
{
Node<T>*p,*s;int count;
p=first;count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL)throw"位置非法";
s=new Node<T>;s->data=x;
s->next=p->next;
p->next=s;
length++;
}
template<class T>
T D<T>::Delete(int i)
{
Node<T> *q,*p; T x; int count;
p=first;count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL||p->next==NULL)throw"位置";
else{
q=p->next;x=q->data;
p->next=q->next;
delete q;
return x;
}
}
template<class T>
T D<T>::get(int i)
{
Node<T>*p;int count;
p=first->next;count=1;
while(p!=NULL&&count<i)
{p=p->next;count++;}
if(p==NULL)throw"位置非法";
else return p->data;
}
template<class T>
int D<T>::locate(T x)
{
Node<T>*p;int count =1;
p=first->next;
while(p!=NULL)
{
if(p->data==x)returncount;
p=p->next;
count++;
}
return 0;
}
template<class T>
void D<T>::print()
{
Node<T>*p;
p=first->next;
while(p!=NULL)
{cout<<p->data<<" ";;
p=p->next;
}
}
void main()
{
float score[8] = {88,89.5,89,79.5,96.5,76,100,88.5 };
D<float>student(score, 8);
cout << " 学生的所有成绩如下 " << endl;
student.print();
cout << endl << "删除在位置6的成绩如下 ：" << student.Delete(6) <<" , "<<"删除后结果如下:"<< endl;
student.print();
cout << endl <<"在位置7插入成绩99，插入后结果如下：" << endl;
student.insert(7,99);
student.print();
cout << endl <<"位置5的成绩为：" << student.get(5)<< endl;
cout << endl <<"成绩100所在位置为：" <<student.locate(100) << endl;
}
2、实现两个集合的相等判定、并、交和差运算
#include<stdio.h>
#include<stdlib.h>
int unionSets(int *A, int *B, int lenA, intlenB)
{
int i, j;
int flag, index = lenB;
int *buffer = (int*)malloc(sizeof(int) * (lenA + lenB));
for (i = 0; i < lenB; i++) {
buffer[i] = B[i];
}
for (i = 0; i < lenA; i++) {
flag = 1;
for (j = 0; j < lenB; j++) {
if (A[i] == B[j]) {
flag = 0;
}
}
if (flag) {
buffer[index] = A[i];
index++;
}
}
printf("并集:{ ");
for (i = 0; i < index; i++) {
printf("%d ", buffer[i]);
}
printf("}\n");
}
int intersection(int *A, int *B, int lenA,int lenB)
{
int i, j;
int flag, index = 0, len = lenA > lenB ? lenA : lenB;
int *buffer = (int*)malloc(sizeof(int) * len);
for (i = 0; i < lenA; i++) {
flag = 0;
for (j = 0; j < lenB; j++) {
if (A[i] == B[j]) {
flag = 1;
}
}
for (j = 0; j < index; j++) {
if (A[i] == buffer[j]) {
flag = 0;
}
}
if (flag) {
buffer[index] = A[i];
index++;
}
}
printf("交集:{ ");
for (i = 0; i < index; i++) {
printf("%d ", buffer[i]);
}
printf("}\n");
}
int complementary(int *A, int *B, int lenA,int lenB)
{
int i, j;
int flag, index = 0;
int *buffer = (int*)malloc(sizeof(int)*lenA);
for (i = 0; i < lenA; i++) {
flag = 1;
for (j = 0; j < lenB; j++) {
if (A[i] == B[j]) {
flag = 0;
}
}
if (flag) {
buffer[index] = A[i];
index++;
}
}
printf("相对补:{ ");
for (i = 0; i < index; i++) {
printf("%d ", buffer[i]);
}
printf("}\n");
}
int SymDifference(int *A, int *B, int lenA,int lenB)
{
int i, j;
int flag, index = 0;
int *buffer = (int*)malloc(sizeof(int)*lenA);
for (i = 0; i < lenA; i++) {
flag = 1;
for (j = 0; j < lenB; j++) {
if (A[i] == B[j]) {
flag = 0;
}
}
if (flag) {
buffer[index] = A[i];
index++;
}
}
for (i = 0; i < lenB; i++) {
flag = 1;
for (j = 0; j < lenA; j++) {
if (B[i] == A[j]) {
flag = 0;
}
}
if (flag) {
buffer[index] = B[i];
index++;
}
}
printf("对称差:{ ");
for (i = 0; i < index; i++) {
printf("%d ", buffer[i]);
}
printf("}\n");
}
int equalSets(int *A, int *B, int lenA, intlenB)
{
int top = 0, i, j, temp;
int *buffer = (int*)malloc(sizeof(int) * lenA);
if (lenA != lenB) {
printf("\nA与B相等\n");
return 0;
}
for (i = 0; i < lenA; i++) {
for (j = i + 1; j < lenA; j++) {
if (A[i] < A[j]) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
for (i = 0; i < lenB; i++) {
for (j = i + 1; j < lenB; j++) {
if (B[i] < B[j]) {
temp = B[i];
B[i] = B[j];
B[j] = temp;
}
}
}
for (i = 0; i < lenA; i++) {
if (A[i] != B[i]) {
printf("\nA与B不相等\n");
return 0;
}
}
printf("相等\n");
}
int powerSets(int *A, int lenA)
{
int i, j;
int tag, index;
printf("幂集:{ { 空集 }, ");
for (tag = 1; tag <= lenA; tag++) {
for (index = 0; index < lenA - tag + 1; index++) {
printf("{ ");
for (i = index,j=0; j < tag; i++,j++) {
printf("%d ", A[i]);
}
printf("},");
}
}
printf("}\n");
}
int main()
{
int *A, *B;
int lenA, lenB;
int i;
printf("输入A,B的元素个数: ");
scanf("%d%d", &lenA, &lenB);
A= (int*)malloc(sizeof(int) * lenA);
B= (int*)malloc(sizeof(int) * lenB);
printf("输入A的元素\n");
for (i = 0; i < lenA; i++) {
scanf("%d", &A[i]);
}
getchar();
printf("输入B的元素\n");
for (i = 0; i < lenB; i++) {
scanf("%d", &B[i]);
}
equalSets(A, B, lenA, lenB);
unionSets(A, B, lenA, lenB);
intersection(A, B, lenA, lenB);
printf("A对B的");
complementary(A, B, lenA, lenB);
printf("B对A的");
complementary(B, A, lenA, lenB);
SymDifference(A, B, lenA, lenB);
printf("A的");
powerSets(A, lenA);
printf("B的");
powerSets(B, lenB);
system("pause");
return 0;
}