线性表

引入

多项式的表示

关键信息：项数，系数及指数i

顺序存储

数组的每个分量是系数与指数对应的二元组

链表存储

每个节点存储系数与指数，指针指向下一个节点

顺序存储实现

数组实现

利用数组的连续存储空间来存放线性表的各种元素

struct ListNode {
    ElementType Data[MAXSIZE];
    int last;
};

data存放数据，last指示最后一个有效元素的位置

两种查找方式：

1. 定义结构体指针

ListNode *Ptrl;
ptrl->Data[i];

2. 定义结构体对象

ListNode list;
list.Data[i];

所有数据都存放在这一个结构体中

这种存储方式查找很简单，但插入和删除很不方便，需要挪动很多元素

结构体数组实现

数组元素即是结点，所以只需要用id表示结点位置,now指示有效元素下一个。

单向

const int MAXSIZE = 10000;
struct node{
    int id;
    int data;
    int nextid;
}nodes[N];

双向

const int MAXSIZE = 10000;
struct node{
    int id;
    int preid;
    int data;
    int nextid;
}

插入删除类似

可以使用node在nodes中的下标作为node的id，所以可以省掉id这个变量。

初始化

令nodes[0]和nodes[1]相互指，后续添加的node在这两个结点中间。这样链表id一定以0开始以1结束

void init() {
    nodes[0].nextid = 1;
    nodes[1].preid = 0;
    now = 2;
}

遍历

for(int i = nodes[0].nextid; i != 1; i=nodes[i].nextid){
    pass;
}

链式存储实现

不要求逻辑相邻的元素物理上相邻，用过链建立联系

struct ListNode {
    ElementType Data;
    ListNode *next;
};
ListNode *Ptrl;

主要操作

求表长

p不为空时循环，计数器加一

int length(ListNode *ptrl) {
    ListNode *p = ptrl;
    int count = 0;
    while (p) {
        p = p->next;
        count++;
    }
    return count;
}

查找

按序号

查找序号为k的元素

p不等于空（链表没结束）和i<k时循环，p指向下一个，i++，循环结束就有两种情况：

1. p为空，此时i != k，意味着链表结束，返回NULL
2. i==k，返回p

ListNode *FindKth(int k, ListNode ptrl) {
    ListNode *p = prtl;
    int i = 1;
    while (p != NULL && i < k) {
        p = p->next;
        i++;
    }
    //两种情况
    if (i == k) {
        return p;
    } else {
        return NULL;
    }
}

按值

p不等于空且Data不等于key时循环，结束也是两种情况

1. p为空，没找到，返回p
2. 找到了，返回p

ListNode *Find(int key, ListNode ptrl) {
    ListNode *p = ptrl;
    while (p != NULL && p->Data != key) {
        p = p->next;
    }
    return p;
}

共同点

循环使p不断向下指，循环条件记得有链表未结束，即p不等于空

判断一下循环结束后的情况

插入

1. 构造新节点，用s指向
2. 找到链表的第k-1个节点，用p指向
3. 修改指针，插入s

              1. s指向p->next
                    2. p->next指向s
   

4. 返回链表头指针

如果插入的位置是链表头则做特殊处理，注意p指向空的情况。

ListNode *insert(int x, int i, ListNode *ptrl) {
    ListNode *p, s;
    if (i == 1) {
        s = (ListNode *) malloc(sizeof(struct ListNode));
        s->Data = x;
        s->next = prtl;
        return s;
    }
    p = FindKth(i - 1, ptrl);
    if (p == NULL) {
        return NULL;
    } else {
        s = (ListNode *) malloc(sizeof(struct ListNode));
        s->Data = x;
        s->next = p->next;
        p->next = s;
        return ptrl;
    }
}

删除

删除下标为i的结点s

1. 找到第i-1个结点p
2. s指向被删除元素
3. p->next指向s->next
4. free(s)
5. 返回头指针

若i==1

1. s=ptrl
2. ptrl指向ptrl的next
3. free(s)

因为要的free，所以第一步的赋值是必要的

ListNode *delete(int i, ListNode ptrl) {
    ListNode p, s;
    if (i == 1) {
        s = ptrl;
        if (ptrl != NULL) {
            ptrl = ptrl->next;
        }
        free(s);
        return ptrl;
    }

    p = FindKth(i - 1, ptrl);
    if (p == NULL) {
        return NULL;
    } else if (p->next == NULL) {
        return NULL;
    } else {
        s = p->next;
        p->next = s->next;
        free(s);
        return ptrl;
    }
}

插入删除共同点

1. 对链表头进行操作时均需特殊处理
2. p使用FindKth函数指向操作对象前一个节点
3. 注意p为空的情况

STL-list

是双向链表

1. 定义

   listnode;
   

2. 赋值

   node.push_back(value);
   

3. 遍历

   使用it迭代器

   list::iterator it = node.begin();
   while(node.size()>1){
       it++;
       pass;
   }
   

   it相当于指向链表元素的指针

4. 删除

   node.erase(it);
   

5. 插入

   node.insert(it,value);
   

广义表和多重链表

广义表

是线性表的推广。

线性表的元素都是基本的单元素

广义表的元素还可以是另一个广义表

组成：

1. tag，0表示存的是单元素，1表示存的是广义表
2. 子表指针域和单元素数据与复用，使用共用体
3. next结构体指针

struct gNode {
    int tag;//标志域：0单元素，1广义表
    union {
        ElementType Data;
        gNode *subList;
    };
    gNode* next;
}    

多重链表

结点可同时隶属于多个链

指针会有多个

包含多个指针域不一定是多重链表

查找操作的优化

插入n个结点复杂度是O(n^2)，容易超时

可以额外创建一个迭代器类型的数组loc来定位值为x的结点存在哪个位置上

list::iterator loc[MAXSIZE];

loc[x]=iterator就表示值为x的结点存放在iterator所指的地址中。

这样当需要查找值为x的结点只需要:

iterator = loc[x];

成功将查找所需的O(n)变成了O(1)

例题

算法描述

对于第一辆以后的每一辆车的xyz：

1. 找到链表中值为y的位置
2. 1就把x插入右边，0就把x插入左边

STL实现

1. 初始化

   list L;
   scanf("%ld %ld",&n,&x);
   L.push_back(x);         //插入刚开始编号
   loc[x] = L.begin();     //迭代器地址存入数组
   list::iterator temp;
   

2. 对于每一辆车

   1. 输入

      cin>>a>>b>>c;//a,b,c就是x,y,z
      temp = loc[b];
      

   2. 判断

      1. c==0

      L.insert(temp,a);
      loc[a] = --temp;
      

      2. c==1

      L.insert(++temp,a);
      loc[a] = --temp;
      

3. 输出链表

   for(list::iterator it=L.begin();it!=L.end();it++){
       cout<<*it<<" ";
   }
   

手写链表

使用结构体数组实现比较简单

1. 定义结构体数组和定位数组

   struct node{
       int id;
       int perid;
       int nextid;
       int data;
   }nodes[N];
   int loc[N];
   int now = 0;//指示有效元素下一个
   

2. 实现双向链表基本操作

   初始化：所有的元素都插入到nodes[0]和nodes[1]之间，这样这个链表一定是以id为0开始，id为1结束

   void init(){
       nodes[0].nextid = 1;
       nodes[1].perid = 0;
       now = 2;
   }
   

   插入：把a插到k右边

   void insert(int k, int a) {
       nodes[now].data = a;
       loc[a] = now;
       nodes[now].nextid = nodes[k].nextid;
       nodes[nodes[k].nextid].preid = now;
       nodes[k].nextid = now;
       nodes[now].preid = k;
       now++;
   }
   

3. 运算

   1. 初始化

      int n;
      cin >> n;
      init();
      int a;
      cin >> q;
      insert(0,a);
      n--;
      

   2. 根据输入插入元素

      while(n--){
          int x,y,z;
          cin >> x,y,z;
          if(z == 0){
              insert(nodes[loc[y]].perid, x);
          }else{
              insert(locate[y],x);
          }
      }
      

   3. 输出链表

      for(int i=nodes[0].nextid;i!=1;i=nodes[i].nextid){
          cout << nodes[i].data << " ";
      }