线性链表
-
2023年3月3日发(作者：葵花神功)实训报告书
实训名称：数据结构之线性链表基本操作
系（部）：信息工程系
专业班级：计算机高本08—１班
学生姓名：何文晶
学号：
指导教师：亓静
完成日期：2010—06—05
实训课题C语言实现线性链表的基本操作
实训人姓名何文晶同组人员无
实训日期2010－06—05
实训成绩
指导
教师
评语
指导教师签名：______________
_______年____月____日
目录
目录.........................................................................................................1
1实训总结.................................................................................................2
2线性链表的功能描述..........................................................................3
2.1线性链表基本功能实现的目标................................................3
概要设计各模块.........................................................................3
2.3各模块详细设计........................................................................3
3主要功能实现原理及代码..................................................................5
4附录.......................................................................错误!未定义书签。
…
…
…
…
…
…
…
…
…
…
…
装
…
…
…
…
…
…
…
…
…
…
…
…
…
…
订
…
…
…
…
…
…
…
…
…
…
…
…
…
线
…
…
…
…
…
…
…
…
…
…
…
线性链表的基本操作
1实训总结
数据结构实训周的结束，让大家都长舒了一口气，这其中努力或不劳而获的
各种复杂心情，也都随着轻烟袅袅而逝了。不过给我留下的一些经验、教训以及
感想还是挺多的。
一年一度的实训周，实习科目，科目在变，忐忑而为难的心却总也不变。
原因有几个：
1．平日里听课就不怎么认真，就算哪堂课听了，但就感觉跟实训也联
系不上，上课是上课，实训是实训，没有什么联系。
2．实训周之前，简直就是文盲，什么也不知道，书都没怎么看，但迫
于实训，书是要好好看的，所以感谢实训。
3．平日，也不会和同学有学术上有什么讨论，但实训了就不一样了，
同学之间也有了团队合作。
对于实训的感想好像写的多了些，下面是我的实训中编程的一些经验总结：
1．多看看书，数据结构就是一些算法，而实训就是把算法应用，所以在应
用之前总要先知道它是什么。
2．到处收集一些资料，可以从网海中拾些贝，看着别人做的也会有些收获，
但不要不劳而获。因为到老师验收时，你恐怕会上言不接下语。
3．谦虚的向同学和老师求教，自己做不出来，不要硬憋着，三人行必有我
师，和同学一起研讨，把自己的想法说出来，也可以让自己对一些东西
的理解不至于走到胡同里去。
4．最后，把程序调试好，千万不要在关键的时候出了问题。
这一周的实训结束了，总感觉也长大了不少，对于数据结构这一学科也有了
更深入的理解，虽然只是部分算法的简单应用，但以小见大，收获还是不小
的。
2线性链表的功能描述
利用C语言在TC的环境中实现线性链表的基本操作，如创建一个空链表，
给每个结点存储数据，按位置查找或按数值查找，按位置插入，链表的逆置操作，
链表的排序，链表的输出等等。
2.1线性链表基本功能实现目标
链表的各种基本操作：创建一个空链表，为每个结点存储数据，按位置查找
或按数值查找，按位置插入，链表的逆置操作，链表的排序，链表的输出。
以上功能分别为各个函数，在主界面内，按选项调用，以人性化的界面来使
用各项功能，保证各项功能均能正常调用，及输出，及程序不能进入死循环。
2.2概要设计各模块
创建链表
建立一个单链表（或二叉链表），输入链表中要存储的信息。
2.2.2数据输出
实现对当前单链表中数据的输出。
数据插入
实现向单链表中插入数据，插入时需输入要插入的位置和要插入的数据。
数据删除
实现对单链表中指定位置的数据的删除，删除数据是输入要删除数据的位
置。
数据查找
查找单链表中指定位置的数据并输出。
数据排列
实现对单链表中的数据进行初步排列。
数据逆置
对单链表中的数据的位置进行逆置，即使其输出顺序颠倒。
2．3各模块详细设计
表1功能模块关系图
.1主界面
1．线性链表基本操作”MAINOPERATIONOFLINKLIST”的主界面上显示着
这个C程序的9大功能：创建链表（CREATEALIST）、输出链表数据（PRINT
LIST）、按位置插入数据（INPUTDATA）、按位置删除数据（DELETEDATA）、
查找数据（LOCATEDATA）、计数链表长度（COUNTLIST）、排序链表（ORDER
LIST）、逆置链表（NIZHILIST）、退出（QUIT）。
2．以上功能分别对应着1~9的序号，输入序号执行相应的功能。
.2创建链表
输入序号1，执行该功能，先由用户输入链表结点个数，再输入各结点数据。
.3输出链表数据
输入序号2，执行该功能，输入当前链表内各结点数据。
.4按位置插入数据
输入序号3，由用户输入要插入数据的位置，再输入要插入的数据。
.5按位置删除数据
输入序号4，由用户输入要删除数据的位置，再输入要删除的数据。
.6查找数据
输入序号5，由用户输入要查找数据的结点位置，即可显示要查找的数据。
.7计数链表长度
输入序号6，执行该功能，显示当前链表的结点个数。
.8排序链表
查询
主界面
插入逆置排序清单
线性链表
删除查找
输入序号7，执行该功能，将当前链表由大到小排序。
.9逆置链表
输入序号8，执行该功能，将当前链表逆置存储。
.2退出
输入序号9，执行该功能，退出。
3主要功能实现原理及代码
3.1初始界面
提示语:输入要选择的功能,即可调用.
代码如下:
a=240;b=0;
for(ii=0;ii<100;i++)
{clrscr();
for(i=1;i<=80;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=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<=16;i++)printf("%c",b);
printf(">>>MAINOPERATIONOFLINKLIST<<<");
……/*这中间部分代码省略*/
printf("ALIST.");
for(i=3;i<=12;i++)printf("%c",b);
printf("IST.");
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(".");
for(i=6;i<=19;i++)printf("%c",b);
for(i=6;i<=7;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=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选项1,创建链表
LinkNode*create_list(LinkNode*head,intn)
/*建立创建链表的指针函数，指函数根据用户提供的输入的数据来创建节点*/
{LinkNode*p,*q;/*定义指针*/
inti;
p=head;
for(i=1;i<=n;i++)
/*n为用户提供的链表长度，循环接收用户提供的数据，写注释好累啊。。。*/
{q=(Linklist)malloc(sizeof(LinkNode));/*分配存储空间*/
printf("DATA:%d:t",i);scanf("%d",&q->data);/*接受用户输入的数据*/
q->next=NULL;
p->next=q;
p=q;}
returnp;
}
说明：建立创建链表的指针函数，指函数根据用户提供的输入的数据来创建结点
及结点数据，该算法，先定义指针，再在循环内分界存储空间并接受用户输入的
数据，并依次存储，并返回指针P的值。
3.3输出链表
图3.3选项2,输出链表
voidprint(LinkNode*head)
/*建立输出数据的静态函数*/
{LinkNode*p;
printf("nTHEALLDATA:");
for(p=head->next;p!=NULL;)
{
printf("%d->",p->data);
p=p->next;
}
}
说明：建立输出链表各结点数据的静态函数，该算法是先定义指针，再遍历各结
点，到一个结点输出一个结点的数据，从而实现输出各个结点数据的功能。
这个函数在各个模块中应用的也比较多。
3.4按位置插入数据
图3.4选项3,按位置插入数据
voidinsert_list(LinkNode*head)/*建立插入数据的静态函数，*/
{LinkNode*p,*s;
inti,e,j=0,x;
p=head;
printf("INPUTINSERTLOCATE:");scanf("%d",&i);/*用户输入插入位置*/
printf("INPUTTHEDATA:");scanf("%d",&x);/*用户输入要插入的数据*/
while((p!=NULL)&&(j {p=p->next; j++;} if(p==NULL)exit(0);/*如果指针为空，则退出*/ s=(Linklist)malloc(sizeof(LinkNode));/*新结点空间*/ s->data=x;/*用户输入的值赋给新的结点空间*/ s->next=p->next;/*新的结点链上一个结点的next*/ p->next=s;/*原结点接上新的结点，插入完成！！*/ print(head); printf("n");} 说明：建立插入数据的静态函数，按用户提供的插入位置，再输入要插入的数据， 循环内建立新的结点空间，并为其赋值，最后将整条链表输出。 3.5按位置删除数据 图3.5选项4按位置删除数据 voiddelete_list(LinkNode*head)/*建立删除数据的静态函数*/ {LinkNode*p,*q; inti,e,j=0,x; p=head; printf("nINPUTDELETELOCATE:");scanf("%d",&i); /*根据用户输入的位置删除结点数据*/ while((p!=NULL)&&(j {p=p->next; 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查找数据 图3.6选项5查找数据 LinkNode*search(LinkNode*head,inti) /*建立查找数据的指针函数*/ { LinkNode*p,*q; inte,j=0; p=head;/*头结点*/ while(p&&j {p=p->next;++j;} /*当用户查找的数据位置合理时，进行查找*/ e=p->data; returnp; } 说明：建立按位置查找数据的函数，由用户指示要查找数据的位置，将指针定位 到该位置，再输出该数据。该算法相对比较容易。 3.7计数链表 图3.7选项6计数链表 intcount(LinkNode*head)/*建立计数函数*/ { LinkNode*p; intj=-1; p=head; while(p!=NULL) {j++; p=p->next; /*指针循环，J累加，得到链表的长度*/ } returnj; } 说明：建立计数函数，先定义指针函数，当指针不为空，指针不断循环，计数J 累加，从而得到链表的长度，并返回J的值，输出表长。 3.8排序链表 图3.8选项7排序链表 voidorder(LinkNode*head)/*建立排序函数*/ {LinkNode*p,*s; intsize=0,i,j; intmin; size=count(head);/*取链表长度*/ s=head->next; for(i=0;(i<=size-1);i++) {p=s; for(j=0;(jnext!=NULL);j++){ min=p->data; p=p->next; if(min>p->data)/*从小到大排列*/ exchange(head,j+1,j+2);/*这里用到了上面定义的交换函数*/ } } } 说明：建立排序链表的函数，使该链表中的当前结点的全部数据按从小到大的顺 序排列，其中用到的exchange()函数也是用户自定义，后面会补充。 3.9逆置链表 图3.9选项8逆置链表 voidcontray(LinkNode*head)/*建立逆置函数*/ {LinkNode*rear,*s,*h; intsi=0; inti; h=(LinkNode*)malloc(sizeof(LinkNode));/*生成新结点空间*/ si=count(head); rear=search(head,si);/**/ h->next=rear; for(i=si-1;i>0;i--){ s=search(head,i);/*寻找到位置i结点数据，完成逆置操作*/ rear->next=s; rear=s;} rear->next=NULL; print(h); } 说明：建立逆置链表函数，用到的search()为查找函数，这里是函数的嵌套使用， 先定义指针函数，再把生成的新结点空间赋给H，由SI存储当前表长，上图的 逆置结果，为了效果是在排序前运行得到的，最后输出逆置的结果。 附录 注：此处补充部分辅助函数等 #include/*头文件啊*/ #include/*还是头文件*/ typedefstructLinkNode {longintdata; structLinkNode*next; }LinkNode,*Linklist;/*定义了一个结构体，LNODE，和结构体指针*/ LinkNode*create_head()/*建立头结点*/ {LinkNode*p; p=(Linklist)malloc(sizeof(LinkNode));/*新的结点空间*/ p->next=NULL; return(p); } intexchange(LinkNode*head,inti,intj)/*建立交换函数*/ {intdata; 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; return1; }elsereturn0; } main()/*主函数*/ {inti,j; chara,b; intn,m,x,ii,bb; LinkNode*head,*p; a=240; b=0; head=create_head(); printf("nn"); ……省略主界面部分…… printf("nPLEASECHOOSETHENUM:"); scanf("%d",&m); switch(m) { case1:printf("nINPUTTHENUMBEROFDATA: ");scanf("%d",&n);create_list(head,n);getch();break; case2:print(head);printf("n");getch();break; case3:insert_list(head);getch();break; case4:delete_list(head);getch();break; case5:printf("INPUTLOCATE:");scanf("%d",&i);printf("THE%dDATAIS AT%d",i,search(head,i)->data);printf("n");getch();break; case6:printf("LINKLISTLENGTH%d ",count(head));printf("n");getch();break; case7:order(head);print(head);printf("n");getch();break; case8:contray(head);printf("n");getch();break; case9:exit(0); }} getch(); }