1、数据结构实验1线性表的基本操作实验1线性表的基本操作一、 需求分析目的:掌握线性表运算与存储概念,并对线性表进行基本操作。1.初始化线性表;2.向链表中特定位置插入数据;3.删除链表中特定的数据;4.查找链表中的内容;5.销毁单链表释放空间;二、概要设计 基础题主要函数:初始化线性表InitList(List* L,int ms)向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录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中,否则将L 1,L2元素按顺序放进L。 本程序主
3、要包含7个函数主函数main()初始化线性表InitList(List* L,int ms)向顺序表指定位置插入元素InsertList(List* L,int item,int rc)删除指定元素值的顺序表记录DeleteList1(List* L,int item)删除指定位置的顺序表记录 DeleteList2(List* L,int rc)查找顺序表中的元素 FindList(List L,int item)输出顺序表元素OutputList(List L)提高题的程序void Combine(List* L1,List* L2,List* L)void DeleteList3(Lis
4、t* L,int x,int y)二、 详细设计初始化线性表InitList(List* L,int ms)void InitList(List* L,int ms)L-list=(int*)malloc(LIST_INIT_SIZE*sizeof(int);L-size=0;L-MAXSIZE=LIST_INIT_SIZE;向顺序表指定位置插入元素InsertList(List* L,int item,int rc)void InsertList(List* L,int item,int rc)int i;if (L-size=L-MAXSIZE)L-list=(int*)realloc(L
5、-list,(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,int item)void DeleteList1(List* L,int item)int i,j;for (i=0;isize;i+)if (L-listi=item)break;for (j=i;jsize;j+)L-listj=L-listj+1;L-size-;删除指定位置的顺序表
6、记录 DeleteList2(List* L,int rc)void DeleteList2(List* L,int rc)int i;for (i=rc-1;isize;i+)L-listi=L-listi+1;L-size-;查找顺序表中的元素void FindList(List* L,int item)int i;for (i=0;isize;i+)if (L-listi=item)break;if (L-size=i)printf(找不到n);elseprintf(第%d个元素为%dn,i+1,item);输出顺序表元素OutputList(List L)void OutputList
7、(List* L)int i;for (i=0;isize;i+)printf(%d ,L-listi);printf(n);删除x到y之间的所有元素void DeleteList3(List* L,int x,int y)int i,j,temp;if (xy)temp=x;x=y;y=temp;for (i=0,j=0;isize;i+)if (L-listilistiy)L-listj=L-listi;j+;L-size=j;将两个有序的线性表进行合并void Combine(List* L1,List* L2,List* L)int i,j,k,temp;if (L1-sizeL2-s
8、ize)temp=L2-size;elsetemp=L1-size;i=0,j=0,k=0;while(1)if (i=L1-size | j=L2-size)break;if (L1-listilistj)L-listk=L1-listi;k+;i+;else if (L1-listiL2-listj)L-listk=L2-listj;k+;j+;elseL-listk=L2-listj;k+;j+;i+;if (i=L1-size)for (i=j;isize;i+,k+)L-listk=L2-listi;elsefor (j=i;jsize;j+,k+)L-listk=L1-listj;
9、L-size=k;三、 调试分析体会:线性表内数据都是顺序排放所以实验中比较容易写出程序时间复杂度:初始化线性表InitList(List* L,int ms) (1)向顺序表指定位置插入元素InsertList(List* L,int item,int rc) (n)删除指定元素值的顺序表记录DeleteList1(List* L,int item) (n)删除指定位置的顺序表记录 DeleteList2(List* L,int rc)(n)查找顺序表中的元素 FindList(List L,int item)(n)输出顺序表元素OutputList(List L)(n)删除x到y之间的所有元素 (n)将两个有序的线性表进行合并 (n)四、 调试与结果测试继续阅读