数据结构实验报告--2.docx

长春理工大学数据结构与算法实验报告实验题目： 实验时间： 实验地点： 班 级： 学 号： 姓 名： 实验目的及要求1、掌握用Visual C++6.0上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现实验意义及原理1、单链表基本操作的实现[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。[基本要求]用链式存储结构实现存储[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。2、求表长以及有序单链表的合并算法的实现[问题描述] 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。[基本要求]用链式存储结构实现存储算法分析(1)建立带头结点链表算法void CreatListF(ListNode *L){char ch;ListNode *s; //工作指针Init_List(L);L-next=NULL; cout请输入节点内容:;ch=getchar(); //读入第1个字符while(ch!=\n){s=(ListNode *)malloc(sizeof(ListNode)); //生成新结点s-data=ch;//将读入的数据放入新结点的数据域中s-next=L-next;L-next=s;ch=getchar();//读入下一字符}} (2)合并单链表算法 int MergeSL(slnodetype * la , slnodetype *lb,slnodetype * *lc){ slnodetype * pa, * pb, * pc; lc=(slnodetype *)malloc(sizeof(slnodetype)); pa=la-next; pb=lb-next; pc= *lc;while(papb) {pc-next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc-next;if(pa-data=pb-data) { pc-data=pa-data; pa=pa-next; }else {pc-data=pb-data;pb=pb-next; }} while (pa) /*插入la链的剩余段 */{ pc-next=(slnodetype*)malloc(sizeof(slnodetype)); pc=pc-next;pc-data=pa-data; pa=pa-next; } /*插入lb链的剩余段*/ while(pb) { pc-next=(slnodetype*)malloc(sizeof(slnodetype)); pc=pc-next;pc-data=pb-data; pb=pb-next;} 源代码（1）单链表基本操作#includestdio.h #includestdlib.h#includeiostreamusing namespace std;typedef char DataType;typedef struct node{DataType data; //结点的数据域struct node *next; //结点的指针域}ListNode;//初始化链表,生成头结点void Init_List(ListNode *L){L=(ListNode *)malloc(sizeof(ListNode));//产生头结点L-next=NULL;}//计算链表结点个数int List_Length(ListNode *L ){ int n=0;ListNode *p=L-next;while(p!=NULL){n++;p=p-next;}return n;}//找返回指向链表第i个结点的指针,或找不到返回NULLListNode *GetNode(ListNode *L,int i){int j;ListNode *p;p=L;j=0; //从头结点开始扫描while(p-nextji) //顺指针向后扫描,直到p-next为NULL或i=j为止{ p=p-next; j++;} if(i=