◆2.11② 设顺序表L中的数据元素递增有序。
试写一算法，将x插入到L的适当位置上，并保
持该表的有序性。
要求实现下列函数：
void InsertOrderList(SqList &L, ElemType x)
/* 在有序的顺序表 L 中保序插入数据元素 x */
顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int      length;
    int      listsize;
} SqList;
void InsertOrderList(SqList &L, ElemType x)
// 在有序的顺序表 L 中保序插入数据元素 x
{
    int i=0,j;
    while(L.elem[i]<x&&i<L.length)
        i++;
    for(j=L.length;j>i;j--)
    {
      L.elem[j]=L.elem[j-1];
    }
    L.elem[i]=x;
    L.length+=1;
}
◆2.12③ 设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，
A'和B'分别为A和B中除去最大共同前缀后的子表（例如，
A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大
的共同前缀为(x,y,y,z)， 在两表中除去最大共同前缀后
的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，
则A=B；若A'=空表，而B'≠ 空表，或者两者均不为空表，
且A'的首元小于B'的首元，则A<B；否则A>B。试写一个比
较A和B大小的算法。（注意：在算法中，不要破坏原表A
和B，也不一定先求得A'和B'才进行比较）。
要求实现下列函数：
char Compare(SqList A, SqList B);
/* 比较顺序表A和B,      */
/*  返回'<', 若A<B;    */
/*      '=', 若A=B;    */
/*      '>', 若A>B    */
顺序表类型定义如下：
typedef struct {
    ElemType *elem;
    int      length;
    int      listsize;
} SqList;
char Compare(SqList A, SqList B)
// 比较顺序表A和B,
//  返回'<', 若A<B;
//      '=', 若A=B;
//      '>', 若A>B
{
    int i=0;
    while(A.elem[i]==B.elem[i]&&i<A.length&&i<B.length)
        i++;
    if(i==A.length&&i==B.length)
        return '=';
    else if(A.elem[i]<B.elem[i]||i==A.length)
        return '<';
    else if(A.elem[i]>B.elem[i]||i==B.length)
        return '>';   
}
2.13② 试写一算法在带头结点的单链表结构上实现线性表操作
Locate(L,x)。
实现下列函数：
LinkList Locate(LinkList L, ElemType x);
// If 'x' in the linked list whose head node is pointed
// by 'L',  then return pointer pointing node 'x',
// otherwise return 'NULL'
单链表类型定义如下：
typedef struct LNode {
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
LinkList Locate(LinkList &L, ElemType x)
//  If 'x' in the linked list whose head node is pointed
//  by 'L', then return pointer ha pointing node 'x',
//  otherwise return 'NULL'
{
    LinkList p;
    int i=0;
    p=L->next;
    while(p->data!=x&&p!=NULL)
    {
        i++;
        p=p->next;
float()函数
    } 
    return p;
       
}
2.14② 试写一算法在带头结点的单链表结构上实现线性表
操作Length(L)。
实现下列函数：
int Length(LinkList L);
// Return the length of the linked list
// whose head node is pointed by 'L'
单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
int Length(LinkList L)
// Return the length of the linked list
// whose head node is pointed by 'L'
{
  LinkList p;
  int i=0;
  p=L->next;
  while(p!=NULL)
  {
    i++;
    p=p->next;
  }
  return i;
}
2.17② 试写一算法，在无头结点的动态单链表上实现
线性表操作INSERT(L,i,b)，并和在带头结点的动态单
链表上实现相同操作的算法进行比较。
实现下列函数：
void Insert(LinkList &L, int i, ElemType b);
单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
void Insert(LinkList &L, int i, ElemType b)
{
    LinkList p,q;
    int j=2;
    p=L;
    while(j<i)
    {
        j++;
        p=p->next;
    }
    if(i!=0&&i!=1)
    {
    q=(LinkList)malloc(sizeof(LNode));
    q->data=b;
    q->next=p->next;
    p->next=q;
    }
    if(i==1)
    {
    q=(LinkList)malloc(sizeof(LNode));
    q->data=b;
    q->next=p;
    L=q;
    }   
}
2.18②  同2.17题要求。试写一算法，
实现线性表操作DELETE(L,i)。
实现下列函数：
void Delete(LinkList &L, int i);
单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
void Delete(LinkList &L, int i)
{
    LinkList p,q;
    int j=2;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。