线性表

  1. 线性表的定义：相同数据类型、有限、序列（有前驱与后继）。
  2. 线性表由相同数据类型的有限数据元素组成，数据元素由数据项组成。

顺序表

  1. 分为1-静态分配存储空间；2-动态分配存储空间。
  2. 优缺点
    • 随机访问，存储密度高
    • 插入、删除难，不够灵活

链表

  1. 结点类型描述
1
2
3
4
typedef struct LNode{
    ElementType data,
    struct LNode *next,
}LNode,*LinkList
- LNode *L 等价于 LinkList L
  1. 头结点与头指针的关系

头指针始终指向链表中第一个节点，头节点时带头节点链表中第一个结点，通常不存储信息。

  1. 引入头结点所带来的好处
  • 统一了空表与非空表操作
  • 在链表第一个位置上的操作与其他位置一致
  1. 单链表的初始化
1
2
3
4
5
6
7
8
9
10
11
/*
说明：初始化链表，返回头节点
*/ 
LinkList InitList() {
    LinkList L = (LNode*)malloc(sizeof(LNode));  // 创建头节点
    if (L != NULL) {
        L->next = NULL;  // 初始化头节点的next为NULL
        L->data = 0;
    }
    return L;
}

注意

若p为指针，可用p->data或者(*p).data访问这个节点的数据域

  1. 求表长（有头结点）
1
2
3
4
5
6
7
8
int length(LinkList L){
    int length = 0 ;
    LinkList q = L;//防篡改
    while(q->next != null){
        length++;
        q = q->next;
    }
}
  1. 按照值查找节点
1
2
3
4
5
6
7
LinkList GetElem(LinkList L,int i){
    LinkList q = L->next;
    while(q->data != i && q != null){
        q = q->next;
    }
    return q;
}
  1. 按照位序（序号）查找节点
1
2
3
4
5
6
7
8
9
LinkList GetElem(LinkList L,int pos){
    LinkList q = L;
    int j = 0 ; //头结点是第零个节点
    while(j < pos && q!=null){
        q = q->next;
        j++;
    }
    return q;
}
  1. 插入
1
2
3
4
5
6
//若新结点为s，则其关键算法为
//顺序不能颠倒
s->data = e;
s->next = p->next;
p->next = s;