实验:顺序表的应用

一、实验目的

1.掌握如何将算法转换为程序;
2.熟悉顺序存储结构;
3.熟悉顺序表的操作;
4.熟悉顺序表的应用。

二、实验要求

1.程序要有注释,包括对总体功能、关键句、段的说明;
2.源程序必须调试通过,对每个输入的要求以及输出要有清晰的提示。程序要具有一定的健壮性,即当输入数据非法时,程序也能适当地做出反应,如插入删除时指定的位置不对等。

三、实验内容

1.实验题目
(1)完成顺序表的基本运算:初始化、显示、求长度、判空、判满、插入、删除、按位置取元素、按值查找等,并编写主函数测试算法。
(2))设计算法:将一个元素插入到有序的顺序表中,使顺序表仍有序,并编写主函数测试算法。

(3)设A和B两个顺序表,其元素按从小到大的顺序排列。编写一个算法将A和B的全部元素合并到有序顺序表C中,并编写主函数测试算法。
提示:有序表的合并;
有序表的产生,可以人为输入,也可以调用(2)的算法来实现。

2.数据结构的设计:
所选数据结构为顺序表。
3.算法描述:
(2)用循环给顺序表赋初值,将要插入的数据从前往后一个一个和原顺序表元素比较,当该数据比顺序表此该位置的值大,小于或等于原顺序表的后一个值时,记录该位置,然后将数据插入到该位置。
(3)在A,B都没合并完的前提下,用while循环一个个比较A和B里边的元素值,谁小,就把谁放到C里,以此类推。

四、算法实现

头文件:table.h

#ifndef _TABLE_H_
#define _TABLE_H_
#include <stdio.h>
#include <stdlib.h>
#define Size 5

typedef struct Table{
int * head;
int length;
int size;
}table;

table initTable();
int TableLength(table t);
int emptyTable(table t);
int fullTable(table t);
table addTable(table t,int elem,int add);
table insertTable(table t,int elem);
table mergeTable(table t1,table t2,table t3);
table delTable(table t,int add);
int selectTable(table t,int elem);
int getTable(table t,int add);
table amendTable(table t,int elem,int newElem);
void displayTable(table t);

#endif // TABLE_H

主函数:main.c

#include "table.h"

int main(){
int i,add=0,elem=0;
table t1=initTable();

//初始化后赋值
for (i=1; i<=Size; i++) {
t1.head[i-1]=i;
t1.length++;
}
printf("原顺序表:\n");
displayTable(t1);
printf("当前顺序表长度为:%d\n",TableLength(t1));
if (fullTable(t1)){
printf("当前顺序表已满\n");
}
printf("\n");

//删除指定元素
printf("请输入要删除的元素:");
scanf("%d",&elem);
t1=delTable(t1, elem);
printf("删除%d元素后,顺序表为:",elem);
displayTable(t1);
printf("\n");

//按位置插入元素
printf("请输入要插入元素的位置和元素的值:");
scanf("%d %d",&add,&elem);
printf("在第%d的位置插入元素%d后,顺序表为:\n",add,elem);
t1=addTable(t1, elem, add);
displayTable(t1);
printf("\n");

//查找元素的位置
printf("请输入要查找元素的值:");
scanf("%d",&elem);
printf("查找元素%d的位置为:\n",elem);
add=selectTable(t1, elem);
printf("%d\n",add);

//修改元素的值
printf("请输入要修改的元素:");
scanf("%d",&elem);
printf("请输入修改后的值:");
scanf("%d",&add);
printf("将元素%d改为%d:\n",elem,add);
t1=amendTable(t1, elem, add);
displayTable(t1);
printf("\n");

//按位置查找元素
printf("请输入要查找元素的位置:\n");
scanf("%d",&add);
printf("位置%d的元素为:",add);
printf("%d\n",getTable(t1,add));

//有序顺序表的插入
printf("有序顺序表如下\n");
t1.length=0;
for (i=1; i<=Size; i++) {
t1.head[i-1]=i;
t1.length++;
}
displayTable(t1);
printf("请输入要插入的元素值:\n");
scanf("%d",&elem);
t1=insertTable(t1,elem);
displayTable(t1);

//有序顺序表的合并
t1.length=0;
for (i=1; i<=t1.size; i++) {
t1.head[i-1]=i;
t1.length++;
}
printf("顺序表A的值为:\n");
displayTable(t1);//t1为A顺序表

table t2=initTable();//t2为B顺序表
for (i=t1.head[t1.size-1]+1; i<=t1.size+5; i++) {
t2.head[i-t1.head[t1.size-1]-1]=i;
t2.length++;
}
printf("顺序表B的值为:\n");
displayTable(t2);
table t3=initTable(); //t3用来存放合并后的顺序表
t3=mergeTable(t1,t2,t3);
printf("合并后的顺序表为:");
displayTable(t3);
return 0;
}

//初始化函数
table initTable(){
table t;
t.head=(int*)malloc(Size*sizeof(int));
if (!t.head)
{
printf("初始化失败\n");
exit(0);
}
t.length=0;
t.size=Size;
return t;
}

//求长度
int TableLength(table t){
return t.length;
}

//判空函数
int emptyTable(table t){
if (!t.length)
return 1;
return 0;
}

//判满
int fullTable(table t){
int temp=0;
if (t.length==t.size)
temp=1;
return temp;
}

//插入函数,其中,elem为插入的元素,add为插入到顺序表的位置
table addTable(table t,int elem,int add)
{
//判断插入本身是否存在问题
if (add>t.length+1||add<1) {
printf("插入位置有问题\n");
return t;
}
//判断是否需要申请内存空间
if (fullTable(t)) {
t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
if (!t.head) {
printf("存储分配失败\n");
return t;
}
t.size++;
}
//后移操作
for (int i=t.length-1; i>=add-1; i--) {
t.head[i+1]=t.head[i];
}
//将所需插入元素,添加到顺序表的相应位置
t.head[add-1]=elem;
t.length++;
return t;
}

//按顺序插入,找插入位置
table insertTable(table t,int elem){
int i=0;
while(i < t.length && elem >= t.head [i])//从小到大排列
{
i++;//注意i从0开始的 ,所以后面不用i - 1 ,这里的i即为下标
}
t=addTable(t,elem,++i);
return t;
}

table mergeTable(table t1,table t2,table t3){
int i=0,j=0,k=0;
while(i<t1.length || j<t2.length){

if(j == t2.length || i<t1.length && t1.head[i]<t2.head[j])

t3.head[k++] = t1.head[i++];
else
t3.head[k++] = t2.head[j++];
}
t3.length = k;
return t3;
}

table delTable(table t,int add){
if (add>t.length || add<1) {
printf("被删除元素的位置有误\n");
return t;
}
//删除操作
for (int i=add; i<t.length; i++) {
t.head[i-1]=t.head[i];
}
t.length--;
return t;
}

//按值查找函数,其中,elem表示要查找的数据元素的值
int selectTable(table t,int elem){
for (int i=0; i<t.length; i++) {
if (t.head[i]==elem) {
return i+1;
}
}
return -1;//如果查找失败,返回-1
}

//按位置取元素
int getTable(table t,int add){
if (add>t.length || add<1) {
printf("被查找元素的位置有误\n");
return 0;
}
return t.head[add-1];
}

//更改函数,其中,elem为要更改的元素,newElem为新的数据元素
table amendTable(table t,int elem,int newElem){
int add=selectTable(t, elem);
t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置,所以-1就是该元素在数组中的下标
return t;
}

void displayTable(table t){
for (int i=0;i<t.length;i++) {
printf("%d ",t.head[i]);
}
printf("\n");
}

五、实验运行结果

原顺序表:
1 2 3 4 5
当前顺序表长度为:5
当前顺序表已满

请输入要删除的元素:3
删除3元素后,顺序表为:1 2 4 5

请输入要插入元素的位置和元素的值:4
5
在第4的位置插入元素5后,顺序表为:
1 2 4 5 5

请输入要查找元素的值:5
查找元素5的位置为:
4
请输入要修改的元素:3
请输入修改后的值:4
将元素3改为4:
1 2 4 5 5

请输入要查找元素的位置:
3
位置3的元素为:4
有序顺序表如下
1 2 3 4 5
请输入要插入的元素值:
4
1 2 3 4 4 5
顺序表A的值为:
1 2 3 4 5 6
顺序表B的值为:
7 8 9 10 11
合并后的顺序表为:1 2 3 4 5 6 7 8 9 10 11

Process returned 0 (0x0) execution time : 18.143 s
Press any key to continue.