数据结构之C语言实现单链表

• 定义
• • 什么是单链表
  • 用代码定义一个单链表
  • • typedef使用
    • 不带头节点
    • 带头结点
• 基本操作的实现
• • 插入删除操作
  • 查找操作
  • 单链表的建立

• 优点：不要求大片不连续空间，改变容量方便
• 缺点：不可随机存取，要耗费一定空间存放指针

struct LNode{
  ElementType data;
  struct LNode *next;
}


struct LNode* p=(struct LNode*)malloc(sizeof(struct LNode));

要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个节点

// typedef 关键字--数据类型重命名
typedef <数据类型> <别名>
typedef int zhengshu;
typedef int *zhengshuzhizhen;
type struct LNode LNode;
LNode *p=(LNode*)malloc(sizeof(LNode));

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

struct LNode{
  ElemType data;
  struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

LNode *GetElem(LinkList l,int i){
  int j=1;
  LNode *p=l->next;
  if(i==0){
    return l;
  }
  if(i<1){
    return NULL;
  }
  where(p!=NULL&&jnext;
    j++;
  }
  return p;
}

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

//初始化一个空的单链表
bool initList(LinkList &l){
  //空表，暂时还没有任何结点，防止脏数据
  l=NULL;
  return true;
}
//判断单链表是否为空
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;
}
//判断单链表是否为空
bool Empty(LinkList L){
  return L->next==NULL;
}

1. 插入
   1. 按位序插入
      1. 带头结点
      2. 不带头节点
   2. 指定节点的后插操作
   3. 指定节点的前插操作
2. 删除
   1. 按位序删除
   2. 指定节点的删除

#include "stdlib.h"
#include "stdio.h"
#include "stdbool.h"

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


bool initList(LinkList *linkList) {
    *linkList = (LinkList) malloc(sizeof(LNode));
    if (NULL == *linkList) {
        return false;
    }
    (*linkList)->data = 0;
    (*linkList)->next = NULL;
    return true;
}


bool empty(LinkList linkList) {
    return linkList == NULL;
}


bool listInsert(LinkList linkList, int i, int e) {
    //下标不合法，默认不允许插入到第一位
    if (i < 1) {
        return false;
    }
    LNode *cur = NULL;
    cur = linkList;
    int curIndex = 0;
    //把下标以后的结点都后移一个，并且将目标指针的上个指征保留下来，i-1即可
    while (cur != NULL && curIndex < i - 1) {
        cur = cur->next;
        curIndex++;
    }
    //判断当前结点是否有效，下标可能指向了空结点，看上面的while循环
    if (NULL == cur) {
        return false;
    }
    //创建结点，赋值插入
    LNode *targetNode = (LNode *) malloc(sizeof(LNode));
    //内存失败
    if (NULL == targetNode) {
        return false;
    }
    targetNode->data = e;
    //插入，目标结点的一些指针为当前结点的下一节点,当前结点的下一指针为目标结点
    targetNode->next = cur->next;
    cur->next = targetNode;
    return true;
}


bool insertNextNode(LNode *p, int e) {
    if (NULL == p) {
        return false;
    }
    //创建指针,分配空间
    LNode *targetNode = (LNode *) malloc(sizeof(LNode));
    if (NULL == targetNode) {
        return false;
    }
    targetNode->data = e;
    targetNode->next = p->next;
    p->next = targetNode;
    return true;
}


bool insertPriorNode(LNode *p, int e) {
    if (NULL == p) {
        return false;
    }
    //创建指针,分配空间
    LNode *targetNode = (LNode *) malloc(sizeof(LNode));
    if (NULL == targetNode) {
        return false;
    }
    targetNode->next = p->next;
    p->next = targetNode;
    //修改元素值
    targetNode->data = p->data;
    p->data = e;
    return true;
}

bool listDelete(LinkList linkList, int i, int *e) {
    //不可删除头结点
    if (i < 1) {
        return false;
    }
    LNode *cur = NULL;
    cur = linkList;
    int curIndex = 0;
    while (NULL != cur && curIndex < i - 1) {
        cur = cur->next;
        curIndex++;
    }
    if (NULL == cur) {
        return false;
    }
    LNode *targetLNode = cur->next;
    //返回值赋值
    *e = targetLNode->data;
    //跳过结点
    cur->next = targetLNode->next;
    //释放内存
    free(targetLNode);
    return true;
}


bool deleteNode(LNode *p) {
    if (NULL == p) {
        return false;
    }
    LNode *nextNode = p->next;
    if (NULL!=nextNode) {
        p->data = nextNode->data;
        p->next = nextNode->next;
        //释放内存
        free(nextNode);
    } else {
        p = NULL;
    }
    return true;
}


int main() {
    LinkList linkList = NULL;
    initList(linkList);
    printf("%llun", sizeof(*linkList));
    printf("%llun", sizeof(*(linkList->next)));
    return 0;
}

1. 按位查找

2. 按值查找

3. 求单链表长度

4. 三种基本操作的时间复杂度都是O_(n)

5. 如何写循环扫描各个节点的代码逻辑

6. 注意边界条件处理

LNode *getElem(LinkList linkList, int i) {
    LNode *node = NULL;
    if (NULL == linkList) {
        return node;
    }
    node = linkList;
    while (node != NULL && i > 0) {
        node = node->next;
        i--;
    }
    return node;
}


LNode *locateElem(LinkList linkList, int e) {
    LNode *node = NULL;
    node = linkList;
    while (node != NULL) {
        if (node->data == e) {
            return node;
        }
        node = node->next;
    }
    return node;
}


int length(LinkList linkList) {
    int length = 0;
    LNode *node = linkList;
    //有next才加1(初始化头结点不算入进来)
    while (node->next != NULL) {
        node = node->next;
        length++;
    }
    return length;
}

步骤：

1. 初始化一个单链表
2. 每次取一个数据元素，插入到表尾或表头

LinkList listTailInsert(LinkList *linkList, int data) {
    int x;
    *linkList = (LinkList) malloc(sizeof(LNode));
    (*linkList)->data = data;
    (*linkList)->next = NULL;
    LNode *s = NULL;
    LNode *r = *linkList;
    //下列写法s不会赋值
    //LNode *s,*r = *linkList;
    scanf("%d", &x);
    while (x != -1) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return *linkList;
}


LinkList listHeadInsert(LinkList *linkList, int data) {
    int x = 0;
    *linkList = (LinkList) malloc(sizeof(LNode));
    (*linkList)->data = data;
    (*linkList)->next = NULL;
    LNode *s;
    scanf("%d", &x);
    while (x != -1) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        s->next = (*linkList)->next;
        (*linkList)->next = s;
        scanf("%d", &x);
    }
    return *linkList;
}

头插法，尾插法：核心就是初始化操作、指定节点的后插操作

tips：尾插法注意设置一个尾指针tip