数据结构课程设计报告-单链表

链表操作..目录TOC\o"1-3"\h\u166971选题背景2232202方案与论证3258412.1链表的概念和作用3265912.3算法的设计思想4187062.4相关图例5150312.4.1单链表的结点构造5277712.4.2算法流程图5122303实验结果220343.1链表的建立6258113.2单链表的插入6320213.3单链表的输出7190563.4查找元素7135493.5单链表的删除8325073.6显示链表中的元素个数〔计数〕9165624结果分析1098784.1单链表的构造1050594.2单链表的操作特点10204464.2.1顺链操作技术10123154.2.2指针保存技术10131654.3链表处理中的相关技术10226005设计体会及今后的改良意见1119571参考文献1214900附录代码：131选题背景火旺院士把计算机60多年的开展成就概括为五个"一〞：开辟一个新时代信息时代，形成一个新产业信息产业，产生一个新科学计算机科学与技术，开创一种新的科研方法计算方法，开辟一种新文化计算机文化，这一概括深刻影响了计算机对社会开展所产生的广泛而深远的影响。数据构造和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，"在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息〞。计算机科学就是"一种关于信息构造转换的科学〞。信息构造〔数据构造〕是计算机科学研究的根本课题，数据构造又是算法研究的根底。2方案与论证2.1链表的概念和作用链表是一种链式存储构造，链表属于线性表，采用链式存储构造，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象)+

指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以"结点的序列〞表示线性表称作线性链表〔单链表〕单链表是链式存取的构造，为找第i个数据元素，必须先找到第i-1个数据元素。因此，查找第i个数据元素的根本操作为：移动指针，比拟j和i单链表1、存储方法方式存储的线性表简称为链表〔LinkedList〕。链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点〔这组存储单元既可以是连续的，也可以是不连续的〕②链表中结点的逻辑次序和物理次序不一定一样。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址〔或位置〕信息〔称为指针〔pointer〕或链(link)〕注意：链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据构造。2、链表的结点构造┌───┬───┐│data│next│└───┴───┘data域--存放结点值的数据域next域--存放结点的直接后继的地址〔位置〕的指针域〔链域〕注意：①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序在一起的。②每个结点只有一个链域的链表称为单链表〔SingleLinkedList〕。3、头指针head和终端结点指针域的表示单链表中每个结点的存储地址是存放在其前趋结点next域中，而开场结点无前趋，故应设头指针head指向开场结点。注意：链表由头指针唯一确定，单链表可以用头指针的名字来命名。终端结点无后继，故终端结点的指针域为空，即NULL。2.2实验的根本要求〔软硬件〕用VC++6.0软件平台，操作系统：WindowsXP硬件：存要求：存大小在256MB，其他配置一般就行。2.3算法的设计思想〔a〕定义一个创立链表的函数，通过该头插法创立一个带头结点的链表，在接下来的链表操作中使用。〔b〕定义输出链表的算法，遍历结点的指针域判断是否为空，如果不为空那么输出其数据域，直到指针域为空为止。〔c〕定义一个遍历查找的算法，通过遍历的数据域，分别与要查询的元素进展比拟，如果查找到那么返回并输出，如入查找失败那么返回错误提示信息。〔d〕定义插入结点的算法，首先查找指针域为空的结点，并申请空间插入在结点的后边，并且将其指针域置空。〔e〕定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作，其关键在于前驱结点的保存，查找到需删除的结点，将其删除，并将其后继结点连到其前驱结点。2.4相关图例2.4.1单链表的结点构造如图2-1所示,为单链表的结点构造示意图：Data域Next域Data域Next域图2-1单链表的结点构造2.4.2算法流程图如图2-2所示，为此算法流程图：开场开场定义构造体Node定义构造体Node构建各种对链表操作的函数〔插入、删除、查找、输出〕，并写出相应的算法及实现过程创立一个单链表，用于之前所定义的函数对其进展操作按要求输出结果完毕图2-2算法流程图3实验结果3.1链表的建立图3-1链表的建立3.2单链表的插入图3-2单链表的插入3.3单链表的输出图3-3输出单链表元素3.4查找元素图3-4查找成功图3-5查找失败3.5单链表的删除图3-6删除成功图3-6删除失败3.6显示链表中的元素个数〔计数〕图3-7输出长度4结果分析4.1单链表的构造一般情况下，使用链表，只关心链表中结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此通常情况下用箭头来表示链域中的指针，于是链表就可以更直观的画成用箭头起来的结点序列，如下列图所示：ABABCDE^H图4-1单链表的例如图4.2单链表的操作特点4.2.1顺链操作技术从"头〞开场，访问单链表L中的结点i〔p指向该节点〕时，由于第i个结点的地址在第i-1个结点〔pre指向该结点，为p的前驱〕的指针域中存放，查找必须从单链表的"首结点〞开场〔p=L〕；通过p=p->next并辅助计数器来实现。4.2.2指针保存技术通过对第i个结点进展插入、删除等操作时，需要对第i-1个结点的指针域进展链址操作〔pre->next〕，因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系，将这种技术称为"指针保存技术〞。4.3链表处理中的相关技术1〕单链表与多重链表的差异在于指针域的个数。2〕判断当前结点p是否为表尾。一半链表中，p结点是表尾的条件是：该节点的后继结点为空指针，即p->next==NULL;3〕链表的长度并未显示保存。由于链表是动态生成的构造，其长度要通过顺链查找到表尾得到。因此在处理链表时，往往是以当前处理结点p是否为表尾作为控制条件，而不是长度n作为控制条件。5设计体会及今后的改良意见通过这次实验加深了我对于单链表的进一步了解，了解到了单链表在存中的存储构造，最重要的是学会了如何运用C语言将单链表的建立，插入、删除、添加等操作。在程序实现中也遇到了一些困难，在单链表初始化时，使用了0作为完毕输入符，导致单链表不能存储数据0；单链表中只能存储一样类型的数据，在存储不同类型的数据时需要改变输入完毕标志，程序通用性比拟差。在进展程序设计的时候没有考虑好删除和查找的方式，只进展了输入元素的查找和删除，而且进展链表的插入时，只考虑了头插法在结尾插入，而没有考虑输入结点插入等，程序的灵活性比拟低。通过这次课程设计，让我充分认识到数据构造在编写程序方面的重要地位。不仅仅是单链表的操作，还有栈和队列等特殊的单链表操作，以及其他一些常用的数据构造对于程序的效率和存使用有很大的帮助。我希望在接下来的学习中收获更多的东西。参考文献[1]耿.数据构造--用C语言描述[M].:高等教育,2011.6.[2]谭浩强.C程序设计[M].:清华大学,2004.6.附录代码：构造体定义：#pragmaonce#include<stdio.h>#include<stdlib.h>enummy_enum{ _EXIT, _CREATE, _INSERT, _PRINT, _SEARCH, _DELETE, _COUNT,};staticintcount=0;typedefintElemtype;typedefstructNode/*单链表构造体的定义*/{Elemtypedata;structNode*next;}Node,*LinkList;voidtest();/*测试函数*/voidmain_menu();//主菜单函数voidCreatFromHead(LinkList*l);/*头插法建立单链表*/voidInsert(LinkListl);//单链表的插入voidPrint(LinkListl);/*单链表的输出*/intSearch(LinkListl,Elemtypee);//查找指定的元素voidDeletelist(LinkListl,Elemtypee);//删除元素voidCount();//计数voidCREATE(LinkList*head);voidINSERT(LinkList*head);voidPRINT(LinkList*head);voidSEARCH(LinkList*head);voidDELET(LinkList*head);voidCOUNT();单链表操作函数：#define_CRT_SECURE_NO_WARNINGS#include"linklist.h"voidmain_menu(){ printf("\t单链表的简单操作\t\t\n\n"); printf("\t1单链表的建立\n"); printf("\t2单链表的插入\n"); printf("\t3单链表的输出\n"); printf("\t4单链表的查找\n"); printf("\t5单链表的删除\n"); printf("\t6单链表的长度\n"); printf("\t0退出\n");}voidCreatFromHead(LinkList*l)/*头插法建立单链表*/{Node*s;intc=0;intflag=1; *l=(Node*)malloc(sizeof(Node));if(*l==NULL) { printf("申请空间失败！！\n");return; } (*l)->next=NULL;while(flag) { scanf("%d",&c);if(c!=0) { s=(Node*)malloc(sizeof(Node));if(s==NULL) { printf("申请空间失败！！\n");return; } s->data=c; s->next=(*l)->next; (*l)->next=s; count++; }elseflag=0; }}voidInsert(LinkListl)//单链表的插入{intinsert=0;Node*s=NULL; printf("请输入需要插入的元素："); scanf("%d",&insert); s=(Node*)malloc(sizeof(Node));if(s==NULL) { printf("申请空间失败！！\n");return; }while(l->next!=NULL) {l=l->next; } s->data=insert; s->next=l->next;l->next=s; count++;}voidPrint(LinkListl)/*单链表的遍历*/{Node*p; p=l->next;while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("\n");}intSearch(LinkListl,Elemtypee)//查找指定的元素{while((l!=NULL)&&(l->data!=e)) {l=l->next; }if(l==NULL) {return-1;//查找失败 }else {return1;//查找成功 }}voidDeletelist(LinkListl,Elemtypee)//删除节点{Node*p,*r,*q; p=l->next;q=l;while(p!=NULL) {if(p->data==e) { r=p; p=r->next; q->next=p; count--; free(r);break; }else { q=p;/*保存前驱节点*/ p=p->next; } }if(p==NULL) { printf("删除失败，没有找到相应的元素\n"); }}voidCount(){ printf("单链表中一共有%d个元素\n",count);}voidCREATE(LinkList*head){ printf("请建立单链表用"0〞来完毕输入\n"); CreatFromHead(head); printf("初始化后的单链表为："); Print(*head);}voidINSERT(LinkList*head){ Insert(*head); printf("插入后的单链表为："); Print(*head);}voidPRINT(LinkList*head){ printf("单链表的输出为："); Print(*head);}voidSEARCH(LinkList*head){intsearch=0;intret=0; printf("请输入需要查找的元素："); scanf("%d",&search); ret=Search(*head,search);if(1==ret) { printf("查找成功\n"); }else { printf("查找失败\n"); }}voidDELET(LinkList*head){intdelet=0; printf("请输入需要删除的元素："); scanf("%d