销售团队的工作职责:数据结构题集（C语言版）算法设计题解析-第二章

来源：百度文库 编辑：中财网 时间：2024/04/30 03:47:00

2.10 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

SqList.h

typedef struct{
 ElemType * elem;   //存储空间基址
 int      length;   //当前长度
 int      list;     //当前分配的存储容量
}SqList;

void InitList(SqList &a)
{  //初始化线性表
 a.list=listlength;
 a.elem=(ElemType*)malloc(a.list*sizeof(SqList));
 if(a.elem==NULL)
 {
  printf("初始化失败");
  exit(1);
 }
 a.length=0;
}

void ClearList(SqList &a)
{   //清除线性表
 if(a.elem!=NULL)
 {
  free(a.elem);
  a.elem=NULL;
 }
 a.length=0;
 a.list=0;
}

int LengthList(SqList a)
{  //求线性表长度
 return a.length;
}

bool InsertList(SqList &a, ElemType item, int pos)
{   //按给定条件pos向线性表插入一个元素
 if(pos<-1||pos>a.length+1)
 {
  printf("pos输入错误\n");
  return false;
 }
 int i;
 if(pos==0)
 {
  for(i=0;i   if(a.elem[i]>item)
    break;
  pos=i+1;
 }
 else if(pos==-1)
  pos=a.length+1;
 if(a.length==a.list)
 {
  a.elem=(ElemType*)realloc(a.elem,2*a.list*sizeof(ElemType));
  if(a.elem==NULL)
  {
   printf("空间分配失败\n");
   exit(1);
  }
  a.list*=2;
 }

 for(i=a.list-1;i>=pos-1;i--)
  a.elem[i+1]=a.elem[i];
 a.elem[pos-1]=item;
 a.length++;
 return true;
}

ElemType GetList(SqList L, int pos)
{  //在线性表L中求序号为pos的元素，该元素作为函数值返回
 if(pos<1||pos>L.length)
 {
  printf("pos输入错误\n");
  exit(1);
 }
 return L.elem[pos-1];
}

Status DeleteK(SqList&a,int i,int k){
 //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
 //注意i的编号从0开始
 int j;
 if(i<0||k<0||i+k-1>a.length) return INFEASIBLE;

                                     //参数不合法，原题条件i+k>a.length改为i+k-1>a.length
 while(i+k<=a.length)
 {
            a.elem[i-1]=a.elem[i+k-1];i++;
 }
    a.length=a.length-k;
    return OK;
}

main.cpp

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define INFEASIBLE -1
#define OK 1
#define listlength 10
typedef int ElemType;
typedef int Status;
#include
#include
#include"SqList.h"
void main()
{
 SqList myList;
 int account=1, x, n;
 int i,k;
 printf("请输入正整数（输入结束以-1结尾）：\n");
 InitList ( myList);
 scanf("%d", &x);
 while ( x!= -1 )
 { 
  if ( InsertList (myList,x,account)==0) {
   printf("错误!\n");
   return ;
  }
       account++;
    scanf("%d", &x);
 }
 printf("请输入i的值：");
 scanf("%d",&i);
 printf("请输入k的值：");
 scanf("%d",&k);
 DeleteK(myList,i,k);
 n = LengthList (myList);
 printf("删除线性表a中第%d元素起的%d个元素后:",i,k);
 for (i=1; i<=n; i++)
  printf("%d ",GetList(myList, i));
  printf("\n");
  ClearList(myList);
 }
运行截图：

2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

SqList.h

typedef struct{
 ElemType * elem;   //存储空间基址
 int      length;   //当前长度
 int      list;     //当前分配的存储容量
}SqList;

void InitList(SqList &a)
{  //初始化线性表
 a.list=listlength;
 a.elem=(ElemType*)malloc(a.list*sizeof(SqList));
 if(a.elem==NULL)
 {
  printf("初始化失败");
  exit(1);
 }
 a.length=0;
}

void ClearList(SqList &a)
{   //清除线性表
 if(a.elem!=NULL)
 {
  free(a.elem);
  a.elem=NULL;
 }
 a.length=0;
 a.list=0;
}

int LengthList(SqList a)
{  //求线性表长度
 return a.length;
}

bool InsertList(SqList &a, ElemType item, int pos)
{   //按给定条件pos向线性表插入一个元素
 if(pos<-1||pos>a.length+1)
 {
  printf("pos输入错误\n");
  return false;
 }
 int i;
 if(pos==0)
 {
  for(i=0;i   if(a.elem[i]>item)
    break;
  pos=i+1;
 }
 else if(pos==-1)
  pos=a.length+1;
 if(a.length==a.list)
 {
  a.elem=(ElemType*)realloc(a.elem,2*a.list*sizeof(ElemType));
  if(a.elem==NULL)
  {
   printf("空间分配失败\n");
   exit(1);
  }
  a.list*=2;
 }

 for(i=a.list-1;i>=pos-1;i--)
  a.elem[i+1]=a.elem[i];
 a.elem[pos-1]=item;
 a.length++;
 return true;
}

ElemType GetList(SqList L, int pos)
{  //在线性表L中求序号为pos的元素，该元素作为函数值返回
 if(pos<1||pos>L.length)
 {
  printf("pos输入错误\n");
  exit(1);
 }
 return L.elem[pos-1];
}

void InsertOrderList(SqList &a, ElemType x)
// 在有序的顺序表 L 中保序插入数据元素 x
{
   int i=0,j;     
   if(x>=a.elem[a.length-1])
    a.elem[a.length]=x;//如果x大于表最后一个元素，则直接插到最后面
   else{
     while(a.elem[i]<=x) i++;            //找到x的插入位置
           for(j=a.length-1;j>=i;j--) 
     a.elem[j+1]=a.elem[j] ;
           a.elem[i]=x;
       }
   a.length++;                 //表长加1
}

main.cpp

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define INFEASIBLE -1
#define OK 1
#define listlength 10
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
#include
#include
#include"SqList.h"
void main()
{
 SqList va;
 int account=1, x, n,y;
 int i;
 printf("请输入正整数（输入结束以-1结尾）：\n");
 InitList (va);
 scanf("%d", &y);
 while ( y!= -1 )
 { 
  if ( InsertList (va,y,account)==0) {
   printf("错误!\n");
   return ;
  }
       account++;
    scanf("%d", &y);
 }
 printf("请输入x的值：\n");
 scanf("%d",&x);
 InsertOrderList(va,x);
 n= LengthList (va);
 printf("将x插入顺序表后：\n");
 for (i=1; i<=n; i++)
  printf("%d ",GetList(va, i));
 printf("\n");
    ClearList(va);
 }

运行结果截图：



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'的首元，则AB。试写一个比较A,B大小的算法（请注意在算法中，不要破坏表A和B，并且，也不一定先求得A’和 B’才比较）。

SqList.h

typedef struct{
 ElemType * elem;   //存储空间基址
 int      length;   //当前长度
 int      list;     //当前分配的存储容量
}SqList;

void InitList(SqList &a)
{  //初始化线性表
 a.list=listlength;
 a.elem=(ElemType*)malloc(a.list*sizeof(SqList));
 if(a.elem==NULL)
 {
  printf("初始化失败");
  exit(1);
 }
 a.length=0;
}

void ClearList(SqList &a)
{   //清除线性表
 if(a.elem!=NULL)
 {
  free(a.elem);
  a.elem=NULL;
 }
 a.length=0;
 a.list=0;
}

bool InsertList(SqList &a, ElemType item, int pos)
{   //按给定条件pos向线性表插入一个元素
 if(pos<-1||pos>a.length+1)
 {
  printf("pos输入错误\n");
  return false;
 }
 int i;
 if(pos==0)
 {
  for(i=0;i   if(a.elem[i]>item)
    break;
  pos=i+1;
 }
 else if(pos==-1)
  pos=a.length+1;
 if(a.length==a.list)
 {
  a.elem=(ElemType*)realloc(a.elem,2*a.list*sizeof(ElemType));
  if(a.elem==NULL)
  {
   printf("空间分配失败\n");
   exit(1);
  }
  a.list*=2;
 }
 for(i=a.list-1;i>=pos-1;i--)
  a.elem[i+1]=a.elem[i];
 a.elem[pos-1]=item;
 a.length++;
 return true;
}

char Compare(SqList A, SqList B)
{
  int i;
  for(i=1;i  {
    if(A.elem[i]!=B.elem[i])
    return A.elem[i]>B.elem[i]?'>':'<';
  }
    if(A.length==B.length)
    return '=';
    else
    return A.length>B.length?'>':'<';
}
main.cpp

#define listlength 10
typedef int ElemType;
typedef int Status;
#include
#include
#include"SqList.h"
void main()
{
 SqList A;
 int a=1,b=1,x,y;
 printf("请输入线性表A中的正整数（输入结束以-1结尾）：\n");
 InitList (A);
 scanf("%d", &x);
 while ( x!= -1 )
 { 
  if ( InsertList (A,x,a)==0) {
   printf("错误!\n");
   return ;
  }
       a++;
    scanf("%d", &x);
 }
 printf("请输入线性表B中的正整数（输入结束以-1结尾）：\n");
 SqList B;
 InitList (B);
 scanf("%d", &y);
 while ( y!= -1 )
 { 
  if ( InsertList (B,y,b)==0) {
   printf("错误!\n");
   return ;
  }
       b++;
    scanf("%d", &y);
 }
 printf("表A和表B的比较结果：\n");
 printf("表A %c 表B\n",Compare(A,B));
 ClearList(A);
 ClearList(B);
 }







2.13 试写一算法在带头节点的单链表结构上实现线性表操作LOCATE(L,X).

2.14 试写一算法在带头节点的单链表结构上实现线性表操作LENGTH（L）。

LinkList.h

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

//构造一个空的线性表L
int InitList(LinkList *L)
{
 
 (*L)=(LinkList)malloc(sizeof(struct LNode));
 if(!(*L))
  exit(0);
 (*L)->next=NULL;
 return 1;
}


// 在带头结点的单链线性表L中第i个位置之前插入元素e
int ListInsert(LinkList *L,int i,ElemType e)
{
 int j=0;
 LinkList p=*L,s;
 while(p && j {
  p=p->next;
  j++;
 }
 if(!p || j>i-1) // i小于1或者大于表长
  return 0;
 s=(LinkList)malloc(sizeof(struct LNode)); // 生成新结点
 s->data=e; // 插入L中
 s->next=p->next;
 p->next=s;
 return 1;
}


int ClearList(LinkList L)
{
 LinkList p,q;
 p=L->next;
 while(p)
 {
  q=p->next;
  free(p);
  p=q;
 }
 L->next=NULL;
 return 1;
}

// L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并
// 返回1,否则返回0。
int GetElem(LinkList L,ElemType *e,int i)
{
 int j = 1;   // j为计数器
 LinkList p=L->next; // p指向第一个结点
 while(p&&j // 顺指针向后查找,直到p指向第i个元素或p为空
 {
  p=p->next;
  j++;
 } 

 if(!p||j>i) // 第i个元素不存在
  return 0;
 *e = p->data; // 取第i个元素
 return 1;
}

//返回L中数据元素个数。
int LENGTH(LinkList L)
{
 int i=0;
 LinkList p=L->next;
 while(p)
 {
  i++;
  p=p->next;
 }
 return i;
}

LinkList Locate(LinkList &L, ElemType x)
{    LinkList p;
     p=L->next;
     while(p)
      { 
    if(p->data==x)  return p;   //找到x则输出
         else p=p->next;   //找不到则指针指向下一位
      }
      return NULL;                  //表里没有x
                
}

main.cpp

typedef int ElemType;
#include
#include
#include"LinkList.h"
void main()
{
  LinkList myList;
 int account=1, x,y, n;
 int i;
 printf("请输入正整数（输入结束以-1结尾）：\n");
 InitList ( &myList);
 scanf("%d", &y);
 while ( y!= -1 )
 {
  if (  ListInsert (&myList,account,y)==0) {
   printf("错误!\n");
   return ;
  }
       account++;
    scanf("%d", &y);
 }
    printf("请输入x的值：\n");
 scanf("%d",&x);
 printf("查找结果为：\n");
 if(Locate(myList,x)==0)
  printf("x不在链表中\n");
 else
  printf("x在链表中\n");
  n=LENGTH(myList);
  printf("输出线性表如下：\n");
  for(i=1;i<=n;i++)
  {
   GetElem(myList,&x,i);
    printf("%d ",x);
  }
  printf("\n");
  ClearList(myList);
}


2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。

试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个

结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接

运算。请分析你的算法的时间复杂度。

LinkList.h

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

//构造一个空的线性表L
int InitList(LinkList *L)
{
 
 (*L)=(LinkList)malloc(sizeof(struct LNode));
 if(!(*L))
  exit(0);
 (*L)->next=NULL;
 return 1;
}

 

void CreateList(LinkList &L,int n)
{
     int i;
     LinkList p,q;
     L=(LinkList)malloc(sizeof(LNode));
     L->next=NULL;
     q=L;
     printf("Please input %d numbers:\n",n);
     for(i=1; i<=n; i++)
     {
          p=(LinkList)malloc(sizeof(LNode));
          scanf("%d",&p->data);
          q->next=p;
          q=q->next;
        }
        p->next=NULL;
}


int ClearList(LinkList L)
{
 LinkList p,q;
 p=L->next;
 while(p)
 {
  q=p->next;
  free(p);
  p=q;
 }
 L->next=NULL;
 return 1;
}

void PrintList(LinkList L)
{
     LinkList p;
     p=L->next;
     while(p)
     {
          printf("%d ",p->data);
          p=p->next;
        }
        printf("\n");
   
}

LinkList connect(LinkList ha,LinkList hb)
{
     LinkList hc,p,q;
     hc=(LinkList)malloc(sizeof(LNode));
     p=ha->next;
     hc->next=p;
     q=hb->next;
     while(p->next)
     {
          p=p->next;
        }
        p->next=q;
        free(ha);
        free(hb);
        return hc;
}

main.cpp

typedef int ElemType;
#include
#include
#include"LinkList.h"
void main()
{
  LinkList ha,hb,hc;
  CreateList(ha,8);
  CreateList(hb,4);
  hc=connect(ha,hb);
  printf("LinkList hc: ");
     PrintList(hc);
  printf("\n");
  ClearList(ha);
  ClearList(hb);
  ClearList(hc);
}



2.16已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个数

起共len个元素后，将它们插入到表lb中第j个元素之前。试问此算法是否正确？若有错，请改正之。

linklist.h

#include
#define INFEASIBLE -1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;
//构造一个空的线性表L
int InitList(LinkList *L)
{
 (*L)=(LinkList)malloc(sizeof(struct LNode));
 if(!(*L))
  exit(0);
 (*L)->next=NULL;
 return 1;
}
void CreateList(LinkList &L,int n)
{
     int i;
     LinkList p,q;
     L=(LinkList)malloc(sizeof(LNode));
     L->next=NULL;
     q=L;
     printf("请输入 %d 个数字:\n",n);
     for(i=1; i<=n; i++)
     {
          p=(LinkList)malloc(sizeof(LNode));
          scanf("%d",&p->data);
          q->next=p;
          q=q->next;
        }
        p->next=NULL;
}


int ClearList(LinkList L)
{
 LinkList p,q;
 p=L->next;
 while(p)
 {
  q=p->next;
  free(p);
  p=q;
 }
 L->next=NULL;
 return 1;
}

void PrintList(LinkList L)
{
     LinkList p;
     p=L->next;
     while(p)
     {
          printf("%d ",p->data);
          p=p->next;
        }
        printf("\n");
  
}

Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len)
{
   LinkList p,prev,q,s;
   int k;
   if(i<0||j<0||len<0) return INFEASIBLE;
   p=la; k=0; prev=NULL;
   while(p&&k   {
    prev=p; p=p->next;k++;//在la查找第i个结点
   }
   if(!p) return INFEASIBLE;
   q=p; k=1;               //p指向la表中的第i个结点
   while(q&&k   {
    q=q->next; k++;     //查找la表中的第i+len-1个结点
   }
   if(!q) return INFEASIBLE;
   if(!prev) la=q->next;   //i=1的情况
   else prev->next=q->next;//完成删除
   if(j==1)
   {
    q->next=lb; lb=p;  //将从la中删除的结点插入到lb中
   }
   else {
    s=lb;k=1;
    while(s&&k    {
     s=s->next; k++;//查找lb表中的第j-1个元素
    }
    if(!s) return INFEASIBLE;
    q->next=s->next; s->next=p;//完成插入
    return OK;
   }
}
mian.cpp

#include
#include"linklist.h"
void main()
{
  LinkList la,lb;
 int account=1, x,y,m,n;
 int i,j,len,a,b;
 printf("请输入线性表A的长度：");
 scanf("%d",&a);
 CreateList(la,a);
 printf("请输入线性表B的长度：");
 scanf("%d",&b);
 CreateList(lb,b);
 printf("请输入i的值：");
 scanf("%d",&i);
 printf("请输入j的值：");
 scanf("%d",&j);
 printf("请输入len的值：");
 scanf("%d",&len);
 DeleteAndInsertSub(la,lb,i,j,len);
 printf("输出线性表A如下：\n");
 PrintList(la);
 printf("输出线性表B如下：\n");
 PrintList(lb);
 ClearList(la);
 ClearList(lb);
}



《数据结构题集》（C语言版）答案 数据结构（C语言版）的算法C语言源码 数据结构（C语言版）编程题 数据结构课程设计（C语言版） 数据结构与算法中的一点问题(c语言版)? 数据结构与算法中的一点问题(c语言版) 《数据结构（c语言版）习题集》下载 数据结构 c语言版(严尉敏) 数据结构(C语言版) 数据结构(C语言版)下载 数据结构C语言版笔记 数据结构（C语言版）的视频在哪里下载的 急:::《数据结构》（C语言版）．严蔚敏，吴伟明 在哪能下到数据结构C语言版 谁知道清华大学的教材<数据结构题集(c语言版)>有没有配套的习题解答啊? 《数据结构(C语言版)》(配书光盘DSDemo)[ISO] 数据结构C语言版的那些伪代码，根本看不懂怎么办？ 数据结构学不会，怎么办啊？C语言版严蔚敏版的 一个很有挑战性的数据结构问题(C语言版) 高分求！！！！数据结构严慰敏c语言版的多媒体课件 关于数据结构(c语言版的)的几个程序问题 求严蔚敏的数据结构(C语言版)的电子书下载 改程序——银行家算法C语言版 求数据结构 c语言算法代码