实验项目：单链表的操作一、实验目的（1）了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；（2）掌握线性表的基
本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。二、实验内容1.
实验需求输入格式：整型输出值的范围：整型（2）输出的形式：单链表（3）程序所能到达的功能：实现一个单链表的插入，删除，查找，建立（
4）测试数据：数字2.数据结构定义确定数据对象及结构单链表：1，2，3，4，5，6，7，8，9，10存储结构的选择和定义链式存
储结构typedefintDataType;/定义DataType为int/typedefstruct
Node{DataTypedata;structNodenext;}SLNode;3.主程序的流程及各程序的关系v
oidListInitiate(SLNodehead)/初始化/intListLength(SLNodehea
d)/单链表的长度/intListInsert(SLNodehead,inti,DataTypex)/
在带头结点的单链表的数据元素ai（0≤i≤size）前插入一个存放数据元素x的结点/intListDelete(S
LNodehead,inti,DataTypex)/删除带头结点的单链表head的数据元素ai（0≤i
≤size-1）结点//删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0/intListGet(
SLNodehead,inti,DataTypex)voidDestroy(SLNodehead)三、程序实
现#include/该文件包含pringtf()等函数/#include/
该文件包含exit()等函数/#include/该文件包含malloc()等函数/t
ypedefintDataType;/定义DataType为int/typedefstructNode
{DataTypedata;structNodenext;}SLNode;voidListInitiate(SL
Nodehead)/初始化/{/如果有内存空间，申请头结点空间并使头指针head指向头结点/if((he
ad=(SLNode)malloc(sizeof(SLNode)))==NULL)exit(1);(head)->
next=NULL;/置链尾标记NULL/}intListLength(SLNodehead)/单链表的
长度/{SLNodep=head;/p指向首元结点/intsize=0;/size初始
为0/while(p->next!=NULL)/循环计数/{p=p->next;size++;}ret
urnsize;}intListInsert(SLNodehead,inti,DataTypex)/在带头结点
的单链表的数据元素ai（0≤i≤size）前插入一个存放数据元素x的结点/{SLNodep,q;intj;
p=head;/p指向首元结点/j=-1;/j初始为-1/while(p->next!=N
ULL&&jnext;j++;}i
f(j!=i-1){printf("插入位置参数错！");return0;}/生成新结点由指针q指示/if
((q=(SLNode)malloc(sizeof(SLNode)))==NULL)exit(1);q->data
=x;//此段程序有一处错误q->next=p->next;/给指针q->next赋值/p->next
=q;/给指针p->next重新赋值/return1;}intListDelete(SLNode
head,inti,DataTypex)/删除带头结点的单链表head的数据元素ai（0≤i≤size
-1）结点//删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0/{SLNodep,s;int
j;p=head;/p指向首元结点/j=-1;/j初始为-1/while(p->next!=
NULL&&p->next->next!=NULL&&j/{p=p->next;j++;}if(j!=i-1){printf("删除位置参数错！");retur
n0;}//此段程序有一处错误s=p->next;/指针s指向数据元素ai结点/x=p->dat
a;/把指针s所指结点的数据元素域值赋予x/p->next=s->next;/把数据元素ai结点从
单链表中删除指/free(s);/释放指针s所指结点的内存空间/return1;}intListGet(SL
Nodehead,inti,DataTypex)/取数据元素ai和删除函数类同，只是不删除数据元素ai结点
/{SLNodep;intj;p=head;j=-1;while(p->next!=NULL&&j<
i){p=p->next;j++;}if(j!=i){printf("取元素位置参数错！");return0;}/
/此段程序有一处错误x=p->data;return1;}voidDestroy(SLNodehead){SLN
odep,p1;p=head;while(p!=NULL){p1=p;p=p->next;free(
p1);}head=NULL;}intmain(){SLNodehead;inti,x;ListInitiat
e(&head);/初始化/for(i=0;i<10;i++){if(ListInsert(head,i
,i+1)==0)/插入10个数据元素/{printf("错误!\n");return0;}}i
f(ListDelete(head,4,&x)==0)/删除数据元素5/{printf("错误!\n");
return0;}for(i=0;ii,&x)==0)/取元素/{printf("错误!\n");return0;}elseprin
tf("%d",x);/显示数据元素/}Destroy(&head);}合并链表void?combine(S
LNode?head,?SLNode?two){?SLNode?p,?s,?H;??H?=?head;???p?=?he
ad;?s?=?two;while?(p->next!=?NULL)????{?p?=?p->next;???}?p->next=
s->next;while?(H->next!=?NULL)????{?H?=?H->next;?printf("%d?",?H-
>data);????}}四．调试分析voidListInitiate(SLNodehead)O（1）intListLe
ngth(SLNodehead)O（1）intListInsert(SLNodehead,inti,DataTyp
ex)O（n）intListDelete(SLNodehead,inti,DataTypex)O（n）intListGet(SLNodehead,inti,DataTypex)O(n)voidDestroy(SLNodehead)O(1)五．运行结果七．总结有的程序没用到，而且只有一次的改变，值都是固定的，伪代码的可用性差，占内存空间较大，应该充分利用。 |
|
