路线图:由零个或多个数据元素组成的有限序列
线性表有两种物理存储结构:顺序存储结构和链存储结构
顺序存储器结构顺序存储器结构是将逻辑上相邻的节点物理上存储在相邻的存储器单元中的一种存储器结构类型,节点之间的逻辑关系通过存储器单元的相邻关系来表示。
插入算法的思路:
1、插入位置不合适时,抛出异常
2、线性表长度大于或等于数组长度时,抛出异常或动态增加数组容量
3、从最后一个要素前进到第I个位置,分别向后移动一个
4、在位置I填写要插入的要素
5、线形表长1
实现代码如下所示
statuslistinsert(sqlist*L,int i,ElemType e ) { int k; if(L-Length==maxsize ) /线性表已满({ return ERROR; (if ) I1|||il-Length1)/I超出范围时) { return ERROR; }if(I=L-Length ) /如果插入数据的位置不在表的末尾(/*在插入数据的位置之后)/for ) k=L-Length-1; k=i-1; k--}{l-data[k1]=l-data[k]; } L-data[i-1]=e; //在L-length中插入新元素; 返回确定; }} 删除算法的思路
1、删除位置不合理时,抛出异常
2、取出删除元素
3、从删除要素的位置开始扫描到最后一个要素的位置,分别移动到前一个位置
4、表长-1
实现代码如下所示
statuslistdelete(SQList*L,int i,ElemType *e ) int i; if(L-Length==0)//确定表的长度是否为空({ return ERROR; (if ) I1|||il-Length )/I超出范围时) { return ERROR; } *e=L-data[i-1]; 如果返回//e中删除的值if(IL-Length )/*,则删除位置后面的所有元素都将向前移动()/for ) k=I; k L-length; k({L-data[K-1]=L-data[K] ); (L-Length----); 返回确定; }线性表的依次存储结构在存储、读出数据时,无论在哪个位置时间复杂度都为o(1)。 对于插入或删除,时间复杂度均为o(n )。
二、连锁记忆结构又称连锁记忆结构、连锁记忆结构。 计算机在任何一组存储单元中存储线性表的数据元素。 这个集合可以是连续的也可以是不连续的。 逻辑上相邻的元素在物理上也不必相邻
单链表存储结构
用结构指针说明单链表
typedef struct Node { ElemType data; //数据域struct Node* Next //指针域} Node; typedef struct node *链接列表;获得链表第i个数据的算法思路
1、一个节点p指向链表中的第一个节点,声明初始化j从1开始
2、对于ji,遍历链表,将p的指针向后移动,继续指向下一个节点,j 1
3、如果p到链表的末尾为空,则表示不存在第I个要素
4、否则搜索成功,返回节点p的数据
实现代码如下所示
statusgetelem(linklistL,int i,ElemType *e ) int i; 链接列表p; p=L-next; j=1; while(pJi ) { p=p-next; j; (if (! p|||Ji({returnerror; } *e=p-data; 回复
urn OK;}单链表第i个数据插入结点的算法思路
1、声明一个结点p指向链表头结点,初始化j从1开始
2、当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
3、若到链表末尾p为空,则说明第i个元素不存在
4、否则查找成功,在系统中生成一个空结点s
5、将数据元素e赋值给s->data
6、执行这两个语句 s->next = p->next ; p->next = s;
下面是实现代码
Status ListInsert(LinkList *L, int i, ElemType e){ int j; LinkList p,s; p = *L; j = 1; while(p && j<i) // 用于寻找第i个结点 { p = p->next; j++; } if(!p || j>i) { return ERROR; } s = (LinkList)malloc(sizeof(Node)); // 申请一个结点长度空间 s->data = e; s->next = p->next; // 将原始指向的指针域赋给插入结点的指针域 p->next = s; // 插入结点赋给P的指针域 return OK;}单链表第i个数据删除结点的算法思路
1、声明一个结点p指向第一个结点,初始化j=1
2、当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加1
3、若到链表末尾p为空,则说明第i个元素不存在
5、否则查找成功,将欲删除结点p->next赋值给q
6、执行这个语句 p->next = q->next ;
7、将q结点中的数据赋值给e,作为返回
下面是实现代码
Status ListDelete(LinkList *L, int i, ElemType *e){ int j; LinkList p,q; p = *L; j = 1; while(p->next && j<i) // 用于寻找第i个结点 { p = p->next; j++; } if(!(p->next) || j>i) { return ERROR; } q = p->next; // 删除的结点赋给q p->next = q->next; // 将欲删除的下一个结点指向p的指针域 *e = q->data; // 作为返回欲删除的数据 free(q); // 释放删除的结点 return OK;} 三、单链表结构和顺序存储结构的优缺点存储分配方式:
顺序存储结构用一般连续单元依次存储线性表的数据元素
单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
时间性能:
查找
顺序存储结构O(1)
单链表O(n)
插入和删除
顺序存储结构需要平均移动表长一半的元素,时间为O(n)
单链表在计算出位置的指针后,插入和删除时间仅为O(1)
空间性能:
顺序存储结构需要预分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出。
单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制
☆ 若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构
☆ 若需要频繁插入和删除时,宜采用单链表结构