LinearTable-2

先来比较一下顺序表跟单链表的优缺点:

顺序表：

优点: 可随机存取，存取密度高

缺点:要求大片连续空间，改变容量不方便

单链表：

优点：不要求大量的存储空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

单链表

用线性存储的方式实现线性结构。

结点：空间+指针

定义一个单链表

∵单链表都是靠其结构中的指针找寻下一个结点的头指针而连起来的，∴找到这个单链表只需要找到其头指针即可。

typedef struct LNode
{
	ElemType data;//data成为数据域
	struct LNode* next;//指针存放下一个节点
}LNode,*LinkList;
LinkList L;//声明一个指向单链表第一个节点的指针 等价于LNode*L
//向单链表中增加一个新的节点：在内存中申请一个节点空间，并用指针p指向这个节点
struct LNode* p = (struct LNode*)malloc(sizeof(struct LNode));

LinkList等价于LNode*

前者强调这个是单链表，后者强调这是结点

区分来写为了提高代码可读性。

初始化

不带头节点

//初始化一个单链表
bool InitList(LinList &L){
	L=NULL;//防止脏数据
	return true;
}
//判断单链表是否为空
bool Empty(LinkList L){
	return (L==NULL);
}
void test(){
	LinkList L;//声明一个指向单链表的指针
	InitList(L);
}

带头节点

typedef struct LNode
{
	ElemType data;//data成为数据域
	struct LNode* next;//指针存放下一个节点
}LNode,*LinkList;
bool InitList(LinList &L){
	L= (LNode*)malloc(sizeof(LNode));//分配头结点
    if(L==NULL)//内存不足，分配失败
        return false;
    L->next=NULL;//头结点之后没有其他结点
	return true;
}
bool isEmpty(LinList L){
    return L->next==NULL;
}
void test(){
	LinkList L;//声明一个指向单链表的指针
	InitList(L);
}

带头节点先办会比不带头节点更方便。

插入

LineInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素。

带头节点

typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, *LinkList;
//在第i个位置插入元素e(带头节点)
bool ListInert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
    LNode *p;//指针p指向当前扫描到的结点
    int j =0;//当p指向的是第几个节点
    p =L;//L指向头节点，头节点是第0个结点（不保存数据）
    while(p!=NULL && j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)//i值不合法
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;//将结点s连接到p之后
    return true;//插入成功
}

平均时间复杂度=O(n)

不带头结点

如果不带头结点，则插入、删除第1个元素时，需要更改头指针L。

typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, *LinkList;
//在第i个位置插入元素e(不带头节点)
bool ListInert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	if(i==1){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;//头指针指向新结点
    }
    LNode *p;//指针p指向当前扫描到的结点
    int j =1;//当p指向的是第几个节点
    p =L;//L指向头节点，头节点是第1个结点
    while(p!=NULL && j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)//i值不合法
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;//将结点s连接到p之后
    return true;//插入成功
}

指定结点的后插操作

在指定结点之前插入都是未知区域，之后都是可知区域

//在p结点之后插入元素
bool InsertNextNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)//内存分配失败情况
        return false;//某些情况可能分配失败
    s->data=e;//用结点s保存数据元素e
    s->next=p->next;
    p->next=s;//将结点s连到p之后
    return true;
}

时间复杂度=O(1)

对照上面的带头节点的第i个元素插入元素e可直接找到第i-1个结点，调用此时的后插操作。

指定结点的前插操作

直接去找前驱除非指定头结点，否则很难办到

这时可以将要插入的结点与该结点替换

//在p结点之前插入元素e
bool InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)//内存分配失败
        return false;
    s->next=p->next;
    p->next=s;//将新结点s连接到p之后
    s->data=p->data;//将p中元素复制到s中
    p->data=e;//p中元素覆盖为e
    return true;
}

or

bool InsertPriorNode(LNode *p,LNode *s){
    if(p==NULL||s=NULL)
        return false;
    s->next=p->next;
    p->next=s;//将新结点s连接到p之后
    ElemType temp=->p->data;//交换数据部分
    p->data=s->data;//将p中元素复制到s中
    s->data=temp;//p中元素覆盖为e
    return true;
}

删除

ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点。

带头指针

typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, *LinkList;
//在第i个位置插入元素e(带头节点)
bool ListDelete(LinkList &L,int i,ElemType &e){
	if(i<1)
		return false;
    LNode *p;//指针p指向当前扫描到的结点
    int j =0;//当p指向的是第几个节点
    p =L;//L指向头节点，头节点是第0个结点（不保存数据）
    while(p!=NULL && j<i-1){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)//i值不合法
        return false;
    if(p->next==NULL){
        return false//第i-1个之后没有结点了
    }
    LNode *q=p—>next;//令q指向被删除结点
    e=q->data;//用e返回元素的值
    p->next=q->next;//将*q结点从链中断开
    free(q);//释放结点的存储空间
    return true;//删除成功
}

最坏、平均时间复杂度=O(n)

最好时间复杂度=O(1)

指定结点的删除

bool DeleteNode (LNode *p) {
	if (p==NULL)
    	return false;
	LNode *q=p->next;//令q指向*p的后继结点
    p->data=p->next->data;//和后继结点交换数据域
    p->next=q->next;//将*q结点从链中“断开”
    free(q);//释放后继结点的存储空间
    return true;
}

如果要被删除的结点恰巧是最后一个结点，p指向next的后继的时候会出现bug

此时只能从头开始检索

时间复杂度=O(1)

查找

按位查找

GetElem(L,i):按位查找操作，获取表中第i个位置的元素的值。

LNode * GetElem(LinkList L,int i){
	if(i<0)
		return false;
    LNode *p;//指针p指向当前扫描到的结点
    int j =0;//当p指向的是第几个节点
    p =L;//L指向头节点，头节点是第0个结点（不保存数据）
    while(p!=NULL && j<i){//循环找到第i-1个结点
        p=p->next;
        j++;
    }
    return p;
}

平均时间复杂度=O(n)

则带头结点的插入操作也可简化

bool ListInert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
    LNode *p=GetElem(L,i-1);
    return InsertNextNode(p,e);
}

按值查找

LocateElem(L,e):按值查找操作，在表L中查找具有给定关键字值的元素。

//找到数据域==e的结点
LNode * LocateElem(LinkList L,ElemType e){
    LNode *p =L->next;
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL && p->data!=e)//这里默认就是int型数据，如果是struct类型则!=应该被替换
        p=p->next;
    return p;//找到后返回该结点指针，否则返回NULL
}

时间复杂度为O(n)

求表的长度

int Length(LinkList L){
	int len=0;//计数器
    LNode *p=L;
    while(p->next !=NULL){
        p=p->next;
        len++;
    }
    return len;
}

时间复杂度为O(n)

单链表的建立

尾插法

LinkList List_TailInsert(ListList &L){//正向建立单链表
	int x;//设ElemType为整型
    
    //初始化空表
    L=(LinkList)malloc(sizeof(LNode));//建立头结点
    
    LNode *s,*r=L;//r为表尾指针
    scanf("%d",&x);//输入结点的值
    
    //后插操作
    while(x!=8848){//输入8848表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        
        //保持r指向最后一个结点
        r=s;//r指向新的表尾结点
        
        scanf("%d",&x);
    }
    r->next=NULL;//尾结点指针置空
    return L;
}

头插法

LinkList List_HeadInsert(ListList &L){//逆向建立单链表
	LNode *s;
    int x;//设ElemType为整型
    
    //初始化空表
    L=(LinkList)malloc(sizeof(LNode));//建立头结点
    L->next=NULL;//初始化为空链表
    
    scanf("%d",&x);//输入结点的值
    
    //后插操作
    while(x!=8848){//输入8848表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=L->next;
        L->next=s;
        
        scanf("%d",&x);
    }
    return L;
}

因为每次直接往头结点后面插入

这样会使得插入的数据逆置

小结

饿🍲