数据结构-线性表-单链表

不带头结点的单链表

#include <stdio.h>

typedef struct LNode{  //定义单链表结点类型
    int data;  //每个结点存放一个数据元素
    struct LNode * next;  //指针指向下一个结点
}LNode, *LinkList;

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;  //空表，暂时没有任何节点，防止脏数据
    return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
    return (L == NULL);
}

int main(void){

}

带头结点的单链表

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
    int 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;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList &L){
    if(L->next == NULL){
        return true;
    }else{
        return false;
    }
}

void test(){
    LinkList L;  //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    //...后续代码...
}

插入删除

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
    int data;
    struct LNode * next;
}LNode, * LinkList;

#if 0
//带头结点，按位序插入
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, int e){
    if(i<1) return false;  //i的值不合法
    LNode *p;  //指针p指向当前扫描到的结点
    int j = 0;  //当前p指向的是第几个结点
    p = L;  //L指向头结点，头结点是第0个结点（不存数据）
    while(p!=NULL&&j<i-1){  //循环找到第i-1个结点
        p = p->next;
        j++;
    }  //循环的目的是找到第i-1个结点
    if(p == NULL) return false;  //i值不合法，说明第i-1个结点不存在
    LNode *s = (LNode *)malloc(sizeof(LNode));  //申请一个结点
    s->data = e;
    s->next = p->next;  
    p->next = s;  //将结点s连到p之后，这一句和上一句的顺序不能颠倒
    return true;  //插入成功
}
//最坏的时间复杂度O(n)
#endif

#if 1
//不带头结点
bool ListInsert(LinkList &L, int i, int e){
    if(i<1) return false;
    if(i == 1){
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;  //NULL
        L = s;  //需要更改头指针的指向，带头结点的则不需要
        return true;
    }
    LNode *p;
    int j = 1; //表示头指针刚开始指向的是第一个结点
    p = L;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }

    #if 0
    if(p==NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next=p->next;
    p->next=s;
    return true;
    #endif

    //上面if之间的代码可以用下面的代码代替
    return InsertNextNode(p,e);

}
#endif

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, int 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)

//前插操作，在p结点之前插入元素e
bool InsertPriorNode(LNode *p, int 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->data = p->data;
    p->data = e;
    return true;
}

//前插操作，在p结点之前插入结点s
bool InsertPriorNode(LNode *p, LNode *s){
    if(p==NULL||s==NULL)  return false;
    s->next = p->next;
    p->next = s;
    int tmp = p->data;
    p->data = s->data;
    s->data = tmp;
    return true;
}

//怎么删除结点，带头结点
bool ListDelete(LinkList &L, int i, int &e){
    if(i<1) return false;
    LNode *p;  //指针p指向当前扫描到的结点
    int j = 0;  //当前p指向的是第几个结点
    p = L;  //L指向头结点，头结点是第零个结点，不存数据
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL) return false;  //i值不合法
    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(1) 最差，平均：O(n)

//删除指定结点p
bool DeleteNode(LNode *p){
    if(p==NULL) return false;
    LNode *q = p->next;
    p->data = p->next->data;
    p->next = q->next;
    free(q);
    return true;
}
//单链表的局限性：无法逆向搜索，有时候不太方便
//如果p是最后一个结点，只能从表头开始以此寻找p的前驱结点，时间复杂度为O(n)
展开 

查找

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
    int 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指向头结点，头结点是第零个结点
    while(p!=NULL&&j<i){  //循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}
//平均时间复杂度O(n)

//后插操作
bool InsertNextNode(LNode *p, int e){
    if(p==NULL) return false;  //p有可能为NULL
    LNode *s = (LNode *)malloc(sizeof(LNode));  
    if(s==NULL) return false; //内存分配失败
    s->data = e;  //用结点保存数据元素e
    s->next = p->next;
    p->next = s;  //将结点s连接到p之后
    return true;
}

//王道书版本的按位查找操作
#if 0
LNode * GetElem(LinkList &L, int i){
    int j = 1;
    LNode *p = L->next;  //刚开始指向的是第一个结点
    if(i==0) return L;  //再判断i的值是否为零
    if(i<1) return NULL;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}
#endif

//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, int e){
    if(i<1) return false;

    #if 0
    LNode *p;  //指针p指向当前扫描到的结点
    int j = 0;  //当前p指向第几个结点
    p = L;
    while(p!=NULL&&j<i-1){  //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    #endif

    //以上if之间的代码还可以这样写
    LNode *p = GetElem(L,i-1);

    #if 0
    if(p==NULL) return false;  //i值不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;  //将结点s连到p之后
    return true;  //插入成功
    #endif

    //以上if之间的代码还可以这样写
    return InsertNextNode(p,e);
}

//删除第i个位置的元素
bool ListDelete(LinkList &L, int i, int &e){
    if(i<1) return false;

    #if 0
    LNode *p;
    int j = 0;
    p = L;
    while(p!=NULL&&j<i-1){
        p = p->next;
        j++;
    }
    #endif

    //以上if之间的代码可以用下面的代码代替
    LNode *p = GetElem(L,i-1);

    if(p==NULL) return false;  //i值不合法
    if(p->next==NULL) return false;  //第i个结点之后已无其他结点
    LNode *q = p->next;  //另q指向被删除结点
    e = q->data;  //用返回元素的值
    p->next = q->next;  //将*q结点从链中断开
    free(q);  //释放结点的存储空间
    return true;  //删除成功
}

//按值查找操作，找到数据域等于e的结点
LNode * LocateElem(LinkList &L, int e){
    LNode *p = L->next;  //p刚开始指向第一个数据结点
    //从第一个结点开始查找数据域为e的结点
    while(p!=NULL&&p->data!=e){
        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)

int main(void){
    return 0;
}
展开 

单链表的建立

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
    int 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;
}

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, int 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;
}

//尾插法建立单链表，正向建立单链表
LinkList List_TailInsert(LinkList &L){
    int x;  //局部变量x
    
    //初始化空表
    L = (LinkList)malloc(sizeof(LNode));  //建立头结点

    LNode *s, *r=L;
    scanf("%d",&x);
    while(x!=9999){
        
        //在r结点之后插入元素x
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next = s;

        r = s;  //r指向新的尾部结点，r始终指向表尾数据结点
        scanf("%d",&x);
    }
    r->next = NULL;  //尾结点指针置空
    return L;
}
//时间复杂度o(n)

//头插法建立单链表，逆向建立单链表
//只要初始化单链表，都要把头指针指向NULL
//头插法的策略可以实现链表的逆置
LinkList List_HeadInsert(LinkList &L){
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));  //创建头结点
    L->next = 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;
}

int main(void){
    return 0;
}
展开