王道数据结构课本代码

本文记录王道数据结构各章知识点部分的代码

Ch2

2.1 线性表的定义和基本操作

2.1.2 线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表。
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

“&”表示C++语言中的引用调用，在C语言中采用指针也可达到同样的效果。

2.2 线性表的顺序表示

2.2.1 顺序表的定义

假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为：
a.静态分配

#define MaxSize 50              //定义线性表的最大长度
typedef struct{
  ElemType data[MaxSize];       //顺序表的元素
  int length;                   //顺序表的当前长度
}SqList;                        //顺序表的类型定义

b.动态分配

#define InitSize 100            //表长度的初始定义
typedef struct{     
  ElemType *data;               //指示动态分配数组的指针
  int MaxSize,length;           //数组的最大容量和当前个数
} SeqList;                      //动态分配数组顺序表的类型定义

C的初始动态分配语句为：
L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
C++的初始动态分配语句为：
L.data = new ElemType[InitSize];

2.2.2 顺序表上基本操作的实现

(1)插入操作
在顺序表L的第i(1<=i<=L.length+1)个位置插入新元素e。平均时间复杂度为O(n)。

bool ListInsert(SqList &L, int i, ElemType e) {
  if(i < 1 || i > L.length+1)             //判断i的范围是否有效
	  return false;
  if(L.length >= MaxSize)                 //当前存储空间已满，不能插入
	  return false;
  for(int j = L.length; j >=i; j--)       //将第i个元素及之后的元素后移
	  L.data[j] = L.data[j-1];
  L.data[i-1] = e;                        //在位置i处放入e
  L.length++;                             //线性表长度加1
  return true;
}

(2)删除操作
删除顺序表L中第i(1<=i<=L.length)个位置的元素，用引用变量e返回。平均时间复杂度为O(n)。

bool ListDelete(SqList &L, int i, ElemType &e) {
  if(i < 1 || i > L.length)                 //判断i的范围是否有效
    return false;
  e = L.data[i-1];                          //将被删除的元素赋值给e
  for(int j = i; j < L.length; j++)         //将第i个位置后的元素前移
    L.data[j-1] = L.data[j];
  L.length--;                               //线性表长度减1
  return true;
}

(3)按值查找(顺序查找)
在顺序表L中查找第一个元素值等于e的元素，并返回其位序。平均时间复杂度为O(n)。

int LocateElem(SqList L, ElemType e) {
  int i;
  for(i = 0; i < L.length; i++)
    if(L.data[i] == e)
      return i+1;                 //下标为i的元素值等于e，返回其位序i+1
  return 0;                       //退出循环，说明查找失败。
}

2.3 线性表的链式表示

2.3.1 单链表的定义

单链表中结点类型的描述如下：

typedef struct LNode{     //定义单链表结点类型
  ElemType data;          //数据域
  struct LNode *next;     //指针域
}LNode, *LinkList;

2.3.2 单链表上基本操作的实现

1.采用头插法建立单链表
该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。
算法如下：

LinkList List_HeadInsert(LinkList &L) {     //逆向建立单链表
  LNode *s; int x;
  L = (LinkList)malloc(sizeof(LNode));      //创建头结点
  L->next == NULL;                          //初始为空链表
  scanf("%d", &x);                          //输入结点的值
  while(x != 9999) {                        //输入9999表示结束
    s = (LNode*)malloc(sizeof(LNode));      //创建新结点
    s->data = x;
    s->next = L->next;
    L->next = s;                            //将新结点插入表中，L为头指针
    scanf("%d", &x);
  }
  return L;
}

每个结点插入的时间是O(1)，设单链表长为n，则总时间复杂度为O(n)。
2.采用尾插法建立单链表
该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。
算法如下：

LinkList List_TailInsert(LinkList &L) {   //正向建立单链表
  int x;                                  //设元素类型为整型
  L = (LinkList)malloc(sizeof(LNode));
  LNode *s, *r = L;                       //r为表尾指针
  scanf("%d", &x);                        //输入结点的值
  while(x != 9999) {                      //输入9999表示结束
    s = (LNode *)malloc(sizeof(LNode));
    s->data = x;
    r->next = s;
    r = s;                                //r指向新的表尾结点
    scanf("%d", &x);
  }
  r->next = NULL;                         //尾结点指针置空
  return L;
}

因为附设了一个指向表尾结点的指针，故时间复杂度和头插法的相同。
3.按序号查找结点值
在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL。
算法如下：

LNode *GetElem(LinkList L, int i) {
  int j = 1;                      //计数，初始为1
  LNode *p = L->next;             //头结点指针赋给p
  if(i == 0)
    return L;                     //若i等于0，则返回头结点
  if(i < 1)
    return NULL;                  //若i无效，则返回NULL
  while(p && j < i) {             //从第1个结点开始找，查找第i个结点
    p = p->next;
    j++;
  }
  return p;                       //返回第i个结点的指针，若i大于表长，则返回NULL
}

时间复杂度为O(n)。
4.按值查找表结点
从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。
算法如下：

LNode *LocateElem(LinkList L, ElemType e) {
  LNode *p = L->next;
  while(p != NULL && p->data != e)        //从第1个结点开始查找data域为e的结点
    p = p->next;
  return p;                               //找到后返回该结点指针，否则返回NULL
}

时间复杂度为O(n)。
5.插入结点操作
插入结点操作将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。
代码片段如下：

1
2
3

p = GetElem(L, i-1);            //查找插入位置的前驱结点
s->next = p->next;
p->next = s;

本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若在给定的结点后面插入新结点，则时间复杂度仅为O(1)。

可采用另一种方式将前插操作转化为后插操作来实现，设待插入结点为*s，将*s插入到*p的前面。我们仍然将*s插入到*p的后面，然后将p->data与s->data交换，这样既满足了逻辑关系，又能使得时间复杂度为O(1)。算法的代码片段如下：

//将*s结点插入到*p之前的主要代码片段
s->next = p->next;              //修改指针域，不能颠倒
p->next = s;
temp = p->data;                 //交换数据域部分
p->data = s->data;
s->data = temp;

6.删除结点操作
删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。
代码片段如下：

p = GetElem(L, i-1);                //查找删除位置的前驱结点
q = p->next;                        //令q指向被删除结点
p->next = q->next;                  //将*q结点从链中“断开”
free(q);                            //释放结点的存储空间

和插入算法一样，该算法的主要时间夜耗费在查找操作上，时间复杂度为O(n)。

其实，删除结点*p的操作可用删除*p的后继结点操作来实现，实质就是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O(1)。
实现上述操作的代码片段如下：

q = p->next;                      //令q指向*p的后继结点
p->data = p->next->data;          //和后继结点交换数据域
p->next = q->next;                //将*q结点从链中“断开”
free(q);                          //释放后继结点的存储空间

7.求表长操作
求表长操作就是计算单链表中数据结点（不含头结点）的个数，需要从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加1，知道访问到空结点为止。算法的时间复杂度为O(n)。

2.3.3 双链表

双链表中结点类型的描述如下：

typedef struct DNode{                 //定义双链表结点类型
  ElemType data;                      //数据域
  struct DNode *prior, *next;         //前驱和后继指针
}DNode, *DLinklist;

插入、删除操作的时间复杂度仅为O(1)。
插入操作的代码片段如下：

s->next = p->next;                  //将结点*s插入到结点*p之后
p->next->prior = s;
s->prior = p;
p->next = s;

删除操作的代码片段如下：

1
2
3

p->next = q->next;                  //删除*p后的*q
q->next->prior = p;
free(q);                            //释放结点空间

2.3.5 静态链表

静态链表结构类型的描述如下：

#define MaxSize 50                    //静态链表的最大长度
typedef struct{                       //静态链表结构类型的定义
  ElemType data;                      //存储数据元素
  int next;                           //下一个元素的数组下标
}SLinkList[MaxSize];