天大数据结构实验作业一线性表链表.doc

实验作业一：线性表（链表） 1. 从左到右及从右到左遍历一个单链表是可能的，其方法是在从左向右遍历的过程中将连接方向逆转，如右图所示。在图中的指针p指向当前正在访问的结点，指针pr指向指针p所指结点的左侧的结点。此时，指针p所指结点左侧的所有结点的链接方向都已逆转。 (1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。 2.（1）如果用循环链表表示一元多项式，试编写一个函数 Calc(x)，计算多项式在x处的值。 （2）设a和b是两个用带有表头结点的循环链表表示的多项式。试编写一个算法，计算这两个多项式的乘积c = a*b，要求计算后多项式a与b保持原状。 编写实习报告要求： 一、需求分析 二、概要设计 1.抽象数据类型 2.算法 三、详细设计 程序代码（注释） 四、调试分析 调试过程中所做的工作，时间复杂度等 五、测试结果 输入数据和输出数据示例 六、说明（如果有） 编程语言：C语言或C++语言 实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一个rar文件，文件名称为学号_班级_姓名_第几次作业。例如：3010216155_六班_张三_第一次作业.rar。实习报告作为本课程的平时成绩。 抄袭、雷同，双方均为0分。 第一题： 需求分析 题目需要自行定义一个链表，然后依据给出的p指针的位置找到p指针和其前驱pr指针。然后把p之前（包含pr）的所有链接方向逆转。处理好这些准备工作后，开始按照问题对指针进行运算。 1) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p右移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最右边的结点上。 (2) 编写一个算法，从任一给定的位置(pr, p)开始，将指针p左移k个结点。如果p移出链表，则将p置为0，并让pr停留在链表最左边的结点上。 二、概要设计 1.抽象数据类型 typedef struct L{ char data; struct L *next; }L; 2.算法 （1）.创建链表的算法。 void creat(node first){ char a; node x,y; first=(node) malloc (sizeof(L)); y=first; while((a=getchar())!=\n){ x=y; y-data=a; y=(node) malloc (sizeof(L)); x-next=y; } x-next=NULL; delete(y); } （2）.查找指针位置，并返回是否可操作的算法。 int find(node first,int X,node pr,node p){ int a=1; if(first-next==NULL){ pr=0; p=first; return 0; } else{ p=first; while(p!=NULLaX){ pr=p; p=p-next; a++; } return 1; } } （3）.对题目所要求的指针位置之前的链接进行逆转的算法。 void reverse(node first,node pr){ node A,B,C; A=first; B=A-next; A-next=NULL; if(first!=pr){ while(B!=pr){ C=B-next; B-next=A; A=B; B=C; } pr-next=A; } } （4）.指针向右跳跃的算法。 int right(node p,int k1){ int n=0; for(n;nk1;n++){ if(p-next!=NULL){ p=p-next; } else{ p-data=0; return 0; } } return 1; } （5）.指针向左跳跃的算法。 int left(node pr, int k2){ int n=0; for(n;nk2;n++){ if(pr-next!=NULL){ pr=pr-next; } else{ pr-data=0; return 0; } } return 1; } 三、详细设计 #includestdlib.h #includ