单链表的插入、删除、合并等基本操作 一、实验目的 1、理解数据结构中单链表的定义和建立。 2、掌握单链表中结点结构的C 语言描述。 3、熟练掌握单链表的插入、删除和修改等算法的设计与C 语言实现。 4、将理论与实际相结合,切实提高自己的逻辑能力和动手能力。 二、设计内容 1、输入单链表长度,创建一个单链表。 2、对建立好的单链表进行插入操作。 3、对建立好的单链表进行删除操作。 4、对建立好的单链表进行合并操作。 三、概要设计 抽象数据类型线性表的定义如下: ADTA List{ 数据对象:D={ai I ai∈ElemSet , i=1 ,2 , … , n n>=0 } 数据关系:R1={
I ai-1 , ai∈D , i=2 , … , n } 基本操作: Creates( &L ) 操作结果:构建一个空的线性表L。 Insertsl( &L , k ,i) 初始条件:线性表L 已存在。 操作结果:在带有头结点单链表的第 k 个元素之前插入元素 i。 Deletesl( &L , i, j ) 初始条件:线性表L 已存在。 操作结果:删除指定位置 j 元素 i。 Hebing( &L ) 初始条件:线性表L 已存在。 操作结果:清除新链表中相同的元素。 }ADT List 四、算法流程图 五、算法源代码 #include #include typedef struct node { int data; struct node *next; }node; node *head; int k; 开始 创建 插 入 删 除 合 并 主函数 输出 结束 node * creates() { node *p,*s,*h; int j=1,x, n; p=h=(node*)malloc(sizeof(node)); h->next=NULL; printf("请输入链表长度:"); scanf("%d",&n); printf("请输入 %d 个数字创建链表:",n); while(j<=n) { scanf("%d",&x); s=(node*)malloc(sizeof(node)); s->data=x; p->next=s; p=s; j++; } p->next=NULL; return h; } void insertsl(node *head, int k, int i) { /*在带有头结点单链表的第 k 个元素之前插入元素 i*/ int j; node *p, *t; p=head; j=0; while ( p&&jnext; j++; } if (!p||j>k-1) /*k 小于1 或大于表长*/ printf("插入位置不对。\n"); t=(node *)malloc (sizeof (node)); /*生成新结点*/ t->data=i; t->next=p->next; /*插入新结点*/ p->next=t; } /*insertsl*/ void deletesl(node *h,in...