单链表的操作.doc

XXXX本科数据结构课程设计总结报告设计题目：单链表的操作学生姓名：系 别：专 业：班 级：学 号：指导教师：完 成 期 限： 指导教师签名： 课程负责人签名： 年 月 日一、 设计题目作链表的插入运算建立线性链表，然后利用链表的查找、删除、查找前驱后继、输出等运算反复实现链表的这些操作（插入、删除、查找、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。二、 运行环境（软、硬件环境）用VC+6.0软件平台，操作系统：Windows XP 硬件：内存要求在：内存大小在256MB，其他配制一般就行。三、 算法设计的思想思想：首先通过定义一个动态链表节点的结构体，然后根据结构体定义相应的操作，（1） 定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备工作。（2） 定义遍历链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步通过调用遍历链表的函数算法来实现对链表的遍历操作。（3） 定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存在。（4） 定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对链表的前驱和后继的查找工作。（5） 定义插入节点的算法，通过定义这个算法并结合这查找前驱后继的算法便可以在链表的任何位置进行插入一个新的节点。（6） 定义删除节点的操作，这个算法是用于对链表中某个多余节点的删除工作。（7） 定义退出函数，通过调用这个函数，可以退出当前的系统。 设计思想流程图四、 主要算法的流程图及说明定义结构体lnode 请按8键退出输出各函数执行结果构建各种对链表操作的函数，并相应写出各种函数算法及实现过程。 创建一个单链表，用于之前所定义的函数对其操作请按1-8数字键选择函数，可对单链表进行各种操作具体实现步骤流程图五、算法设计分析 （1）数据结构：typedef struct lnode char value; struct lnode * link; llistnode; 所有函数和算法的入口参数及说明#includestdio.h#includemalloc.h#includestdlib.htypedef struct lnode /链表的结构体定义 char value;/节点 struct lnode * link;/指针 llistnode;llistnode *creat( ) / 创建一个动态链表 llistnode *head , *p; char ch; head = (lnode*)malloc(sizeof(llistnode); head-link=NULL; printf(创建一个链表：n); while( (ch=getchar( )!=n) p=(lnode*)malloc(sizeof(llistnode); p-value=ch; p-link=head; head=p; return head;void print(llistnode *head) / 遍历输出 llistnode *p; printf(n遍历结果为); p=head; while(p) printf(%c,p-value); p=p-link; llistnode *visitll(llistnode *h , char x) / 查找节点 llistnode *p; p = h; while(p-value!=x)&(p-link!=NULL) p = p-link; return p;llistnode *predall(llistnode *h , llistnode *q) /查找前驱 llistnode *p; if(q=h ) p=NULL; else p=h; while(p-link!=q)&(p!=NULL) p=p-link; return p; void insertll(llistnode *h , llistnode *q , char x ) /插入节点 llistnode *p , *r ; r = (llistnode *)malloc(sizeof(llistnode); r-value = x; if(h=q) h=r; else p=predall(h , q); p-link=r; r-link=q; printf(结点已插入!n); 六、源代码#includestdio.h#includemalloc.h#includestdlib.htypedef struct lnode /链表的结构体定义 char value; /结点 struct lnode* link; /指针 llistnode;llistnode *creat( ) / 创建一个动态链表 llistnode *head,*p; char ch; head = (lnode*)malloc(sizeof(llistnode); head-link=NULL; printf(|创建一个链表|n); printf(input:); while(ch=getchar()!=n) /注意:输入一串数据时数据之间不要留空格 p=(lnode*)malloc(sizeof(llistnode); p-value=ch; p-link=head; head=p; printf(创建成功!); return head;void print(llistnode *head) / 遍历输出 llistnode *p; printf(n遍历结果(反序输出)为:); p=head; while(p) printf(%c,p-value); p=p-link; llistnode *visitll(llistnode *h , char x) / 查找结点 llistnode *p; p = h; while(p-value!=x)&(p-link!=NULL) p = p-link; return p;llistnode *predall(llistnode *h , llistnode *q) /查找前驱 llistnode *p; if(q=h) p=NULL; else p=h; while(p-link!=q)&(p-link!=NULL) p=p-link; return p; void insertll(llistnode *h , llistnode *q , char x ) /插入结点 llistnode *p , *r ; r = (llistnode *)malloc(sizeof(llistnode); r-value = x; if(h=q) /待插入结点q是头结点 h=r; else p=predall(h,q); p-link=r; r-link=q;printf(结点已插入!n); void menu() printf(nn); printf( * * * * * * * * * * * *n); printf( * 一 创建链表 *n); printf( * 二 遍历输出 *n); printf( * 三 遍历查找 *n); printf( * 四 查找前驱 *n); printf( * 五 查找后继 *n); printf( * 六 插入节点 *n); printf( * 七 删除节点 *n); printf( * 八 退出系统 *n); printf( * * * * * * * * * * * *nn); void deletell(llistnode *h , llistnode *q) /删除结点 llistnode *p; if (h=q) /删除的是头结点 h = q-link; else p=predall(h,q); p-link= q-link; free(q); printf(该结点已被删除!);void main( ) llistnode *a; llistnode *result=NULL; int choice; char data,data_cz; printf(* n); printf(n); printf( n); printf( n); printf( n); printf( 单链表操作 n); printf( n); printf( n); printf( n);printf(n);printf( * n);printf(n以下是单链表的应用,请选择:); while(1) menu(); scanf(%d,&choice); switch(choice) case 1: getchar( ); /吸收回车符 a = creat( ); break; case 2: print(a); break; case 3: getchar( ); printf(请输入待查结点的值:); data = getchar( ); result = visitll(a,data); if(result-link!=NULL) printf(%c在链表中.,data); else printf(%c不在链表中!,data); result = NULL; /置空指针 break; case 4: getchar(); printf(请输入待查结点的值:); data = getchar( ); result = visitll(a,data); if (result-link=NULL) printf(%c不在链表中!,data); break; result=predall(a,result); if (result!=NULL) printf(%c的前驱是%c.,data,result-value); else printf(%c没有前驱!,data); result = NULL; break; case 5: getchar(); printf(请输入待查结点的值:); data = getchar( ); result = visitll(a,data); if (result-link = NULL) printf(%c不在链表中!,data); break; if (result-link-link!=NULL) printf(%c的后继是%c,data,result-link-value); else printf(%c没有后继!,data); result = NULL; break; case 6:getchar(); printf(请输入待插结点的值:); data = getchar( ); getchar(); printf(请输入插入在哪个结点前面:); data_cz=getchar( ); result = visitll(a,data_cz); if (result-link = NULL)printf(%c不在链表中!,data_cz); break; insertll(a , result , data); break;case 7:getchar( ); printf(请输入待删除结点的值:); data = getchar( ); result = visitll(a,data); if (result-link = NULL) printf(%c不在链表中!,data); break; deletell(a , result); break;case 8:exit(0);default: printf(你输入的数字不正确,请重新输入!); 七、运行结果分析以下是单链表的应用请选择：* 一 创建链表 * * 二 遍历输出 * * 三 遍历查找 * 四 查找前驱 * * 五 查找后继 * * 六 插入节点 * 七 删除节点 * * 八 退出系统 *请按1-8数字键选择函数输入数字：1|创建一个链表|Input: e2wr9t显示：创建成功输入数字：2遍历结果(反序输出)为：t9rw2e输入数字：3请输入待查结点值：输入r显示：r在链表中输入数字：4请输入待查结点值：输入2显示：2的前驱是w输入数字：5请输入待查结点值：输入9显示：9的后继是r输入数字：6请输入待插入结点值：输入b显示：请输入插在那个节点后面输入w显示：结点已插入输入2显示：遍历输出结果为：t9rbw2e输入数字：7显示：请输入待删除结点的值输入t显示：结点已被删除输入2显示：遍历输出结果为：9rbw2e输入8显示：Press any key to continue 八、部分截图A. 创建链表B. 遍历输出C.遍历查找D.查找前驱E.查找后继F.插入结点G.删除结点九、收获及体会通过这周的课程设计,我对数据结构中单链表的应用有了更深的理解，并且更使自己深刻地认识到实践的重要性，只有理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。在实验之前，通过浏览、阅读有关的资料，学到了很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。由于刚开始对单链表的应用总体结构不熟悉，对书本知识的学习很不扎实，刚拿到这个题目的时候，还不好怎么动手，就请教做过这样的课程设计的学长，并认真阅读了实验指导书，才对这次课程设计有了初步的了解。根据自己对数据结构的了解，我感觉我对单链表的认识比较深刻。因此我选择做单链表的实验，作为线性表的一种存储结构，它的特点是可以充分利用存储单元来存储数据，并且可以方便的实现对数据进行插入、删除、遍历等操作。在我进行课程设计时，虽然在大体上算法是正确的，但是常常会出现一些小的问题，使我在做课程