《数据结构高分笔记》线性表

男娘i 2024-05-08 06:04 69阅读 0赞

#### 目录 ####

*   *   *   *  例题2-1 有序顺序表的插入，删除元素
             *  例2-3 有序链表的合并，头插法，尾插法
             *  例2-4 查找某一元素是否存在，若存在删除，返回1，不存在返回0
             *  真题仿照1 一个数组分段有序，进行排序，类似于插入排序
             *  顺序表逆置
             *  删除链表中的重复元素

##### 例题2-1 有序顺序表的插入，删除元素 #####

思路：先找到插入位置，然后将后面的元素依次向后移动一位，最后将目标元素赋值，注意长度的加一；

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int maxn = 1000;
    
    //顺序表的结构体定义
    typedef struct {
        
         int data[maxn];
         int length;
    }Sqlist;
    //使用typedef定义结构体，最后这个Sqlist是类型名，而不是变量名；
    //如果只使用struct则是变量名
    
    Sqlist sqlist;
    
    //指定位置插入元素，1插入成功，0插入失败
    int insertElem(Sqlist &L, int p, int e){
        
         //判断插入位置是否合法
         if(p < 0 || p > L.length || L.length == maxn)
              return 0;
         //移动后边元素
         for(int i = L.length - 1; i >= p; i --){
        
              L.data[i + 1] = L.data[i];
         }
         L.data[p] = e;
         L.length ++;//长度加1
         return 1;
    }
    
    //指定位置删除元素，1删除成功，0删除失败
    int deleteElem(Sqlist &L, int p){
        
         //判断删除位置是否合法
         if(p < 0 || p >= L.length)
              return 0;
         //后边元素向前移动一位，相当于删除
         for(int i = p + 1; i < L.length; i ++){
        
              L.data[i - 1] = L.data[i];
         }
         L.length --;//长度减1
         return 1;
    }
    
    //向有序顺序表中插入一个元素，仍保证有序
    void insertElement(Sqlist &L, int x){
        
         //找到插入位置
         int i = 0;
         while(x > L.data[i] && i < L.length) i ++;//注意不要越界，考虑在末尾插入的情况
         //将后边元素移动一位
         for(int j = L.length - 1; j >= i; j --){
        
              L.data[j + 1] = L.data[j];
         }
         //赋值
         L.data[i] = x;
         L.length ++;//长度加一
    }
    
    void show(){
        
         for(int i = 0; i < sqlist.length; i ++){
        
              printf("%d ", sqlist.data[i]);
         }
         printf("\n");
    }
    
    int main()
    {
        
        int n, t, e;
        scanf("%d", &n);
        sqlist.length = 0;//初始化
        for(int i = 0; i < n; i ++){
        
              scanf("%d%d", &t, &e);
              insertElem(sqlist, t, e);//插入元素
        }
        show();
        //从小到大排序
        sort(sqlist.data, sqlist.data + n);
        show();
        scanf("%d", &t);
        //有序表插入一个元素
        insertElement(sqlist, t);
        show();
        //删除一个元素
        deleteElem(sqlist, 2);
        show();
        return 0;
    }

##### 例2-3 有序链表的合并，头插法，尾插法 #####

有序链表的合并核心需要记录两个链待处理元素的位置，以及最终链尾结点的位置；  
如果需要从大到小排列，则用头插法合并，但是最后多余链的元素必须一个个插入；  
如果需要从小到大排列，则用尾插法合并，最后多余链的元素一次操作就可以；  
头插法需要记录每次插入元素的指针，不需要记录链尾结点的指针；  
尾插法除了需要记录每次插入元素的指针，还需要记录链尾结点的指针，用于插入；  
查完所有元素要赋空；

#include <iostream>
    #include <algorithm>
    #include <memory>
    using namespace std;
    
    const int maxn = 1000;
    
    //单链表结点定义
    typedef struct LNode{
        
         int data;
         struct LNode *next;
    }LNode;
    LNode *ans1, *ans2, *res;//notice signal *
    //有序链表的合并，重点是需要记录每个链待处理元素的位置和最终链末尾结点的位置
    void mergeList(LNode *A, LNode *B, LNode *&C){
        
         LNode *p = A->next, *q = B->next;//分别用来记录两个链的待处理元素的位置
         LNode *r ; //指向C链中末尾结点
         C = A;//利用A的头结点
         C->next = NULL;//带头结点的初始化为空
         r = C;//r初始化到末尾节点
         free(B);//把B头结点释放掉，唯一释放的一个节点
         //迭代结束条件两个链有一个为空
         while(p != NULL && q != NULL){
        
              if(p->data <= q->data){
        
                   r->next = p;//把p所指的值接在后面
                   r = r->next;
                   p = p->next;
              }
              else{
        
                   r->next = q;
                   r = r->next;
                   q = q->next;
              }
         }
         r->next = NULL;//可以去掉，下边两句肯定有一个会执行
         if(p != NULL) r->next = p;
         else r->next = q;
    }
    //tail insert of link list
    void insertListR(LNode *&A, int a[], int n){
        
         LNode *r, *s; //r refer to tail, s refer to element which will be inserted
         A = (LNode *)malloc(sizeof(LNode));//allocate head element memory for A
         A->next = NULL;//initialize to NULL
         r = A;
         for(int i = 0; i < n; i ++){
        
              s = (LNode *)malloc(sizeof(LNode));
              s->data = a[i];//initialize data of s
              r->next = s;//insert s to the end of A
              r = r->next;//move r to next position
         }
         r->next = NULL;//mark to NULL after insert
    }
    //head insert of link list
    void insertListF(LNode *&A, int a[], int n){
        
         LNode *s;//just need point of insert element
         A = (LNode *)malloc(sizeof(LNode));
         A->next = NULL;
         for(int i = 0; i < n; i ++){
        
              s = (LNode *)malloc(sizeof(LNode));
              s->data = a[i];
              s->next = A->next;
              A->next = s;
         }
         //no more need initialize NULL
    }
    void show(LNode *p){
        
         p = p->next;
         while(p != NULL) {
        
              printf("%d ", p->data);
              p = p->next;
         }
         printf("\n");
    }
    int main()
    {
        
         int a[5] = {
        1, 3, 5, 7};
         int b[5] = {
        8, 6, 4, 2};
         insertListR(ans1, a, 4);
         show(ans1);
         insertListF(ans2, b, 4);
         show(ans2);
         mergeList(ans1, ans2, res);
         show(res);
         return 0;
    }

##### 例2-4 查找某一元素是否存在，若存在删除，返回1，不存在返回0 #####

删除元素时需要记录前驱，所以在前一个结点就判断其后一个结点是不是目标值，当指针指向最后一个元素后就停止，不用检查其值，因为在前一个元素已经检查过了；

//record precursor when delete
    int findAndDelete(LNode *C, int x){
        
         LNode *p, *q;
         p = C;
         //loop until p point last elem
         while(p->next != NULL){
        
              //judge before elem
              if(p->next->data == x) break;
              p = p->next;
         }
         if(p->next == NULL) return 0;
         else{
        
              q = p->next;
              p->next = p->next->next;//assignment
              free(q);
         }
         return 1;
    }

##### 真题仿照1 一个数组分段有序，进行排序，类似于插入排序 #####

依次处理下标从 m 到 n + m - 1的元素，处理每个元素时向前找到合适的插入位置；

//sort two order sub array, likely insert sort
    void insertElem(int A[], int m, int n){
        
         int temp;
         for(int i = m; i < m + n; i ++){
        
              temp = A[i];//record element of this loop handle
              int j = i - 1;
              //elem move backward a position
              while(j >= 0 && A[j] > temp) {
        
                   A[j+1] = A[j];
                   j --;
              }
              A[j + 1] = temp;
         }
    }

##### 顺序表逆置 #####

//reverse all elem in Sq-list
    void reverseElem(int a[], int n){
        
         int temp;
         for(int i = 0, j = n - 1; i < j; i ++, j --){
        
              temp = a[i];
              a[i] = a[j];
              a[j] = temp;
         }
    }
    int main()
    {
        
         int a[10] = {
        1, 3, 5, 7, 2, 4, 6, 8};
         int b[5] = {
        8, 6, 4, 2};
         reverseElem(a, 8);
         showArray(a, 8);
         return 0;
    }

##### 删除链表中的重复元素 #####

定义两个指针p, q; p指向已知的不重复链表元素的末尾，q依次指向待处理元素；用一个额外变量former存储上一次不重复的值，如果q所指元素等于former，说明q所指元素重复，应该删除；如果q所指元素不等于former，说明元素不重复，q和p都向后移一位，同时修改former的值；

void deleteLoopElem(LNode *A){
        
         LNode *p, *q, *t;//p point former elem, q point elem which be handled
         int former = -1;
         p = A, q = A->next;
         while(q != NULL){
        
              //if not same with former,change former value, continue move to next
              if(q->data != former){
        
                   former = q->data;
                   p = q;//p move backward
                   q = q->next;
              }
              //if same with former,delete current elem,continue move to next
              else{
        
                  t = q;
                  p->next = q->next;//modify p->next, but p is no change
                  q = q->next;
                  free(t);
              }
         }
    }