顺序表的基本运算
[html]viewplaincopy
问题描述及代码：
[cpp]viewplaincopy
1./
2.烟台大学计控学院
3.作者：朱建豪
4.完成日期：2016年9月17日
5.问题描述：在数据结构的学习中，掌握基本运算是一个基础性的工作。这种“抽象”级别的成果，适用于各种应用场合，也是训练计算思维的根本依托之一。
6.（1）初始化线性表InitList(&L)：构造一个空的线性表L
7.（2）销毁线性表DestroyList(&L)：释放线性表L占用的内存空间
8.（3）判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假
9.（4）求线性表的长度ListLength(L)：返回L中元素个数
10.（5）输出线性表DispList(L):当线性表L不为空时，顺序显示L中各节点的值域
11.（6）求线性表L中指定位置的某个数据元素GetElem(L,i,&e)：用e返回L中第i个元素的值
12.（7）查找元素LocateElem(L,e)：返回线性表L中第1个与e相等的序号，找不到返回0
13.（8）插入元素ListInsert(&L,i,&e)：在线性表L中的第i个位置插入元素e；
14.（9）删除元素ListDelete(&L,i,&e)：在线性表L中删除第i个元素，有e返回删除的值；
15./
（1）目的是要测试“建立线性表”的算法CreateList，为查看建表的结果，需要实现“输出线性表”的算法DispList。在研习DispList中发现，要输出线性表，还要判断表是否为空，这样，实现判断线性表是否为空的算法ListEmpty成为必要。这样，再加上main函数，这个程序由4个函数构成。main函数用于写测试相关的代码。
[cpp]viewplaincopy
1.#include
2.#include
3.#defineMaxsize50
4.typedefintElemType;
5.typedefstruct
6.{
7.ElemTypedata[Maxsize];
8.intlength;
9.}SqList;
10.//自定义函数声明部分
11.voidCreatList(SqList&L,ElemTypea[],intn);//用数组创建线性表
12.voidDispList(SqListL);//输出线性表DisList(L)
13.boolListEmpty(SqListL);//判断是否为空表ListEmpty(L)
14.//实现测试函数
15.intmain()
16.{
17.SqListsq;
18.ElemTypex[6]={5,8,7,2,4,9};
19.CreatList(sq,x,6);
20.DispList(sq);
21.return0;
22.}
23.//实现自定义函数
24.voidCreatList(SqList&L,ElemTypea[],intn)//用数组创建线性表
25.{
26.inti;
27.L=(SqList)malloc(sizeof(SqList));
28.for(i=0;i
29.L->data[i]=a[i];
30.L->length=n;
31.}
32.voidDispList(SqListL)//输出线性表DisList(L)
33.{
34.inti;
35.for(i=0;ilength;i++)
36.printf("%d",L->data[i]);
37.printf("\n");
38.}
39.boolListEmpty(SqListL)//判断是否为空表ListEmpty(L)
40.{
41.return(L->length==0);
42.}
运行结果：
（2）在已经创建线性表的基础上，求线性表的长度ListLength、求线性表L中指定位置的某个数据元素GetElem、查找元素LocateElem的算法都可以实现了。就在原程序的基础上增加：
增加求线性表的长度ListLength的函数并测试；?
增加求线性表L中指定位置的某个数据元素GetElem的函数并测试；?
增加查找元素LocateElem的函数并测试?
1.head.h的代码
[cpp]viewplaincopy
1.#include
2.#include
3.#defineMaxsize50
4.typedefintElemType;
5.typedefstruct
6.{
7.ElemTypedata[Maxsize];
8.intlength;
9.}SqList;
10.//自定义函数声明部分
11.voidCreatList(SqList&L,ElemTypea[],intn);//用数组创建线性表
12.voidDispList(SqListL);//输出线性表DisList(L)
13.boolListEmpty(SqListL);//判断是否为空表ListEmpty(L)
14.intListLength(SqListL);//求线性表的长度ListLength(L)
15.boolGetElem(SqListL,inti,ElemType&e);//求某个数据元素值GetElem(L,i,e)
16.intLocateElem(SqListL,ElemTypee);//按元素值查找LocateElem(L,e)
2.main.cpp中的代码
[cpp]viewplaincopy
1.#include"head.h"
2.//实现测试函数
3.intmain()
4.{
5.SqListsq;
6.ElemTypex[6]={5,8,7,2,4,9};
7.CreatList(sq,x,6);
8.DispList(sq);
9.ElemTypea;
10.intloc;
11.
12.printf("表长度：%d\n",ListLength(sq));//测试求长度
13.
14.if(GetElem(sq,3,a))//测试在范围内的情形
15.printf("找到了第3个元素值为：%d\n",a);
16.else
17.printf("第3个元素超出范围！\n");
18.
19.if(GetElem(sq,15,a))//测试不在范围内的情形
20.printf("找到了第15个元素值为：%d\n",a);
21.else
22.printf("第15个元素超出范围！\n");
23.
24.if((loc=LocateElem(sq,8))>0)//测试能找到的情形
25.printf("找到了，值为8的元素是第%d个\n",loc);
26.else
27.printf("值为8的元素木有找到！\n");
28.
29.if((loc=LocateElem(sq,17))>0)//测试不能找到的情形
30.printf("找到了，值为17的元素是第%d个\n",loc);
31.else
32.printf("值为17的元素木有找到！\n");
33.
34.return0;
35.
36.}
3.创建线性表的基础代码
[cpp]viewplaincopy
1.//自定义函数声明部分
2.voidCreatList(SqList&L,ElemTypea[],intn);//用数组创建线性表
3.voidDispList(SqListL);//输出线性表DisList(L)
4.boolListEmpty(SqListL);//判断是否为空表ListEmpty(L)
5.
6.//实现自定义函数
7.voidCreatList(SqList&L,ElemTypea[],intn)//用数组创建线性表
8.{
9.inti;
10.L=(SqList)malloc(sizeof(SqList));
11.for(i=0;i
12.L->data[i]=a[i];
13.L->length=n;
14.}
15.voidDispList(SqListL)//输出线性表DisList(L)
16.{
17.inti;
18.for(i=0;ilength;i++)
19.printf("%d",L->data[i]);
20.printf("\n");
21.}
22.boolListEmpty(SqListL)//判断是否为空表ListEmpty(L)
23.{
24.return(L->length==0);
25.}
26.
27.
4.查找，求长度等的代码
[cpp]viewplaincopy
1.#include"head.h"
2.//实现测试函数
3.intListLength(SqListL)//求线性表的长度ListLength(L)
4.{
5.return(L->length);
6.}
7.boolGetElem(SqListL,inti,ElemType&e)//求某个数据元素值GetElem(L,i,e)
8.{
9.if(i<1||i>L->length)
10.returnfalse;
11.e=L->data[i-1];
12.returntrue;
13.}
14.intLocateElem(SqListL,ElemTypee)//按元素值查找LocateElem(L,e)
15.{
16.inti=0;
17.while(ilength&&L->data[i]!=e)
18.i++;
19.if(i>=L->length)
20.return0;
21.else
22.returni+1;
23.}
运行结果：
[html]viewplaincopy
（3）其余的4个基本运算：插入数据元素ListInsert、删除数据元素ListDelete、初始化线性表InitList、销毁线性表DestroyList都可以同法完成。
1.初始化及插入的代码
[cpp]viewplaincopy
1.#include
2.#include
3.#defineMaxsize50
4.typedefintElemType;
5.typedefstruct
6.{
7.ElemTypedata[Maxsize];
8.intlength;
9.}SqList;
10.//自定义函数声明部分
11.voidCreatList(SqList&L,ElemTypea[],intn);//用数组创建线性表
12.voidDispList(SqListL);//输出线性表DisList(L)
13.boolListEmpty(SqListL);//判断是否为空表ListEmpty(L)
14.voidInitList(SqList&L);//初始化线性表
15.boolListInsert(SqList&L,inti,ElemTypee);//插入数据元素
16.voidCreatList(SqList&L,ElemTypea[],intn)//用数组创建线性表
17.{
18.inti;
19.L=(SqList)malloc(sizeof(SqList));
20.for(i=0;i
21.L->data[i]=a[i];
22.L->length=n;
23.}
24.voidDispList(SqListL)//输出线性表DisList(L)
25.{
26.inti;
27.for(i=0;ilength;i++)
28.printf("%d",L->data[i]);
29.printf("\n");
30.}
31.boolListEmpty(SqListL)//判断是否为空表ListEmpty(L)
32.{
33.return(L->length==0);
34.}
35.
36.voidInitList(SqList&L)//初始化线性表
37.{
38.L=(SqList)malloc(sizeof(SqList));
39.L->length=0;
40.}
41.boolListInsert(SqList&L,inti,ElemTypee)//插入数据元素
42.{
43.intj;
44.if(i<1||i>L->length+1)
45.returnfalse;
46.i--;
47.for(j=L->length;j>i;j--)
48.L->data[j]=L->data[j-1];
49.L->data[i]=e;
50.L->length++;
51.returntrue;
52.}
53.intmain()
54.{
55.SqListsq;
56.InitList(sq);
57.ListInsert(sq,1,5);
58.ListInsert(sq,2,3);
59.ListInsert(sq,1,4);
60.DispList(sq);
61.return0;
62.}
运行结果：
[html]viewplaincopy
[html]viewplaincopy
2.删除及销毁的代码
[cpp]viewplaincopy
1.#include
2.#include
3.#defineMaxsize50
4.typedefintElemType;
5.typedefstruct
6.{
7.ElemTypedata[Maxsize];
8.intlength;
9.}SqList;
10.//自定义函数声明部分
11.voidCreatList(SqList&L,ElemTypea[],intn);//用数组创建线性表
12.voidDispList(SqListL);//输出线性表DisList(L)
13.boolListEmpty(SqListL);//判断是否为空表ListEmpty(L)
14.voidInitList(SqList&L);//初始化线性表
15.boolListInsert(SqList&L,inti,ElemTypee);//插入数据元素
16.boolListDelete(SqList&L,inti,ElemType&e);//删除数据元素
17.voidDestroyList(SqList&L);//销毁线性表
18.voidCreatList(SqList&L,ElemTypea[],intn)//用数组创建线性表
19.{
20.inti;
21.L=(SqList)malloc(sizeof(SqList));
22.for(i=0;i
23.L->data[i]=a[i];
24.L->length=n;
25.}
26.voidDispList(SqListL)//输出线性表DisList(L)
27.{
28.inti;
29.for(i=0;ilength;i++)
30.printf("%d",L->data[i]);
31.printf("\n");
32.}
33.boolListEmpty(SqListL)//判断是否为空表ListEmpty(L)
34.{
35.return(L->length==0);
36.}
37.
38.voidInitList(SqList&L)//初始化线性表
39.{
40.L=(SqList)malloc(sizeof(SqList));
41.L->length=0;
42.}
43.boolListInsert(SqList&L,inti,ElemTypee)//插入数据元素
44.{
45.intj;
46.if(i<1||i>L->length+1)
47.returnfalse;
48.i--;
49.for(j=L->length;j>i;j--)
50.L->data[j]=L->data[j-1];
51.L->data[i]=e;
52.L->length++;
53.returntrue;
54.}
55.boolListDelete(SqList&L,inti,ElemTypee)//删除数据元素
56.{
57.intj;
58.if(i<1||i>L->length-1)
59.returnfalse;
60.i--;
61.e=L->data[i];
62.for(j=i;jlength-1;j++)
63.L->data[j]=L->data[j+1];
64.L->length--;
65.returntrue;
66.}
67.voidDestroyList(SqList&L)
68.{
69.free(L);
70.}
71.intmain()
72.{
73.SqListsq;
74.InitList(sq);
75.ListInsert(sq,1,5);
76.ListInsert(sq,2,3);
77.ListInsert(sq,1,4);
78.printf("插入后的：\n");
79.DispList(sq);
80.ListDelete(sq,1,5);
81.ListDelete(sq,2,3);
82.printf("删除后的：\n");
83.DispList(sq);
84.
85.DestroyList(sq);
86.printf("销毁后的：\n");
87.DispList(sq);
88.return0;
89.
90.}
运行结果：
[html]viewplaincopy
知识点总结：
实现线性表的基本运算：（1）初始化线性表InitList(&L)：构造一个空的线性表L（2）销毁线性表DestroyList(&L)：释放线性表L占用的内存空间（3）判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假（4）求线性表的长度ListLength(L)：返回L中元素个数（5）输出线性表DispList(L):当线性表L不为空时，顺序显示L中各节点的值域（6）求线性表L中指定位置的某个数据元素GetElem(L,i,&e)：用e返回L中第i个元素的值（7）查找元素LocateElem(L,e)：返回线性表L中第1个与e相等的序号，找不到返回0。（8）插入数据元素ListInsert(SqList&L,inti,ElemTypee)：在L的第i个元素之前插入新的元素e，L的长度增加1；（9）删除数据元素ListDele（&L，i，&e）：删除L的第i个数据元素，并用e返回其值，L的长度减1；（10）销毁线性表DestroyList(SqList&L)：释放线性表L占用的内存空间；
学习心得：
这是个庞大的工程啊，我刚开始使用的程序的多文件组织来写的，可是因为好几个主函数不能通用，最后就又建了个工程来写，我还是喜欢自己敲代码的过程，虽然很慢很累，但是我可以在敲代码的过程中真正理解了这个算法。今天的收获很大！
|
|
