经典数据结构上机题—答案

数据结构上机实验题目

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

实验学时 2学时

背景知识:顺序表的插入、删除及应用。

目的要求：

1．掌握顺序存储结构的特点。

2．掌握顺序存储结构的常见算法。

实验内容

1．输入一组整型元素序列，建立顺序表。

2．实现该顺序表的遍历。

3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。

4．判断该顺序表中元素是否对称,对称返回1,否则返回0。

5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。

6．输入整型元素序列利用有序表插入算法建立一个有序表。

7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。

8. 利用该顺序结构实现循环队列的入队、出队操作。

8．编写一个主函数,调试上述算法。

#include <stdio.h>

#include <stdlib.h>

#define OVERFLOW 0

#define MAXSIZE 100

typedef int ElemType;

typedef struct list

{ElemType elem[MAXSIZE];

int length;

}Sqlist;

void Creatlist(Sqlist &L)

{int i;

printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。

scanf("%d",&L.length);

for(i=0;i<L.length;i++)

scanf("%d",&L.elem[i]);

}

void printlist(Sqlist &L) //以输出的形式实现对该顺序表的遍历

{int i;

for(i=0;i<L.length;i++)

printf("%d ",L.elem[i]);

printf("\n");

}

void Searchlist(Sqlist &L,int x) //在顺序表中进行顺序查找某一元素x，查找成功则返回其存储位置i，否则返回错误信息

{int i,k=-1;

for(i=0;i<L.length;i++)

if(L.elem[i]==x){

k=i+1;printf("%d ",k);}

if(k==-1)

printf("error!");

printf("\n");

}

void Inseri(Sqlist &L,int i,int x) //在顺序表的第i个位置上插入一个元素x {int j;

for(j=L.length;j>=i;j--)

L.elem[j]=L.elem[j-1];

L.elem[j]=x;

L.length++;

}

void Delete(Sqlist &L,int i) //删除顺序表中第i个元素

{int j;

for(j=i;j<L.length;j++)

L.elem[j-1]=L.elem[j];

L.length--;

}

void Insert(Sqlist &L,int x) //输入一个元素x，把它插入到有序表中，使顺序表依然有序。

{int i,j;

if(L.length==MAXSIZE) exit(OVERFLOW); //表满，不能插入

for(i=1;i<=L.length&&L.elem[i-1]<=x;i++);

for(j=L.length;j>=i;j--)

L.elem[j]=L.elem[j-1];

L.elem[i-1]=x;

L.length++;

}

void Creatlist_sorted(Sqlist &L) //利用有序表插入算法建立一个有序表 {int i,num;

ElemType x;

L.length=0;

printf("请输入顺序表的长度：");

scanf("%d",&num);

for(i=1;i<=num;i++)

{

scanf("%d",&x);

Insert(L,x);

}

}

void Merger(Sqlist &p,Sqlist &r,Sqlist &c) //建立两个非递减有序表，并把它们合并成一个非递减有序表

{

ElemType *a,*b,i=0,j=0,k=0;

a=&p.elem[0];

b=&r.elem[0];

c.length=p.length+r.length;

while(i<p.length&&j<r.length)

{if(*a>=*b)

{c.elem[k]=*b;b++;k++;j++;}

else {c.elem[k]=*a;a++;k++;i++;}

}

if(j==r.length)

for(;k<c.length;k++)

{c.elem[k]=*a;a++; }

else if(i==p.length)

for(;k<c.length;k++)

{c.elem[k]=*b;b++;}

}

void main()

{Sqlist L,M,N;

int x,i,n;

printf("1.建立一个顺序表.\n");

printf("2.以输出的形式对该顺序表遍历.\n");

printf("3.在顺序表中进行顺序查找某一元素x.\n");

printf("4.在顺序表的第i个位置上插入一个元素x.\n");

printf("5.删除顺序表中第i个元素.\n");

printf("6.利用有序表插入算法建立一个有序表.\n");

printf("7.建立两个非递减有序表，并把它们合并成一个非递减有序表.\n"); printf("8.输入一个元素x，把它插入到有序表中，使顺序表依然有序.\n"); while(1){

printf("请选择：");

scanf("%d",&n);

switch(n)

{case 1:Creatlist(L);break;

case 2:printlist(L);break;

case 3:printf("请输入要查找的元素x:");

scanf("%d",&x);

Searchlist(L,x);break;

case 4:printf("请输入要插入的位置i:");

scanf("%d",&i);

if(i<1||i>L.length+1){

printf("error!\n");break;}

printf("请输入要插入的值x:");

scanf("%d",&x);

Inseri(L,i,x);

printlist(L);break;

case 5:printf("请输入要删去的元素的位置i:");

scanf("%d",&i);

if(i<1||i>L.length){

printf("error!\n");break;}

Delete(L,i);

printlist(L);break;

case 6:Creatlist_sorted(L);

printlist(L);break;

case 7:Creatlist_sorted(L);

Creatlist_sorted(M);

Merger(L,M,N);

printlist(N);break;

case 8:Creatlist_sorted(L);

printf("请输入要插入的元素x:");

scanf("%d",&x);

Insert(L,x);

printlist(L);break;

}

}

}

实验二 链式存储结构（一）----单向链表的有关操作

实验学时 3学时

背景知识：单向链表的插入、删除及应用。

目的要求

1．掌握单向链表的存储特点及其实现。

2．掌握单向链表的插入、删除算法及其应用算法的程序实现。 实验内容

1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

2．遍历单向链表。

3．把单向链表中元素逆置（不允许申请新的结点空间）。

4．在单向链表中删除所有的偶数元素结点。

5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。

7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。

8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

* 9．采用单向链表实现一元多项式的存储并实现两个多项式相加 …… 此处隐藏：8654字，全部文档内容请下载后查看。喜欢就下载吧 ……