数据结构实验1线性表的基本操作

1、实验1线性表的基本操作需求分析目的：掌握线性表运算与存储概念，并对线性表进行基本操作。1 .初始化线性表；2 .向链表中特定位置插入数据；3 .删除链表中特定的数据；4 .查找链表中的内容；5 .销毁单链表释放空间；、概要设计基础题主要函数：初始化线性表 InitList (List* L , int ms ),int rc )向顺序表指定位置插入元素InsertList (List* L , int item 删除指定元素值的顺序表记录 DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2 (List* L,int rc 查找顺序表中的

2、元素 FindList (List L , int item ) 输出顺序表元素OutputList(List L )实验步骤：1,初始化顺序表2,调用插入函数3,在顺序表中查找指定的元素4,在顺序表中删除指定的元素5,在顺序表中删除指定位置的元素6,遍历并输出顺序表提高题要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素方法：按顺序取出元素并与x、y比较，若小于x且大于y,则存进新表中。编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。方法：分别按顺序取出L1,L2的元素并进行比较，若相等则将L1元素放进L中，否则将L1,L2元素按顺序放进L。本程序

3、主要包含7个函数主函数main()初始化线性表InitList(List*L,intms)向顺序表指定位置插入元素InsertList(List*L,intitem,intrc)删除指定元素值的顺序表记录DeleteList1(List*L,intitem)删除指定位置的顺序表记录DeleteList2(List*L,intrc)查找顺序表中的元素FindList(ListL,intitem)输出顺序表元素OutputList(ListL)提高题的程序voidCombine(List*L1,List*L2,List*L)voidDeleteList3(List*L,intx,inty)详细设计

4、初始化线性表InitList(List*L,intms)voidInitList(List*L,intms)L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int);L->size=0;L->MAXSIZE=LIST_INIT_SIZE;向顺序表指定位置插入元素InsertList(List*L,intitem,intrc)voidInsertList(List*L,intitem,intrc)inti;if(L->size>=L->MAXSIZE)L->list=(int*)realloc(L->list,

5、(L->MAXSIZE+LISTI)*sizeof(int);L->MAXSIZE+=LISTI;for(i=L->size-1;i>=rc-1;i-)L->listi+1=L->listi;L->listrc-1=item;L->size+;删除指定元素值的顺序表记录DeleteList1(List*L,intitem)voidDeleteList1(List*L,intitem)inti,j;for(i=0;i<L->size;i+)if(L->listi=item)break;for(j=i;j<L->size

6、;j+)L->listj=L->listj+1;L->size-;删除指定位置的顺序表记录DeleteList2(List*L,intrcvoidDeleteList2(List*L,intrc)inti;for(i=rc-1;i<L->size;i+)L->listi=L->listi+1;L->size-;查找顺序表中的元素voidFindList(List*L,intitem)inti;for(i=0;i<L->size;i+)if(L->listi=item)break;if(L->size=i)printf(&q

7、uot;找不到n");elseprintf("第於元素为%dn",i+1,item);输出顺序表元素OutputList(ListL)voidOutputList(List*L)inti;for(i=0;i<L->size;i+)printf("%d",L->listi);printf("n");删除x到y之间的所有元素voidDeleteList3(List*L,intx,inty)inti,j,temp;if(x>y)temp=x;x=y;y=temp;for(i=0,j=0;i<L->

8、;size;i+)if(L->listi<x|L->listi>y)L->listj=L->listi;j+；L->size=j;将两个有序的线性表进行合并voidCombine(List*L1,List*L2,List*L)inti,j,k,temp;if(L1->size>L2->size)temp=L2->size;elsetemp=L1->size;)i=0,j=0,k=0;while(1)(if(i=L1->size|j=L2->size)break;if(L1->listi<L2->

9、;listj)(L->listk=L1->listi;k+;i+;)elseif(L1->listi>L2->listj)(L->listk=L2->listj;k+;j+;)else(L->listk=L2->listj;k+;j+;i+;)if(i=L1->size)(for(i=j;i<L2->size;i+,k+)L->listk=L2->listi;elsefor(j=i;j<L1->size;j+,k+)L->listk=L1->listj;L->size=k;三、调试

10、分析体会：线性表内数据都是顺序排放所以实验中比较容易写出程序时间复杂度：初始化线性表InitList(List*L,intms)0(1)向顺序表指定位置插入元素InsertList(List*L,intitem,intrc)O(n)删除指定元素值的顺序表记录DeleteList1(List*L,intitem)O(n)删除指定位置的顺序表记录DeleteList2(List*L,intrc)O(n)查找顺序表中的元素FindList(ListL,intitem)O(n)输出顺序表元素OutputList(ListL)O(n)删除x到y之间的所有元素O(n)将两个有序的线性表进行合并O(n)四、调试与结果测试建立顺序表-3-2-