1.线性表：顺序表、链表——数据结构（严蔚敏C语⾔版）线性表
线性表定义
线性表(Linear List) : 由n个具有相同特性的数据元素(结点)a1, a2,…组成的有限序列。
其中数据元素的个数n定义为表的长度。
当n=0时称为空表将⾮空的线性表(n>0)记作: (a1, a2, …an)
线性表特性
线性表的逻辑特征是:
在⾮空的线性表， 有且仅有⼀个开始结点a1，它没有直接前趋，⽽仅有⼀个直接后继a2;
有且仅有⼀个终端结点an，它没有直接后继，⽽仅有⼀个直接前趋an-1;
其余的内部结点都有且仅有⼀个直接前趋ai-1.和⼀个直接后继ai+1。
元素个数有限。
线性表是⼀种逻辑结构，表⽰元素之间⼀对⼀相邻的关系。1233
线形表顺序存储结构占⽤⼀⽚连续的存储空间。知道某个元素的存储位置就可以计算其他元素的存储位置。
线性表的顺序表⽰
线性表的基本操作（抽象数据类型定义）
InitList(&L)
//初始化操作，建⽴⼀个空的线性表L
c语言listinsert函数DestertList(&L)
//销毁已存在的线性表L
ClearList(&L)
//将线性表清空
ListInsert(&L, i, e)
//在线性表L中第i个位置插⼊新元素e
ListDelete(&L i, &e)
//删除线性表L中第i个位置元素，⽤e返回
lsEmpty(L)
//若线性表为空，返回true，否则false
ListLength(L)
//返回线性表L的元素个数
LocateElem(L, e)
// L中查与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
GetElem(L,i, &e)
// 将线性表L中的第i个位置元素返回给e
#define MAXSIZE 100
typedef struct{
ElemType *elem;
int length;
} SqList;
顺序表基本操作的实现
1.构造顺序表
Status InitList Sq(SqlList &L){//构造⼀个空的顺序表L
L.elem= new ElemType[MAXSIZE];//1.为顺序表分配空间
if(!L.elem)exit(OVERFLOW);//2.判断是否有⾜够的存储空间：存储分配失败退出，分配成功，则继续执⾏
L.length=0;//3.空表：长度为0
return OK;
}
//status⽤来返回本函数是否执⾏成功：1.OK  2.ERROR  3.OVERFLOW
//!L.elem  ：如果不存在
2.销毁顺序表
void DestroyList(SqList &L){
if(L.elem)
delete L.elem;//释放存储空间
}
3.顺序表的取值(根据位置 i 获取相应位置数据元素的内容) 随机存取
Status GetElem(SqList L,int i, ElemType &e){
if(i<1|| i>L.length)return ERROR;//第⼀步：判断i值是否合理，若不合理，返回ERROR
e=L.elem[i-1];//第⼆步：elem[i-1]单元存储第i个数据元素
return OK;//查成功
}
//e=L.elem[i-1];    返回的是数组下标，⽽不是元素位置，所以是i—1
4.顺序表的查
算法思想:
在线性表L中查与指定值e相同的数据元素的位置
从表的⼀端开始，逐个进⾏记录的关键字和给定值的⽐较。到，返回该元素的位置序号，未到，返回0。按值查：时间复杂度：最好O(1) 平均O(n) 最坏O(n)
int LocateElem(SqList L, ElemType e){//在顺序表L中查值为e的数据元素，返回其序号
for(i=0;i< L.length;i++)
if(L.elem[i]==e)return i+1;//查成功，返回序号i+1
return0;//查失败，返回0
}
5.顺序表的插⼊
算法思想:
判断插⼊位置i是否合法。
判断顺序表的存储空间是否已满，若已满返回ERROR。
将第n⾄第i位的元素依次向后移动⼀个位置，空出第i个位置。
Status ListInsert(SqList &L,int i ,ElemType e)
{//在顺序表⼯中第i个位置插⼈新的元素e,i值的合法范围是1≤i≤L.length+1
if((i<1)||(i>L.length+1))return ERROR;//i值不合法
if(L. length==MAXSIZE)return ERROR;//当前存储空间已满
for(j=L. length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j];//插⼊位置及之后的元素向后移动
L.elem[i-1]=e;//将新元素e放⼈第i个位置
++L.length;//表长加1
return OK;
}
插⼊操作的时间复杂度：最好O(1) 平均O(n) 最坏O(n)
6.顺序表的删除
算法思想:
判断删除位置i是否合法（合法值为1≤i≤n) 。
将欲删除的元素保留在e中。
将第i+1⾄第n 位的元素依次向前移动⼀个位置。
表长减1，删除成功返回OK。
Status ListDelete(SqList &L,int i)
{//在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.length
if((i<1)1I(i>L. length))return ERROR;//i 值不合法
for(j=i;j<=L. length-1;j++)
L.elem[j-1]=L.elem[j];//被删除元素之后的元素前移
--L.length;//表长减1
return OK;
}
删除操作：时间复杂度：最好O(1) 平均O(n) 最坏O(n)
顺序表(线性表的顺序存储结构)的特点
利⽤数据元素的存储位置表⽰线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构⼀致
在访问线性表时，可以快速地计算出任何⼀个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等这种存取元素的⽅法被称为随机存取法。
顺序表优缺点
优点:
存储密度⼤(结点本⾝所占存储量/结点结构所占存储量)
可以随机存取表中任⼀元素
缺点:
在插⼊、删除某⼀元素时，需要移动⼤量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能⾃由扩充
线性表的链式表⽰
链式存储结构特点
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素，在物理上不⼀定相邻；
线性表的链式表⽰⼜称为⾮顺序映像或链式映像。
⽤⼀组物理位置任意的存储单元来存放线性表的数据元素。
这组存储单元既可以是连续的，也可以是不连续的，甚⾄是零散分布在内存中的任意位置上的。
链表中元素的逻辑次序和物理次序不⼀定相同。
单链表
单链表是线性表的链式存储。只能从头节点依次向后遍历。
结点: 数据元素的存储映像。由数据域和指针域两部分组成
数据域
指针域
链表: n个结点由指针链组成⼀个链表。
它是线性表的链式存储映像，称为线性表的链式存储结构。
单链表是由表头唯⼀确定，因此单链表可以⽤头指针的名字来命名。 若头指针名是L，则把链表称为表L。
⼏个节点差别p31
头指针: 是指向链表中第⼀个结点的指针
⾸元结点: 是指链表中存储第⼀个数据元素a，的结点
头结点：是在链表的⾸元结点之前附设的⼀个结点;
表空条件
单链表基本操作
0.单链表的定义
p30
typedef struct Lnode{
ElemType
data;
struct Lnode *next;} LNode,*LinkList;
1.单链表的初始化
Status InitList(LinkList &L){//构造⼀个空的单链表L
L=new LNode;//⽣成新结点作为头结点，⽤头指针⼯指向头结点
L->next=NULL;//头结点的指针域置空
return OK;
}
2.头插法建⽴单链表
引⼊head结点的优点：
可以使插⼊删除操作统⼀
⾮空表和空表操作统⼀
void CreateList_H(Linkist &L,int n)
{//逆位序输⼊n个元素的值，建⽴带表头结点的单链表LL=new LNode;
L->next=NULL;//先建⽴⼀个带头结点的空链表
A
for(i=0;i<n;++i){
p=new LNode;//⽣成新结点*p
cin>>p->data;//输⼊元素值赋给新结点*p的数据域
p->next=L->next; L->next=p;//将新结点*p插⼊到头结点之后
}
}
3.尾插法建⽴单链表
void CreateList_R(LinkList &L,int n)
{//正位序输⼈n个元素的值，建⽴带表头结点的单链表L
L=new LNode;
L->next=NULL;//先建⽴⼀个带头结点的空链表
r=L;//尾指针r指向头结点
for(i=0;i<n;++i)
p=new LNode;//⽣成新结点
cin>>p->data;//输⼊元素值赋给新结点*p的数据域
p->next=NULL;
r->next=p;//将新结点*p插⼊尾结点*⼯之后
r=p;//r指向新的尾结点*p
)
4.单链表的取值
Status GetElem(LinkList L,int i,ElemType &e)
{//在带头结点的单链表⼯中根据序号i获取元素的值，⽤e返回L中第i个数据元素的值
p=L->next;j=1;//初始化,p指向⾸元结点，计数器j初值赋为1
while(p&&j<i)//顺链域向后扫描，直到p为空或p指向第i个元素
{
p=p->next;//p指向下⼀个结点
++j;//计数器j相应加1
}
if(!pl1j>i)return ERROR;//i值不合法,i>n或i≤0
e=p->data;//取第i个结点的数据域
return OK;
}
5.单链表的按值查
//按值地址
LNode *LocateElem(LinkList L， ElemType e){//在带头结点的单链表⼯中查值为e的元素 p=L->next;//初始化，p指向⾸元结点
while(p && p->data !=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p=p->next;//p指向下⼀个结点
return p;//查成功返回值为e的结点地址p，查失败p为NULL
}
//按值i在表中的位置？
6.单链表的插⼊

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。