数据结构 实验一 线性表
#include <iostream>
using namespace std;
const int MAXSIZE = 20;
const int ERROR = 0;
const int OK = 1;
typedef int Status;
//顺序表实现
//template <typename T>
typedef struct Student
{
int number;
int grade; //分数为int或double?
Student() {}
Student(int num, int g):number(num), grade(g) {}
}Student;
class SqList
{
public:
SqList();
~SqList();
Status ListInsert(int i, Student &e);
Status ListDelete(int i, Student &e);
void OutoutList() const;
void InputList();
void MergeList(const SqList &La, const SqList &Lb);
private:
Student *elem;
int length; //实际存放元素的个数
int listSize; //可以容纳的最大元素的个数
};
//重载输出运算符,直接cout<<student*
ostream& operator << (ostream& os, const Student& x)
{
return os << '(' <<x.number << ',' << x.grade << ')';
}
SqList::SqList()
{
elem = new Student[MAXSIZE];
length = 0; //当前长度
listSize = MAXSIZE;
}
SqList::~SqList()
{
delete[] elem;
}
//在第i个元素之前插入元素
Status SqList::ListInsert(int i, Student &e)
{
Student *p;
//插入位置不合理
if(i<1 || i>length+1)
{
return ERROR;
}
//容量已满扩容
if(length >= MAXSIZE)
{
Student *newbase = new Student[MAXSIZE*2];
if(!newbase)
{
cerr << "内存分配错误!" <<endl;
return ERROR;
}
p = elem;
elem = newbase;
//复制原来的数据
for(int i=0; i<length; i++)
{
elem[i] = p[i];
}
listSize = MAXSIZE * 2; //更新当前可容纳最多元素
}
Student *q = &(elem[i-1]); //新插入节点位置,即为第(i-1)处
for(p=&(elem[length-1]); p>=q; p--) //移动
{
*(p+1) = *p;
}
*q = e;
++length; //更新当前表长
return OK;
}
//删除第i个元素,并用e返回
Status SqList::ListDelete(int i, Student &e)
{
Student *p, *q;
if(i<1 || i>length)
{
return ERROR;
}
p = &(elem[i-1]); //第i个元素对应下标为(i-1)
e.number = p->number;
e.grade = p->grade;
q = elem + length - 1;
for(++p; p<=q; p++)
{
*(p-1) = *p;
}
--length;
return OK;
}
void SqList::InputList()
{
Student e;
int cnt = 0;
cout << "请输入表中学生的个数: ";
cin >>cnt;
cout << "请按学号由小到大输入学生数据!~"<<endl;
for(int i=0; i<cnt; i++)
{
cout << "请输入表中第" << length+1 << "个学生的数据: ";
cin >> e.number >> e.grade;
ListInsert(1, e);
}
}
void SqList::OutoutList() const
{
cout << "***按照学号从大到小的有序表***"<<endl;
for(int i=0; i<length; i++)
{
cout<< elem[i] <<endl;
}
}
void SqList::MergeList(const SqList &La, const SqList &Lb)
{
Student *pa, *pb, *pc, *pa_last, *pb_last;
pa = La.elem; //La表头
pb = Lb.elem; //Lb表头
pa_last = La.elem + La.length - 1; //La表尾
pb_last = Lb.elem + Lb.length - 1; //Lb表尾
listSize = length = La.length + Lb.length;
pc = elem = new Student[listSize];
if(!elem)
{
cerr << "空间分配失败!" <<endl;
}
while(pa<=pa_last && pb<=pb_last)
{
if(pa->number < pb->number)
{
*pc++ = *pb++;
}
else
{
*pc++ = *pa++;
}
}
while(pa<=pa_last)
{
*pc++ = *pa++;
}
while(pb<=pb_last)
{
*pc++ = *pb++;
}
}
int main()
{
// SqList list1;
// Student stu1 = Student(2 , 90);
// cout << stu1 <<endl;
// list1.ListInsert(1, stu1);
// list1.OutoutList();
// Student stu2 = Student(4, 100);
// cout << stu2 <<endl;
// list1.ListInsert(1, stu2);
// list1.OutoutList();
// list1.ListDelete(1, stu2);
// list1.OutoutList();
// cout<<stu2 <<endl;
//
// SqList list2;
// Student stu3 = Student(3, 95);
// cout<<stu3 <<endl;
// list2.ListInsert(1, stu3);
// list2.OutoutList();
//
// SqList list3;
// list3.MergeList(list1, list2);
// list3.OutoutList();
SqList list4;
list4.InputList();
list4.OutoutList();
SqList list5;
list5.InputList();
list5.OutoutList();
SqList list6;
list6.MergeList(list4, list5);
list6.OutoutList();
cout << "Hello world!" << endl;
return 0;
}
基本实现了要求的功能,但是还有很多可以优化的地方。
#include <iostream>
using namespace std;
const int ERROR = 0;
const int OK = 1;
typedef int Status;
class ListNode
{
public:
int number;
int grade;
ListNode *next;
ListNode() {}
ListNode(int num, int g):number(num), grade(g)
{
this->next = NULL;
}
};
class LinkList
{
public:
LinkList();
//~LinkList();
Status CreateList();
void OutputList() const;
Status ListInsert(int i, ListNode &e);
Status ListDelete(int i, ListNode &e);
void MergeList(const LinkList &La, const LinkList &Lb);
private:
ListNode *head;
};
//重载输出运算符,直接cout<<student*
ostream& operator << (ostream& os, const ListNode& x)
{
return os << '(' <<x.number << ',' << x.grade << ')';
}
LinkList::LinkList()
{
head = new ListNode;
}
Status LinkList::CreateList()
{
cout << "***请按学号从小到大输入***"<<endl;
int cnt = 0;
cout << "请输入表中学生的个数: ";
cin >> cnt;
ListNode *p;
int number = 0;
int grade = 0;
static int numOrder = 1;
for(int i=cnt; i>0; i--,numOrder++)
{
cout << "请输入第" << numOrder << "个学生的学号: ";
cin >> number;
cout << "请输入第" << numOrder << "个学生的成绩: ";
cin >> grade;
p = new ListNode(number, grade);
if(!p)
{
return ERROR;
}
p->next = head->next;
head->next = p;
}
return OK;
}
void LinkList::OutputList() const
{
ListNode *p = head->next;
while(p != NULL)
{
cout << *p <<endl;
p = p->next;
}
}
void LinkList::MergeList(const LinkList &La, const LinkList &Lb)
{
ListNode *pa, *pb, *pc, *p;
pa = La.head->next; //指向首元节点
pb = Lb.head->next;
pc = head; //合并后新链表头指针
while(pa != NULL && pb != NULL)
{
if(pa->number >= pb->number) //小的头插法到尾部
{
p = new ListNode(pa->number, pa->grade);
pc->next = p;
pc = pc->next;
pa = pa->next;
}
else
{
p = new ListNode(pb->number, pb->grade);
pc->next = p;
pc = pc->next;
pb = pb->next;
}
}
while(pa != NULL)
{
p = new ListNode(pa->number, pa->grade);
pc->next = p;
pc = pc->next;
pa = pa->next;
}
while(pb != NULL)
{
p = new ListNode(pb->number, pb->grade);
pc->next = p;
pc = pc->next;
pb = pb->next;
}
}
Status LinkList::ListInsert(int i, ListNode &e)
{
ListNode *p, *s;
p = head;
int j = 0;
while(p != NULL && j<i-1) //寻找第i-1个节点
{
p = p->next;
++j;
}
if(!p || j>i-1)
{
return ERROR;
}
s = &e;
s->next = p->next;
p->next = s;
return OK;
}
Status LinkList::ListDelete(int i, ListNode &e)
{
ListNode *p, *q;
p = head;
int j = 0;
while(p->next && j<i-1) //寻找第i个节点,并另p指向其前趋
{
p = p->next;
++j;
}
if(!(p->next) || j>i-1)
{
return ERROR;
}
q = p->next;
p->next = q->next;
e = *q;
delete q;
return OK;
}
int main()
{
LinkList list1;
list1.CreateList();
list1.OutputList();
LinkList list2;
list2.CreateList();
list2.OutputList();
LinkList list3;
list3.MergeList(list1, list2);
list3.OutputList();
cout << "Hello world!" << endl;
return 0;
}