数据结构之线性链表基本操作实训报告书

1、实训报告书实训名称： 数据结构之线性链表基本操作 系 （部）： 信息工程系 专业班级： 计算机高本08班 学生姓名： 何文晶 学 号： 0823010113 指导教师： 亓静 完成日期： 20100605 实训课题C语言实现线性链表的基本操作实训人姓名何文晶同组人员无实训日期20100605实训成绩指导教师评语指导教师签名：_年 _ 月_日装订线目 录 TOC o 1-2 h z u HYPERLINK l _Toc243090018 目 录 PAGEREF _Toc243090018 h 1 HYPERLINK l _Toc243090019 1 实训总结 PAGEREF _Toc24309

2、0019 h 2 HYPERLINK l _Toc243090020 2 线性链表的功能描述 PAGEREF _Toc243090020 h 3 HYPERLINK l _Toc243090021 2.1 线性链表基本功能实现的目标 PAGEREF _Toc243090021 h 3 HYPERLINK l _Toc243090022 概要设计各模块3 HYPERLINK l _Toc243090023 2.3 各模块详细设计 PAGEREF _Toc243090023 h 3 HYPERLINK l _Toc243090025 3 主要功能实现原理及代码5 HYPERLINK l _Toc2

3、43090026 4 附录 PAGEREF _Toc243090026 h 6线性链表的基本操作1 实训总结数据结构实训周的结束，让大家都长舒了一口气，这其中努力或不劳而获的各种复杂心情，也都随着轻烟袅袅而逝了。不过给我留下的一些经验、教训以及感想还是挺多的。一年一度的实训周，实习科目，科目在变，忐忑而为难的心却总也不变。原因有几个：平日里听课就不怎么认真，就算哪堂课听了，但就感觉跟实训也联系不上，上课是上课，实训是实训，没有什么联系。实训周之前，简直就是文盲，什么也不知道，书都没怎么看，但迫于实训，书是要好好看的，所以感谢实训。平日，也不会和同学有学术上有什么讨论，但实训了就不一样了，同学之

4、间也有了团队合作。对于实训的感想好像写的多了些，下面是我的实训中编程的一些经验总结：多看看书，数据结构就是一些算法，而实训就是把算法应用，所以在应用之前总要先知道它是什么。到处收集一些资料，可以从网海中拾些贝，看着别人做的也会有些收获，但不要不劳而获。因为到老师验收时，你恐怕会上言不接下语。谦虚的向同学和老师求教，自己做不出来，不要硬憋着，三人行必有我师，和同学一起研讨，把自己的想法说出来，也可以让自己对一些东西的理解不至于走到胡同里去。最后，把程序调试好，千万不要在关键的时候出了问题。这一周的实训结束了，总感觉也长大了不少，对于数据结构这一学科也有了更深入的理解，虽然只是部分算法的简单应用，

5、但以小见大，收获还是不小的。2 线性链表的功能描述利用C语言在TC的环境中实现线性链表的基本操作，如创建一个空链表，给每个结点存储数据，按位置查找或按数值查找，按位置插入，链表的逆置操作，链表的排序，链表的输出等等。2.1 线性链表基本功能实现目标链表的各种基本操作：创建一个空链表，为每个结点存储数据，按位置查找或按数值查找，按位置插入，链表的逆置操作，链表的排序，链表的输出。以上功能分别为各个函数，在主界面内，按选项调用，以人性化的界面来使用各项功能，保证各项功能均能正常调用，及输出，及程序不能进入死循环。2.2 概要设计各模块创建链表建立一个单链表（或二叉链表），输入链表中要存储的信息。2

6、.2.2数据输出实现对当前单链表中数据的输出。数据插入实现向单链表中插入数据，插入时需输入要插入的位置和要插入的数据。数据删除实现对单链表中指定位置的数据的删除，删除数据是输入要删除数据的位置。数据查找查找单链表中指定位置的数据并输出。数据排列实现对单链表中的数据进行初步排列。数据逆置对单链表中的数据的位置进行逆置，即使其输出顺序颠倒。23各模块详细设计查 询主界面插 入逆 置排序清单线性链表删 除查 找表 1功能模块关系图.1主界面1线性链表基本操作”MAIN OPERATION OF LINKLIST”的主界面上显示着这个C程序的9大功能：创建链表（CREATE A LIST）、输出链表数

7、据（PRINT LIST）、按位置插入数据（INPUT DATA）、按位置删除数据（DELETE DATA）、查找数据（LOCATE DATA）、计数链表长度（COUNT LIST）、排序链表（ORDER LIST）、逆置链表（NI ZHI LIST）、退出（QUIT）。2以上功能分别对应着19的序号，输入序号执行相应的功能。.2创建链表输入序号1，执行该功能，先由用户输入链表结点个数，再输入各结点数据。.3输出链表数据输入序号2，执行该功能，输入当前链表内各结点数据。.4按位置插入数据输入序号3，由用户输入要插入数据的位置，再输入要插入的数据。.5按位置删除数据输入序号4，由用户输入要删除数

8、据的位置，再输入要删除的数据。.6查找数据输入序号5，由用户输入要查找数据的结点位置，即可显示要查找的数据。.7计数链表长度输入序号6，执行该功能，显示当前链表的结点个数。.8排序链表输入序号7，执行该功能，将当前链表由大到小排序。.9逆置链表输入序号8，执行该功能，将当前链表逆置存储。.2退出输入序号9，执行该功能，退出。3 主要功能实现原理及代码3.1 初始界面提示语:输入要选择的功能,即可调用.代码如下: a =240 ; b =0 ;for(ii=0;ii100;i+) clrscr(); for(i=1;i=80;i+) printf(%c,a); /*第一行显示*/ for(i=2

9、;i=3;i+) printf(%c,a); for(i=2;i=77;i+) printf(%c,b); for(i=2;i=3;i+) printf(%c,a); /*以上作为第二行显示*/ for(i=2;i=3;i+) printf(%c,a); for(i=2;i=77;i+) printf(%c,b); for(i=2;i=3;i+) printf(%c,a); /*以上作为穿插行显示*/ for(i=3;i=4;i+) printf(%c,a); for(i=3;i MAIN OPERATION OF LINKLIST ); /*这中间部分代码省略*/ printf( 1 .CR

10、EATE A LIST. ); for(i=3;i=12;i+) printf(%c,b); printf( 2 .PRINT LIST. ) ; for(i=3;i=16;i+) printf(%c,b); for(i=3;i=4;i+) printf(%c,a); /*以上作为第三行的选项*/ for(i=6;i=7;i+) printf(%c,a); for(i=6;i=19;i+) printf(%c,b); printf( 9 . QUIT .); for(i=6;i=19;i+) printf(%c,b); for(i=6;i=7;i+) printf(%c,a); /*以上作为第

11、六行的选项*/ for(i=2;i=3;i+) printf(%c,a); for(i=2;i=77;i+) printf(%c,b); for(i=2;i=3;i+) printf(%c,a); /*以上作为第二行显示*/ for(i=7;i=8;i+) printf(%c,a); for(i=7;i=82;i+) printf(%c,b); for(i=7;i=8;i+) printf(%c,a); /*以上作为第七行显示*/ for(i=1;i=80;i+) printf(%c,a); /*第八行显示*/说明：主界面用了很多循环输出字符图形，形成的一个界面效果。3.2 创建链表图3.2选

12、项1,创建链表LinkNode *create_list(LinkNode *head,int n) /*建立创建链表的指针函数，指函数根据用户提供的输入的数据来创建节点*/ LinkNode *p,*q; /*定义指针*/ int i; p=head; for(i=1;idata); /*接受用户输入的数据*/ q-next=NULL; p-next=q; p =q; return p; 说明：建立创建链表的指针函数，指函数根据用户提供的输入的数据来创建结点及结点数据，该算法，先定义指针，再在循环内分界存储空间并接受用户输入的数据，并依次存储，并返回指针P的值。3.3 输出链表图3.3选项2

13、,输出链表void print(LinkNode *head) /*建立输出数据的静态函数*/ LinkNode *p; printf(nTHE ALL DATA:); for(p=head-next;p!=NULL;) printf(%d - ,p-data); p=p-next; 说明：建立输出链表各结点数据的静态函数，该算法是先定义指针，再遍历各结点，到一个结点输出一个结点的数据，从而实现输出各个结点数据的功能。这个函数在各个模块中应用的也比较多。3.4 按位置插入数据图3.4选项3,按位置插入数据void insert_list(LinkNode *head) /*建立插入数据的静态函

14、数， */ LinkNode *p,*s; int i,e,j=0,x; p=head; printf(INPUT INSERT LOCATE:);scanf(%d,&i); /*用户输入插入位置*/ printf( INPUT THE DATA :);scanf(%d,&x); /*用户输入要插入的数据*/ while(p!=NULL)&(jnext; j+; if(p=NULL) exit(0); /*如果指针为空，则退出*/ s=(Linklist)malloc(sizeof(LinkNode); /*新结点空间*/ s-data=x; /*用户输入的值赋给新的结点空间*/ s-next

15、=p-next; /*新的结点链上一个结点的next*/ p-next=s; /*原结点接上新的结点，插入完成！*/ print(head); printf(n);说明：建立插入数据的静态函数，按用户提供的插入位置，再输入要插入的数据，循环内建立新的结点空间，并为其赋值，最后将整条链表输出。3.5 按位置删除数据图3.5选项4按位置删除数据void delete_list(LinkNode *head) /*建立删除数据的静态函数*/ LinkNode *p,*q; int i,e,j=0,x; p=head; printf(nINPUT DELETE LOCATE: );scanf(%d,&

16、i); /*根据用户输入的位置删除结点数据*/ while(p!=NULL)&(jnext; j+; if(p=NULL) exit(0); q=p-next; /*要删除结点Q等于原结点的下一个结点*/ p-next=q-next; /*P的next 指向q的next*/ x=q-data; /*用一个变量来存储要删除结点 q的值。*/ free(q); /* 释放结点*/ print(head); /*删除节点操作完成！*/ printf(n);说明：建立删除数据的静态函数，该算法，和插入算法有些类似，按用户提供的删除位置，将指针定位到该结点处，然后删除该结点的数据，并释放该结点。3.6

17、查找数据图3.6选项5查找数据LinkNode *search(LinkNode *head,int i) /*建立查找数据的指针函数*/ LinkNode *p,*q; int e,j=0; p=head; /*头结点*/ while ( p & j next; +j; /*当用户查找的数据位置合理时，进行查找*/ e=p-data; return p;说明：建立按位置查找数据的函数，由用户指示要查找数据的位置，将指针定位到该位置，再输出该数据。该算法相对比较容易。3.7 计数链表图3.7选项6计数链表int count(LinkNode *head) /*建立计数函数*/ LinkNode

18、 *p; int j=-1; p=head; while(p!=NULL) j+; p=p-next; /*指针循环，J累加，得到链表的长度*/ return j; 说明：建立计数函数，先定义指针函数，当指针不为空，指针不断循环，计数J累加，从而得到链表的长度，并返回J的值，输出表长。3.8 排序链表图3.8 选项7 排序链表void order(LinkNode *head) /*建立排序函数*/ LinkNode *p,*s; int size=0,i,j; int min; size=count(head); /*取链表长度*/ s=head-next; for(i=0;(i=size-

19、1);i+) p=s; for(j=0;(jnext!=NULL);j+) min=p-data; p=p-next; if(minp-data) /*从小到大排列*/ exchange(head,j+1,j+2); /*这里用到了上面定义的交换函数*/ 说明：建立排序链表的函数，使该链表中的当前结点的全部数据按从小到大的顺序排列，其中用到的exchange()函数也是用户自定义，后面会补充。3.9 逆置链表图3.9 选项8 逆置链表void contray(LinkNode *head) /*建立逆置函数*/ LinkNode *rear,*s,*h; int si=0; int i; h=

20、(LinkNode*)malloc(sizeof(LinkNode); /*生成新结点空间*/ si=count(head); rear=search(head,si); /*/ h-next=rear; for(i=si-1;i0;i-) s=search(head,i); /*寻找到位置i结点数据，完成逆置操作*/ rear-next=s; rear=s; rear-next=NULL; print(h); 说明：建立逆置链表函数，用到的search()为查找函数，这里是函数的嵌套使用，先定义指针函数，再把生成的新结点空间赋给H，由SI存储当前表长，上图的逆置结果，为了效果是在排序前运行得

21、到的，最后输出逆置的结果。附录注：此处补充部分辅助函数等#include /*头文件啊*/#include/*还是头文件*/ typedef struct LinkNode long int data; struct LinkNode *next;LinkNode,*Linklist; /*定义了一个结构体，LNODE，和结构体指针*/LinkNode *create_head() /* 建立头结点*/ LinkNode *p; p=(Linklist)malloc(sizeof(LinkNode); /*新的结点空间*/ p-next=NULL; return(p);int exchange(LinkNode *head,int i,int j) /*建立交换函数*/ int data; LinkNode *p1=NULL,*p2=NULL; p1=search(head,i); p2=search(head,j); if(p1!=NULL&p2!=NULL) /*两个指针不为空*/ data=p1-data; p1-data=p2-data; p2-data=data; return 1; else ret