数据结构作业

【项目1 – 顺序表的基本运算】

建立建立顺序表运算的算法库。 算法库包括两个文件： 头文件：list.h，包含定义顺序表数据结构的代码、宏定义、要实现算法的函数的声明； 源文件：list.cpp，包含实现各种算法的函数的定义 请采用程序的多文件组织形式，建立如上的两个文件，另外再建立一个源文件，编写main函数，完成相关的测试工作（以下操作在主函数中调用实现）。

创建一个顺序表，测试样例：5，9，6，7，4，8，1，3，2；在已经建立的线性表的第8个位置插入一个元素x（10），测试样例：5，9，6，7，4，8，1，10，3，2。删除第4个位置上的元素，并输出线性表。从顺序表中删除具有最小值的元素（假设值唯一），并由函数返回被删除元素的值。若顺序表为空则提示错误信息信息并退出。注意时间复杂度。编写算法函数 Reverse( )实现将顺序表的倒置。要求算法的空间复杂度为O(1)

list.h

#ifndef LIST_H_INCLUDED #define LIST_H_INCLUDED #include<stdio.h> #define MaxSzie 100 typedef int ElemType; typedef struct { ElemType data[MaxSzie]; int length; }SqList; void CreateList(SqList *&L, ElemType a[],int n); void InitList(SqList *&L); void Insert(SqList *&L, int i,int n); void ShowList(SqList *L); void DeleteList(SqList *&L,int n); void Reverse(SqList *&L); void DeleteMin(SqList *&L); #endif // LIST_H_INCLUDED

list.cpp

#include <iostream> #include <stdio.h> #include <stdlib.h> #include "list.h" void CreateList(SqList *&L, ElemType a[],int n) { int i =0,k =0 ; L = (SqList *)malloc(sizeof(SqList)); while(i<n) { L->data[k] = a[i]; k++; i++; } L->length = k; } void InitList(SqList *&L) { printf("正在进行列表初始化：\n"); L=(SqList *)malloc(sizeof(SqList)); L->length = 0; printf("列表初始化完成！\n\n"); } void Insert(SqList *&L, int i,int n) { int j; if(i<1||i>L->length+1||L->length==MaxSzie) { printf("无法插入！\n"); } else { for(j = L->length;j>i;j--) { L->data[j] = L->data[j-1]; } L->data[i] = n; L->length++; } } void ShowList(SqList *L) { int i; for(i=0;i<L->length;i++) { printf("%d ",L->data[i]); } printf("\n"); } void DeleteList(SqList *&L,int n) { if(n<1||n>L->length) { printf("删除位置不存在\n"); } n--; int i; for(i=n;i<L->length;i++) { L->data[i] = L->data[i+1]; } L->length--; } void Reverse(SqList *&L) { int temp,i; for(i = 0;i<L->length/2;i++) { temp = L->data[i]; L->data[i] = L->data[L->length-1-i]; L->data[L->length-1-i] = temp; } } void DeleteMin(SqList *&L) { int i; int Min = L->data[0]; int MinPos = 0; if(L->length == 0) { printf("列表为空，信息错误\n"); } for(i=0;i<L->length;i++) { if(L->data[i]<Min) { Min = L->data[i]; MinPos = i; } } DeleteList(L,MinPos); printf("被删除的数是：%d\n",Min); ShowList(L); }

main.cpp

#include <iostream> #include<stdio.h> #include "list.h" #include "list.cpp" using namespace std; int main() { int n,i,k; SqList *L; printf("请输入创建数组的大小：\n"); scanf("%d",&n); int a[n]; printf("请输入创建数组的每个数：\n"); for(i =0;i<n;i++) { scanf("%d",&k); a[i]=k; } //初始化列表 InitList(L); printf("1.+++++++++++++++++++++++++++++\n"); //1.创建一个顺序表，测试样例：5，9，6，7，4，8，1，3，2 CreateList(L,a,n); ShowList(L); printf("2.+++++++++++++++++++++++++++++\n"); //2.在已经建立的线性表的第8个位置插入一个元素x（10），测试样例：5，9，6，7，4，8，1，10，3，2。 Insert(L,8,10); ShowList(L); printf("3.+++++++++++++++++++++++++++++\n"); //3.删除第4个位置上的元素，并输出线性表 DeleteList(L,4); ShowList(L); printf("4.+++++++++++++++++++++++++++++\n"); //从顺序表中删除具有最小值的元素（假设值唯一），并由函数返回被删除元素的值。若顺序表为空则提示错误信息信息并退出。注意时间复杂度。 DeleteMin(L); printf("5.+++++++++++++++++++++++++++++\n"); //5.编写算法函数 Reverse( )实现将顺序表的倒置。要求算法的空间复杂度为O(1) Reverse(L); ShowList(L); }

运行结果如下：

【项目2 – 顺序表应用】

在上题完成的算法库的基础上，定义一个采用顺序结构存储的线性表，设计算法完成下面的工作： 1、删除元素下标介于[x, y]之间的所有元素（包含x，y要求x < y ），x,y由用户随机指定,如果x, y 不合理或者顺序表为空则显示出错信息并退出运行。 尽量考虑以较好的时间复杂度和空间复杂度来实现。 2、将所有偶数移到所有奇数的前面，尽量考虑以较好的时间复杂度和空间复杂度来实现。

【提示】： （1）充分利用前面建立的算法库解决建立顺序表、输出线性表的问题； （2）为保证复杂度的要求，设计算法并用专门的函数实现算法； （3）每项工作写一个程序

基于项目一的代码，在其上进行补充：

list.h

bool DeleteSome(SqList *&L,int x,int y); void change(SqList *&L);

list.cpp

//项目二 bool DeleteSome(SqList *&L,int x,int y) { int m = y-x+1;//计算还有多少元素 int j; if(y<=x||x<0||y>L->length) { return false; } for(j =x-1;j<L->length-m;j++) { L->data[j] = L->data[j+m]; } L->length = L->length-m; return true; } void change(SqList *&L) { int i,j; int temp; for(i = 0;i<L->length;i++) { if(L->data[i]%2 == 0) { for(j = i+1;j<L->length;j++) { if(L->data[i]%2 == 1) { temp = L->data[i]; L->data[i] = L->data[j]; L->data[j] = temp; } } } } ShowList(L); }

mian.cpp

printf("项目二+++++++++++++++++++++++++++++\n"); printf("1.+++++++++++++++++++++++++++++\n"); if(DeleteSome(L,3,5)) { printf("删除成功 ！\n"); } else { printf("发生错误！\n"); } printf("2.+++++++++++++++++++++++++++++\n"); change(L);

运行结果如下：