数据结构-实验2-链表的基本操作

实验2链表的基本操作一、需求分析1，初始化链表2，调用插入函数建立一个链表3，链表的插入和删除4，链表元素的查找4，将链表分为奇链表和偶链表5，链表的逆置二、概要设计1.基础题1)编写链表基本操作函数typedefstructlist{Intdata;Structlist*next}LIST;LIST*InitList()//初始化LIST*InsertList(LIST*L,intitem,intre)//向链表指定位置插入元素LIST*InsertOrderList(LIST*L,intitem)//向有序链表指定位置插入元素voidFindList(LIST*L,intitem)//查找链表中的元素voiddisplay(LIST*L)//显示链表voiddivide(LIST*La,LIST*Lb)//拆分链表LIST*turn(LIST*L)//转置链表2)调用上述函数实现下列操作，操作步骤如下。A.初始化链表B.调用插入函数建立一个链表C.在链表中寻找指定的元素D.在链表中删除指定值的元素E.遍历并输出链表注意每完成一个步骤，必须及时输出顺序表元素，便于观察操作结果2.提高题a)将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a，b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。解题思路将单链表A中含有序号为偶数的元素删除，并在删除时把这些结点链接起来构成单链表B即可。b)将链接存储线性表逆置，即最后一个结点变成第一个结点原来倒数第二个结点变成第二个结点，如此等等。解题思路依次遍历源链表，将每个元素依次赋给一个新链表并将新链表从后到前连接。3.主函数voidmain(){LIST*L1,*L2,*L3;inti;L1=InitList();printf(创建链表L1:\n);for(i=1;i=5;i++){L1=InsertList(L1,i*2,i);}display(L1);for(i=1;i=9;i+=4){printf(在L1的%d位置插入3:\n,i);L1=InsertList(L1,3,i);display(L1);}//有序表L2=InitList();printf(\n有序表实验:\n);printf(创建链表L2:\n);for(i=1;i=5;i++){L2=InsertList(L2,i*2,i);}display(L2);for(i=1;i=13;i+=6){printf(插入%d:\n,i);L2=InsertOrderList(L2,i);display(L2);}//删除元素实验printf(\n删除元素实验:\n);printf(L2插入1:\n,i);L2=InsertList(L2,1,1);display(L2);for(i=1;i12;i+=5){printf(删除L2中%d\n,i);L2=DeleteList(L2,i);display(L2);}//查找printf(\n查找元素实验:\n);printf(查找L2中%d\n,13);FindList(L2,13);printf(查找L2中%d\n,6);FindList(L2,6);//分解printf(\n分解实验:\n);printf(L2:\n);display(L2);L3=InitList();printf(将L2偶序数拆分到L3\n);divide(L2,L3);printf(L2:\n);display(L2);printf(L3:\n);display(L3);printf(\n逆序实验:\n);printf(L2:\n);display(L2);L2=turn(L2);printf(转置L2:\n);display(L2);}三、详细分析插入实验，函数能够在链表前、中、后插入元素，并判断插入位置是否超过链表长度，若超过则接入链尾。有序表插入实验，函数能够在链表前、中、后插入元素，并判断插入位置是否超过链表长度，若超过则接入链尾。删除实验，对于指定元素，能将多个符合的数值都删除，若找不到元素，则输出“找不到”。查找实验，查找指定元素，并输出位置，若找不到元素，则输出“找不到”。四、调试分析整个过程最低时间复杂度为⊙(1)，最高⊙(n)，因此时间复杂度为⊙(n)。五、调试与结果测试