《算法与数据结构》实验指导书p=(LinkList)malloc(sizeof(struct LNode):scanf("%d",&p->data);q->next=p;q=q->next;3p->next=NULL;3StatusPriorElem_Link (LinkListL,ElemTypecur_e,ElemType&pre_e)/*为扩展实验的内容*/（*初始条件：线性表L已存在*//*操作结果：若cure是L的数据元素,且不是第一个，则用pre_e返回它的前驱，*/*返回OK：否则操作失败，pree无定义，返回INFEASIBLE*/LinkListq,P=L->next；/*p指向第一个结点*/while(p->next)/*p所指结点有后继*/1；/*q为p的后继*/q=p->next;if(q->data==cur_e)tpre_e=p->data;return OK;3p=q；/*p向后移*/3retunINFEASIBLE;3/*为扩展实验的内容*StatusNextElemLink(LinkListL,ElemTypecur_e,ElemType&next_e)（/*初始条件：线性表L已存在*/*操作结果：若cur_e是L的数据元素，且不是最后一个，则用nexte返回它的后继，*//*返回OK否则操作失败，nexte无定义，返回INFEASIBLE*21
《算法与数据结构》实验指导书 21 { p=(LinkList)malloc(sizeof(struct LNode))； scanf("%d",&p->data)； q->next=p； q=q->next； } p->next=NULL； } Status PriorElem_Link (LinkList L,ElemType cur_e,ElemType &pre_e) /* 为扩展实验的内容 */ { /* 初始条件: 线性表 L 已存在 */ /* 操作结果: 若 cur_e 是 L 的数据元素,且不是第一个,则用 pre_e 返回它的前驱, */ /* 返回 OK；否则操作失败,pre_e 无定义,返回 INFEASIBLE */ LinkList q,p=L->next； /* p 指向第一个结点 */ while(p->next) /* p 所指结点有后继 */ { q=p->next； /* q 为 p 的后继 */ if(q->data==cur_e) { pre_e=p->data； return OK； } p=q； /* p 向后移 */ } return INFEASIBLE； } Status NextElem_Link (LinkList L,ElemType cur_e,ElemType &next_e) /* 为扩展实验的内容 */ { /* 初始条件：线性表 L 已存在 */ /* 操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继， */ /* 返回 OK；否则操作失败，next_e 无定义，返回 INFEASIBLE */
《算法与数据结构》实验指导书/*p指向第一个结点*/LinkList p-L->next;while(p->next)/*p所指结点有后继*/1if(p->data==cur_e)( next_e=p->next->data:return OK;-p=p->next;1returnINFEASIBLE;3void MergeList Link(LinkList&La,LinkList&Lb,LinkList&Lc)/*算法2.12为扩展实验的内容*(/*已知单链线性表La和Lb的元素按值非递减排列。*//*归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列*/LinkList pa=La->next,pb=Lb->next,pc;Lc=pc=La;/*用La的头结点作为Lc的头结点*/while(pa&&pb)if(pa->data<=pb->data)pc->next=pa;pc=pa;pa=pa->next;3else1pc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;/*插入剩余段*/22
《算法与数据结构》实验指导书 22 LinkList p=L->next； /* p 指向第一个结点 */ while(p->next) /* p 所指结点有后继 */ { if(p->data==cur_e) { next_e=p->next->data； return OK； } p=p->next； } return INFEASIBLE； } void MergeList_Link (LinkList &La,LinkList &Lb,LinkList &Lc) /* 算法 2.12 为扩展实验的内容*/ { /* 已知单链线性表 La 和 Lb 的元素按值非递减排列。 */ /* 归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按值非递减排列 */ LinkList pa=La->next,pb=Lb->next,pc； Lc=pc=La； /* 用 La 的头结点作为 Lc 的头结点 */ while(pa&&pb) if(pa->data<=pb->data) { pc->next=pa； pc=pa； pa=pa->next； } else { pc->next=pb； pc=pb； pb=pb->next； } pc->next=pa?pa:pb； /* 插入剩余段 */
《算法与数据结构》实验指导书free(Lb);/*释放Lb的头结点*/Lb-NULL;33.将测试数据和主函数新定义一个文件，如取名为：linlistUse.cpp./*linlistUse.cpp主要实现算法2.9、2.10、2.11、2.12的程序*/#include"pubuse.h"typedef int ElemType;#include"linklistDef.h"#include"linklistAlgo.h"voidmainOtint n=5;LinkList La, Lb, Lc;int i;ElemType e:printf("按非递减顺序，")；CreateList2_Link（La,n)；/*正位序输入n个元素的值，建立一个单链表*printf("La-"):/*输出链表La的内容*/ListTraverse_Link (La);printf("按非递增顺序，")；CreateList_Link（Lb,n)；/*逆位序输入n个元素的值*/printf("Lb="):/*输出链表Lb的内容*/ListTraverse_Link (Lb);MergeList_Link(La,Lb,Lc)：/*按非递减顺序归并La和Lb，得到新表Lc*/printf("Lc=");/*输出链表Lc的内容*/23
《算法与数据结构》实验指导书 23 free(Lb)； /* 释放 Lb 的头结点 */ Lb=NULL； } 3．将测试数据和主函数新定义一个文件,如取名为:linlistUse.cpp. /* linlistUse.cpp 主要实现算法2.9、2.10、2.11、2.12的程序 */ #include"pubuse.h" typedef int ElemType； #include"linklistDef.h" #include"linklistAlgo.h" void main() { int n=5； LinkList La,Lb,Lc； int i； ElemType e； printf("按非递减顺序, ")； CreateList2_Link (La,n)； /* 正位序输入 n 个元素的值 ,建立一个单链表*/ printf("La=")； /* 输出链表 La 的内容 */ ListTraverse_Link (La)； printf("按非递增顺序, ")； CreateList_Link (Lb,n)； /* 逆位序输入 n 个元素的值 */ printf("Lb=")； /* 输出链表 Lb 的内容 */ ListTraverse_Link (Lb)； MergeList_Link (La,Lb,Lc)； /* 按非递减顺序归并 La 和 Lb,得到新表 Lc */ printf("Lc=")； /* 输出链表 Lc 的内容 */
《算法与数据结构》实验指导书ListTraverse_Link (Lc);/*算法2.9的测试*/printf("In enter insert location and value :");scanf("%d%d"&i,&e)ListInsert_Link (Lc,i,e);/*在Lc链表中第i个结点处插入一个新的结点，其值为e：*printf("Lc=");/*输出链表Lc的内容*/ListTraverse_Link (Lc);/*算法2.10的测试*/printf("In enter deletd location:");scanf("%d，&i);ListDelete_Link (Lc,i,e);/*在Lc链表中删除第i个结点，其值为返回给e变量*/printf("The Deleted e=%d)n",e):/*输出被删结点的内容*/printf("Lc=");/*输出链表Lc的内容*/ListTraverse_Link (Lc):1五、实验环境和实验步骤实验环境：利用VisualC++集成开发环境进行本实验的操作。实验步骤一一顺序表的定义与操作：1.启动VC++；2.新建工程/Win32ConsoleApplication，选择输入位置：如“d:"，输入工程的名称：如“SeqlistDemo"；按“确定”按钮，选择“AnEmptyProject"”，再按“完成”按钮，3.新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“pubuse.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序：4.新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“seqlistDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；24
《算法与数据结构》实验指导书 24 ListTraverse_Link (Lc)； /* 算法 2.9 的测试 */ printf("\n enter insert location and value : ")； scanf("%d %d",&i,&e)； ListInsert_Link (Lc,i,e)； /* 在 Lc 链表中第 i 个结点处插入一个新的结点，其值为 e；*/ printf("Lc=")； /* 输出链表 Lc 的内容 */ ListTraverse_Link (Lc)； /* 算法 2.10 的测试 */ printf("\n enter deletd location : ")； scanf("%d",&i)； ListDelete_Link (Lc,i,e)； /* 在 Lc 链表中删除第 i 个结点，其值为返回给 e 变量*/ printf("The Deleted e=%d\n",e)； /* 输出被删结点的内容 */ printf("Lc=")； /* 输出链表 Lc 的内容 */ ListTraverse_Link (Lc)； } 五、实验环境和实验步骤 五、实验环境和实验步骤 五、实验环境和实验步骤 五、实验环境和实验步骤 实验环境： 利用 Visual C++集成开发环境进行本实验的操作。 实验步骤――顺序表的定义与操作： 1．启动 VC++； 2. 新建工程/Win32 Console Application，选择输入位置：如 “d:\”，输入工程的名称：如 “SeqlistDemo”； 按“确定”按钮，选择“An Empty Project”，再按“完成”按钮， 3．新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“pubuse. h”，按“确定”按 钮，在显示的代码编辑区内输入如上的参考程序； 4. 新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“seqlistDef. h”，按“确定” 按钮，在显示的代码编辑区内输入如上的参考程序；
《算法与数据结构》实验指导书5.新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“seqlistAlgo.h”，按“确定按钮，在显示的代码编辑区内输入如上的参考程序；6.新建文件/C++SourceFile，选中“添加到工程的复选按钮”，输入文件名“seqlistUse.cpp”，按“确定按钮，在显示的代码编辑区内输入如上的参考程序；7.按F7键，或工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立应用程序；8.按Ctrl+F5键，或！工具图标进行工程的执行。实验步骤一一链表的定义与操作1:启动VC++2.新建工程/Win32ConsoleApplication，选择输入位置：如“d:\"，输入工程的名称：如“linklistDemo"；按“确定”按钮，选择“AnEmptyProject”，再按“完成”按钮，3.加载实验一中的pubuse.h选中菜单的“project”一>“add toproject”-->“files”选择已存在文件，确定，然后一定将文件pubuse.h拷贝到所建的工程目录下；4.新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“linklistDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；5.新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“linklistAlgo.h”，按“确定按钮，在显示的代码编辑区内输入如上的参考程序：6.新建文件/C++SourceFile，选中“添加到工程的复选按钮”，输入文件名“linklistUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序7.构件、调试、运行与实验一相同，在此不再复述六、思考题1.如果将所有的常量定义、系统函数声明、类型定义、算法定义以及主函数全部写在一个文件中，试比较其文件的组织方式。2.如果将顺序表的存储分配由动态分配设计为静态分配，其算法该如何修改，比较动态和静态分配的结果对那些算法的操作有影响？3.要求以较高的效率实现删除线性表中元素值在x到y(X和Y自定)之间的所有元素，写出算法。【参考解题思路】在线性表中设置两个初值为O的下标变量1和j，其中，i为比较元素的下标，j为赋值元素的下标。依次取线性表中下标为i的元素与x和y比较，假若是x到y之外的元素，则赋值给下标为25
《算法与数据结构》实验指导书 25 5. 新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“seqlistAlgo. h”，按“确定” 按钮，在显示的代码编辑区内输入如上的参考程序； 6. 新建文件/C++ Source File，选中“添加到工程的复选按钮”，输入文件名“seqlistUse. cpp”，按“确定” 按钮，在显示的代码编辑区内输入如上的参考程序； 7．按 F7 键，或 工具图标进行工程的建立，如有错误，根据错误显示区中的提示，改正错误，重新建立 应用程序； 8．按 Ctrl+F5 键，或 工具图标进行工程的执行。 实验步骤――链表的定义与操作： 1．启动 VC++; 2.新建工程/Win32 Console Application，选择输入位置：如 “d:\”，输入工程的名称：如 “linklistDemo”；按 “确定”按钮，选择“An Empty Project”，再按“完成”按钮， 3．加载实验一中的 pubuse.h 选中菜单的“project”－>“add to project” ->“files”选择已存在文 件，确定，然后一定将文件 pubuse.h 拷贝到所建的工程目录下； 4. 新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“linklistDef.h”，按“确定” 按钮，在显示的代码编辑区内输入如上的参考程序； 5. 新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“linklistAlgo.h”，按“确定” 按钮，在显示的代码编辑区内输入如上的参考程序； 6. 新建文件/C++ Source File，选中“添加到工程的复选按钮”，输入文件名“linklistUse.cpp”，按“确定” 按钮，在显示的代码编辑区内输入如上的参考程序； 7．构件、调试、运行与实验一相同，在此不再复述； 六、思考题 1．如果将所有的常量定义、系统函数声明、类型定义、算法定义以及主函数全部写在一个文件中，试比 较其文件的组织方式。 2．如果将顺序表的存储分配由动态分配设计为静态分配，其算法该如何修改，比较动态和静态分配的结 果对那些算法的操作有影响？ 3．要求以较高的效率实现删除线性表中元素值在 x 到 y(X 和 Y 自定)之间的所有元素，写出算法。 【参考解题思路】在线性表中设置两个初值为 O 的下标变量 i 和 j，其中，i 为比较元素的下标，j 为赋值 元素的下标。依次取线性表中下标为 i 的元素与 x 和 y 比较，假若是 x 到 y 之外的元素，则赋值给下标为