单链表的基本操作

单链表的基本操作

1.实验目的：

(1)掌握使用C集成环境调试单链表的基本方法；

(2)单链表的基本操作：插入、删除、查找等运算，

2.仪器和软件环境：

安装C/C++集成环境的计算机。

3.问题描述和要求：

(1)问题描述：

输入一组整型数(以/结束输入)，建立单链表，并对其进行查找，插入,

删除等基本操作。

(2)要求:

①定义问题的单链表

一个数据域、一个指针域。结构体

②建立单链表(输入数据以T结束输入)

头插法(头结点的后面插入)

尾插法(刚插入，最后一节点)

③求单链表长度

设置一个遍历指针，开始指向第一个节点

计数器

判断到尾？

④查找第i个结点，求其数据域

⑤在第i个位置插入元素e

©删除第i个结点，并释放空间

⑦以上个操作后，要输出单链表，以便比较.

设置一个遍历指针，开始指向第一个节点

输出语句

判断到尾？

⑧写出主函数，完成以上操作

4.实验步骤和代码：

#include<s(dio.h>

#include<malloc.h>

typedefstructnode{

intdata;

structnode*ncxt;

}NODE;

/*建立单链表*/

NODE"Create。{

NODE*p,*head;

intx;

heiid=(NODE*)malloc(sizeof(NODE));

head->nexl=NULL:

prinlfC'Inpuldata,/toEnd!\n");

scanf("%d".&x);

whilc(x!="1){

p=(NODE*)malloc(sizcof(NODE));

p->da(a=x;

p->next=head->next;

head->next=p;

scanf("%d",&x);

)

return(head);

}

思考：如何该单链表逆置？

voidrcverse(NODE*L)

(

p=L->next;

L->ncxt=NULL;

while(p)

{

q=p->ncxt;

p->next=L->next;

L->next=p;

p二q：

/*输出单链表*/

voidOutput(NODE*head){

NODE*p;

p=hcad;

printf("Bcgintodump(heNcxlLisi..An");

while(p->ncx(!=NULL){

printf("->%d",p->next->data);

p=p->next;

printf("\nTheNextListended!\n");

产单链表求长度*/

intListlen(NODE*head){

inti=0;

NODE*p=head;

while(p->ncxt!=NULLj{

i十十；if(p->ncxi->da(a==x)i十十

p=p->ncx(;

}

return(i);

]

思考：求值为x的结点？如何改动？

/*查找第i个结点*/

intGet(NODE*head,inti)|

intj=O;

NODE*p=head;

while(p->next&&j<i){

j++；

p=p->next;

)

if(!p->ncxt||j>i)rcium(O);

elsercturn(p->data):

}

产在第i个位置插入元素e*/

voidIns(NODE*head,inti,inte){

NODE*p=head,*q;

intj=O;

while(p->next<&&j<i-l){

j++；

p=p->next;

)

if(!p->next&&j>i-l)printf("Wrongposilion\n");

clse{

q=(NODE*)malloc(sizeof(NODE));

q->da(a=e;

q->next=p->next;

p->next=q;

)

)

思考：在单链表的表尾插入某结点s

voidinsert(NODE*L,intx)

(

p=L;

whilc(p->ncxt)

p=p->next;

s=(NextList)malloc(sizeof(Node));

s->ncxt=NULL;

p->next=s;

)

/*删除第i个结点*/

voidDcRNODE*head,int:){

NODE*p=hcad;

in(j=0:

while(p->next&&j<i-1){

j++；

p=p->next;

)

if(!p->next||j>i-l)printf("thepositioniswrong\n");

else

p->next=p->next->next;思考：释放节点如何修改？

)

/*主函数*/

main(){

NODE*head;

intlength:

inti,clcmcnt;

hcad=Crcate();

Output(head);

length=IJstleiVhead):

printf("thelengthofthenextis%d\n”,length);

printf("inputtheorder:\n");

scanf("%d",&i);

element=Get(head,i);

printf("theelementoftheorderis%d\n",element);

printf("Inputtheinsertposionandelement:\n");

scanf("%d%d",&i,&