本文共 3098 字,大约阅读时间需要 10 分钟。
线性表(List):零个或多个数据元素的有限序列
学号 | 姓名 | 性别 | 出生年月 |
---|---|---|---|
1 | 张三 | 男 | 19970101 |
2 | 李四 | 男 | 19970102 |
3 | 王五 | 女 | 19970103 |
用一段地址连续的存储单元一次存储线性表的数据元素。
优点 | 缺点 |
---|---|
无须为表示元素之间的逻辑关系而增加额外的存储空间 | 插入、删除需要移动大量元素; 当线性表长度变化较大时,难以确定存储空间的容量 |
可以快速地存取表中任一位置的元素 | 造成存储空间碎片 |
ADT 线性表(list)DataOperation InitList(*L); 初始化操作,建立一个空的线性表L。 ListEmpty(L); 判断线性表是否为空,为空返回true,反之返回false。 ClearLIst(*L); 清空线性表中所有元素。 GetElem(L,i,*e); 得到线性表中第i位置的元素返回给e。 LocateElem(L,e); 判断线性表中是否存在对应元素,查找成功返回对应序号,反之返回失败。 ListInsert(*L,i,e); 在线性表第i个位置插入元素,并用e返回值。 ListDelete(*L,i,*e); 删除第i个位置的元素,并用e返回其值。 ListLength(L); 返回线性表元素个数。
在本书中,线性表元素从1开始,数组从0开始;因此,下图需要好好理解,尤其是在插入、删除操作时,很有必要搞清楚循环的初值和条件。
#include#define OK 1#define ERROR 0#define MAXSIZE 20typedef int status; // Status是函数的类型,其值是函数结果状态代码,如OK等typedef int elemtype; //定义线性表元素的数据类型,便于后期修改操作typedef struct{ elemtype data[MAXSIZE]; //开辟一段空间(占座) int length; //当前线性表的长度,在初始化函数中确定大小}Sqlist;//初始化线性表,建立一个空的线性表status InitList(Sqlist *L) { L->length = 0; return OK;}status ListEmpty(Sqlist L){ if (L.length == 0) return true; else return false;}status ClearList(Sqlist *L){ L->length = 0; return OK;}/*得到线性表中第i个元素并通过e返回,这里是传入一个地址进去接收得到的值。注意事项:1.若线性表为空,返回error2.若i不在当前线性表长度范围内,返回error3.在范围内时,注意线性表的元素位置,与数组位置的差值*/status GetElem(Sqlist L, int i, int *e){ if (L.length == 0||i<1||i>L.length) { return ERROR; } //这一步可以省略下面的if语句,因为if语句顺序执行到这里,只有(<=)这种情况未考虑 //if (i <= L.length) //{ *e = L.data[i - 1]; //} return OK;}//查找线性表内是否存在对应元素status LocateElem(Sqlist L,int e){ if (L.length == 0) return ERROR; //注意这里的循环条件 for (int i = 0; i < L.length; i++) { if (L.data[i] == e) return i; } return ERROR;}/*插入元素条件:1.已达到最大容量的线性表不可插入2.插入的位置不合理也不可插入注意:数组与线性表之间下标的关系插入元素后,线性表长度发生变化,记得+1*/status ListInsert(Sqlist *L, int i,int e){ int k; if (L->length == MAXSIZE || i<1 || i>MAXSIZE) return ERROR; if (i >= 1 && i <= L->length) { for (k = L->length; k >= i; k--) { L->data[k] = L->data[k - 1]; } } //如果线性表没有满,且插入元素位置在当前长度与最大容量之间,可直接插入 L->data[i-1] = e; L->length++; return OK;}/*删除元素并通过地址返回被删除元素的值条件:1、表是否为空,是否在线性表中删除元素后,长度-1*/status ListDelete(Sqlist *L, int i, int *e){ if (L->length == 0||i<1||i>L->length) return ERROR; //注意这里的循环次数 for (int k = i-1; k < L->length-1; k++) { L->data[k] = L->data[k + 1]; } L->length--; return OK;}status ListLength(Sqlist L){ return L.length;}/*求并集:将所有在线性表Lb中但不在La中的元素插入到La中*/void UnionList(Sqlist *La,Sqlist Lb){ int La_len, Lb_len; La_len = ListLength(*La); Lb_len = ListLength(Lb); for (int i = 1; i <= Lb_len; i++) { int e; GetElem(Lb, i, &e); if (!LocateElem(*La, e)) { ListInsert(La,++La_len,e); } }}/*当然上面的初始化线性表操作时,可以直接附初值。我在调试的时候,存在的问题:1、判断语句中,“==”与赋值号书写错误2、循环时,初始条件和判断条件的设置,+-1,相差很大。*/
就先写到这里吧,后面想到要补充得,再回头来改呗!
转载地址:http://tpxtf.baihongyu.com/