创建链表和链表操作实验报告(共9页).doc
精选优质文档-倾情为你奉上数据结构实验报告报告名称 创建链表和链表操作 专 业 网络工程 班 级 1001 学 号 9 姓 名 张剑 指导教师 陈淑红 李珍辉 黄哲 2012 年 5月 4日 一、实验目的：掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验内容与基本要求：实验内容：1. 创建单链表2在链表上进行插入、删除操作；3设计一个程序，用两个单链表分别表示两个集合，并求出这两个集合的并集。实验要求： 1 在上机前写出全部源程序； 2 能在机器上正确运行程序；3 用户界面友好；三、概要设计：1.单链表的存储结构：teypedef struct LNodeElemType date; struct LNond *next;LNode *LinkList;2.单链表的插入操作：Status ListTnsert-L(LinkLIst &L, int i, ElemType e )/再带头结点的单链线性表L中的第i个位置之前插入元素eP=l; j=0;While(p&&j<i-1)P=p->next;+j;/寻找第i-1个结点if(!p|j>i-1) return ERROR; /i小小于1或者大于表长+1s=(LinkList) malloc (sizeof(LNode); /生成新结点s->date=e; s->next=p->next; /插入L中p->next=s;return ok;/ListTnsert L3.单链表的删除操作：Status ListDelete-L(LinkLIst &L, int i, ElemType &e )/在带头结点单链线性表L中，删除低i个元素，并由e 返回其值p=l; j=0;while(p->next&&j<i-1) /寻找第i个结点，并令p指向其前驱 p=p->next; +j;if(!(p->next)|j>i-1)return ERROR; /删除位置不合理q=p->next ; p->next=q->next; /删除并释放结点e=q->date free(q);return OK; /ListDelete-L4.链表的合并操作： void MergeList-L(LinkList &La, LinkList &Lb, LinkList &Lc)/ 已知单链表La和Lb的元素值/合并单链表La和Lb，得到新的单链表Lcpa=La->next; pb=Lb->next;lc=pc=La; /用La的头结点作为Lc的 头结点 while(pa&&pb)if(pa->date<=pb->date)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 头结点 /MergeList-L四、详细设计：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <malloc.h>typedef int status;typedef char ElemType;typedef struct Lnode/定义链表结点类型 ElemType data; struct Lnode *next; Lnode,*Linklist; status initlist(Linklist *L) /单链表的初始化 *L=(Lnode *)malloc(sizeof(Lnode); /创建头结点 (*L)->next=NULL; return 1; status Createlist(Linklist L)/创建自己规定长度的单链表 Lnode *p,*q; int i,j=1,n; ElemType m,M; q=L; printf("请输入你要输入单链中元素的个数n"); scanf("%d",&n); scanf("%c",&m);/回车缓冲区 for(i=n;i>0;i-) p=(Lnode *)malloc(sizeof(Lnode); printf("请输入%2.1d个元素:",j); scanf("%ld",&M); scanf("%c",&m);/回车缓冲区 p->data=M; p->next=q->next; q->next=p; q=p; j+; return 1; status Listinsert(Linklist L,int i,ElemType e)/向单链表指定位置插入一个元素 int j=0; Lnode *p=L,*s; while(p&&j<i-1) p=p->next; +j; if(!p|j>i-1)printf("输入错误!n"); return 0; s=(Lnode *)malloc(sizeof(Lnode); s->data=e; s->next=p->next; p->next=s; return 1;status Listdelete(Linklist L,int i,ElemType *e)/删除单链表指定位置的元素,返回删除后的。链表元素 Lnode *p,*q; int j=0; p=L; while(p->next&&j<i-1) p=p->next; j+; if(!(p->next)|j>i-1)printf("输入错误!n"); return 0; q=p->next; p->next=q->next; *e=q->data; free(q); return 1;void print(Linklist L)/输出单链表中的元素 Linklist p; p=L->next; printf("输出单链表：n"); while(p!=NULL) printf("%5ld",p->data); p=p->next; printf("n"); struct Lnode * inter_link(struct Lnode * chain1, int a, struct Lnode * chain2, int b) /单链表的合并 int temp; struct Lnode *head, *p1, *p2, *p3;/判断a，b大小并合并 if (a >= b) head = p1 = chain1; p2 = chain2; else head = p1 = chain2; p2 = chain1; temp = a, a = b, b = temp; p3 = head; while (p2 != NULL) p1 = p1->next; p3->next = p2; p3 = p2; p2 = p2->next; p3->next = p1; p3 = p1; return head;main() int i,n,a,b,h; struct Lnode*p1,*p2; ElemType e; printf("请输入创建的链表的个数:"); scanf("%1d",&n); switch(n) case 1: Linklist L; initlist(&L); /*创建链表*/ Createlist(L); print(L); /*插入元素*/ printf("请输入需要插入元素的值和位置n"); scanf("%ld",&e); scanf("%d",&i); Listinsert(L,i,e); print(L); printf("请输入需要插入元素的值和位置n"); scanf("%ld",&e); scanf("%d",&i); Listinsert(L,i,e); print(L); /*删除元素*/ printf("请输入要删除的元素的位置:"); scanf("%d",&i); Listdelete(L,i,&e); print(L); printf("被删除元素为:%ldn",e); ;break; case 2: Linklist L,H; initlist(&L); initlist(&H); /*创建链表*/ Createlist(L); print(L); Createlist(H); print(H); L = inter_link(L, a, H, b); printf("n合并后的链表：n："); print(L); ;break; default:printf("Enter data error!n"); 五、调试分析及测试结果：测试数据：1 （3，9，5，6，11，8）；2 在5之前插入4，7，并删除11求集合1，12，8，6，4，9和2，5，12，7，4的并集测试结果及分析：1.运行程序，首先进入选择界面，选择输入需要创建的链表数为1个，输入单链表中的 元素个数为六个。按照操作要求一次输入六个元素3,9，5,6，11,8。按回车键结束，此时程序输出单链表，单链表创建成功。 图1：单链表的创建与输出 2.当程序弹出“请输入需要插入元素的值和位置时”执行单链表的插入操作。按要求输入需要4,插入元素的值“4”和元素的位置“3”，按回车结束，重新输出单链表，插入成功。 图2：单链表的插入操作3.进行删除操作，根据提示输入删除元素的位置“7”，输出单链表后，第七个语速消失，元素删除成功。 图3：单链表的删除操作 4.单链表的合并：再一次运行程序，选择需要创建链表的个数为2个。按照提示一次输入两个单链表的元素个数和元素值；按回车键结束，此时进行两个单链表的合并操作，输入合并后的链表。 图4：链表的合并六、实验心得及经验教训：由于c语言没学好，刚开始做实验时感到无从下手，根本不知道怎样去写源代码。后来通过参考书籍和上网查阅资料，依样画葫芦的弄出了代码，但在程序上一编译，出现了很多错误，根本就不能运行。在编译器的中找到出错的地方，一个个的去改正，有些是由于粗心造成的，有些是因为没有定义造成的。最常见的就是漏掉“；”和大小写不分。但有些程序改了好几遍的都该不过来，这就需要不断的去尝试，again and again ,虽然心里会觉得很烦，但改出来，就会有一种成就感，并非得不偿失。通过本次实验，我知道了写程序是一个循序渐进的过程，并不能一口就吃一个胖子；其次，还要又足够的耐心。当然，扎实的专业知识是少不了的，因此，上课要认真听讲，课外要花点时间巩固提高。这样，做实验写程序时就不会手忙脚乱！ 专心-专注-专业
