简单的总结一下数据结构中的线性表

顺序存储

  • ElemType *elem;
    int length;
  • 随机存取
  • 判断
    • 位置合理
    • 存储空间已满
  • 查找,插入,删除 ⇒ 时间复杂度 O(n)

单链表

  • ElemType data; struct LNode *next;
  • 数据域 & 指针域
  • 头节点
    • 首元结点无需特殊区分
    • 空表和非空表统一判断标准
  • 判断
    • 当前指针 or 下个指针存在
    • 链表为空
  • 查找前驱 O(n)

循环链表

  • 判断尾 p→next == L 而不是 p→next == NULL
  • 使用尾指针更方便合并 ⇒ 尾指针下一个为头结点

双向链表

  • ElemType data; struct DuLNode *prior; struct DuLNode *next;
  • 增删需要同时修改 prior 和 next

空间性能

  • 顺序表要预先分配 ⇒ 易浪费 & 溢出
  • 指针域 ⇒ 存储密度小 ⇒ 长度有限且事先确定大小时,用顺序表

时间性能

  • 顺序表取值效率高
  • 链表插入删除效率高

Tips

  • 特殊点的排除 ⇒ 极端情况(空链表全部)
    判断 NULL, while 条件
  • segmentation fault
    →next 是否存在,下标越界,有没有malloc
  • 存在头节点
    不能倒过来print,会 print 出头结点的值
  • C语言中,没有true,不能 while(true)
  • 就地反转 两个指针,提前记录 next,再从当前指向前一个
  • while(p) { p = p→next; } 遍历

程序

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

typedef int ElemType;

//链表结构体定义
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化链表
LinkList InitList(){
    LNode *L;
    L = (LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}

void PrintList(LinkList L) {
    if(L->next == NULL) {
        return;
    } else {
        LNode *p = L->next;
        while (1) {
            printf("%d", p->data);
            if (p->next != NULL) {
                printf(" ");
                p = p->next;
            } else {
                break;
            }
        }
    }
}

void CreateList(LinkList L)
{
    L->next = NULL;
    LNode *r;
    r = L;
    ElemType x;

    while(1) {
        scanf("%d",&x);
        if(x == -1) {
            break;
        }
        LNode *p;
        p = (LNode *)malloc(sizeof(LNode));
        p->data = x;
        r->next = p;
        r = p;
    }
    r->next = NULL;
}

int length(LinkList L) {
    LNode *p = L->next;
    int length = 1;
    while(p->next) {
        p = p->next;
        ++length;
    }
    return length;
}

Click Here To View DataStructure Section

Tagged in:

, ,

About the Author

XFish

Fisher不钓鱼 川大21级在读 网络空间安全专业 7年前的围棋业余5段 素描彩铅水粉国画书法童子功拥有者 PG13?? Mamba4ever✊? ?Beginner Mahomes/KC Chiefs/NFL 爱好者? nparadigm申工智能yyds?️ 飞禽岛少年Lee Sedol’s fan?

View All Articles