实 实 验 报 告 （ （2018
/ 2019 学年 第 第 一 学期）
课程名称 数据结构 实验名称 线性表及多项式的运算 实验时间
2018 年
10 月
9 日
指导单位 现代邮政学院 指导教师 宁卓
学生姓名 唐棠 班级学号 B17100 学院(系) 现代邮政学院 专
业
物流管理
实 实 验 报 告 实验名称 线性表及多项式的运算 指导教师 宁卓 实验类型 设计 实验学时 2 实验时间 2 一、
实验目的和要求 1、掌握线性表的两种基本存储结构及其应用场合：顺序存储和链接存储。
2、掌握顺序表和链表的各种基本操作算法。
3、理解线性表应用于多项式的实现算法。
二、 实验环境( 实验设备) 硬件：微型计算机 软件：Windows 操作系统、Microsoft Visual C++6.0
2 三、实验原理及内容 1、参照程序 2.1～2.7，编写程序，完成顺序表的初始化、查找、插入、删除、输出、撤销等操作。
2、已知带表头结点单链表的类型定义如下：
typedef struct node { ElemType
element;
//结点的数据域 struct node *link;
//结点的指针域 }node; typedef struct
{ struct node * head; int n; }headerList; 参照程序 2.8～2.14，编写程序，完成带表头结点单链表的初始化、查找、插入、删除、输出、撤销等操作。
3、以题 2 所示带表头结点单链表为存储结构，编写程序实现单链表的逆置操作。（原单链表为（a 0 ，a 1 ，……，a n-1 ），逆置后为（a n-1 ，a n-2 ， ……，a 0 ），要求不引入新的存储空间）
。
4、以题 2 所示带表头结点单链表为存储结构，编写程序实现将单链表排序成为有序单链表的操作。
5、已知带表头结点一元多项式的类型定义如下：
typedef struct pNode { int coef; int exp; struct pNode* link; } pNode; typedef struct
{
struct pNode *head; } polynominal; 编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。
3
实 实 验 报 告
4 2.1 #include<stdio.h> #include<stdlib.h> #define ERROR 0 #define OK 1 typedef int ElemType; typedef int Status;
typedef struct {
int n;
int maxLength;
ElemType *element;
}SeqList; Status Init(SeqList *L, int mSize) {
L->maxLength = mSize;
L->n = 0;
L->element = (ElemType*)malloc(sizeof(ElemType)*mSize);
if(!L->element)
return OK; } Status Find(SeqList L,int i,ElemType *x){
if(i<0||i>L.n-1){
return ERROR;
} *x=L.element[i];
return OK; } Status Insert(SeqList *L, int i, ElemType x) {
int j;
if (i<-1 || i>L->n - 1)
return ERROR;
if (L->n == L->maxLength)
return ERROR;
for (j = L->n - 1; j > i; j--) {
L->element[j + 1] = L->element[j];
5
}
L->element[i + 1] = x;
L -> n = L->n + 1;
return OK; } Status Delete(SeqList *L, int i){
int j; if(i<0||i>L->n-1){
return ERROR;
} if(!L->n){
return ERROR;
}
for(j=i+1;j<L->n;j++){
L->element[j-1]=L->element[j];
} L->n--;
return OK; } int Output(SeqList L) {
int i;
if (!L.n)
return ERROR;
for (i = 0; i <= L.n - 1; i++)
printf("%d ", L.element[i]);
return OK; } void Destroy(SeqList *L){
(*L).n=0;
(*L).maxLength=0;
free((*L).element); } void main() {
int i,x;
6
SeqList list;
Init(&list, 10);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i);
}
Output(list);
printf("\n"); Delete(&list,0);
Output(list);
Find(list,2,&x);
printf("\nthe value is:");
printf("%d",x);
Destroy(&list); }
2.2 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef int Status; #define ERROR 0 #define OK 1 typedef struct Node {
ElemType element;
struct Node * link;
}Node; typedef struct {
struct Node* head;
int n; }HeaderList; Status Init(HeaderList *h) {
h->head=(Node*)malloc(sizeof(Node));
if(!h->head){
return ERROR;
7
}
h->head->link = NULL;
h->n = 0;
return OK; } Status Find(HeaderList *h,int i,ElemType *x){
Node *p;
int j;
if(i<0||i>h->n-1){
return ERROR;
}
p=h->head->link;
for(j=0;j<i;j++){
p=p->link;
}
*x=p->element;
return OK; } Status Insert(HeaderList *h, int i, ElemType x) {
Node *p, *q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head;
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node));
q->element = x;
q->link = p->link;
p->link = q;
h->n++;
return OK; } Status Delete(HeaderList *h,int i){
8
int j;
Node *p,*q;
if(!h->n){
return ERROR;
if(i<0||i>h->n-1){
return ERROR;
}
}
q=h->head;
for(j=0;j<i;j++){
q=q->link;
}
p=q->link;
q->link=p->link;
free(p);
h->n--;
return OK; } Status Output(HeaderList *h) {
Node *p;
if (!h->n)
return ERROR;
p = h->head->link;
while (p) {
printf("%d ",p->element);
p = p->link;
}
return OK; } void Destroy(HeaderList *h){
Node *p,*q;
while(h->head->link){
q=h->head->link;
p=h->head->link->link;
free(h->head->link);
9
h->head=q;
} } void main() {
int i, x;
HeaderList list;
Init(&list);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i);
}
printf("the linklist is:");
Output(&list);
Delete(&list,0);
printf("\nthe linklist is:");
Output(&list);
Find(&list,0,&x);
printf("\nthe value is:");
printf("%d ",x);
Destroy(&list); }
2.3 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef int Status; #define ERROR 0 #define OK 1 typedef struct Node {
ElemType element;
struct Node * link;
}Node; typedef struct {
10
struct Node* head;
int n; }HeaderList; Status Init(HeaderList *h) {
h->head=(Node*)malloc(sizeof(Node));
if(!h->head){
return ERROR;
}
h->head->link = NULL;
h->n = 0;
return OK; } Status Find(HeaderList *h,int i,ElemType *x){
Node *p;
int j;
if(i<0||i>h->n-1){
return ERROR;
}
p=h->head->link;
for(j=0;j<i;j++){
p=p->link;
}
*x=p->element;
return OK; } Status Insert(HeaderList *h, int i, ElemType x) {
Node *p, *q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head;
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node));
11
q->element = x;
q->link = p->link;
p->link = q;
h->n++;
return OK; } Status Delete(HeaderList *h,int i){
int j;
Node *p,*q;
if(!h->n){
return ERROR;
if(i<0||i>h->n-1){
return ERROR;
}
}
q=h->head;
for(j=0;j<i;j++){
q=q->link;
}
p=q->link;
q->link=p->link;
free(p);
h->n--;
return OK; } Status Output(HeaderList *h) {
Node *p;
if (!h->n)
return ERROR;
p = h->head->link;
while (p) {
printf("%d ",p->element);
p = p->link;
}
return OK;
12 } void Destroy(HeaderList *h){
Node *p,*q;
while(h->head->link){
q=h->head->link;
p=h->head->link->link;
free(h->head->link);
h->head=q;
} } void Inverse(HeaderList *h){
Node *p=h->head->link,*q;
h->head->link = NULL;
while(p){
q=p->link;
p->link=h->head->link;
h->head->link=p;
p=q;
} } void main(){
int i, x;
HeaderList list;
Init(&list);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i);
}
printf("the linklist is:");
Output(&list);
Inverse(&list);
printf("\nthe linklist is:");
Output(&list);
Destroy(&list); }
13
2.4 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef int Status; #define ERROR 0 #define OK 1
typedef struct Node {
ElemType element;
struct Node * link;
}Node;
typedef struct {
struct Node* head;
int n; }HeaderList; Status Init(HeaderList *h) {
h->head=(Node*)malloc(sizeof(Node));
if(!h->head){
return ERROR;
}
h->head->link = NULL;
h->n = 0;
return OK; } Status Find(HeaderList *h,int i,ElemType *x){
Node *p;
int j;
if(i<0||i>h->n-1){
return ERROR;
}
p=h->head->link;
for(j=0;j<i;j++){
14
p=p->link;
}
*x=p->element;
return OK; } Status Insert(HeaderList *h, int i, ElemType x) {
Node *p, *q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head;
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node));
q->element = x;
q->link = p->link;
p->link = q;
h->n++;
return OK; } Status Delete(HeaderList *h,int i){
int j;
Node *p,*q;
if(!h->n){
return ERROR;
if(i<0||i>h->n-1){
return ERROR;
}
}
q=h->head;
for(j=0;j<i;j++){
q=q->link;
}
p=q->link;
15
q->link=p->link;
free(p);
h->n--;
return OK; } Status Output(HeaderList *h) {
Node *p;
if (!h->n)
return ERROR;
p = h->head->link;
while (p) {
printf("%d ",p->element);
p = p->link;
}
return OK; } void Destroy(HeaderList *h){
Node *p,*q;
while(h->head->link){
q=h->head->link;
p=h->head->link->link;
free(h->head->link);
h->head=q;
} } Status Order(HeaderList *h){
Node *s1,*s2,*s3,*s4,*p,*q;
for (p=h->head;p!=NULL && p->link!=NULL;p=p->link) {
for (q=p->link;q!=NULL && q->link!=NULL;q=q->link) {
if (p->link->element > q->link->element) {
s1=p->link;
s2=p->link->link;
s3=q->link;
s4=q->link->link;
if (s2!=s3) {
16
p->link=s3;
s3->link=s2;
q->link=s1;
s1->link=s4;
}
else {
p->link=s3;
s3->link=s1;
q=s3;
s1->link=s4;
}
}
}
}
return OK; } void main() {
int i,j, x;
HeaderList list;
Init(&list);
for (i = 8,j = 0; i >= 0; i--,j ++) {
Insert(&list, j - 1, i);
}
printf("the linklist is:");
Output(&list);
Order(&list);
printf("\nthe linklist is:");
Output(&list);
Destroy(&list); }
2.5 #include<stdio.h>
17 #include<stdlib.h>
typedef struct PNode{
int coef;
int exp;
struct PNode* link; }PNode;
typedef struct{
struct PNode *head; }polynominal; void Create(polynominal *p){
PNode *pn,*pre,*q;
p->head = (PNode*)malloc(sizeof(PNode));
p->head->exp = -1;
p->head->link = p->head;
for(;;){
pn=(PNode*)malloc(sizeof(PNode));
printf("coef:\n");
scanf("%d",&pn->coef);
printf("exp:\n");
scanf("%d",&pn->exp);
if(pn->exp<0) break;
pre = p->head;
q = p->head->link;
while(q && q->exp > pn->exp){
pre = q;
q = q->link;
}
pn->link = q;
pre->link = pn;
} } void Output(polynominal p){
PNode *q;
18
int flag = 1;
q = p.head->link;
if (!q){
return;
}
while(q != p.head){
if (!flag && (q->coef > 0)) printf("+");
flag = 0;
if(q->coef == 0){
return;
}
printf("%d",q->coef);
switch(q->exp){
case 0:break;
case 1:printf("X");break;
default:printf("X^%d",q->exp);break;
}
q = q->link;
} } void Add(polynominal *px,polynominal *qx){
PNode *q,*q1 = qx->head,*p, *p1,*temp;
p = px->head->link;
p1 = px->head;
q = q1->link;
while(p->exp >= 0){
while(p->exp < q->exp){
q1 = q;
q = q->link;
}
if(p->exp == q->exp){
q->coef = q->coef + p->coef;
if(q->coef == 0){
q1->link = q->link;
free(q);
19
q = q1->link;
p = p->link;
}
else{
q1 = q;
q = q->link;
p = p->link;
}
}
else{
temp = malloc(sizeof(PNode));
temp->coef = p->coef;
temp->exp = p->exp;
temp->link = q1->link;
q1->link = temp;
q1 = q1->link;
p = p->link;
}
} } void Multiply(polynominal *px,polynominal *qx){
polynominal qx1,qx2;
PNode *q1,*q2,*q3,*q4,*pre,*q;
qx1.head = (PNode*)malloc(sizeof(PNode));
qx1.head->exp = -1;
qx1.head->link = qx1.head;
q1 = px->head->link;
q2 = qx->head->link;
while(q2->exp != -1){
q3 = (PNode*)malloc(sizeof(PNode));
q3->coef = q1->coef * q2->coef;
q3->exp = q1->exp + q2->exp;
if(qx1.head->link->exp == -1){
q3->link = qx1.head->link;
qx1.head->link = q3;
20
pre = qx1.head->link;
}
else{
q3->link = qx1.head;
pre->link = q3;
pre = pre->link;
}
q2 = q2->link;
}
q1 = q1->link;
while(q1->exp != -1){
q2 = q2->link;
qx2.head = (PNode*)malloc(sizeof(PNode));
qx2.head->exp = -1;
qx2.head->link = qx2.head;
while(q2->exp != -1){
q4 = (PNode*)malloc(sizeof(PNode));
q4->coef = q1->coef * q2->coef;
q4->exp = q1->exp + q2->exp;
if(qx2.head->link->exp == -1){
q4->link = qx2.head->link;
qx2.head->link = q4;
pre = qx2.head->link;
}
else{
q4->link = qx2.head;
pre->link = q4;
pre = pre->link;
}
q2 = q2->link;
}
Add(&qx2,&qx1);
q1 = q1->link;
}
Output(qx1);
21 }
int main(){
polynominal p,q;
int x;
printf("Please enter the first poly:\n");
Create(&p);
Output(p);
printf("\n\nPlease enter the second poly:\n");
Create(&q);
Output(q);
printf("\n\nPlease choose the function:\n");
scanf("%d",&x);
switch(x){
case 0:printf("Add:\n");
Add(&p,&q);
Output(q);
break;
case 1:printf("Multiply:\n");
Multiply(&p,&q);
default:break;
}
return 0; }
实 实 验 报 告
22 实 实 验 报 告 实 实 验 报 告 四、实验小结 （包括问题和解决方法、心得体会、意见与建议等）
(一)实验中遇到的主要问题及解决方法
在题目一编译时，总出现问题，发现是没有初始化线性表所导致的错误，进行重新定义线性表的修改后错误消除； 在题目二到五编译运行时，出现了没有检查下标越界问题，后来用百度方法查找，进行增加判断下标是否越界的修改后错误消除，从而说明在程序运行过程中需要防止下标越界，避免出现覆盖内存导致运行出现错误； 在题目运行时，出现了代码的变量命名，标点符号缺失问题，后来根据下方的提示栏出现的错误和提醒方法查找，修改后错误消除，从而说明写代码很容易出错；
（二）实验心得
本学期第一次数据结构实验设计结束了，感觉学到了很多知识。这次 C 语言数据结构程序设计刚拿到要完成的题目时，感觉程序要求的一个个实现功能完成起来不是很难，但是当真的开始思考怎么去写代码，怎么去安排程序结构，怎么去实现想要的程序功能等等一系列的事情就发现问题很大，任务很重；特别是在调试程序的时候更是让人头痛，辛辛苦苦的写好了函数，等到调试运行就出现一堆错误通过这次编程我们深深的感受到对代码的变量命名，代码内注释格式，甚至嵌套中行缩进的长度和函数间的空行数字都有明确规定，良好的编写习惯，不但有助于代码的移植和纠错，也有助于不同人员之间的协作。这个程序设计主要涉及到了线性表在多项式和其他方面的应用。只有充分掌握了线性表的定义初始化等这些内容，才有可能组织好这些代码，使之符合运算逻辑，得到理想的结果。
善于总结，也是学习能力的一种体现，每次完成一个编程任务，完成一段代码，都应当有目的的跟踪该程序的应用状况，随时总结，找到自己的不足，这样所编写的程序才能逐步提高，生活就是这样，汗水预示着结果也见证着收获。的确，自从拿到题目到完成整个编程，从理论到实践，在一次实验过程内，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过完成这种实验实践使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能提高自己的实际动手能力和独立思考的能力。
23
（三）意见与建议（没有可省略）
实验设计上机实践对个人的编程能力有很高的要求，每个人的能力水平不太一样，有的时候可以讲一些基础的知识先过渡，比如怎么初始化变量，算法的基本思路等等，然后再由浅入深。
24
五、 支撑毕业要求指标点 《数据结构》课程支撑毕业要求的指标点为：
1.2-M 掌握计算机软硬件相关工程基础知识，能将其用于分析计算机及应用领域的相关工程问题。
3.2-H 能够根据用户需求，选取适当的研究方法和技术手段，确定复杂工程问题的解决方案。
4.2-H 能够根据实验方案，配置实验环境、开展实验，使用定性或定量分析方法进行数据分析与处理，综合实验结果以获得合理有效的结论。
实验内容 支撑点 1.2 支撑点 3.2 支撑点 4.2 线性表及多项式的运算 √
二叉树的基本操作及哈夫曼编码译码系统的实现
√ √ 图的基本运算及智能交通中的最佳路径选择问题
√ √ 各种内排序算法的实现及性能比较 √
√
六、指导教师评语 ( 含学生能力达成度的评价)
如评分细则所示
成 成
绩 XX 批阅人 XX 日 日
期 XXX
评
分
细
则 评分项 优秀 良好 中等 合格 不合格 遵守实验室规章制度
学习态度
算法思想准备情况
程序设计能力
解决问题能力
课题功能实现情况
算法设计合理性
算法效能评价
回答问题准确度
报告书写认真程度
内容详实程度
文字表达熟练程度
其它评价意见
本次实验能力达成评价（总成绩）
25
