线性表的基本操作及其应用
前言
本次实验为个人作业，这里只作为记录和参考，代码部分注释自己看，部分代码无用注释并未删除，是写代码时测试用的，请自行删除，代码内所需文件请自行建立
一、实验目的
1、帮助读者复习C语言程序设计中的知识。
2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现。
4、掌握顺序表的存储结构形式及其描述和基本运算的实现。
5、熟练掌握动态链表结构及有关算法的设计
二、实验环境
- PC机一台，Dev-c或CodeBlocks
三、实验内容
题目一：线性表的基本操作（要求必须采用顺序存储结构）
[问题描述]
实现线性表的建立、求长度，取元素、修改元素、插入、删除等基本操作。要求采用顺序存储结构完成。
[基本要求]
（1）依次从键盘或文件读入数据，建立线性表A和表B；
（2）输出两个线性表中的数据元素；
（3）求线性表A和表B的长度；
（4）取表A的第3个元素和修改表B的第6个元素15为14；
（5）实现在表A的第3个位置前插入元素6，删除原来第3个位置（插入操作后第4个为位置）元素8；
（6）将两个有序的线性表表A和表B合并成一个有序线性表（元素可以重复），测试数据经过上述修改后输出结果为2 3 5 6 6 8 9 11 11 14 20；
[测试数据]
ListA.txt文件内容如下：3 5 8 11
ListB.txt文件内容如下：2 6 8 9 11 15 20
题目二：图书管理系统的单链表存储(要求必须采用链式存储)
[问题描述]
从book.txt中读入图书数据，已结构体Book作为一行图书记录的数据存储结构，实现带头结点的图书信息单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。（程序参考I/O框架已给出）
[基本要求]
（1）依次book.txt文件读入数据，建立带头结点的单链表；
（2）输出单链表中的数据元素
（3）求单链表的长度；
（4）根据指定条件能够取出元素和修改元素；(取出和修改位置内容任选)
（5）实现在指定位置插入和删除元素的功能。（插入和删除位置和内容任选）
[测试数据] book.txt
ISBN 书名 定价
9787302257646 程序设计基础 25
9787302219972 单片机技术及应用 32
9787302203513 编译原理 46
9787811234923 汇编语言程序设计教程 21
9787512100831 计算机操作系统 17
9787302265436 计算机导论实验指导 18
9787302180630 实用数据结构 29
9787302225065 数据结构（C语言版） 38
9787302171676 C#面向对象程序设计 39
9787302250692 C语言程序设计 42
9787302150664 数据库原理 35
9787302260806 Java编程与实践 56
9787302252887 Java程序设计与应用教程 39
9787302198505 嵌入式操作系统及编程 25
9787302169666 软件测试 24
9787811231557 Eclipse基础与应用 35四、实验记录与分析
此部分内容要求有效果截图和实现过程的文字描述，代码要求结合截图和文字，粘贴核心部分内容，并加入必要注释！
五、实验总结
实验总结请从下面课程目标3的能力要求出发，客观描述自己通过理论和实践内容的学习和练习，能力方面的变化情况。
题目一实现线性表顺序存储操作代码
#include<iostream>
#include<fstream>
#define MAXSIZE 100
#define ERROR 0
#define OK 1
using namespace std;
//定义顺序表(表结构)
typedef int ElemType;//初始化一个通配的类型，防止数据换类型
typedef struct {
ElemType *elem;//地址
int length;
} SqList;
//初始化顺序表，创建
void InitSqList(SqList &L) {
L.elem =new int[MAXSIZE];//为顺序表分配MAXSIZE大小的空间
if(!L.elem) exit(ERROR);//存储分配失败退出
L.length = 0;//空表长度为0
}
//读取文件中内容并赋值给SqList
void SqListInput(SqList &L, char filename[]) {
//与源代码同级目录下的文件filename中输入数据，把数据读入到线性表L中
int i = 0;
fstream file; //构造fstream类的对象file，你可以理解为是一个有操作的ADT
file.open(filename); //使用file对象中的open操作打开filename中的文件
if(!file) { //如果没见不存在则返回空，输出找不到文件的提示信息
cout << "未找到"<<filename<<"文件，无法打开！" << endl;
exit(ERROR);
}
while (!file.eof())
//使用file对象中判断文件中数据是否结束的方法eof。如果到达文件结尾返回true，否则false
{
file >> L.elem[i]; //文件中的数据流式输入到线性表中
i++;
}
L.length = i; //更新线性表表长
}
//输出SqList
void SqListOutPut(SqList L) {
int i;
for(i=0; i<L.length; i++) {
cout << L.elem[i] << " ";
}
}
//获取SqList长度
int GetLength(SqList L) {
return L.length;
}
//获取第i个数据
int GetElem(SqList L,int i) {
if(i<1||i>L.length) return ERROR;
ElemType e;
e = L.elem[i-1];
return e;
}
//获取第i个数据
//int getElem1(SqList L,int i,ElemType &e)
//{
// if(i<1||i>L.length) return ERROR;
// e = L.elem[i-1];
// return OK;
//}
//获取元素下标
int GetIndex(SqList L,ElemType e) {
int i;
for(i=0; i<L.length; i++)
if(L.elem[i]==e) return i;
return ERROR;
}
//修改表元素
int ChangeElem(SqList &L,int i,ElemType e) {
if(i<1||i>L.length)
return ERROR;
L.elem[i-1]=e;
return OK;
}
//在第i个元素插入
int InsertElem(SqList &L,int i,ElemType e) {
if(i<1||i>L.length+1)
return ERROR;
if(L.length==MAXSIZE) //存储空间已满
return ERROR;
int j;
for(j=L.length-1; j>=i-1; j--)
L.elem[j+1]=L.elem[j];//要插入位置的元素以及它后边的元素后移
L.elem[i-1]=e;
++L.length;
return OK;
}
//删除表中第i个元素
int DeleteElem(SqList &L,int i) {
if(i<1||i>L.length)
return ERROR;
int j;
for(j=i; j<L.length; j++)
L.elem[j-1]=L.elem[j];//被删除元素后边的元素前移
--L.length; //表长减1
return OK;
}
int MergeSqList(SqList &LA,SqList &LB,SqList &LC) {
int i,j,flag;
if(LA.length==MAXSIZE||LB.length==MAXSIZE) //存储空间已满
return ERROR;
LC.length=LA.length+LB.length;
for(i=0; i<LA.length; i++) {
LC.elem[i]=LA.elem[i];
}
for(i=0; i<LB.length; i++) {
LC.elem[i+LA.length]=LB.elem[i];
}
//冒泡排序
for(i=0; i<LC.length; i++) {
for(j=0;j<=i;j++) {
if(LC.elem[j]>LC.elem[j+1]) {
flag=LC.elem[j+1];
LC.elem[j+1]=LC.elem[j];
LC.elem[j]=flag;
}
}
}
return OK;
}
int main() {
//LA表的建立与读取
SqList LA;
InitSqList(LA);
SqListInput(LA, (char*)"ListA.txt");
cout << "ListA: ";
SqListOutPut(LA);
//LB表的建立与读取
SqList LB;
InitSqList(LB);
SqListInput(LB, (char*)"ListB.txt");
cout << endl<<"ListB: ";
SqListOutPut(LB);
//表C的建立与初始化
SqList LC;
InitSqList(LC);
//LA表长
cout << endl<<"ListA的长度: " << GetLength(LA) << endl;
//LB表长
cout << "ListB的长度: " << GetLength(LB) << endl;
//读取表A中第三个元素
cout << "ListA中第三个元素: " << GetElem(LA,3) << endl;
//获取表A中数据为8的下标
cout << "ListA中元素为5的下标: " << GetIndex(LA,5) << endl;
//修改表B的第6个元素15为14；
ChangeElem(LB,6,14);
cout << "已经将第6个元素值15修改为14，新的线性表LA内容如下："<< endl;
SqListOutPut(LB);
//在LA的第三个元素前插入数据：6
InsertElem(LA,3,6);
cout <<endl<< "在表A的第3个位置前插入元素6, 新的线性表LA内容如下："<< endl;
SqListOutPut(LA);
//删除LA中的第三个元素
DeleteElem(LA,3);
cout <<endl<< "删除表A中的第3个元素，新的线性表LA内容如下："<<endl;
SqListOutPut(LA);
//合并AB表并排序
MergeSqList(LA,LB,LC);
cout <<endl <<"合并两个线性表LA和LB,并保持其元素有序性。合并后新的线性表LC内容如下："<<endl;
SqListOutPut(LC);
return 0;
}
题目二实现线性表链式存储操作代码
#include<iostream>
#include<string>
#include<fstream>
#include<iomanip>
using namespace std;
#define OVERFLOW -2
#define ERROR 0
#define OK 1
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型
struct Book {
string id;//ISBN
string name;//书名
double price;//定价
};
//LinkNode中存了数据和指向下一个结点的指针地址
typedef struct LinkNode {
Book data; //数据域
struct LinkNode *next; //指针域，指向直接后继
} LinkNode, *LinkList;
string head_1, head_2, head_3; //全局变量，记录book.txt表头信息
int length; //全局变量，记录链表表长信息
Status InitLinkList_L(LinkList &L) {
//构造一个空的单向链表L
L = new LinkNode;
//相当于L.next
L->next = NULL;//头结点指针域置空
return OK;
}
//帮助理解 L->next=(*L).next=head.next=首元结点的地址 而*L表示取指针L所指的地址的内容（也就是头结点）
Status CreateList(LinkList &L,char filename[]) {
//使用前/后插法从文件book.txt读入图书数据，并写入线性表L中，下面是部分代码需要自己完善
// LinkNode *p;
//定义一个 LinkNode的指针head指向L，否则不能对L操作
LinkNode* head = L,*p;
// L = new LinkNode;
// L->next = NULL; //先建立一个带头结点的空链表
length = 0;
fstream file;
file.open(filename);//book.txt文件要放在和源代码文件同级目录下（英文路径）
if (!file) {
cout << "未找到"<<filename<<"文件，无法打开！" << endl;
exit(ERROR);
}
file >> head_1 >> head_2 >> head_3;
while (!file.eof()) {
p = new LinkNode; //生成新结点
file >> p->data.id >> p->data.name >> p->data.price; //输入元素值
// p=p->next;
// L->data.id = p->data.id;
// p=L->next;
// L->next=NULL;
//方法一，将P赋值给首元结点，然后首元结点的指针后移
head->next = NULL;//头结点指针域置空
head->next=p;
head=head->next;
//方法二，将P赋值给首元结点，并将p赋值给head，此时head会随着循环不断后移
//head->next = NULL;//头结点指针域置空
//head->next = p;
//head = p;
length++;
// L=p;
// L->next=L->next->next;
// L->next=p->next;
// cout<< L->next->data.id <<endl;
// p=p->next;
// cout<< L->next->data.name <<endl;
// cout<< L->next->data.price <<endl;
}
file.close();
}//CreateList
//输出OutputLinkList
void OutputLinkList(LinkList &L) {
LinkNode* p = L->next;
ElemType e;
while(p) {
cout<< p->data.id <<" "<<p->data.name<<" "<<p->data.price<<endl;
p=p->next;
}
}
LinkNode *GetElem(LinkList L, int i) {
//在带头结点的单向链表L中查找第i个元素，返回结点的地址，下面代码需要自己编写
LinkNode* p=L->next;
int j=1;
//j<i控制循环次数
while(p && j<i) {
p=p->next;
++j;
}
return p;
} //GetElem
Status ListInsert(LinkList &L, int i, Book e) { // 单向链表的插入元素，下面代码需要自己编写
LinkNode* p=L;
LinkNode* newNode=new LinkNode;
int j=0;
while(p && j<i-1) {
p=p->next;
++j;
}
if(!p||j>i-1) return ERROR;
newNode->data=e;
newNode->next=p->next;
p->next=newNode;
return OK;
} //ListInsert
Status ListDelete(LinkList &L, int i) { //单向链表的删除，下面代码需要自己编写
LinkNode* p=L;
int j=0;
while(p && j<i-1) {
p=p->next;
++j;
}
if(!(p->next)||(j>i-1)) return ERROR;
LinkNode* q=p->next;
cout<<q<<endl;
p->next=q->next;
delete q;
return OK;
}//ListDelete
int main() {
int a, choose;
Book e;
LinkList L, p;
cout << "1. 建立\n";
cout << "2. 输入\n";
cout << "3. 插入\n";
cout << "4. 删除\n";
cout << "5. 输出\n";
cout << "0. 退出\n\n";
choose = -1;
while (choose != 0) {
cout << "请选择:";
cin >> choose;
switch (choose) {
case 1: //建立一个链表
if (InitLinkList_L(L))
cout << "成功建立链表!\n\n";
break;
case 2: //使用前/后插法创建链表
CreateList(L,(char*)"book.txt");
cout << "输入 book.txt 信息完毕\n\n";
break;
case 3: //链表的插入
cout <<
"请输入两个数分别代表插入的位置和数值（书的信息：编号&书名&价格）:";
cin >> a;
cin >> e.id >> e.name >> e.price;
if (ListInsert(L, a, e))
cout << "插入成功.\n\n";
else
cout << "插入失败!\n\n";
break;
case 4: //链表的删除
cout << "请输入所要删除的书籍的位置:";
cin >> a;
if (ListDelete(L, a))
cout << "删除成功!\n\n";
else
cout << "删除失败!\n\n";
break;
case 5: //链表的输出
cout << "当前图书系统信息读出:\n";
p = L->next;
if (p)
OutputLinkList(L);
else
cout << "没有图书信息!\n\n";
break;
}
}
return 0;
}