线性表是最基础最常用的一种线性结构,同时也是其它数据结构的基础。因此,为了打好基础,学习本章的时候应明确相关概念,以免混淆。
1.定义:由 n(n>=0)个数据特性相同的元素构成的有限序列被称为线性表。
2.特点:
1.集合中必存在唯一的一个"第一元素"。
2.集合中必存在唯一的一个 “最后元素” 。
3.除最后一个元素之外,均有 唯一的后继(后件)。
4.除第一个元素之外,均有 唯一的前驱(前件)。
总结:除了线性表所拥有的唯一的第一元素及最后元素,剩下元素均拥有唯一的前驱及后继。
线性表主要由顺序表示或链式表示。
顺序表示 的特点:逻辑关系相邻的元素在物理位置上也相邻。查找元素快。
链式表示 的特点:相比于顺序表示,链式表示不要求物理位置。插入和删除操作时,只需修改结点的下一个元素指针,但查找元素时效率不如顺序存储。好操作
节点由两部分组成:1.数据域 2.指针域
数据域用来存储数据,指针域用来存储下一个结点的地址。
1.创建链表
typedef struct { ElemType data[10]; /* 数组,存储数据元素 */ int length; /* 线性表当前长度 */ }SqList;
2.初始化链表
Status InitList(SqList *L) { L->length=0; return OK; }
3.创建结点
Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==10) /* 顺序线性表已经满 */ return ERROR; if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */ return ERROR; if (i<=L->length) /* 若插入数据位置不在表尾 */ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */ L->data[k+1]=L->data[k]; } L->data[i-1]=e; /* 将新元素插入 */ L->length++; return OK; }
4.删除结点
Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) /* 顺序线性表已经满 */ return ERROR; if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */ return ERROR; if (i<=L->length) /* 若插入数据位置不在表尾 */ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */ L->data[k+1]=L->data[k]; } L->data[i-1]=e; /* 将新元素插入 */ L->length++; return OK; }
5.查找
int LocateElem(SqList L,ElemType e) { int i; if (L.length==0) return 0; for(i=0;i<L.length;i++) { if (L.data[i]==e) break; } if(i>=L.length) return 0; return i+1; }