数据结构(二)——线性表(单链表)

 2.3线性表的链式表示

顺序表的优缺点：
优点：可随机存储，存储密度高
缺点：要求大片连续空间，且改变容量不方便

2.3.1 单链表的基本概念

单链表：用链式存储实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。
优点：不要求大片连续空间，改变容量方便。
缺点：不可随机存取，要耗费一定空间存放指针。

//用代码定义一个单链表
struct LNode{    //LNode是结点
    ElemType data;    //data为数据域 定义单链表结点类型
    struct LNode *next;  //*next是指针域 指针指向下一个结点  
}
 
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));
//增加一个新的结点：在内存中申请一个结点所需空间，并用指针n指向这个结点

typedef关键字——数据类型重命名
typedef <数据类型> <别名>
typedef struct LNode LNode;        //这样使用就可以直接哟弄个LNode 不需要前面加一长串
typedef struct LNode *LinkList;

要表示一个单链表时，只需要表明一个头指针L,指向单链表的第一个结点
LNode *L;        //声明一个指向单链表第一个结点的指针 
或
LinkList L;        //声明一个指向单链表第一个结点的指针  代码可读性更强

不带头结点的单链表

typedef struct LNode{    //定义单链表结点类型
    ElemType data;       //每个节点存放一个数据元素
    struct LNode *next;    //指针指向下一个节点
}LNode, *LinkList;
 
//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL; //空表，暂时还没有任何结点 防止脏数据
    return true;
}
 
void test(){
    LinkList L;  //声明一个指向单链表的头指针
    //初始化一个空表
    InitList(L);
    ...
}
 
//判断单链表是否为空
bool Empty(LinkList L){
    return (L==NULL)
}

带头结点的单链表

typedef struct LNode{          
    ElemType data;      
    struct LNode *next;    //指针指向下一结点
}LNode, *LinkList;
 
// 初始化一个单链表（带头结点）
bool InitList(LinkList &L){      
    L = (LNode *)malloc(sizeof(LNode));  //分配一个头结点 
    if (L == NULL)        //内存不足，分配失败    
        return false;    
    L->next = NULL;       //头结点之后暂时还没有结点   
    return true;
}
 
void test(){     
    LinkList L;  //声明一个指向单链表的头指针 
    //初始化一个空表    
    InitList(L);     
    ...
}
 
//判断单链表是否为空
bool Empty(LinkList L){  
    if (L->next == NULL) 
        return true;     
    else             
        return false;
}

不带头结点，写代码更麻烦 对第一个数据结点和后续数据结点的 处理需要用不同的代码逻辑 对空表和非空表的处理需要用不同的 代码逻辑

带头结点，写代码更方便

2.3.2_1单链表的插入删除

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

按位序插入（带头结点）：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
 
//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L,int i ElemType e){    //i是要插入的位序
    if(i<1)    //i表示的是位序 位序最小是1 
        return false;
    LNode *p;    //指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个结点
    p=L;        //L指向头结点，头结点是第0个结点，不存数据
    while(p!=NULL && j-1){    //循环找到第i-1个结点 如果i>length p最后会等于NULL
        p=p->next;
        j++;
    }
    if(p==NULL)       //i值不合法
        return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));    //malloc开辟一块空间s
    s->data=e;    //把要插入的元素存到新结点中
    s->next=p->next;    //让s指向的next的指针等于p结点的next指针指向的位置
    p->next=s;    //让p的结点的next指针指向新的结点s 即将结点s连到p之后
    return true;    //插入成功
}
 

时间复杂度：这里问题规模n指的是表的长度
        最好时间复杂度：O(1)
        最坏时间复杂度：O(n)
        平均时间复杂度：O(n)

按位序插入（不带头结点）：
由于不存在“第0个”结点，因此i=1时需要特殊处理

typedef struct LNode{     
    ElemType data;      
    struct LNode *next;
}LNode, *LinkList;
 
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){   
    //判断i的合法性     
    if(i<1)      
        return false; 
    //需要判断插入的位置是否是第1个 对第一个结点单独写操作进行处理    
    if(i==1){              
        LNode *s = (LNode *)malloc(size of(LNode)); //malloc申请一个结点
        s->data =e;          //把要插入的e放到新申请的结点中
        s->next =L;       //让新结点的指针指向L
        L=s;          //头指针指向新结点   
        return true;      
    }       
    //i>1的情况与带头结点一样，唯一区别是j的初始值为1   
    LNode *p;       //指针p指向当前扫描到的结点     
    int j=1;        //当前p指向的是第几个结点   
    p = L;          //p指向的是第1个结点，注意不是头结点
    //循环找到第i-1个结点    
    while(p!=NULL && j-1){     //如果i>lengh，p最后会等于NULL    
        p = p->next;             
        j++;      
    }       
    //p值为NULL说明i值不合法   
    if (p==NULL)           
        return false;      
    //在第i-1个结点后插入新结点   
    LNode *s = (LNode *)malloc(sizeof(LNode));  
    s->data = e;      
    s->next = p->next;  
    p->next = s;        
    return true;
}

结论:不带头结点写代码更不方便，推荐用带头结点注意

指定结点的后插操作：

typedef struct LNode{        
    ElemType data;        
    struct LNode *next;
}LNode, *LinkList;
 
// 在结点p后插入元素e
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;
}
 
// 按位序插入的函数中可以直接调用后插操作
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i<1)            
        return False;
    LNode *p;     
    //指针p指向当前扫描到的结点 
    int j=0;        
    //当前p指向的是第几个结点 
    p = L;       
    //循环找到第i-1个结点   
    while(p!=NULL && j-1){ 
        //如果i>lengh, p最后会等于NULL   
        p = p->next;        
        j++;       
    }       
    return InsertNextNode(p, e)
}

时间复杂度：O(1)

指定结点的前插操作：

typedef struct LNode{     
    ElemType data;      
    struct LNode *next;
}LNode, *LinkList;
 
//前插操作： 在结点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;
}

按位序删除（带头结点）

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点，头结点可看做“第0个”结点

typedef struct LNode{       
    ElemType 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-1){       //循环找到第i-1个结点     
        p = p->next;                    //如果i>lengh，p和p的后继结点会等于NULL        
        j++;      
    }       
    if(p==NULL)       //i值不合法
        return false;    
    if(p->next == NULL)        //第i-1个结点之后已无其他结点
        return false;    	   
    LNode *q = p->next;        //令q指向被删除的结点   
    e = q->data;             //把删除的结点的值存到变量e
    p->next = q->next;      //p的next指向q的next 就是null 相当于将*q结点从链中“断开”
    free(q);                //释放结点的存储空间     
    return true;        //删除成功
}

指定结点的删除 
删除结点p，需要修改其前驱 结点的 next 指针
方法1：传入头指针，循环寻找 p 的前驱结点
方法2：类似于结点前插的实现

// 删除指定结点p
bool DeleteNode(LNode *p){   
    if(p==NULL)           
        return false;     
    LNode *q = p->next; // 令q指向p的后继结点  
    // 如果p是最后一个结点，则q指向NULL，继续执行就会报错  
    p->data = q->data;  //把后继结点的数据复制到p结点的数据域中
    p->next = q->next;   //让p结点的next指针指向q结点后的位置 相当于将*q结点从链中“断开”
    free(q);    //释放q结点的空间
    return true;
}

 

2.3.2_2单链表的插入查找

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

typedef struct LNode{  
    ElemType data;    
    struct LNode *next;
}LNode, *LinkList;
 
// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){   
    if(i<0)            
        return NULL;   
    LNode *p;     //指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;        //L指向头结点，头结点是第0个结点（不存数据）
    while(p!=NULL && j
        p = p->next;     
        j++;      
    }        
    return p;
}
 
// 在结点p后插入元素e
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;
}
 
// 封装后的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){  
    if(i<1)             
        return False;  
    // 找到第i-1个元素     
    LNode *p = GetElem(L, i-1);   
    // 在p结点后插入元素e     
    return InsertNextNode(p, e);//调用查询操作和后插操作
}

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

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

// 查找数据域为e的结点指针，否则返回NULL
LNode * LocateElem(LinkList L, ElemType e){           
    LNode *p = L->next;  //定义一个指针p，让他指向头结点的下一个结点     
    // 从第一个结点开始查找数据域为e的结点  
    while(p!=NULL && p->data != e){   //当p不为NULL且数据跟传入的e不相等时循环
        p = p->next;     //让p指向下一个结点
    }     
    return p;    //跳出循环后返回p
}

平均时间复杂度：O(n)  只能依次往后查找

求表的长度

// 计算单链表的长度
int Length(LinkList L){      
    int len=0;       //统计表长  
    LNode *p = L;
    while(p->next != NULL){ 
        p = p->next;      
        len++;       
    }      
    return len;
}

2.3.2_3单链表的插入建立

尾插法

// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){   
    int x;			//设ElemType为整型int  
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点(初始化空表)     
    LNode *s, *r = L;                        //r为表尾指针    
    scanf("%d", &x);                         //输入要插入的结点的值   
    while(x!=9999){                          //输入9999表示结束     
        s = (LNode *)malloc(sizeof(LNode));    
        s->data = x;           
        r->next = s;                         //在r结点之后插入元素x
        r = s;                               //r指针指向新的表尾结点     
        scanf("%d", &x);       
    }    
    r->next = NULL;                          //尾结点指针置空      
    return L;
}

头插法

LinkList List_HeadInsert(LinkList &L){       //逆向建立单链表   
    LNode *s;      
    int x;     
    L = (LinkList)malloc(sizeof(LNode));     //建立头结点   
    L->next = NULL;                          //初始为空链表,先把头指针指向NULL,这步很关键  
    scanf("%d", &x);                         //输入要插入的结点的值  
    while(x!=9999){                          //输入9999表结束     
        s = (LNode *)malloc(sizeof(LNode));  //创建新结点
        s->data = x;          
        s->next = L->next;      
        L->next = s;                  //将新结点插入表中，L为头指针   
        scanf("%d", &x);       
    }     
    return L;
}

 头插法实现链表的逆置：

// 将链表L中的数据逆置并返回
LNode *Inverse(LNode *L){	
    LNode *p, *q;	  
    p = L->next;     //p指针指向第一个结点	  
    L->next = NULL;  //头结点置空       
    // 依次判断p结点中的数据并采用头插法插到L链表中	
    while (p != NULL){		   
        q = p;		  
        p = p->next;	
        q->next = L->next;  
        L->next = q;	
    }	   
    return L;
}

 头插法逆置详见【数据结构】单链表逆置：头插法图解