数据结构实验报告
实验一
1、编写算法实现线性顺序表的逆置。
2、用线性表的链式模式编写算法，实现两个表La=(1,5,4,8,6,11)和Lb=(9,7,4,2,1,5)的并集。
实验1-1
主要代码：
bool GetElem(int position, int &e) const // 求指定位置的元素 {
if (position count)
return false;
else
{
e=elems[position-1];
return true;
}
}
bool SetElem(int position, const int &e) // 设置指定位置的元素值 {
if (position count)
return false;
else
{
elems[position-1]=e;
return true;
}
}
void disp()
{
for (int i=0; i
{
cout
}
cout
}
};
void reverse(SqList &la)
{
int leftposition=1;
int rightposition=la.Length();
int a,b;
while(leftposition
{la.GetElem(leftposition,a);
la.GetElem(rightposition,b);
la.SetElem(leftposition,b);
la.SetElem(rightposition,a);
leftposition++;
rightposition--;
} //在这里加代码
}
int main()
{
int a[10]= {1,2,3,4,5,6,7,8,9,10};
SqList la(a,10);
la.disp();
reverse(la); //该函数完成逆置功能
la.disp();
return 0;
}
int *p,*q;
int position=0;
bool flag=false;
p=head;
p=p->next;
while(p!=null)
{position++;
if (position>=2&&p->data==x)
{q=GetElemPtr(position-2);
*tmpPtr=q->next;
}
q->next=tmpPt->next;
delete tmpPtr;
flag=true;
position--;}
p=p->next;
}//这里加代码
return flag;
实验1-2
主要代码：
SimpleLinkList::SimpleLinkList(const SimpleLinkList ©)
// 操作结果：由线性表copy 构造新线性表——复制构造函数模板
{
int copyLength = copy.Length(); // copy的长度
int e;
Init(); // 初始化线性表
for (int curPosition = 1; curPosition
bool SimpleLinkList::Delete_x(int &x)
{
Node *p,*q;
int position=0;
p=head;
p=p->next;
while(p!=NULL)
{
position++;
if (position>=2&&p->data==x)
{
q=GetElemPtr(position-2);
Node *tmpPtr=q->next;
q->next=tmpPtr->next;
delete tmpPtr;
position--;
}
p=p->next;
}
return true;//这里加代码
}
int main()
{
int a[9]= {1,5,4,8,6,11,11,11,56};
SimpleLinkList la(a,9);
la.Traverse();
la.Delete_x(a[5]);
//这里完成删除x 的前一个节点操作
la.Traverse();
}
实验二
1、已知q 是一个非空顺序队列，s 是一个顺序栈，请设计一个算法，实现将队列q 中所有元素逆置。
2、请完成队列划分子集问题的算法。
实验2-1
主要代码：
void SqQueue::Traverse() const
// 操作结果：依次对队列的每个元素调用函数(*visit)
{
for (int curPosition = front; curPosition != rear;
curPosition = (curPosition + 1) % maxSize)
{ // 对队列每个元素调用函数(*visit)
cout
}
cout
}
bool SqQueue::OutQueue(int &e)
// 操作结果：如果队列非空，那么删除队头元素，并用e 返回其值，返回SUCCESS, // 否则返回UNDER_FLOW，
{
if (!Empty())
{ // 队列非空
e = elems[front]; // 用e 返回队头元素
front = (front + 1) % maxSize; // front指向下一元素 return true;
}
else
{ // 队列为空
return false;
}
}
bool SqQueue::GetHead(int &e) const
// 操作结果：如果队列非空，那么用e 返回队头元素，返回SUCCESS, // 否则返回UNDER_FLOW，
{
if (!Empty())
{ // 队列非空
e = elems[front]; // 用e 返回队头元素
return true;
}
else
{ // 队列为空
return false;
}
}
bool SqQueue::InQueue(const int &e)
// 操作结果：如果队列已满，返回OVER_FLOW,
// 否则插入元素e 为新的队尾，返回SUCCESS
{
if (Full())
{ // 队列已满
return false;
}
else
{ // 队列未满，入队成功
elems[rear] = e; // 插入e 为新队尾
rear = (rear + 1) % maxSize; // rear指向新队尾 return true;
}
}
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int i,temp,n=10;
SqQueue q(n+1);
SqStack s(n+1);
for (i=0;i
q.InQueue(a[i]);
cout
q.Traverse();
for (i=0;i
{
q.OutQueue(temp);
s.Push(temp);
}
cout
s.Traverse();
for (i=0;i
{
s.Pop(temp);
q.InQueue(temp);
}
cout
q.Traverse();
return 0;
}
实验2-2
主要代码：
bool SqQueue::OutQueue(int &e)
// 操作结果：如果队列非空，那么删除队头元素，并用e 返回其值，返回SUCCESS, // 否则返回UNDER_FLOW，
{
if (!Empty())
{
// 队列非空
e = elems[front]; // 用e 返回队头元素 front = (front + 1) % maxSize; // front指向下一元素 return true;
}
else
{
// 队列为空
return false;
}
}
bool SqQueue::InQueue(const int &e)
// 操作结果：如果队列已满，返回OVER_FLOW,
// 否则插入元素e 为新的队尾，返回SUCCESS
{
if (Full())
{
// 队列已满
return false;
}
else
{
// 队列未满，入队成功
elems[rear] = e; // 插入e 为新队尾
rear = (rear + 1) % maxSize; // rear指向新队尾 return true;
}
}
int main()
{
int A[9]= {1,2,3,4,5,6,7,8,9};
int R[9][9],n=9,a,b,i,j,temp,group,num_all,num_group;
int result[n],newr[n];
SqQueue q(n+1);
for (i=0; i
{
result[i]=0;
for (j=0; j
{
R[i][j]=0;
}
}
for (i=0; i
q.InQueue(A[i]);
cout>a,a!=-1) //完成关系矩阵的赋值操作
{
cin>>b;
R[a-1][b-1]=1;
R[b-1][a-1]=1;
}
group=0;
num_all=n;
num_group=0;
while(!q.Empty()) //只要循环队列中元素不为空，就做如下的划分操作 {
group++;//第group 组的元素划分
q.OutQueue(temp); //该组第一个元素出栈
num_group++; //该组目前具有的数量
result[temp-1]=group;//该组元素对应的位置放到result 中
for (i=0; i
newr[i]=R[temp-1][i]; //把与该元素的冲突关系记录到数组
newr 中
num_all=num_all-num_group; //还需要出队列判断的元素数量 num_group=0; //初始化
for (j=0; j
{
q.OutQueue(temp);
if (newr[temp-1]==1) //如果该元素与当前的组的元素有冲突，重新入队
q.InQueue(temp);
else //否则把该元素加入到当前组中 {
result[temp-1]=group;
for (i=0; i
{
if (R[temp-1][i]==1) //把鱼当前元素有冲突的冲突关系加入到数组newr 中
newr[i]=1;
}
num_group++; //该组目前具有的元素数量
}
}
}
for (i=1; i
{
cout
for (j=0; j
{
if (result[j]==i)
cout
}
cout
}
return 0;
}
实验三
1、系数矩阵的快速转置，并输出转置之后的矩阵
2、二叉树的遍历，分别调用先序，中序和后序遍历算法输出遍历结果。
实验3-1
主要代码：
void TriSparseMatrix::FastTranspose(const TriSparseMatrix &source, TriSparseMatrix &dest)
// 操作结果：将稀疏矩阵source 转置成稀疏矩阵dest 的快速算法 {
dest.rows=source.cols;
dest.cols=source.rows;
dest.num=source.num;
dest.maxSize=source.maxSize;
delete []dest.triElems;
dest.triElems=new
Triple[dest.maxSize];
if(dest.num>0)
{
int destPos=0;
for(int col=1;col
{
for(int sourcePos=0;sourcePos
if(source.triElems[sourcePos].col==col) {
dest.triElems[destPos].row=source.triElems[sourcePos].col;
dest.triElems[destPos].col=source.triElems[sourcePos].row;
dest.triElems[destPos].value=source.triElems[sourcePos].value; destPos++;
}
}
}
}
//代码写在这里
// 释放cPos
}
int main(void)
{
const int n = 5;
TriSparseMatrix a(n, n); // 定义一个n 行n 列稀疏矩阵 int b[n][n] =
{
1, 0, 3, 0, 0,
4, 0, 6, 0, 0,
0, 0, 8, 9, 0,
0, 0, 0, 1, 12,
1, 0, 0, 3, 1
};
int i, j, v; // 工作变量
// 设置稀疏矩阵a 的元素值
for (i = 1; i
{
// 行
for (j = 1; j
{
// 列
a.SetElem(i, j, b[i - 1][j - 1]); // 设置元素值 }
}
// 显示转置前的稀疏矩阵a
cout
for (i = 1; i
{
// 行
for (j = 1; j
{
// 列
a.GetElem(i, j, v); // 求元素值
cout
}
cout
}
TriSparseMatrix c;
TriSparseMatrix::FastTranspose(a, c);// 转置a 成c
// 显示转置后稀疏矩阵c
cout
for (i = 1; i
{
// 行
for (j = 1; j
{
// 列
c.GetElem(i, j, v); // 求元素值
cout
}
cout
}
return 0; // 返回值0, 返回操作系统
}
实验3-2
主要代码：
void BinaryTree::InOrderHelp(BinTreeNode *r) const
// 操作结果：中序遍历以r 为根的二叉树
{
if(r!= NULL)
{
InOrderHelp(r->leftChild);
coutdata);
InOrderHelp(r->rightChild);
} //代码写在这里
}
void BinaryTree::InOrder() const
// 操作结果：中序遍历二叉树
{
InOrderHelp(root);
}
void BinaryTree::PostOrderHelp(BinTreeNode *r) const
// 操作结果：后序遍历以r 为根的二叉树
{
if(r!= NULL)
{PostOrderHelp(r->leftChild);
PostOrderHelp(r->rightChild);
coutdata);
}//代码写在这里
}
实验四
1、分别用普通查找和折半查找在数组中查找一个数字，输出其数组的下标和比较的次数。
2、散列表的构建与查找已知一组关键字
(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，利用线性探索法构建散列表，并根据每个输入的key 值输出其位置下标和比较的次数。
实验4-1
主要代码：
#include
using namespace std;
bool sqSearch(int a[], int n, int key, int &loc, int &count) //顺序查找函数：数组为a ；n 为数组中元素个数；key 为查找的数据，loc 为数据对应的位置；count 为比较的次数；查找成功返回true ，否则返回false. {
//代码内容
int i;
for (i=0;i
{
if (a[i]==key)
{
loc=i;
count=i+1;
return true;
}
}
return false;
}
bool BinSearch(int a[],int n,int key, int &loc, int &count) //折半查找函数：数组为a;n 为数组中元素个数;key 为查找的数据，loc 为数据对应的位置;count 为比较的次数; 查找成功返回true ，否则返回false.
{
//代码内容
int cou,mid,low,high;
cou=0;
low=0;
high=n-1;
while (low
{
mid=(low+high)/2;
cou=cou+1;
cout
if (a[mid]==key)
{
count=cou;
loc=mid;
return true;
}
else
if (key
high=mid-1;
else
low=mid+1;
}
return false;
}
int main()
{
int
num[19]={3,4,9,11,12,13,16,22,23,24,29,30,38,66,87,91,93,95,99}; int loc,count,n=19,key=91;
if (sqSearch(num,n,key,loc,count)==true)
{
cout
cout
cout
}
if (BinSearch(num,n,key,loc,count)==true)
{
cout
cout
cout
}
return 0;
}
实验4-2
主要代码：
#include
using namespace std;
void Hconstruct(int a[],int n,int c[],int p, int m)
{
int i,te;
int *temp=new int[m];
for (i=0; i
{
temp[i]=0;
}
for (i=0; i
{
te=a[i]%p;
if (temp[te]==0)
{
c[te]=a[i];
temp[te]=1;
}
else
{while (temp[te]==1)
{
te=(te+1)%m;
}
c[te]=a[i];
temp[te]=1;
}
}
}
void Hsearch(int key,int c[],int p,int m,int &loc,int &time) {
int temp;
time=1;
temp=key%p;
while(c[temp]!=key)
{
temp=(temp+1)%m;
time++;
loc=temp;
}
int main()
{
int a[12]={19,14,23,1,68,20,84,27,55,11,10,79};
int c[16];
int loc,time,key,p,m;
p=13;
m=16;
Hconstruct(a,12,c,p,m);
while(cin>>key,key!=-1)
{
Hsearch(key,c,p,m,loc,time);
cout
}
return 0;
}
实验五
1、对于100个无序的整数，分别使用冒泡排序、快速排序和希尔排序使其有序。
2、假设有100个红白蓝三种颜色的小色块(无序：三种颜色分别用0,1,2表示) ，编写程序，使每种颜色有序排列(注意：要求时间复杂度为O(n)).
实验5-1
主要代码：
#include
#include
#include
using namespace std;
//数据交换函数
void Swap(int &a, int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
//冒泡排序
void BubbleSort(int elem[], int n)
{
int flag, low=0, high=n-1 , i;
while (low
{
flag=0;
for (i= low; i
if (elem[i] > elem[i + 1])
{
Swap(elem[i], elem[i + 1]);
flag=1;
}
if(!flag) break;
high--;
for(i=high; i>low; i--) //反向冒泡
if( elem[i]
{
Swap(elem[i], elem[i-1]);
}
low ++;
}
}
//快速排序的一次划分
int Partition(int elem[], int low, int high)
{
while (low
{
while (low = elem[low])
{
high--;
}
Swap(elem[low], elem[high]);
while (low
{
low++;
}
Swap(elem[low], elem[high]);
}
return low;
}
//快速排序
void QuickSort(int elem[], int low, int high)
{
if (low
{
int pivotLoc=Partition(elem, low, high);
QuickSort(elem, low, pivotLoc-1);
QuickSort(elem, pivotLoc+1, high);
}
}
//希尔排序
void ShellInsert(int elem[],int n,int incr)
{
for (int i=incr;i
{
int e=elem[i];
int j;
for (j=i-incr;j>=0 && e
{
elem[j+incr]=elem[j];
}
elem[j+incr]=e;
}
}
void ShellSort(int elem[],int n, int inc[],int t)
{
for (int k=0;k
{
ShellInsert(elem,n,inc[k]);
}
}
int main()
{
int a[101],data[101],shelldata[101],n=100,i;
cout
srand((unsigned)time(NULL));
for (i=0; i
{
a[i]=rand()%1000;
data[i]=a[i];
shelldata[i]=a[i];
coutif ((i+1)%10==0)
{
cout
}
}
BubbleSort(a,n);
cout
for (i=0; i
{
coutif ((i+1)%10==0)
{
cout
}
}
QuickSort(data,0,n-1);
cout
for (i=0; i
{
cout
if ((i+1)%10==0)
{
cout
}
}
int incr[]={50,25,12,6,3,1};
int t=6;
ShellSort(shelldata,n,incr,t);
cout
for (i=0; i
{
cout
if ((i+1)%10==0)
{
cout
}
}
return 0;
}
实验5-2
主要代码：
#include
#include
using namespace std;
#define N 100
void swap (int &var1, int &var2)
{
int temp = var1;
var1 = var2;
var2 = temp;
}
void shuffle(int *array)
{
int current = 0;
int end = N-1;
int begin = 0;
while( current
{
if( array[current] ==0 )
{
swap(array[current],array[begin]);
current++;
begin++;
}
else if( array[current] == 1 )
{
current++;
}
else{//if array[current] =2
swap(array[current],array[end]);
end--;
}
}
}
int main()
{
int a[N];
int i;
cout
for( i=0 ; i
{
a[i] = rand()%3;
cout
}
cout
cout
shuffle(a);
for(i=0 ; i
{
cout
}
cout
return 0;
}
实验心得
数据结构是一门设计数据的结构的学科，要把书本上学到的东西运用到实践中去并不简单，我刚开始自己运用学到的知识去编程的时候有些不知所措，有些东西不能理解，这对初学者来说确实很难，又拿起课本仔细的研究了一下，询问了老师和同学才搞懂了一些东西，自己的程序才能顺利运行。
通过这门课程和这些实验让我逐渐了解了数据结构这门学科，也渐渐对编程加强了兴趣，总之学到了很多也得到了很多，感谢同学和老师对我的帮助和鼓励。
数据结构实验报告
实验一
1、编写算法实现线性顺序表的逆置。
2、用线性表的链式模式编写算法，实现两个表La=(1,5,4,8,6,11)和Lb=(9,7,4,2,1,5)的并集。
实验1-1
主要代码：
bool GetElem(int position, int &e) const // 求指定位置的元素 {
if (position count)
return false;
else
{
e=elems[position-1];
return true;
}
}
bool SetElem(int position, const int &e) // 设置指定位置的元素值 {
if (position count)
return false;
else
{
elems[position-1]=e;
return true;
}
}
void disp()
{
for (int i=0; i
{
cout
}
cout
}
};
void reverse(SqList &la)
{
int leftposition=1;
int rightposition=la.Length();
int a,b;
while(leftposition
{la.GetElem(leftposition,a);
la.GetElem(rightposition,b);
la.SetElem(leftposition,b);
la.SetElem(rightposition,a);
leftposition++;
rightposition--;
} //在这里加代码
}
int main()
{
int a[10]= {1,2,3,4,5,6,7,8,9,10};
SqList la(a,10);
la.disp();
reverse(la); //该函数完成逆置功能
la.disp();
return 0;
}
int *p,*q;
int position=0;
bool flag=false;
p=head;
p=p->next;
while(p!=null)
{position++;
if (position>=2&&p->data==x)
{q=GetElemPtr(position-2);
*tmpPtr=q->next;
}
q->next=tmpPt->next;
delete tmpPtr;
flag=true;
position--;}
p=p->next;
}//这里加代码
return flag;
实验1-2
主要代码：
SimpleLinkList::SimpleLinkList(const SimpleLinkList ©)
// 操作结果：由线性表copy 构造新线性表——复制构造函数模板
{
int copyLength = copy.Length(); // copy的长度
int e;
Init(); // 初始化线性表
for (int curPosition = 1; curPosition
bool SimpleLinkList::Delete_x(int &x)
{
Node *p,*q;
int position=0;
p=head;
p=p->next;
while(p!=NULL)
{
position++;
if (position>=2&&p->data==x)
{
q=GetElemPtr(position-2);
Node *tmpPtr=q->next;
q->next=tmpPtr->next;
delete tmpPtr;
position--;
}
p=p->next;
}
return true;//这里加代码
}
int main()
{
int a[9]= {1,5,4,8,6,11,11,11,56};
SimpleLinkList la(a,9);
la.Traverse();
la.Delete_x(a[5]);
//这里完成删除x 的前一个节点操作
la.Traverse();
}
实验二
1、已知q 是一个非空顺序队列，s 是一个顺序栈，请设计一个算法，实现将队列q 中所有元素逆置。
2、请完成队列划分子集问题的算法。
实验2-1
主要代码：
void SqQueue::Traverse() const
// 操作结果：依次对队列的每个元素调用函数(*visit)
{
for (int curPosition = front; curPosition != rear;
curPosition = (curPosition + 1) % maxSize)
{ // 对队列每个元素调用函数(*visit)
cout
}
cout
}
bool SqQueue::OutQueue(int &e)
// 操作结果：如果队列非空，那么删除队头元素，并用e 返回其值，返回SUCCESS, // 否则返回UNDER_FLOW，
{
if (!Empty())
{ // 队列非空
e = elems[front]; // 用e 返回队头元素
front = (front + 1) % maxSize; // front指向下一元素 return true;
}
else
{ // 队列为空
return false;
}
}
bool SqQueue::GetHead(int &e) const
// 操作结果：如果队列非空，那么用e 返回队头元素，返回SUCCESS, // 否则返回UNDER_FLOW，
{
if (!Empty())
{ // 队列非空
e = elems[front]; // 用e 返回队头元素
return true;
}
else
{ // 队列为空
return false;
}
}
bool SqQueue::InQueue(const int &e)
// 操作结果：如果队列已满，返回OVER_FLOW,
// 否则插入元素e 为新的队尾，返回SUCCESS
{
if (Full())
{ // 队列已满
return false;
}
else
{ // 队列未满，入队成功
elems[rear] = e; // 插入e 为新队尾
rear = (rear + 1) % maxSize; // rear指向新队尾 return true;
}
}
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
int i,temp,n=10;
SqQueue q(n+1);
SqStack s(n+1);
for (i=0;i
q.InQueue(a[i]);
cout
q.Traverse();
for (i=0;i
{
q.OutQueue(temp);
s.Push(temp);
}
cout
s.Traverse();
for (i=0;i
{
s.Pop(temp);
q.InQueue(temp);
}
cout
q.Traverse();
return 0;
}
实验2-2
主要代码：
bool SqQueue::OutQueue(int &e)
// 操作结果：如果队列非空，那么删除队头元素，并用e 返回其值，返回SUCCESS, // 否则返回UNDER_FLOW，
{
if (!Empty())
{
// 队列非空
e = elems[front]; // 用e 返回队头元素 front = (front + 1) % maxSize; // front指向下一元素 return true;
}
else
{
// 队列为空
return false;
}
}
bool SqQueue::InQueue(const int &e)
// 操作结果：如果队列已满，返回OVER_FLOW,
// 否则插入元素e 为新的队尾，返回SUCCESS
{
if (Full())
{
// 队列已满
return false;
}
else
{
// 队列未满，入队成功
elems[rear] = e; // 插入e 为新队尾
rear = (rear + 1) % maxSize; // rear指向新队尾 return true;
}
}
int main()
{
int A[9]= {1,2,3,4,5,6,7,8,9};
int R[9][9],n=9,a,b,i,j,temp,group,num_all,num_group;
int result[n],newr[n];
SqQueue q(n+1);
for (i=0; i
{
result[i]=0;
for (j=0; j
{
R[i][j]=0;
}
}
for (i=0; i
q.InQueue(A[i]);
cout>a,a!=-1) //完成关系矩阵的赋值操作
{
cin>>b;
R[a-1][b-1]=1;
R[b-1][a-1]=1;
}
group=0;
num_all=n;
num_group=0;
while(!q.Empty()) //只要循环队列中元素不为空，就做如下的划分操作 {
group++;//第group 组的元素划分
q.OutQueue(temp); //该组第一个元素出栈
num_group++; //该组目前具有的数量
result[temp-1]=group;//该组元素对应的位置放到result 中
for (i=0; i
newr[i]=R[temp-1][i]; //把与该元素的冲突关系记录到数组
newr 中
num_all=num_all-num_group; //还需要出队列判断的元素数量 num_group=0; //初始化
for (j=0; j
{
q.OutQueue(temp);
if (newr[temp-1]==1) //如果该元素与当前的组的元素有冲突，重新入队
q.InQueue(temp);
else //否则把该元素加入到当前组中 {
result[temp-1]=group;
for (i=0; i
{
if (R[temp-1][i]==1) //把鱼当前元素有冲突的冲突关系加入到数组newr 中
newr[i]=1;
}
num_group++; //该组目前具有的元素数量
}
}
}
for (i=1; i
{
cout
for (j=0; j
{
if (result[j]==i)
cout
}
cout
}
return 0;
}
实验三
1、系数矩阵的快速转置，并输出转置之后的矩阵
2、二叉树的遍历，分别调用先序，中序和后序遍历算法输出遍历结果。
实验3-1
主要代码：
void TriSparseMatrix::FastTranspose(const TriSparseMatrix &source, TriSparseMatrix &dest)
// 操作结果：将稀疏矩阵source 转置成稀疏矩阵dest 的快速算法 {
dest.rows=source.cols;
dest.cols=source.rows;
dest.num=source.num;
dest.maxSize=source.maxSize;
delete []dest.triElems;
dest.triElems=new
Triple[dest.maxSize];
if(dest.num>0)
{
int destPos=0;
for(int col=1;col
{
for(int sourcePos=0;sourcePos
if(source.triElems[sourcePos].col==col) {
dest.triElems[destPos].row=source.triElems[sourcePos].col;
dest.triElems[destPos].col=source.triElems[sourcePos].row;
dest.triElems[destPos].value=source.triElems[sourcePos].value; destPos++;
}
}
}
}
//代码写在这里
// 释放cPos
}
int main(void)
{
const int n = 5;
TriSparseMatrix a(n, n); // 定义一个n 行n 列稀疏矩阵 int b[n][n] =
{
1, 0, 3, 0, 0,
4, 0, 6, 0, 0,
0, 0, 8, 9, 0,
0, 0, 0, 1, 12,
1, 0, 0, 3, 1
};
int i, j, v; // 工作变量
// 设置稀疏矩阵a 的元素值
for (i = 1; i
{
// 行
for (j = 1; j
{
// 列
a.SetElem(i, j, b[i - 1][j - 1]); // 设置元素值 }
}
// 显示转置前的稀疏矩阵a
cout
for (i = 1; i
{
// 行
for (j = 1; j
{
// 列
a.GetElem(i, j, v); // 求元素值
cout
}
cout
}
TriSparseMatrix c;
TriSparseMatrix::FastTranspose(a, c);// 转置a 成c
// 显示转置后稀疏矩阵c
cout
for (i = 1; i
{
// 行
for (j = 1; j
{
// 列
c.GetElem(i, j, v); // 求元素值
cout
}
cout
}
return 0; // 返回值0, 返回操作系统
}
实验3-2
主要代码：
void BinaryTree::InOrderHelp(BinTreeNode *r) const
// 操作结果：中序遍历以r 为根的二叉树
{
if(r!= NULL)
{
InOrderHelp(r->leftChild);
coutdata);
InOrderHelp(r->rightChild);
} //代码写在这里
}
void BinaryTree::InOrder() const
// 操作结果：中序遍历二叉树
{
InOrderHelp(root);
}
void BinaryTree::PostOrderHelp(BinTreeNode *r) const
// 操作结果：后序遍历以r 为根的二叉树
{
if(r!= NULL)
{PostOrderHelp(r->leftChild);
PostOrderHelp(r->rightChild);
coutdata);
}//代码写在这里
}
实验四
1、分别用普通查找和折半查找在数组中查找一个数字，输出其数组的下标和比较的次数。
2、散列表的构建与查找已知一组关键字
(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，利用线性探索法构建散列表，并根据每个输入的key 值输出其位置下标和比较的次数。
实验4-1
主要代码：
#include
using namespace std;
bool sqSearch(int a[], int n, int key, int &loc, int &count) //顺序查找函数：数组为a ；n 为数组中元素个数；key 为查找的数据，loc 为数据对应的位置；count 为比较的次数；查找成功返回true ，否则返回false. {
//代码内容
int i;
for (i=0;i
{
if (a[i]==key)
{
loc=i;
count=i+1;
return true;
}
}
return false;
}
bool BinSearch(int a[],int n,int key, int &loc, int &count) //折半查找函数：数组为a;n 为数组中元素个数;key 为查找的数据，loc 为数据对应的位置;count 为比较的次数; 查找成功返回true ，否则返回false.
{
//代码内容
int cou,mid,low,high;
cou=0;
low=0;
high=n-1;
while (low
{
mid=(low+high)/2;
cou=cou+1;
cout
if (a[mid]==key)
{
count=cou;
loc=mid;
return true;
}
else
if (key
high=mid-1;
else
low=mid+1;
}
return false;
}
int main()
{
int
num[19]={3,4,9,11,12,13,16,22,23,24,29,30,38,66,87,91,93,95,99}; int loc,count,n=19,key=91;
if (sqSearch(num,n,key,loc,count)==true)
{
cout
cout
cout
}
if (BinSearch(num,n,key,loc,count)==true)
{
cout
cout
cout
}
return 0;
}
实验4-2
主要代码：
#include
using namespace std;
void Hconstruct(int a[],int n,int c[],int p, int m)
{
int i,te;
int *temp=new int[m];
for (i=0; i
{
temp[i]=0;
}
for (i=0; i
{
te=a[i]%p;
if (temp[te]==0)
{
c[te]=a[i];
temp[te]=1;
}
else
{while (temp[te]==1)
{
te=(te+1)%m;
}
c[te]=a[i];
temp[te]=1;
}
}
}
void Hsearch(int key,int c[],int p,int m,int &loc,int &time) {
int temp;
time=1;
temp=key%p;
while(c[temp]!=key)
{
temp=(temp+1)%m;
time++;
loc=temp;
}
int main()
{
int a[12]={19,14,23,1,68,20,84,27,55,11,10,79};
int c[16];
int loc,time,key,p,m;
p=13;
m=16;
Hconstruct(a,12,c,p,m);
while(cin>>key,key!=-1)
{
Hsearch(key,c,p,m,loc,time);
cout
}
return 0;
}
实验五
1、对于100个无序的整数，分别使用冒泡排序、快速排序和希尔排序使其有序。
2、假设有100个红白蓝三种颜色的小色块(无序：三种颜色分别用0,1,2表示) ，编写程序，使每种颜色有序排列(注意：要求时间复杂度为O(n)).
实验5-1
主要代码：
#include
#include
#include
using namespace std;
//数据交换函数
void Swap(int &a, int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
//冒泡排序
void BubbleSort(int elem[], int n)
{
int flag, low=0, high=n-1 , i;
while (low
{
flag=0;
for (i= low; i
if (elem[i] > elem[i + 1])
{
Swap(elem[i], elem[i + 1]);
flag=1;
}
if(!flag) break;
high--;
for(i=high; i>low; i--) //反向冒泡
if( elem[i]
{
Swap(elem[i], elem[i-1]);
}
low ++;
}
}
//快速排序的一次划分
int Partition(int elem[], int low, int high)
{
while (low
{
while (low = elem[low])
{
high--;
}
Swap(elem[low], elem[high]);
while (low
{
low++;
}
Swap(elem[low], elem[high]);
}
return low;
}
//快速排序
void QuickSort(int elem[], int low, int high)
{
if (low
{
int pivotLoc=Partition(elem, low, high);
QuickSort(elem, low, pivotLoc-1);
QuickSort(elem, pivotLoc+1, high);
}
}
//希尔排序
void ShellInsert(int elem[],int n,int incr)
{
for (int i=incr;i
{
int e=elem[i];
int j;
for (j=i-incr;j>=0 && e
{
elem[j+incr]=elem[j];
}
elem[j+incr]=e;
}
}
void ShellSort(int elem[],int n, int inc[],int t)
{
for (int k=0;k
{
ShellInsert(elem,n,inc[k]);
}
}
int main()
{
int a[101],data[101],shelldata[101],n=100,i;
cout
srand((unsigned)time(NULL));
for (i=0; i
{
a[i]=rand()%1000;
data[i]=a[i];
shelldata[i]=a[i];
coutif ((i+1)%10==0)
{
cout
}
}
BubbleSort(a,n);
cout
for (i=0; i
{
coutif ((i+1)%10==0)
{
cout
}
}
QuickSort(data,0,n-1);
cout
for (i=0; i
{
cout
if ((i+1)%10==0)
{
cout
}
}
int incr[]={50,25,12,6,3,1};
int t=6;
ShellSort(shelldata,n,incr,t);
cout
for (i=0; i
{
cout
if ((i+1)%10==0)
{
cout
}
}
return 0;
}
实验5-2
主要代码：
#include
#include
using namespace std;
#define N 100
void swap (int &var1, int &var2)
{
int temp = var1;
var1 = var2;
var2 = temp;
}
void shuffle(int *array)
{
int current = 0;
int end = N-1;
int begin = 0;
while( current
{
if( array[current] ==0 )
{
swap(array[current],array[begin]);
current++;
begin++;
}
else if( array[current] == 1 )
{
current++;
}
else{//if array[current] =2
swap(array[current],array[end]);
end--;
}
}
}
int main()
{
int a[N];
int i;
cout
for( i=0 ; i
{
a[i] = rand()%3;
cout
}
cout
cout
shuffle(a);
for(i=0 ; i
{
cout
}
cout
return 0;
}
实验心得
数据结构是一门设计数据的结构的学科，要把书本上学到的东西运用到实践中去并不简单，我刚开始自己运用学到的知识去编程的时候有些不知所措，有些东西不能理解，这对初学者来说确实很难，又拿起课本仔细的研究了一下，询问了老师和同学才搞懂了一些东西，自己的程序才能顺利运行。
通过这门课程和这些实验让我逐渐了解了数据结构这门学科，也渐渐对编程加强了兴趣，总之学到了很多也得到了很多，感谢同学和老师对我的帮助和鼓励。