博客

02 线性表 | 数据结构与算法

  • Post category:C++

1. 线性表

  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)
  2. 线性表的存储结构设计

    1. 连续存储结构(数组)

      1. 存储方式：依次将元素存放进连续的存储空间中
      2. 顺序表示： \(loc(a_i) = loc(a_1)+(i-1)*c\)
      3. 存储特点：逻辑上相邻的元素，物理结构上也相邻
      4. \(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. 优点
          1. 顺序表的存储结构简单
          2. 随机存储，按位置取值速度快
          3. 存储效率高，无需增加逻辑关系的占用空间
        2. 缺点
          1. 删除插入速度慢
          2. 预先分配内存大

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

  1. 链式存储结构

    1. 存储方式：用一组任意的存储单元存储线性表中的数据元素，通过每个结点的指针将数据元素连接在一起
    2. 单链表：具有一个指针，指向后继元素
    typedef struct Node{
    datatype data;
    struct Node *next;
}Node , *head;
    1. \(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;
}
    1. 双链表：前驱指针 *prev 和后继指针 *next
    2. \(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;

    image

    // 3. 删除元素
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
  • 连续设计和连接设计的对比
    Parameters 连续设计 链接设计
    表的容量 固定，不易扩充 灵活，易扩充
    存取操作 随机访问存取，速度快 顺序访问存取，速度慢
    时间 插入、删除操作费时间 访问元素费时间
    空间 估算长度，浪费空间 实际长度
  1. 链接存储设计的数组实现
    data next
    data1 1
    2
    \(\cdots\) \(\cdots\)
    max_size – 1
    -1
    1. 结点：
    #define max_size 1024    \\数组最大容量
typedef int datatype;
typedef int cursor;
typedef struct{
 datatype data;
 cursor next;
}node;

node nodepool[max_size];     // 存储池（数组）
cursor avail;    // 空闲空间的位置
    1. 初始化
    for(int i=0; i < max_size - 1; i++){
     nodepool[i].next = i + 1;
}
nodepool[max_size - 1].next = -1;
avail = 0;   //avail 初始化
    1. 结点 node 的分配
    cursor getNode(){
     cursor p;
     if(avail == -1) p = -1;
     else {
         p = avail;
         avail = nodepool[avail].next;
     }
     return p;
 }
    1. 结点 node 的回收
    void freeNode(cursor p){
     nodepool[p].next = avail;
     avail = p;
}
    1. 静态链表查找算法
    cursor findNode(cursor L , int i){
     cursor p = L;
     int j = 0;
     while(nodepool[p].next != -1 && (j < i>)){
         p = nodepool[p].next;
         ++j;
     }
     if(i == j) return p;
     else return -1;
}

2. \(Applications\)

  1. 合并有向链表

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* preHead = new ListNode(-1);

	ListNode* prev = preHead;
	while (l1 != nullptr && l2 != nullptr) {
		if (l1->val < l2->val) {
			prev->next = l1;
			l1 = l1->next;
		} 
		else {
			prev->next = l2;
			l2 = l2->next;
		}
		prev = prev->next;
	}

	prev->next = (l1 == nullptr) ? l2 : l1;// 合并剩余链表
	return preHead->next;
}

  2. 反转链表

    1. 就地反转
    graph LR
    A(head)-.->B(nextp)
    B–>C(cur)
    C–> D(p)
    D-.->E(NULL)

    反转箭头为：

    graph LR
    A(head)-.->B(nextp)
    B-.->C(cur)
    C==>B
    C–> D(p)
    D-.->E(NULL) 
     ListNode* reverseList(ListNode* head) {
 	if(head == nullptr) return head;
 	ListNode* nextp = nullptr;
 	ListNode* cur = head;
 	ListNode* p = head -> next;
 	while(p){
 		cur -> next = nextp;
 		nextp = cur;
 		cur = p;
 		p = cur -> next;
 	}
 	cur -> next = nextp;
 	return cur;
 }
    1. 递归：处理好 k之后，将 k-1 的箭头倒转；
    graph LR
    A(1)–>B(2)
    B-.-C(k -1)
    C-.-> D(k)
    D==>C
    E(k+1)–>D
    F(n)-.->E 
    ListNode* reverseList(ListNode* head) {
    if(!head || !(head -> next)) return head;
    ListNode* new_Head =  reverseList(head -> next);
    head -> next -> next = head;
    head -> next = nullptr;
    return new_Head;
}
Tags: