线性表：相同数据类型的n个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱；除了最后一个元素外，每个元素有且仅有一个直接后继。
基本操作
InitList (&L)
Length(L)
LocateElem(L,e)
GetElem(L,i)
ListInsert(&L.i,e)
ListDelete(&L,i,&e)
PrintList(L)
Empty(L)
DestroyList(&L)
顺序表
顺序存储，用一组地址连续的存储单元依次存储线性表中的数据元素。逻辑上相邻，物理位置也相邻。
随机访问，通过首地址和元素序号可在O（1）时间内找到指定元素
插入和删除需要移动大量元素
typedef struct
{
ElementType Data[MAX_SIZE];
int Last; //最后一个元素的下标
}List;
动态分配
但数组满了之后就开辟一块更大的存储空间
typedef struct
{
ElemType *data;
int MaxSize, Length;
}List;
data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
初始化
List* MakeEmpty()
{
List* PtrL;
PtrL=new List(); //？
PtrL->Last=-1;
return PtrL;
}
查找
int Find（ElemenType X, List* PtrL)
{
for(i=0;i<=PtrL->Last&&X!=PtrL->Data[i];++i)
if(i>PtrL->Last)
return -1; //没找到
return i;
}
插入
int Insert(ElementType X, int i, List* PtrL)
{
//放到下标为i-1的位置
if(PtrL->Last==MAXSIZE-1) //1.空间满否
return -1;
if(i<1||i>PtrL->Last+2) //2.输入的位置i是否合法
return -1;
for(int j=Last;j>=i-1;--j)
{ //3.将Data[i-1]到Data[Last]倒序向后移动
PtrL->Data[j+1]=PtrL->Data[j];
}
Ptrl->Data[i-1]=X; //4.插入
PtrL->Last++; //5
return 1;
}
插入效率
最好情况：在表尾插入O（1）
最坏情况：在表头插入O（n）
平均情况
插入效率.PNG
删除
int Delete(int i, List* PtrL)
{ //删除下标为i-1的元素即第i个元素
if(i<1||i>PtrL->Last+1) //1.判断空表与删除位置是否合法
return -1;
for(int j=i;j<=PtrL->Last;++j)
{ //2.Data[i]到Data[Last]前移
PtrL->Data[i-1]=PtrL->Data[i];
}
PtrL->Last--; //3.
}
删除效率
删除效率.PNG
链表
typedef struct node
{
ElemType data;
struct node* next;
}Node, *PNode;
typedef struct LNode
{
ElemTypr data;
struct LNode *next;
}LNode, *LinkList;
LinkList L; //表示一个链表，L指向头节点
struct LinkList
{
PNode header; //指向头节点的指针
int Length; //链表长度（不包含头节点）
}
头节点不放具体数据
将s指向的元素插入到p指向的元素后面
s->next=p->next;
p->next=s;
将s指向的元素查到p指向的元素前面
普通的做法是找到p的前驱节点q,q->next=s;s->next=p;O(n)
因为找到p的前置元素很费时间，可以采用先把s插到p后面，再交换s与p的data来实现O(1)
s->next=p->next;
p->next=s;
temp=s->data;
s->data=p->data;
p->data=temp;
删除p指向的元素
普通做法是找到p的前驱元素q，q->next=p->next;free(p)
可以将p的后继元素赋给p，再释放后继元素
q=p->next;
p->data=q->data;
p->next=q->next;
free(q);
初始化空链表（带头节点）
int InitList(LinkList &L)
{
L->header=(PNode)malloc(sizeof(Node)); //申请头节点
if(!L)
exit(OVERFLOW);
L->header->next=NULL;
L->Length=0;
return 1;
}
头插法建立单链表
从表尾到表头逆向建立单链表L，每次均在头节点之后插入，效率O（1）
读入数据的顺序与链表元素顺序相反
若要顺序一致的话可采用尾插法，设置一个尾指针，效率也为O（1）
LinkList List_HeadInsert(LinkList &L)
{
LNode *s;int x;
L=(LinkList)malloc(sizeof(LNode)); //创建头节点
L->next=NULL; //初始为空链表
scanf("%d",&x); //输入结点值
while(x!=9999)
{
s=(LNode*)malloc(sizeof(LNode)); //创建新节点
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
逆置单链表
void InverseList(LinkList &L)
{
PNode p=L->header->next;
PNode q;
L->header->next=NULL;
while(!p)
{
q=p->next;
p->next=L->header->next;
L->header->next=p;
p=q;
}
}
头插法逆置单链表.PNG
void InverseList(LinkList &L)
{
PNode p=L->header->next;
//这里还应检查一下是不是空链表!p
PNode q=p->next;
p->next=NULL;
PNode r;
while(!q)
{
r=q->next;
q->next=p;
p=q;q=r;
}
L->header->next=p;
}
指针逆转逆置单链表.PNG
静态链表
typedef struct
{
ElemType data;
int next;
}SLinkList[MAXSIZE];
}
以next==-1作为结束标志
静态链表.PNG
为辨明数组中哪些空间可被使用，可将所有未被使用的空间及被删除的空间用游标链成一个备用链表
循环链表
判表尾
p->next==header判空
header->next==header用header来引导的话无法直接访问尾节点
可改进为用指向尾节点的rear来引导
循环链表.PNG
合并两个循环单链
q=Rb->next;
Rb->next=Ra->next;
Ra->next=q->next;
Ra=Rb;
free(q);
合并循环单链.PNG
双向循环链表
typedef struct DNode
{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinkList;
双向循环链表.PNG
在p指针指向的元素之前插入s
s->next=p;
s->prior=p->prior;
p->prior->next=s;
p->prior=s;
删除p指向的元素
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
顺序表与链表
对于按值查找，顺序表无序时，两者的时间复杂度均为O(n)；顺序表有序时，可采用折半查找，时间复杂度为O(log2(n))
链表存储空间大，存储密度小
网友评论