单链表的基本操作

1、上机实验报告学院：廿算机与信息枝术学院专业：it算机科学与技术(U )课程名称：数扬给枸实验题目：单铢表建立及操作J9级序号：帅1 J9学号：1学生：邓雪荷导教则：红穎完成时同：2015年12月25号一、实豔目的：(1 )动态地建立单毎表；(2) 拿握线性表的基本操作：求长度、捕人、删除、査找在超直存储给构上的实现;(3) 熟悉单箍表的应用，明确单铢表和顺序表的不间。二、实验环境:Windows 8.1Microsoft Visual C+ 6.0三、实豔容及嬰求：建立单铢表，实现如下助能：1、建立单捷表并输岀（头捕法建立单址表）;2、帝表长;3、按位置查找4、按值査找结点;5、后捕结点；6、

2、前捕结点7、制除结点；四、RSSit：1、通过循坏，由赴盘输入一串数据。创理并初始化一个单缸表。2、编写实现柑关【力能因数，完成子函数模挟。3、燜用子函数，实现菜单凋用功能，完成服序表的松关棵作。五、代昭：#include<stdio.h> #include<stdlib.h> typedef char datatype; typedef struct nodedatatype data;struct node *next;Hinklist;linklist *headf*p;头描法建立单毎表linklist *Creatlistf()char ch;linklist

3、*head/s;head=NULL;ch=getchar();printfC1请输入噸序表元素(敛据以$结束):n");while(ch!=,$,)s=(linklist *)malloc(sizeof(linklist);s->data=ch;s->next=head;head=s;ch=getchar();return head;求单址表的长度void get_length(struct node *head)struct node *p=head->next;int length=O;while(p)length+;p=p->next;head->

4、data=length;printfCi 单魁表的长度为：%dnM,head->data);|按序号查找结点linklist *Get(linklist *headjnt i)intj;linklist *p;p=head;j=O; while(p->next!=NULL)&&(j<i) p=p->next; j+;if(i=j)return p;按值査找给点linklist *Locate(linklist * head,datatype key)int pos=0;p=head->next;printfCS找结点位置为：)； while(p!=

5、NULL)if(p->data!=key)Ip=p->next;pos+;elsepos+;break;return p;后捕结点void lnsertafter(linklist *p?datatype x)linklist *s;s=(Hnklist *)malloc(sizeof(linklist);s->data=x;s->next=p->next;p->next=s;printfC# 人应劝J;前插结点void lnsertbefore(linklist *p,datatype x) linklist *s;s=(linklist *)malloc

6、(sizeof(linklist);s->next=p->next;s->data = p->data;p->data=x;p->next=s;删除结目linklist *Deleteafter(linklist *head)inti;linklist *r,*p;printfC请输入要HI除的给点位置：)；scanfC%dM,&);if(i=1)r=head;head=head->next;elsep=Get(head,i-1-1);r=p->next; p->next=r->next;free(r);return head

7、;/松出单笊表void output(linklist *p)while(p->next!=NULL)printf("%c B,p->data);p=p->next;printfCW);void main()linklist *head;int kj,pos;char x;datatype key;printfC单 fil 表的 If 作W);printfCt1.头插法建立单竝表n); printfCt2.IS出单讎表W)； printfCt3.$ 单疑表的长 gnB);printf(-t4.g序号査找给点W);printf(*t5.按值査找结点n");p

8、rintf(弋6.后捕给点n);printfCt7前捕给点n);printfCt 8.制除接 W);printf(at9. jg 出诃)；doprintfC1选择所需助能:);scanfr%d；&k);switch(k)case 1:head=Creatlistf();break;case2:printf("$®表为:n*);output(head);break;case 3:getenoth(head);break;case 4:printfC请输人要査找的给点序号：“)； scanfC%dM,&);getchar();printfCS 点的值为:%cn&

9、quot;,Get(head,i-1 )->data); break;case 5:printf("博输人要査找的给点值:“)； scanfC%ch,&key);getchar();printf(B%dLocate(head,key);printfC-);break;case6:printf("输人要捕人的给点位置：”)；scanf(d；&pos);getchar();printfCiS H人捕人的结点值:")；scanf(c：&x);getchar();lnsertafter(Get(headtpos-1 ),x); printfC

10、'H 人应 IT)； break;case7:printfC#人要捕人的结点位置利结点值(前捕)(P,x)： °);case &scanfC%d,%c',&pos,&x);getchar();lnsertbefore(Get(head?pos-1 ),x); printfC# 人成 IT);break;head=Deleteafter(head);break;case 9:printf(H退出')；exit(O);default:printf(M# 入措娱W); exit(O);while ；As运行界面菜单单链表的竦作1 头插法建立单

11、链表2 输出单链表3求单链表的长庚 '按序号杳找结点5 按亘查找结点6 后插结点7前插結点8 删除接点a 3 114选择所需功能：七、实验中）8對的问題及总结二次输出捷表元索时址表的第一个结点会变成乱周字符。第一次输出没有錯误。颇序表和单毎表的区别：在服序表中，我01是用一组地址连续的存储卑元来依次存故线 性表的结点，因此结点的逻辑次序和掏卑次序一致。而征表则不然，飪表是用一组任恿的存 储单元来存故线性表的结点，这组存储单元册可£1是连续的，也可以是不连镇的，甚至是零 散分布在存中的任何位置上，因此，捷表中结点的SIUIT和物理次疥不一定松同。力了能 晞正确表示结点间的逻圳关系，在存储每个结点値得间时，if必须存储指示后進结目的地址 （或位置）信息，这个信息怖为常什或超。本次实验采用头捕法