1. 线性表

线性表的定义
1. 特点：
  1. 存在唯一一个被称为第一个的数据元素
  2. 存在唯一一个被称为最后一个的数据元素
  3. 除了第一个元素之外，其他的数据元素都有唯一一个直接前驱
  4. 除了最后一个元素之外，其他的数据元素都有唯一一个直接后驱
2. 定义：是由 \(n(n\ge 0)\) 个相同数据类型的数据元素组成的有限序列
3. 逻辑特征
  1. 有限性：数据元素的个数是有限的
  2. 相同性：数据元素的元素类型是相同的
  3. 相继性（线性性）：\(a_1\) 为表中的第一个元素，无前驱元素，\(a_n\) 为表中最后一个元素，无后驱元素；对于 \(1<i<n\) ， \(a_{i-1}\) 为 \(a_{i}\) 的直接前驱， \(a_{i+1}\) 为 \(a_{i}\) 的直接后驱
4. 基本操作 \(Operations\)
  1. 求线性表的长度 Lenlist(L)
  2. 获取线性表中的元素 GetElem(L , i)
  3. 通过值来查找线性表当中的元素 SearchElem(L , Val)
  4. 插入元素 InsertElem(L , i , Elem)
  5. 删除元素 DeleteElem(L , i)

线性表的存储结构设计

连续存储结构(数组)

存储方式：依次将元素存放进连续的存储空间中
顺序表示： \(loc(a_i) = loc(a_1)+(i-1)*c\)
存储特点：逻辑上相邻的元素，物理结构上也相邻
\(Operations\)

// 1. 插入元素 O(n)
int insertElem(list *L , Datatype x , int i){
    if((*L).last >= maxsize - 1){   //overflow
        printf("Overflow\n");
        return -1;
    }
    else if(i < 1 || i > (*L).last + 1){    //wrong location
        printf("Error\n");
        return -1;
    }
    else{
        for(int j = (*L).last ; j >= i ; --j){  //move the elements
            (*L).data[j + 1] = (*L).data[j];
        }
        (*L).data[i] = x;
        (*L).last++;
    }
    return 1;
}

// 2. 删除元素 O(n)
int deleteElem(list *L , int i){
    if(i < 1 || i > (*L).last + 1){    //wrong location
        printf("Error\n");
        return -1;
    }
    else {
        for(int j = i ; j <= (*L).last ; ++j){
            (*L).data[j - 1] = (*L).data[j];
        }
        (*L).last--;
    }
}

// 3. 按值查找 O(n)
int searchElem(list *L , Datatype x){
    int i = 1;
    while(i <= (*L).last && x != (*L).data[i - 1]){
        ++i;
    }
    if(i <= (*L).last) return i - 1;
    return -1;  //can not find
}

// 4. 按位置查找 O(1)
int getElem(list *L , int i){
    if(i < 1 || i > (*L).last + 1){    //wrong location
        printf("Error\n");
        return -1;
    }
    return (*L).data[i - 1]
}

连续存储的优缺点
1. 优点
  1. 顺序表的存储结构简单
  2. 随机存储，按位置取值速度快
  3. 存储效率高，无需增加逻辑关系的占用空间
2. 缺点
  1. 删除插入速度慢
  2. 预先分配内存大

\(\quad\)
\(存储效率 = \frac{数据元素占用空间}{数据元素占用空间+逻辑关系占用空间}\)
\(\quad\)

链式存储结构

存储方式：用一组任意的存储单元存储线性表中的数据元素，通过每个结点的指针将数据元素连接在一起
单链表：具有一个指针，指向后继元素

typedef struct Node{
    datatype data;
    struct Node *next;
}Node , *head;

\(Operations\)

// 1. 建立单链表
void createList(){
    Node head = new Node();
    head->next = NULL;
}

// 2. 插入元素
int insertList(Node &L , int i , datatype x){
    Node *p = head;
    int j = 0;
    while(p && j < i - 1){
        p = p->next;
        j++;
    }
    if(!p) return -1;
    Node *temp = new Node;
    temp->data = x;     // insert
    temp->next = p->next;
    p->next = temp;
    return 1;
}

// 3. 删除元素
int deleteList(Node &L , int i){
    Node *p = head;
    int j = 0;
    while((p->next) && j < i - 1){
        p = p->next;
        j++;
    }
    if(!(p->next)) return -1;
    Node *temp = p->next;
    p->next = temp->next;
    delete temp;
    return 1;
}

// 4. 通过位置查找元素
datatype getList(Node &L , int i){
    Node *p = head;
    int j = 0;
    while(p && j < i - 1){
        p = p->next;
        j++;
    }
    if(!p) return -1;
    return p->data;
}

// 5. 通过值来查找元素
int searchList(Node &L , datatype x){
    Node *p = head;
    int j = 0;
    while(p && p->data != x){
        p = p->next;
        ++j;
    }
    if(!p) {
        printf("Not Find!");
        return -1;
    }
    return j;
}

双链表：前驱指针 *prev 和后继指针 *next
\(Operations\) 要处理两个指针

// 1. 初始化
typedef struct DulNode{
    datatype data;
    struct DulNode *prev , *next;
}DulNode , *head;

// 2. 插入元素(先右后左)
s->data = _data;
s->next = p->next;
p->next->prev = s;
p->next = s;
s->prev = p;

// 3. 删除元素
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

连续设计和连接设计的对比

Parameters	连续设计	链接设计
表的容量

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：驱动开发：内核字符串拷贝与比较	下一篇：c++ string 类和 c 风格 string ..