求数据结构试验 线性表的顺序存储结构

Question

实验一 线性表的顺序存储结构

一、 实验类型：设计性（2课时）
二、 实验目的与任务：
掌握顺序存储结构的特点，掌握动态顺序存储结构的常见算法。
三、预习要求：熟悉C语言中数组的使用，以及动态内存申请与消毁方法
四、实验基本原理：利用结构体实现动态顺序存储结构，并设计相应函数来解决动态数组的排序等问题。
五、实验仪器与设备：VC++，Windows OS
六、实验内容：
1．输入一组整型元素序列，建立顺序表。
2．实现该顺序表的遍历。判断该顺序表中元素是否对称,对称返回1,否则返回0。
3．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。
4．编写一个主函数,调试上述算法。
七、实验步骤：
1．进入编程环境，建立一新工程；
2. 存储定义
struct SqList{
int * elem; //动态线性表
int length; //表的实际长度
int listsize;
};
3. 编译运行程序，观察运行情况和输出结果。
4. 参考实验程序，以下几个函数实现了顺序表的创建以及插入和销毁，要求同学们能在此基础上完善其它函数并完成其它实验内容
5. 部分源参考源代码
//创建顺序表
void InitSqlist(SqList &sl)
{
sl.elem = (int*)malloc(100*sizeof(int));
sl.length = 0;
sl.listsize = 100;
return;
}

//将元素e插入第i个位置
void InsertSqlist(SqList &sl, int e, int i)
{
if(i>sl.listsize)
{
printf("插入位置超过限制！");
return;
}
//表满，重新分配内存
if(sl.length == sl.listsize)
{
sl.elem = (int *)realloc(sl.elem, (sl.listsize+10)*sizeof(int));
sl.listsize = sl.listsize+10;
sl.elem[i] = e;
}

//表不满，直接插入
if(sl.length<sl.listsize)
{
if(i>sl.length)
{
sl.elem[i] = e;
}
if(i<=sl.length)
{
for(int k=sl.length; k>=i; k--)
{
sl.elem[k+1]=sl.elem[k];
}
sl.elem[i] = e;
}
}
return;
}

//销毁顺序表
void FreeSqlist(SqList &sl)
{
free(sl.elem);
}
八、实验报告要求：按实验报告本格式填写各项内容，不得缺项。

Answer 1

查找：
顺序表的顺序查找算法：
int Seqsearch1(int r[],int n,int k)
{
r[0]=k;
i=n;
while(r[i]!=k)
i--;
return i;
}
单链表的顺序查找算法：
int Seqsearch2(Node<int> *first,int k)
{
p=first->next;j=1;
while(p!=NULL&&p->data!=k)
{
p=p->next;
j++;
}
if(p->data==k)return j;
else return 0;
}
折半查找：
非递归
int Binsearch1(int r[],int n,int k)
{
high=n;low=1;
while(low<=high)
{
mid=(high+low)/2;
if(k<mid) high=mid-1;
else if(k>mid) low=mid+1;
else return mid;
}
return 0;
}
递归
int Binsearch2(int r[],int low,int high,int k)
{
if(low>high) return 0;
else
{
mid=(low+high)/2;
if(K<mid) return Binsearch2(r,low,mid-1,k);
else if(K>mid) return Binsearch2(r,mid+1,high,k);
else return mid;
}
}
二叉树排序：
class BiSortTree
{
public:
BiSortTree(int a[],int n);
~BiSortTree();
void InsertBST(BiNode<int> *root,BiNode<int> *s);
void DeleteBST(BiNode<int> *p,BiNode<int> *f);
BiNode<int>* SearchBST(BiNode<int> *root,int k);
private:
BiNode<int> *root;
};
void BiSortTree::InsertBST(BiNode<int> *root,BiNode<int> *s);
{
if(root==NULL) root=s;
else if(s->data<root->data) InsertBST(root->lchild,s);
else InsertBST(root->rchild,s);
}
BiSortTree::BiSortTree(int r[],int n)
{
for(i=0;i<n;i++)
{
s=new BiNode<int>;s->data=r[i];
s->lchild=s->rchild=NULL;
InsertBST(root,s);
}
}
void BiSortTree::DeleteBST(BiNode<int> *p,BiNode<int> *f)
{
if(!p->lchild&&!p->rchild)
{
f->lchild=NULL;
delete p;
}
else if(!p->lchild)
{
f->lchild=p->rchild;
delete p;
}
else if(!p->rchild)
{
f->lchild=p->lchild;
delete p;
}
else
{
par=p;s=p->rchild;
while(s->lchild!=NULL)
{
par=s;
s=s->lchild;
}
p->data=s->data;
if(par==p) par->rchild=s->rchild;
else par->lchild=s->rchild;
delete s;
}
}
BiNode<int> *BiSortTree::SearchBST(BiNode<int> *root,int k)
{
if(root==NULL) return NULL;
else if(root->data==k) return root;
else if(root->data<k) return SearchBST(root->lchild,k);
else return SearchBST(root->rchild,k);
}
闭散列表的查找算法：
int HashSearch1(int ht[],int m,int k)
{
j=H[k];
if(ht[j]==k) return j;
i=(j+1)%m;
while(ht[i]!=Empty&&i!=j)
{
if(ht[i]==k) return i;
i=(i+1)%m;
}
if(i==j) throw"溢出";
else ht[i]=k;
}
开散列表的查找算法：
Node<int> *HashSearch2(Node<int> *ht[],int m,int k)
{
j=H[k];
p=ht[j];
while(p&&p->data!=k)
p=p->next;
if(p->data==k) return p;
else
{
q=new Node<int>;q->data=k;
q->next=ht[j];
ht[j]=q;
}
}
排序：
插入
直接插入排序算法：
void InsertSort(int r[],int n)
{
for(i=2;i<=n;i++)
{
r[0]=r[i];
for(j=i-1;r[0]<r[j];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
希尔排序算法：
void ShellSort(int r[],int n)
{
for(d=n/2;d>=1;d=d/2)
{
for(i=d+1;i<=n;i++)
{
r[0]=r[i];
for(j=i-d;j>0&&r[0]<r[j];j=j-d)
r[j+d]=r[j];
r[j+d]=r[0];
}
}
}
交换
起泡排序：
void BubbleSort(int r[],int n)
{
exchange=n;
while(exchange)
{
bound=exchange;exchange=0;
for(j=1;j<bound;j++)
if(r[j]>r[j+1])
{
r[j]<-->r[j+1];
exchange=j;
}
}
}
快速排序：
int Partition(int r[],int first,int end);
{
i=first;j=end;
while(i<j)
{
while(i<j&&r[i]<=r[j]) j--;
if(i<j)
{
r[i]<-->r[j];
i++;
}
while(i<j&&r[i]<=r[j]) i++;
if(i<j)
{
r[i]<-->r[j];
j--;
}
}
return i;
}
void QuickSort(int r[],int first,int end)
{
if(first<end)
{
pivot=partition(r,first,end)
QuickSort(r,first,pivot-1);
QuickSort(r,pivot+1,end);
}
}
选择
简单选择排序：
void SelectSort(int r[],int n)
{
for(i=1;i<n;i++)
{
index=i;
for(j=i+1;j<n;j++)
if(r[j]<r[index]) index=j;
if(index!=i) r[i]<-->r[index];
}
}
堆排序：
void Sift(int r[],int k,int m)
{
i=k;j=2*i;
while(j<=m)
{
if(j<m&&r[j]<r[j+1])j++;
if(r[i]>r[j]) break;
else
{
r[i]<-->r[j];
i=j;j=2*i;
}
}
}
void HeapSort(int r[],int n)
{
for(i=n/2;i>=1;i--)
sift(r,i,n);
for(i=1;i<n;i++)
{
r[1]<-->r[n-i+1];
sift(r,1,n-i);
}
}
归并
二路归并排序：
void Merge(int r[],int r1[],int s,int m,int t)
{
i=s;j=m+1;k=s;
while(i<=m&&j<=t)
{
if(r[i]<=r[j]) r1[k++]=r[i++];
else r1[k++]=r[j++];
}
if(i<=m) while(i<=m)
r1[k++]=r[i++];
else while(j<=t)
r1[k++]=r[j++];
}
void Merge(int r[],int r1[],int n,int h)
{
i=1;
while(i<=n-2h+1)
{
Merge(r,r1,i,i+h-1,i+2h-1);
i=i+2*h;
}
if(i<n-h+1) Merge(r,r1,i,i+h-1,n)
else for(k=i;k<=n;k++)
r1[k]=r[k];
}
void MergeSort1(int r[],int r1[],int n)
{
h=1;
while(h<n)
{
MergePass(r,r1,n,h);
h=2*h;
MergePass(r1,r,n,h);
h=2*h;
}
}
void MergeSort2(int r[],int r1[],int s,int t)
{
if(s==t) r1[s]=r[t];
else
{
m=(s+t)/2;
MergeSort2(r,r1,s,m);
MergeSrot2(r,r1,m+1,t);
Merge(r1,r,s,m,t);
}
}

Answer 2

#include<iostream.h>
#include<stdlib.h>
#include <malloc.h>
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100//线性表存储空间的初始增量
#define LISTINCREMENT 10 // ?
typedef struct{
int * elem;// 存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
SqList L;
int InitList_Sq(SqList & L){
//构造一个新的线性表。
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)exit(OVERFLOW);//存储容量失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//存储初始容量
return OK;
}//InitList_Sq
int LIstInsert_Sq(SqList & L,int i,int e){
//在顺序线性表L中第i位置之前插入新的元素e
if(i<1||i>L.length+1) return ERROR;
if(L.length>=L.listsize){
int * newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int * q=&(L.elem[i-1]);
for(int * p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList&L,int i,int &e)
{
if((i<1)||(i>L.length))return ERROR;
int *p=&(L.elem[i-1]);
e=*p;
int *q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return OK;
}
void main()
{
SqList L;
int i,n;
int e;
cout<<"输入顺序表的个数："<<endl;
cin>>n;
int *p=(int *)malloc(n*sizeof(int));
InitList_Sq(L);
cout<<"输入线性表"<<n<<"个元素的值"<<endl;
for(i=0;i<n;i++)
{
cin>>p[i];
L.elem[i]=p[i];
}
cout<<endl;
L.length=i;
cout<<endl;
cout<<"输入要插入元素的值"<<endl;
cin>>e;
cout<<endl;
cout<<"输入要插入的位置"<<endl;
cin>>i;
LIstInsert_Sq( L, i, e);
for(i=0;i<n+1;i++)
cout<<L.elem[i];
cout<<endl;
cout<<"输入要删除的位置"<<endl;
cin>>i;
ListDelete_Sq(L,i,e)
;for(i=0;i<n;i++)
cout<<L.elem[i];
free(p);

Answer 3

#include<stdlib.h>
#define max_sq_size 100

void creat(int *sqlist) {
int a, b, i;
printf("请输入节点数\n：");
scanf("%d", &a);
if(a<0 ||a > max_sq_size){
printf("节点数不正确！\n");
system("PAUSE");
}
for(i=0; i != a; i++) {
printf("请输入第%d 个节点\n",i+1);
scanf("%d", &b);
sqlist[i] = b;
}
}
void hebing(int *sqlist1, int *sqlist2) {
int i, j, a;
i = 0;
while(sqlist1[i]) {
printf("########\n");
a = sqlist1[i];
j = 0;
while(a != sqlist2[j]&&sqlist2[j]) {
printf("*****\n");
j++;
}
if( a != sqlist2[j]) sqlist2[j] = a;

i++;
}
}
void display(int *sqlist) {
int i= 0;
while(sqlist[i]) {
printf("%5d", sqlist[i]);
i++;
}
printf("\n");
}
int main(void )
{
int sqlist1[max_sq_size] =;
int sqlist2[max_sq_size]= ;
creat(sqlist1);
creat(sqlist2);
display(sqlist1);
display(sqlist2);
hebing(sqlist1, sqlist2);
display(sqlist2);
system("PAUSE");
}//草，本来以为很简单的，结果差错查了一个小时。汗

追问

谢谢，不过在VC 6.0下运行不了

Answer 4

都有参考了，为什么不自己做做呢？
自己没有一点想法么