• 已知一个整数线性表采用顺序表L存储。设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设L中值为负整数的元素可能有多个）。

每次删除都需要移动大量元素，会消耗大量的时间，可以换一个角度考虑
采用整体重建顺序表的算法思路,仅仅将插入元素的条件设置为“元素值≥0”即可。

void De(SqList &L)
{
  int i,k = 0;
  for(i = 0;i < L.length;i++)
  {
    if(L.elem[i]>=0)    //非负数插入
    {
      L.elem[k] = L.elem[i];
      k++;
    }
  }
  L.length = k;    //重置长度
}

• 设将\(n（n＞1）\)个整数存放到一维数组R中。试设计一个时间和空间两方面尽可能高效的算法，将R中整数序列循环左移\(p（0＜p＜n）\)个位置，即将R中的数据序列\((X_{0},X_{1},…,X_{n-1})\)变换为\((X_{p},X_{p+1},…,X_{n-1},X_{0},X_{1},…,X_{p-1})\)

设\(R=(X_{0},X_{1},…,X_{p},X_{p+1}, …,X_{n-1)}\)，记\(A=(X_{0},X_{1},…,X_{p-1})\) （共有p个元素），\(B=(X_{p},…,X_{n-1})\)（共有n-p个元素）
设计逆置算法reverse(R)，用于原地逆置数组R，则A原地逆置后A’变为\((X_{p-1},…,X_{1},X_{0})\)，B原地逆置后B’变为\((X_{n-1},…,X_{p-1},X_{p})\)
就是说\(A’B’=(X_{p-1},…,X_{1},X_{0},X_{n-1},…,X_{p-1},X_{p})\)，再将A’B’原地逆置变为\((X_{p},X_{p-1},…,X_{n-1},X_{0},X_{1},…,X_{p-1})\)即为所求，即进行3次逆置操作:\(reverse(R)=reverse(reverse(A),reverse(B))\)

void reverse(int R[],int m,int n) //将R[m..n]逆置
{ 
  int i,tmp;
  for (i=0;i<(n-m+1)/2;i++)
  { 
    tmp=R[m+i]; //将R[m+i]与R[n-i]进行交换
    R[m+i]=R[n-i];
    R[n-i]=tmp;
  }
}

int ListReverse(int R[],int n,int p) //循环左移
{ 
  if (p<=0 || p>=n)
    return 0;
  else
  { 
    reverse(R,0,p-1);
    reverse(R,p,n-1);
    reverse(R,0,n-1);
    return 1;
  }
}

线性表的链式存储和实现

线性链表

存储方式

线性表的单链表存储方法：用一个指针表示结点间的逻辑关系。

因此单链表的一个存储结点包含两个部分，结点的形式如下：

data：为数据域，用于存储线性表的一个数据元素，也就是说在单链表中一个结点存放一个数据元素。

next：为指针域或链域，用于存放一个指针，该指针指向后继元素对应的结点，也就是说单链表中结点的指针用于表示后继关系。

• 特点

每个数据元素由结点构成
线性结构

结点可以连续，可以不连续存储。
结点的逻辑顺序与物理顺序可以不一致
表可扩充。
链表中第一个元素结点称为首结点；最后一个元素称为尾结点，其指针域(next)为空(NULL)。

• 结点类型声明

typedef int ElemType;
typedef int Status; 
#define OK 1
#define ERROR 0

// ------ 结点的C语言描述 --------
typedef struct node {
  ElemType data;
  struct node *next;
} LNode, *LinkList;

带头节点的单链表示意图

常规算法设计

• 初始化单链表算法

创建一个空的单链表，它只有一个头结点，由L指向它。该结点的next域为空，data域未设定任何值。

Status InitList(LinkList &L)
{
  L = (LinkList)malloc(sizeof(LNode));
  if(!L)
    return ERROR;
  L->next = NULL;    //指针域为空
  return OK;
}

• 销毁单链表算法

一个单链表中的所有结点空间都是通过malloc函数分配的，在不再需要时需通过free函数释放所有结点的空间
借助一个遍历指针

Status DestroyList(LinkList &L)
{
  LinkList p;  //临时指针
  while(L)
  {
    p = L->next
    free(L);
    L = p;
  }
  return OK;
}

• 求单链表长度算法

设置一个整型变量i作为计数器，i初值为0，p初始时指向第一个数据结点。
然后沿next域逐个往后查找，每移动一次，i值增1。当p所指结点为空时，结束这个过程，i之值即为表长。

int ListLength(LinkList L)
{
  int i = 0;//计数器
  LinkList p = L->next; // p指向第一个结点
  while(p) { // 没到表尾
    i++;
    p = p->next;
  }
  return i;
}

• 求单链表中值为e的元素算法

用p从头开始遍历单链表L中的结点，用计数器i统计遍历过的结点，其初值为0。
在遍历时，若p不为空，则p所指结点即为要找的结点，查找成功，算法返回位序i
否则算法返回0表示未找到这样的结点。

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

• 单链表的插入算法

在单链表L中第i个位置，插入值为x的结点。

找前驱结点
先在单链表L中查找第i-1个结点，若未找到返回0；
找到后由p指向该结点，创建一个以x为值的新结点s，将其插入到p指结点之后。
在p结点之后插入s结点的操作如下：
① 将结点s的next域指向p的下一个结点（s->next=p->next）。
② 将结点p的next域改为指向新结点s（p->next=s）。

插入操作的①和②执行顺序不能颠倒。
记忆方法：先把没有指向的指针指向一个位置，进行操作

Status ListInsert_L(LinkList &L, int i, ElemType e)
{
  LinkList p, s;
  p = L;
  int j = 0;
  while(p && jnext,j++;  //找结点
  if(!p||j>i-1)  return ERROR;//位置不合法
  s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
  s->data = e;
  s->next = p->next;
  p->next = s;
  return OK;
}

• 单链表的删除算法

先在单链表L中查找第i-1个结点，若未找到返回0
找到后由p指向该结点，然后让q指向后继结点（即要删除的结点）。
若q所指结点为空则返回0，否则删除q结点并释放其占用的空间。
删除p指结点的后继结点的过程：

p->next=q->next;
free(q);
即需要找到删除结点的前驱结点

Status ListDelete_L(LinkList &L, int i, ElemType &e)
{
  LinkList p, q;
  p = L;
  int j = 0;
  while(p && jnext,j++;  //找结点
  if(!(p->next)||j>i-1)  return ERROR;//位置不合法
  q = p->next;  //p为前驱，q为当前结点
  e = q->data;
  free(q);
  return OK;
}

拓展实例

• 设计一个算法，通过一趟遍历确定单链表L（至少含两个数据结点）中第一个元素值最大的结点。

用p遍历单链表，在遍历时用maxp指向data域值最大的结点（maxp的初值为p）。当单链表遍历完毕，最后返回maxp。

LNode *MaxNode(LNode *L)
{
  LNode *p=L->next, *maxp=p;
  while (p!=NULL) //遍历所有的结点
  {
    if(maxp->datadata)
      maxp = p;  //当p指向的值大于maxp时，更新maxp
  }
  return maxp;
}

• 删除一个单链表L（至少含两个数据结点）中第一个元素值最大的结点。

以p遍历单链表，pre指向p结点的前驱结点。
在遍历时用maxp指向data域值最大的结点，maxpre指向maxp结点的前驱结点。
当单链表遍历完毕，通过maxpre结点删除其后的结点，即删除了元素值最大的结点。
用到了同步指针

void DelMaxNode(LNode *&L)
{
  LNode *p=L->next,*pre=L,*maxp=p,*maxpre=pre;  //初始化
  while(p!=NULL)
  {
    if(maxp->data < p->data)
    {
      maxp = p;
      maxpre = pre;
    }
    pre = p;
    p = p->next;//pre、p同步后移，保证pre始终为p的前驱结点
  }
  maxpre->next = maxp->next;//删除maxp结点
  free(maxp);//释放maxp结点
}

• 将一个单链表L（至少含两个数据结点）中所有结点逆置，并分析算法的时间复杂度。

先将单链表L拆分成两部分，一部分是只有头结点L的空表，另一部分是由p指向第一个数据结点的单链表。
然后遍历p，将p所指结点逐一采用头（前）插法插入到L单链表中，由于头插法的特点是建成的单链表结点次序与插入次序正好相反，从而达到结点逆置的目的。
头插法天然可以实现单链表逆置
一样，还是先处理没有指向的指针，再做其他处理

void ListReverse(LNode *&L)
{
  LNode *p = L->next,*q;
  L->next = NULL;
  while(p!=NULL)
  {
    q = p->next;
    
    p->next = L->next;//头插法
    L->next = p;
    p = q;
  }
}

• 假设该单链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。

单链表只能从前往后遍历，并不能从后往前，所以想要再一次循环内找到相对应的结点，只能采用特殊的方式。
考虑双指针的思路，定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动； 当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表尾结点时，q指针所指元素为倒数第k个结点。

详细思路:

①置count=0，p和q指向链表表头结点的下一个结点。
②若p为空，则转向⑤ 。
③若count等于k，则q指向下一个结点；否则，置count=count+1。
④置p指向下一个结点，转向② 。
⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0。
⑥算法结束。

int Searchk(LinkList list,int k)
{
  LinkList p, q;
  int count = 0;
  p = q = list->link;
  while (p!=NULL && countlink;
  }
  if(p == NULL)
    return 0;
  else
  {
    while(p!=NULL)//没有时返回0
    {
      q = p->link;//p和q同步后移直到p=NULL
      p = p->link;
    }
    printf("%d",q->data);
    return 1;
  }
}

循环链表

循环链表是单链表的变形，链表尾结点的next指针不是NULL，而是指向了单链表的前端。

循环链表的判空条件：L->next == L;
循环单链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。
在搜寻过程中，没有一个结点的 next 域为空

遍历条件：for ( p = L->next; p != L; p = p->next )
循环单链表的所有操作的实现类似于单链表，差别在于检测到链尾，指针不为NULL，而是回到链头。

算法设计

• 初始化线性表运算算法

创建一个空的循环单链表，它只有头结点，由L指向它。

Status InitList_cl(LinkList &L)
{
  L = (LinkList)malloc(sizeof(LNode));
  if(!L)exit(OVERFLOW);
  L->next = L;
  return OK;
}

• 求线性表的长度算法

int ListLength(LinkList L)
{
  int i = 0;
  LinkList p = L->next; // p指向第一个结点
  while(p != L) { // 没到表尾
    i++;
    p=p->next;
  }
  return i; 
}

其他

• 设计一个算法求一个循环单链表L中所有值为x的结点个数

int CountNode(LNode *L, ElemType x)
{
  int i = 0;
  LNode *p = L->next;
  while(p!=L)
  {
    if(p->data == x)i++;
    p = p->next;
  }
  return i;
}

• 有一个非递减有序的循环单链表L，设计一个算法删除其中所有值为x的结点

由于循环单链表L是非递减有序的，则所有值为x的结点必然是相邻的
先找到第一个值为x的结点p，让pre指向其前驱结点
然后通过pre结点删除p结点及其后面连续值为x的结点

int Delallx(LNode *&L, ElemType x)
{
  LNode *pre=L,*p=L->next; //pre指向p结点的前驱结点
  while (p!=L && p->data!=x) //找第一个值为x的结点p
  {
    pre = p;
    p = p->next;
  }
  if(p==L)return 0;//没有找到值为x的结点返回0
  while(p!=L&&p->data == x)//删除所有值为x的结点
  {
    pre->next = p->next;
    free(p);
    p = pre->next;
  }
  return 1;//成功删除返回1
}

双向链表

双向链表是指在前趋和后继方向都能遍历的线性链表。

双向链表每个结点的结构为：

双向链表中用两个指针表示结点间的逻辑关系
指向其前驱结点的指针域prior。
指向其后继结点的指针域next。

结点指向:

指向其后继结点的指针域next。
p->next 指示结点 p 的后继结点；
p->prior->next指示结点 p 的前趋结点的后继结点，即结点 p 本身；
p->next->prior指示结点 p 的后继结点的前趋结点，即结点 p 本身。

p->prior->next == p == p->next->prior 固有特性

存储声明

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

双向循环链表

• 双向循环链表长度

int ListLength(DuLinkList L)
{
  int i = 0;
  DuLinkList p = L->next; // p指向第一个结点
  while(p!=L)
  {
    i++;
    p = p->next;
  }
  return i;
}

• 插入

① 将结点s的next域指向结点p的下一个结点（ s->next=p->next）。
② 若p不是最后结点（若p是最后结点，只插入s作为尾结点），则 将p之后结点的prior域指向s（p->next->prior=s）。
将s的prior域指向p结点（s->prior=p）。
④ 将p的next域指向s（p->next=s）。
还是先将没有指向的指针指向该指向的位置

在双向循环链表中，可以通过一个结点找到其前驱结点，所以插入操作也可以改为：在双链表中找到第i个结点p，然后在p结点之前插入新结点。

Status ListInsert(DuLinkList L, int i, ElemType e)
{
  DuLinkList p, s;
  if(i<1 || i>ListLength(L) + 1) //判断位置
    return ERROR;
  p = GetElemP(L, i - 1); // 在L中确定第i个元素前驱的位置指针p
  if(!p) return ERROR;
  s = (DuLinkList)malloc(sizeof(DuLNode));
  if(!s) exit(OVERFLOW);
  
  s->data = e;
  s->prior = p;
  s->next = p->next;
  p->next->prior = s;
  p->next = s;
  return OK;
}

• 删除结点运算算法

若p不是尾结点，则将其后继结点的prior域指向pre结点(p->next->prior=pre）
② 将pre结点的next域改为指向p结点的后继结点（pre-next=p->next）

Status ListDelete(DuLinkList L, int i, ElemType &e)
{
  DuLinkList p;
  if(i<1) return ERROR;
  p = GetElemP(L,i)//确定第i个位置
  if(!p) return ERROR;
  e = p->data;    //保存删除元素
  
  p -> prior -> next = p->next;
  p -> next ->prior = p->prior;
  free(p);
  return OK;
}

总结