线性表的顺序存储结构是指用一段 地址 连续的存储单元存储相邻数据元素,或把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现(逻辑与物理统一),要求内存中可用的存储单元的地址必须是连续的。
1、顺序存储的插入与删除
目录
(1)插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新节点)
(2)删除(删除链表的第i(1<=i<=n)个位置上的结点)
(1)顺序表中插入或删除数据元素存在的情况
- 在表头插入/删除(头插、头删)
- 在表的指定位置插入/删除
- 直接尾随顺序表,作为表的最后一个元素(尾插、尾删)
(2)解决办法
- 插入:找到要插入的位置,将后续的数据元素整体向后移动一个位置,最后直接在空出来的位置上插入指定的数据元素即可。
- 删除:找到想要删除元素的位置,再将后面以为的元素前移,最后表的长度减去1
(3)主要操作的实现
【初始化】
- 建立空顺序表
List MakeEmpty()
{
List PtrL;
Ptrl = (List)malloc(sizeof(struct LNode));
Ptrl->Last = -1;
return Ptrl;
}
【头插】
- 判断顺序表是否为空,若不为空时,就将表中元素用for循环向后移动一位,在要插入的元素赋给首值,同时顺序表的长度加1。
void PushFront(pSeqList pSeq, DataType d)
{
int i = 0;
assert(pSeq);
if (pSeq->sz == MAX)
{
printf("表满,无法插入元素!\n");
return;
}
for (i = pSeq->sz-1; i >= 0 ; i--)
{
pSeq->data[i + 1] = pSeq->data[i];
}
pSeq->data[0] = d;
pSeq->sz++;//长度加1
}
【尾插】
- 先定义变量,然后找到表中最后一个元素,将要插入的数据直接赋值在最后面,表的长度加1。
void PushBack(pSeqList pSeq, DataType d)
{
assert(pSeq);
if (pSeq->sz == MAX)//判断表是否为空
{
printf("表满,无法插入元素!\n");
return;
}
pSeq->data[pSeq->sz] = d;//插入元素
pSeq->sz++;//长度加1
}
【头删】
- 判断元素是否为空,若不为空时,所有元素向前移动一位,顺序表长度减1。
void PopFront(pSeqList pSeq)
{
int i = 0;
assert(pSeq);
if (pSeq->sz == 0)//判断表是否为空
{
printf("表空,无元素可删!\n");
return;
}
for (i = 0; i < pSeq->sz; i++)//删除头部元素
{
pSeq->data[i] = pSeq->data[i + 1];
}
pSeq->sz--;//长度减1
}
【尾删】
判断元素是否为空,若不为空时,顺序表长度减1。
void PopBack(pSeqList pSeq)
{
assert(pSeq);
if (pSeq->sz == 0)
{
printf("表空,无元素可删!\n");
return;
}
pSeq->sz--;//非空长度减1
}
【在指定位置插入】
- 判断顺序表是否满了,未满时,将顺序表的元素从前向后依次移动以为,直至找到要插入的元素位置,再将要插入的元素插入到改空位,顺序表长度加1。
void Insert(pSeqList pSeq, int pos, DataType d)
{
int i = 0;
assert(pSeq);
if (pSeq->sz == MAX)
{
printf("表满,无法插入元素!\n");
return;
}
for (i = pSeq->sz-1; i >= pos; i--)
{
pSeq->data[i + 1] = pSeq->data[i];
}
pSeq->data[pos] = d;
pSeq->sz++;
}
2、线性表顺序存储结构的长度
- 顺序表的长度通常通过length来表达,length并不是表的最大长度,只是长度计数器。当顺序表进行插入与删除的操作时,插入与删除函数要去修改表的长度,这样才能表的长度与length的长度相等。
int Length(Sqlist L) {
return L.length;
}
3、线性表顺序存储结构的查找
- 从查找表的一端开始依次比较,实现代码如下
int Find(ELeementType X,Lust Ptrl)
{
int i=0;
while(i<=Ptrl->Last && Ptrl->Date[i]! = X)
i++;
if(i>Ptrl->Last)//如未找到,返回-1 ,找到了则返回i的值
return -1;
else return i;
}
二、链式存储
链式存储结构,又叫链接存储结构。在计算中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。用于存储逻辑关系为 "一对一" 的数据。
1、链式存储的插入与删除
(1)插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新节点)
- 先构造一个新节点,用s指向
- 再找到链表的第i-1个结点,用p指向
- 然后修改指针,插入结点(p之后插入新结点是s):s->Next=p->Next;p->Next=s
List Insert(Element Type X,int i,List PtrL)
{
List p,s;
if (i==1)
{
s=(List)malloc(sizeof(struct LNode));
s->Data=X;
s->Next=PtrL;
return s;
}
p=FindKth(i-1,PtrL);
if (p==NULL)
{
printf("参数i错");
return NULL;
}
else
{
s=(List)malloc(sizeof(struct LNode));
s->Data=X;
s->Next=p->Next;
p->Next=s;
return PtrL;
}
}
(2)删除(删除链表的第i(1<=i<=n)个位置上的结点)
- 先找到链表的第i-1个结点,用p指向
- 再用指针s指向要被删除的结点(p的下一个结点)
- 然后修改指针,删除s所指结点
- 然后释放s所指结点的空间
List Delete(int i,List PtrL)
{
List p,s;
if (i==1)
{
s=PtrL;
if (PtrL!=NULL) PtrL=PtrL->Next;
else return NULL;
free(s);
return PtrL;
}
p=FindKth(i-1,PtrL);
if (p==NULL)
{printf("第%d个结点不存在",i-1);return NULL;}
else if (p->Next==NULL)
{
printf("第%d个结点不存在",i);
return NULL;
}
else
{
s=p->Next;
p->Next=s->Next;
free(s);
return PtrL;
}
}
2、链表的长度
int ListLength(Student L)
{
Student *p;
p=L->next;
int j=0;/*用来存放链表的长度*/
while(p!=NULL)
{
p=p->next;
j++;
}
return j;
}
3、链表的按位查找
/*单链表按值查找*/
Status Locate_Linklist(Linklist *L,Elemtype e)
{
int i=1;
Linklist p,q;
p = (*L)->next;
while(p->data!=e&&p)
{
p=p->next;
i++;
}
if(p->data!=e) return -1;
else return i;
}
本文含有隐藏内容,请 开通VIP 后查看