Linear_list

类型定义

一个线性表是n个数据元素的有限序列，线性表中的元素个数n定义为线性表的长度，n=0时成为空表；
抽象数据类型：

InitList(&L)                //构造空线性表L
DestroyList(&L)             //销毁线性表L
ClearList(&L)               //将L重置为空表
ListEmpty(L)                //若L为空表返回TRUE，否则返回FALSE
ListLength(L)               //返回L中数据元素个数
GetElem(L, i, &e)           //用e返回L中第i个元素的值
//不常用
LocateElem(L, e, compare()) //返回L中第一个与e满足关系compare()的数据元素的位序，若不存在，则返回0
PriorElem(L, cur_e, &pre_e) //用pre_e返回L中数据元素cur_e的前驱
NextElem(L, cur_e, &next_e) //用next_e返回L中数据元素cur_e的后继
ListInsert(&L, i, e)        //在L的第i个位置前插入新数据元素e，长度更新
ListDelete(&L, i, &e)       //删除L的第i个数据元素，并用e返回其值，长度更新
ListTraverse(L, visit())    //依次对L的每个数据元素调用函数visit()

顺序表示和实现

顺序表示

#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef struct{
  ElemType *elem;
  int length;
}SqList;

基本实现

InitList

Status InitList(SqList *L)
{ //构造空线性表
  L->elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
  if(!L->elem)
    return ERROR;
  L->length = 0;
  return OK;
}

ListInsert

Status ListInsert(SqList *L, int i, ElemType e)
{ //顺序表插入
  int k;
  if(i < 1 || i > L->length + 1)
    return ERROR;
  for(k = L->length - 1; k >= i - 1; k--)
    L->elem[k + 1] = L->elem[k];
  L-elem[i - 1] = e;
  L->length++;
  return OK;
}

ListDelete

Status ListDelete(SqList *L, int i, ElemType *e)
{ //顺序表删除
  int k;
  if(i < 1 || i > L->length)
    return ERROR;
  *e = L->elem[i - 1];
  if(i < L->length)
  {
    for(k = i; k < L->length; k++)
      L->elem[k - 1] = L->elem[k];
  }
  L->length--;
  return OK;
}

链式表示和实现

链式表示

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

//节点结构体
typedef struct Node
{
  ElemType data;
  struct Node *next;
}Node;
//单链表
typedef struct
{
  int length;
  Node *next; //头指针(不储存任何值)，指向头结点
}*LinkList;

基本实现

InitList

Status InitList(LinkList *L)
{ //创建单链表以及新节点
  LinkList p = (LinkList)malloc(sizeof(LinkList));
  Node *q = (Node *)malloc(sizeof(Node));   //创建头结点
  q->next = NULL;
  p->next = q;
  p->length = 0;
  (*L) = p;
  return OK;
}

ListInsert

Status ListInsert(LinkList *L, ElemType elem. int pos)
{ //单链表插入
  if(pos < 1 || pos > (*L)->length + 1)
    return ERROR;     //范围
  Node *p = (*L)->next;
  for(int i = 1; i < pos; i++)
    p = p->next;
  //创建新节点插入
  Node *q = (Node *)malloc(sizeof(Node));
  q->data = elem;
  q->next = p->next;
  p->next = q;
  (*L)->length += 1;
  return OK;
}

ListDelete

Status ListDelete(LinkList *L, ElemType *elem, int pos)
{ //单链表删除
  if(pos < 1 || pos > (*L)->length)
    return ERROR;
  //查找
  Node *p = (*L)->next, *q;
  for(int i = 0; i < pos; i++)
    p = p->next;
  //删除
  q = p->next;
  p->next = q->next;
  free(q);
  (*L)->length -= 1;
  return OK;
}

循环链表

表中最后一个节点的指针域指向头结点，整个链表形成一个环；

考虑此时查找最后一个节点时其时间复杂度为O(n)，可对此优化在循环链表中设立尾指针；同时这样也可简化某些操作，比如两个线性表合并时，仅需将表的表尾与另一个表的表头相接；

双向链表

存储结构

在双向链表的节点中有两个指针域，即后继与前驱；

typedef struct DuLNode
{
  ElemType data;
  struct DuLNode *prior;
  struct DuLNode *next;
}DuLNode, *DuLinkList;

基本实现

ListInsert

Status ListInsert(DuLinkList *L, int i, ElemType e)
{ //插入操作
  DuLNode *p, *s = (DuLNode *)malloc(sizeof(DuLNode));
  //查找位置
  if(!(p = GetElemP_DuL(L, i)))
    return ERROR;
  s->data = e;
  //更新s前驱
  s->prior = p->prior;
  p->prior->next = s;
  //更新s后继
  s->next = p;
  p->prior = s;
  return OK;
}

ListDelete

Status ListDelete(LinkList *L, int i, ElemType *e)
{ //删除操作
  DuLNode *p;
  if(!(p = GetElemP_DuL(L, i)))
    return ERROR;
  (*e) = p->data;
  p->prior->next = p->next;
  p->next->prior = p->prior;
  free(p);
  return OK;
}

静态链表

存储结构

借用一维数组来描述线性链表，便于在不设“指针”类型的高级程序设计语言中使用链表结构；
游标指向下一个节点，在作线性表的插入和删除操作时无需移动元素，仅需修改指针；
其中未被使用的数组成为备用链表，插入时从其中取得，删除时回收到备用链表中；同时规定下标为0的cur为备用链表第一个节点的下标，数组最后一个元素的cur为第一个有数值的元素的下标，若链表为空，则为0；

//静态单链表存储结构
#define MAXSIZE 1000  //链表最大长度
typedef struct
{
  ElemType data;
  int cur;  //游标，为0时无指向
}component, SLinkList[MAXSIZE];

基本实现

InitSpace_SL

void InitSpace_SL(SLinkList *space)
{ // 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针
  for (int i = 0; i < MAXSIZE - 1; i++)
    space[i]->cur = i + 1;
  space[MAXSIZE - 1]->cur = 0;  //无指向
}

LocateElem_SL

Status LocateElem_SL(SLinkList *S, ElemType e)
{ // 查找元素，返回位序
  int i = S[0]->cur;
  while (i && S[i]->data != e)
    i = S[i]->cur;
  return i;
}

Malloc_SL

int Malloc_SL(SLinkList space)
{ // 若备用空间链表非空，返回分配的节点下标，否则为0
  int i = space[0].cur; // 每次从头结点开始
  if (space[0].cur)     // 可分配
    space[0].cur = space[i].cur;
  return i;
}

Free_SL

void Free_SL(SLinkList *space, int k)
{ // 将下标为k的空闲节点回收到备用链表
  space[k]->cur = space[0]->cur;
  space[0]->cur = k;
  // 相当于在0与其[0].cur之间插入k
}

ListInsert

Status ListInsert(component *L, int i, ElemType e)
{ //插入操作
  if(i < 1 || i > ListLength(L) + 1)
    return ERROR;
  //获取空间
  int k = Malloc_SL(L);
  n = MAXSIZE - 1;  //从最后一个元素开始，即头结点
  if(k)
  {
    L[k].data = e;
    for(int l = 1; l <= i - 1; l++)
      n = L[n]->cur;        //找到第i个元素前的下标
    L[k]->cur = L[n]->cur;  
    L[n]->cur = k;          //插入
    return OK;
  }
  return ERROR;
}

ListDelete

Status ListDelete(component *L, int i)
{
  if(i < 1 || i > ListLength(L) + 1)
    return ERROR;
  int n = MAXSIZE - 1;
  for(int j = 1; j <= i - 1; j++)
    n = L[n].cur;           //查找
  j = L[n].cur;
  L[n].cur = L[j].cur;      //删除
}