首页 > 代码库 > 【数据结构第二周】线性表知识点整理

【数据结构第二周】线性表知识点整理

2024-10-29 03:11:40   210人阅读

1、什么是线性表？

线性表（Linear List）：由同类型元素构成有序序列的线性结构。

表中元素个数称为线性表的长度

线性表没有元素时，称为空表

表起始位置称表头，表结束位置称为表尾

2、线性表的抽象数据类型描述

List MakeEmpty():初始化一个空线性表L;
ElementType FindKth( int K, List L ):根据位序K,返回相应元素 ;
int Find( ElementType X, List L ):在线性表L中查找X的第一次出现位置;
void Insert( ElementType X, int i, List L):在位序i前插入一个新元素X;
void Delete( int i, List L ):删除指定位序i的元素;
int Length( List L ):返回线性表L的长度n。 

3、主要实现方式：顺序存储实现和链式存储实现

4、线性表的顺序存储实现

（1）如何存储

//如何存储typedef struct {	ElementType Data[MAXSIZE];	int Last;}List; List L,*PtrL;

访问下标为i的元素：L.Data[i]或PtrL->Data[i]

线性表的长度：L.Last+1或者PtrL->Last+1

技术分享

（2）初始化（建立空的顺序表）

List *MakeEmpty(){	List *PtrL;	PtrL = (List *)malloc(sizeof(List));	PtrL->Last = -1;	return PtrL;}

 （3）查找

int Find(ElementType X, List *PtrL){	int i = 0;	while(i <= PtrL->Last && PtrL->Data[i]!=X)		i++;	if (i > PtrL->Last)	{		return -1;	}else	{		return i;	}}

查找成功的平均比较次数为（n+1）/ 2（第一次比较就找到或者最后一次比较才找到），平均时间性能为O（n）。

（4）插入（第i（1<=i<=n+1）个位置上插入一个值为X的新元素）

技术分享

//插入void Insert(ElementType X, int i,List *PtrL){	int j;	if (PtrL->Last==MAXSIZE-1)	{		printf("表满");		return;	}	if (i < 1 || PtrL->Last+2)	{		printf("位置不合法");		return;	}	for (j = PtrL->Last; j >= i-1; --j)	{		PtrL->Data[j+1]=PtrL->Data[j];//将ai~an倒序向后移动	}		PtrL->Data[i-1] = X;//插入新元素	PtrL->Last++;//Last仍指向最后元素		return;}

平均移动次数为n/2，平均时间性能为O(n)。

（5）删除

技术分享　　

//删除void Delete(int i,List *PtrL){	int j;	if (i < 1 || i >PtrL->Last+1)	{		printf("不存在第%d个元素",i );		return；	}	for (j = i; j <= PtrL->Last;++j)	{		PtrL->Data[j-1]=PtrL->Data[j];//将ai+1~an顺序向前移动	}	PtrL->Last--;	return;}

平均移动次数为(n-1)/2，平均时间性能为O(n)。

5、线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系

插入、删除不需要移动数据元素，只需要修改“链”。

（1）如何存储

技术分享

//如何存储typedef struct Node{	ElementType Data;	struct Node *Next;}List;List L,*PtrL;

（2）求表长

//求表长int Length(List *PtrL){	List *p = PtrL;//p指向表的第一个结点	int j = 0;	while(p)	{		p = p->Next;//当前p指向第j个结点		j++;	}	return j;}

 （3）查找

按照序号查找：FindKth

List *FindKth(int K,List *PtrL){	List *p = PtrL;	int i = 1;	while(p != NULL&&i < k)	{		p = p->Next;		i++;	}	if (i==k)	{		return p;//找到第K个，返回指针	}else	{		return NULL;	}}

按照值查找：Find

List *Find(ElementType X,List *PtrL){	List *p = PtrL;	while(p != NULL && p->Data != X)	{		p = p->Next;	}	return p;}

（4）插入

技术分享

 

List *Insert(ElementType X, int i, List *PtrL){	List *p,*s;	if (i == 1)//新结点插入在表头	{		s = (List *)malloc(sizeof(List));		s->Data = http://www.mamicode.com/X;"参数i错误");//第i-1个元素不存在，则不能插入		return NULL;	}else	{		s = (List *)malloc(sizeof(List));		s->Data = http://www.mamicode.com/X;>

（5）删除（删除链表的第i(1<=i<=n)个位置上的结点）

技术分享

List *Delete(int i,List *PtrL){	List *p,*s;	if (i == 1)//删除的结点是第一个结点	{		s = PtrL;//s指向第一个结点		if (PtrL!=NULL)		{			PtrL = PtrL->Next;//从链表中删除		}else		{			return NULL;		}		free(s);		return PtrL;	}	P = FindKth(i-1, PtrL);//查找第i-1个结点	if (p == NULL)	{		printf("第%d个结点不存在"，i-1);		return NULL;	}else if (p->Next==NULL)	{		printf("第%d个结点不存在",i );		return NULL;	}else	{		s = p->Next;//s指向第i个结点		p->Next = s->Next;//从链表中删除		free(s)		return PtrL;	}}

 

【数据结构第二周】线性表知识点整理


联系
我们