数据结构第一次实验报告

实验1 线性表的实现与应用

一．实验目的

掌握顺序表的实现及基本操作；
掌握单链表的实现及基本操作；
编写主函数，调用操作函数解决应用问题；
增加代码经验,加深对C语言的理解。

二．实验内容

1．项目2_1：顺序表实现一般集合求并集。

【问题描述】

有集合A={7,5,3,11}和集合B={2,6,3},现需要将他们合并。

【算法分析】

在原有可动态分配大小的顺序表上进行修改，首先调用建表函数把A和B放入两张表里，然后调用合并函数。

在合并函数里，先用if保证被插入的永远为长的表，再用一个for不停用getElemByIndex取短表里的元素，再用getIndexByElem获取该元素在长表里的位置，如果返回为-1，则调用ListInsert插入。

2. 项目2_2：单链表实现有序集合求并集。

【问题描述】

现有有序集合A={3,5,8}和B={2,6,8,9,11,15,20},现需将他们合并为有序集合。

【算法分析】

在单链表的基础上进行更改。首先调用尾插法建表函数把A和B放入两张表里，然后调用合并函数。

在合并函数里，先用if保证被插入的永远为长的表，再用两个for进行逻辑处理。第一个for不停用getListByIndex从短链表取元素前一个结点，进行下一步逻辑。第二个for不停用getListByIndex从长表取元素的前一个结点并比较下一个结点的值与第一个for里取出的结点的下一个结点的值，然后调用insertList插入

3．项目2-3：单链表实现一元稀疏多项式加法运算。

【问题描述】

现有多项式和，需要进行合并成一个多项式。

【算法分析】

通过分析发现与上一个项目的代码有相似之处，更改结构定义和各个函数。由于和上一个项目相似，所以分析关键代码。

先将指数相同项的系数相加，后将没有的项插入（虽看起来简单，其实比较难的。我还添加一个可以带入x计算结果功能）。

三．源代码

1. 一般集合的并集2_1_彭喜.cpp

#include<stdio.h>
#include<iostream>
#include<malloc.h>
#include<stdlib.h>
using namespace std;
#define OK 1 //通过
#define ERROR 0 //错误
#define OVERFLOW -2 //堆栈溢出
#define LIST_INIT_SIZE 10 //线性表储存空间初始分配量
#define LISTINCREMRNT 10 //线性表储存空间的分配增量
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型
//线性表动态分配顺序储存结构
typedef struct
{
ElemType* elem;//储存空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
//初始化一个空的表
Status InitList(SqList* L)
{
L->elem = (ElemType*)__vcrt_malloc_normal(LIST_INIT_SIZE * sizeof(ElemType));
if (!(L->elem))
exit(OVERFLOW);//分配失败
L->length = 0;//长度
L->listsize = LIST_INIT_SIZE;//容量
return OK;
}
//插入
Status ListInsert(SqList* L, int i, ElemType e)
{
if (i<1 || i>L->length + 1)
return ERROR;
ElemType* q = &(L->elem[i - 1]), *p = NULL;// q为插入位置
for (p = &(L->elem[L->length - 1]); p >= q; --p)
* (p + 1) = *p;// 插入位置及之后的元素后移
*q = e;// 插入e
++(L->length);// 表长增加1
if (L->length == L->listsize) {
ElemType* newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMRNT) * sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L->elem = newbase;// 新基址
L->listsize += LISTINCREMRNT;// 增加存储容量
}
return OK;
}
//获取长度
int getLength(SqList* L)
{
return L->length;
}
//通过索引取值
ElemType getElemByIndex(SqList* L, int i)
{
return L->elem[i - 1];
}
//通过值取索引
int getIndexByElem(SqList* L, ElemType e)
{
for (int j = 0; j < L->length; ++j)
{
if ((L->elem[j]) == e)
return j + 1;
}
return -1;
}
//遍历表
Status myPrintf(SqList* L)
{
for (int i = 0; i < L->length; i++) {
cout << "第"<< i + 1<<"个值------------" << (L->elem[i])<<endl;
}
return OK;
}
//创建表
Status creatList(SqList* L)
{
scanf_s("%d", &(L->length));
printf("输入为 %d\n", L->length);
for (int i = 0; i < L->length; i++)
{
cin >> L->elem[i];
}
return OK;
}
//合并
Status mergeList(SqList* LA,SqList* LB)
{
if (LA->length < LB->length) {
SqList* temp;
temp = LA;
LA = LB;
LB = temp;
}
for (int i = 0; i < LB->length; i++)
{
ElemType e = getElemByIndex(LB,i+1);
if (getIndexByElem(LA, e)==-1) {
ListInsert(LA, 1, e);
}
}
printf("合并后\n");
myPrintf(LA);
return OK;
}
int main(void) {
SqList* LA = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
InitList(LA);
printf("请输入表A的长度\n");
creatList(LA);
myPrintf(LA);
SqList* LB = (SqList*)__vcrt_malloc_normal(sizeof(SqList));
InitList(LB);
printf("请输入表B的长度\n");
creatList(LB);
myPrintf(LB);
mergeList(LA, LB);
system("pause");
return 0;
}

运行截图：

2．有序集合求并集2_2_彭喜.cpp

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define OK 1 //通过
#define ERROR 0 //错误
typedef int Status; //函数类型,其值为状态码
typedef int ElemType; //抽象数据类型
//单链表
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化
Status initList(LinkList* L)
{
*L = (LinkList)malloc(sizeof(LNode));
(*L)->data = 0;
(*L)->next = NULL;
return OK;
}
//判空
char* isEmpty(LinkList* L)
{
return (*L)->next == NULL ? "空" : "不空";
}
//获取长度
int getLength(LinkList* L)
{
LinkList p = *L;
int i = 0;
while (p->next)
{
++i;
p = p->next;
}
return i;
}
//默认头插法建表
Status creatListHead(LinkList* L , ElemType str[],int n)
{
LinkList p;
(*L)->data = n;
for (int i = 0; i <n; ++i)
{
p = (LinkList)malloc(sizeof(LNode));
p->data = str[i];
p->next = (*L)->next;
(*L)->next = p;
}
return OK;
}
//默认尾插法建表
Status creatListEnd(LinkList* L, ElemType str[], int n)
{
LinkList p, r = *L;
(*L)->data = n;
for (int i = 0; i < n; ++i)
{
p = (LinkList)malloc(sizeof(LNode));
p->data = str[i];
p->next = NULL;//必须要否则遍历异常
r->next = p;
r = p;
}
return OK;
}
//遍历表
Status traversalList(LinkList L)
{
LinkList p = L->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
//插入
Status insertList(LinkList* L, int i, ElemType c)
{
if (L == NULL || (i > (*L)->data || i < 1))return ERROR;
LinkList p = *L;
int j = 0;
while (p&&j<i - 1)
{
p = p->next;//定在前一个
j++;
}
LinkList q = (LinkList)malloc(sizeof(LNode));
q->data = c;
q->next = p->next;
p->next = q;
(*L)->data++;
return OK;
}
//按位查找
LNode* getListByIndex(LinkList L, int i)
{
//if (L == NULL || (i > (L)->data || i < 1))return NULL;
LinkList p = L;
int j = 0;
while (p&&j<i - 1)
{
p = p->next;//前一个
j++;
}
// p = p->next;
return (p);//前一个
}
//按值查找
LNode* getListByElem(LinkList L, ElemType c,int* i)
{
LinkList p = L;
int j = 0;
while (p&&p->next->data != c)
{
p = p->next;//前一个
j++;
}
*i = j + 1;
return p->next;
};
//合并
Status mergeList(LinkList* LA, LinkList* LB )
{
if (getLength(LA)>getLength(LB))
{
LinkList* temp=LA;
LA = LB;
LB = temp;
}
ElemType e;
for (int i = 1; i <= getLength(LA); i++)
{
e = getListByIndex(*LA, i)->next->data;//取元素
//printf("___%d\n", e);
for (int i = 1; i <= getLength(LB); i++)
{
// printf("___---%d\n", i);
if (getListByIndex(*LB, i)->next->data>e)
{
//printf("_----__%d\n", i);
insertList(LB, i, e);
break;
};
}
}
printf("合并后: ");
traversalList(*LB);
return OK;
}
int main(void)
{
ElemType stra[4] = { 3,5,8,11 };
ElemType strb[7] = { 2,6,8,9,11,15,20 };
LinkList LA,LB;
initList(&LA);
initList(&LB);
creatListEnd(&LA, stra,sizeof(stra)/sizeof(stra[0]));
creatListEnd(&LB, strb, sizeof(strb) / sizeof(strb[0]));
printf("表LA: ");
traversalList(LA);
printf("表LB: ");
traversalList(LB);
mergeList(&LA, &LB);
system("pause");
return 0;
}

运行截图：

3. 一元稀疏多项式加法2_3_彭喜.cpp

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define OK 1 //通过
#define ERROR 0 //错误
typedef int Status; //函数类型,其值为状态码
typedef long double ElemType; //抽象数据类型
//单链表
typedef struct LNode
{
ElemType conf;//系数
ElemType expn;//指数
struct LNode *next;
}LNode, *LinkList;
//初始化
Status initList(LinkList* L)
{
*L = (LinkList)malloc(sizeof(LNode));
(*L)->conf = -1;
(*L)->expn = -1;
(*L)->next = NULL;
return OK;
}
//判空
char* isEmpty(LinkList* L)
{
return (*L)->next == NULL ? "空" : "不空";
}
//获取长度
int getLength(LinkList* L)
{
LinkList p = *L;
int i = 0;
while (p->next)
{
++i;
p = p->next;
}
return i;
}
//默认尾插法建表
Status creatListEnd(LinkList* L, ElemType c[], ElemType e[], int n)
{
LinkList p, r = *L;
for (int i = 0; i < n; ++i)
{
p = (LinkList)malloc(sizeof(LNode));
p->conf = c[i];
p->expn = e[i];
p->next = NULL;//必须要否则遍历异常
r->next = p;
r = p;
}
return OK;
}
//遍历表
Status traversalList(LinkList L)
{
LinkList p = L->next;
while (p)
{
if (p->conf>=0)
{
printf("+%fx^%f", p->conf,p->expn);
}
else
{
printf("%fx^%f", p->conf, p->expn);
}
p = p->next;
}
printf("\n");
return OK;
}
//插入
Status insertList(LinkList* L, int i, ElemType c, ElemType e)
{
if (L == NULL || (i > getLength(L) || i < 1))return ERROR;
LinkList p = *L;
int j = 0;
while (p&&j<i - 1)
{
p = p->next;//定在前一个
j++;
}
LinkList q = (LinkList)malloc(sizeof(LNode));
q->conf = c;
q->expn = e;
q->next = p->next;
p->next = q;
return OK;
}
//按位查找
LNode* getListByIndex(LinkList L, int i)
{
//if (L == NULL || (i > (L)->data || i < 1))return NULL;
LinkList p = L;
int j = 0;
while (p&&j<i - 1)
{
p = p->next;//前一个
j++;
}
// p = p->next;
return (p);//前一个
}
//按值查找
LNode* getListByElem(LinkList L, ElemType e, int* i)
{
LinkList p = L;
int j = 0;
while (p&&p->next->expn != e)
{
p = p->next;//前一个
j++;
}
*i = j + 1;
return p->next;
};
//计算
long double calculateMultinomial(LinkList L, int x)
{
LinkList p = L->next;
long double sum=0;
while (p)
{
sum = p->conf*pow(x, p->expn)+sum;
p = p->next;
}
return sum;
}
//合并
Status mergeList(LinkList* LA, LinkList* LB)
{
if (getLength(LA)>getLength(LB))
{
LinkList* temp = LA;
LA = LB;
LB = temp;
}
ElemType e,c;
for (int i = 1; i <= getLength(LA); i++)
{
e = getListByIndex(*LA, i)->next->expn;//取指数
c = getListByIndex(*LA, i)->next->conf;//取系数
//先指数相同
for (int i = 1; i <= getLength(LB); i++)
{
if (getListByIndex(*LB, i)->next->expn==e)
{
getListByIndex(*LB, i)->next->conf =getListByIndex(*LB, i)->next->conf + c;//系数相加
break;
};
}
//指数不同
for (int i = 1; i <= getLength(LB); i++)
{
if (getListByIndex(*LB, i)->expn<e&&getListByIndex(*LB, i)->next->expn>e)
{
insertList(LB, i, c, e);
break;
};
}
}
printf("多项式相加后: ");
traversalList(*LB);
printf("请输入x的值 ");
int x;
scanf_s("%d", &x);
printf("答案为 %f\n\n", calculateMultinomial(*LB, x));
return OK;
}
int main(void)
{
ElemType ac[4] = { 7,3,9,5 };//系数
ElemType ae[4] = { 0,1,8,17 };//指数
ElemType bc[3] = { 8,22,-9};
ElemType be[3] = { 1,7,8};
LinkList LA, LB;
int x;
initList(&LA);
initList(&LB);
creatListEnd(&LA, ac,ae,4 );
creatListEnd(&LB, bc, be, 3);
printf("多项式LA: ");
traversalList(LA);
printf("请输入x的值 ");
scanf_s("%d", &x);
printf("答案为 %f\n\n", calculateMultinomial(LA, x));
printf("多项式LB: ");
traversalList(LB);
printf("请输入x的值 ");
scanf_s("%d", &x);
printf("答案为 %f\n\n", calculateMultinomial(LB, x));
mergeList(&LA, &LB);
system("pause");
return 0;
}

运行截图：

四.问题及总结

这次实验用的是vs2015编译器编写，增加了熟练度，还进一步加强了对调试的使用经验，加深了对指针、结构体和线性表的理解。
这次实验一不小心多写了一个有序集合使用顺序表合并，具体代码可见我的博客https://pengxiandyou.github.io (GIthub上搭建的，速度较慢，耐心等待)。
第一个项目比较简单，没什么需要百度的问题，写起来比较轻松。
第二个项目有点困难了，出来点小问题，例如野指针、插入位置不对等，不过这些都解决了。还有一个小问题，那就是和书上一样会把相同的也插入（第三个项目里解决了），不过我比书少用一张表。
第三个项目巧妙修改了定义使得在一个结点可以存放两个值，巧妙的修改了初始化让代码逻辑减少许多。先将指数相同的系数相加，在将没有的插入也是一个很棒的设计。添加一个计算功能更是锦上添花。小问题也就是像条件分析得有点久。
卡住的一个略大的问题是C语言中没有关于数组长度函数，所以一般用sizeof(a)/sizeof(int)来计算数组长度，但是当数组作参数传递时，函数里面sizeof(a)/sizeof(int)会等于1（应该或2）。这是因为编译器会将a当一个指针。
反正当出现问题时，调试是一个很棒的工具。