线性表

1. 概念

线性表是具有相同特性的数据元素的一个有限序列。

1.1. 逻辑特征

线性表中的元素位置是有序的，这种位置关系构成了一种线性关系，因此线性表是一个线性结构，即对于至少含有一个数据元素的线性表，除起始元素外均有且仅有一个前驱，除终端元素外均有且仅有一个后继。若线性表中的元素按照某种顺序排列，则称该线性表为有序表。

1.2. 存储结构

有顺序和链式两种存储结构，分别称为顺序表和链表。链表的每个节点包含数据域和指针域，第一个节点的存储位置称为头指针，如果链表带有头结点，那头指针为头结点的地址，否者为起始节点。

2. 顺序表

定义

#define MaxSize 50
typedef struct
{
  ElemType data[MaxSize];
  int length;
}SqList;

初始化顺序表

void InitList(SqList &L)
{
  L.length = 0;
}

求指定位置元素

int GetElem(SqList L, int i, ElemType &e)
{
  if(i < 1 || i > L.length)
    return 0;
  e = L.data[i-1];
  return 1;
}

按元素查找

int LocateElem(SqList L, int &n, ElemType e)
{
  if(L == NULL)
    return 0;
  int i = 0;
  while(L.data[i] != e && i < L.length)
    i++;
  if(i == L.length)
    return 0;
  n = i+1;
  return 1;
}

插入数据元素（插到第 i 个位置上）

int ListInsert(SqList &L, ElemType e, int i)
{
  if(i < 1 || i > L.length+1)
    return 0;
  L.length++;
  int j;
  for(j = L.length-1; j >= i; j--)
    L.data[j] = L.data[j-1];
  L.data[j] = e;
  return 1;
}

删除数据元素

int ListDelete(SqList &L, int i, ElemType &e)
{
  if(i < 1 || i > L.length)
    return 0;
  e = L.data[i-1];
  for(int j = i-1; j < L.length-1; j++)
    L.data[j] = L.data[j+1];
  L.lenght--;
  return 1;
}

有序顺序表的归并算法

void MergeList(SqList L1, SqList L2, SqList &L3)
{
  int i = 0, j = 0, k = 0;
  while(i < L1.length && j < L2.length){
    if(L1.data[i] < L2.data[j]){
      L3.data[k] = L1.data[i];
      k++; i++;
    }else if(L1.data[i] > L2.data[j]){
      L3.data[k] = L2.data[j];
      k++; j++;
    }else{
      L3.data[k] = L1.data[i];
      k++; i++; j++;
    }
  }
  while(i < L1.length){
    L3.data[k] = L1.data[i];
      k++; i++;
  }
  while(j < L2.length){
    L3.data[k] = L1.data[j];
      k++; j++;
  }
  L3.length = k;
}

3. 单链表

定义

typedef struct LNode{
  ElemType data;
  LNode *next;
}LinkList;

头插法建立单链表（次序与原来次序相反）

void CreateListF(LinkList *&L, ElemType a[], int n)
{
  LinkList *s; int i;
  L = (LinkList *)malloc(sizeof(LinkList)); //创建头结点
  L->next = NULL;
  for(i = 0, i < n, i++){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = a[i];
    s->next = L->next;
    L->next= s;
  }
}

尾插法建立单链表（次序与原来次序相同）

void CreateListR(LinkList *&L, ElemType a[], int n)
{
  LinkList *s, *r; int i;
  L = (LInkList *)malloc(sizeof(LinkList));
  L->next = NULL;
  r = L;
  for(i=0, i<n, i++){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = a[i];
    r->next = s;
    r = s;
  }
  r->next = NULL;
}

按元素查找

int LocateElem(LinkList *L, ElemType e)
{
  LinkList *p = L->next;
  int i = 1;
  while(p!=NULL && p->data!=e){
    p = p->next;
    i++;
  }
  if(p==NULL)
    return 0;
  else
    return i;
}

将 e 插入到单链表的第 i 个节点位置上

int InsertElem(LinkList *&L, ElemType e, int n)
{
  LinkList *p = L, *s; // p 为第一个节点位置的前一个节点
  int j = 0;
  while(p!=NULL && j<n-1){
    p = p->next;
    j++;
  }
  if(p!=NULL){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
  }
  else
    return 0;
}

删除第 i 个节点位置上的元素

int DeleteElem(LinkList *&L, ElemType &e, int n)
{
  LinkList *p = L, *q; // p 为第一个节点位置的前一个节点
  int j = 0;
  while(p!=NULL && j<n-1){
    p = p->next;
    j++;
  }
  if(p!=NULL && p->next!=NULL){
    q = p->next;
    p->next = q->next;
    free(q);
    return 1;
  }
  else
    return 0;
}

有序单链表的归并（新建单链表）

void MergeList1(LinkList *L1, LinkList *L2, LinkList *&L3)
{
  LinkList *s1 = L1->next, *s2 = L2->next, *r, *s;
  L3 = (LinkList *)malloc(sizeof(LinkList));
  L3->next = NULL;
  r = L3;

  while(s1!=NULL && s2!=NULL){
    if(s1->data < s2->data){
      s = (LinkList *)malloc(sizeof(LinkList));
      s->data = s1->data;
      r->next = s;
      r = s; s1 = s1->next;
    }else if(s1->data > s2->data){
      s = (LinkList *)malloc(sizeof(LinkList));
      s->data = s2->data;
      r->next = s; s2 = s2->next;
      r = s;
    }else{
      s = (LinkList *)malloc(sizeof(LinkList));
      s->data = s1->data;
      r->next = s;
      r = s; s1 = s1->next; s2 = s2->next;
    }
  }
  if(s2!=NULL)
    s1 = s2;
  while(s1!=NULL){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = s1->data;
    r->next = s;
    r = s; s1 = s1->next;
  }
  r->next = NULL;
}

有序单链表的归并（要求空间复杂度为 O(1) ，即舍弃原来的两个单链表）

void MergeList(LinkList *L1, LinkList *L2, LinkList *&L3)
{
  LinkList *p = L1->next, *q = L2->next;
  L3 = (LinkList *)malloc(sizeof(LinkList));
  L3 = L1;
  free(L2);
  r = L3;
  while(p!=NULL && q!=NULL){
    if(p->data < q->data){
      r->next = p;
      p = p->next;
    }
    else if(p->data > q->data){
      r->next = q;
      q = q->next;
    }
    else{
      r->next = p;
      p = p->next;
      q = q->next;
    }
  }
  if(q!=NULL)
    p = q;
  r->next = p;
}

4. 双链表

双链表头尾不相接

定义

typedef struct DLinkList{
  ElemType data;
  DLinkList *next;
  DLinkList *prior;
}DLinkList;

头插法建立双链表

void CreateDListF(DLinkList *&L, ElemType a[], int n)
{
  DLinkList *s;
  L = (DLinkList *)malloc(sizeof(DLinkList));
  L->next = L->prior = NULL;
  for(int i=0; i<n; i++){
    s = (DLinkList *)malloc(sizeof(DLinkList));
    s->data = a[i];
    s->next = L->next;
    if(L->next!=NULL)
      L->next->prior = s;
    L->next = s;
    s->prior = L;
  }
}

尾插法建立双链表

void CreateDListR(DLinkList *&L, ElemTyoe a[], int n)
{
  DLinkList *s, *r;
  L = (DLinkList *)malloc(sizeof(DLinkList));
  L->next = L->prior = NULL;
  r = L;
  for(int i=0; i<n; i++){
    s = (DLinkList *)malloc(sizeof(DLinkList));
    s->data = a[i];
    r->next = s;
    s->prior = r;
    r = s;
  }
  r->next = NULL;
}

查找指定元素节点

int FindNode(DLinkList *L, ElemType e)
{
  DLinkList *p = L->next;
  int i = 1;
  while(p!=NULL && p->data != e){
    p = p->next;
    i++;
  }
  if(p!=NULL)
    return i;
  else
    return 0;
}

将 e 插入第 n 个节点位置

int InsertNode(DLinkList *&L, ElemType e, int n)
{
  DLinkList *p, *s;
  int i = 0;
  p = L;
  while(p!=NULL && i<n-1){
    p = p->next;
    i++;
  }
  if(p!=NULL){
    s = (DLinkList *)malloc(sizeof(DLinkList));
    s->data = e;
    s->next = p->next;
    s->prior = p;
    if(p->next!=NULL){
          p->next->prior = s;
        p->next = s;
    }
    return 1;
  }
  else
    return 0;
}

删除第 n 个节点位置的元素

int DeleteNode(DLinkList *&L, ElemType e, int n)
{
  DLinkList *p, *q;
  int i = 0;
  p = L;
  while(p!=NULL && i<n-1){
    p = p->next;
    i++;
  }
  if(p!=NULL){
    q=p->next;
    if q==NULL;
        return 0;
    p->next = q->next;
    if(q->next!=NULL)
        q->next->prior = p;
    free(q);
    return 1;
  }
  else
    return 0;
}

5. 循环链表

定义

typedef struct LNode{
  ElemType data;
  next LNode *next;
}LinkList;

头插法建立循环链表

void CreateListF(LinkList *&L, ElemType a[], int n)
{
  LinkList *s;
  int i;
  L = (LinkList *)malloc(sizeof(LinkList));
  L->next = L;
  for(i=0; i<n; i++){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = a[i];
    s->next = L->next;
    L->next = s;
  }
}

尾插法建立循环链表

void CreateListR(LinkList *&L, ElemType a[], int n)
{
  LinkList *s, *r;
  int i;
  L = (LinkList *)malloc(sizeof(LinkList));
  L->next = L;
  r = L;
  for(i=0; i<n; i++){
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = a[i];
    r->next = s;
    r = s;
  }
  r->next = L;
}

查找元素值为 e 的节点

int FindNode(LinkList *L, ElemTpye e)
{
  LinkList *p = L->next;
  int i = 1;
  while(p!=L && p->data = e){
    p = p->next;
    i++;
  }
  if(p==L)
    return 0;
  else
    return i;
}

6. 静态链表

struct Node{
    typename data; // 数据域
    int next; // 存放下一个结点的数组下标
    xxx; // 结点的某些性质
}

7. 申请动态内存函数

7.1. C 语言

malloc 函数：typename* p=(typename*)malloc(sizeof(typename));

对应的内存释放函数 free ：free(p);

7.2. C++

new 函数：typename* p=new typename;

对应的内存释放函数 delete ：delete(p);