原创数据结构第二章习题参考答案(第一部分)

 2008-3-31 21:13  4472 6 6 分类: 软件与OS

这章题目比较多,这是第一部分,后续等我有时间再做.

#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct{
int *elem;
int length;
int listsize;
}SqList;

//初始化顺序表
bool init_sqlist(SqList *L)
{
if((L->elem=(int *)malloc(sizeof(int)*LIST_INIT_SIZE))==NULL)
return false;
L->length=0;
L->listsize=LIST_INIT_SIZE;
return true;
}

//习题2.10
bool delete_slistk(SqList *L,int i,int k)
{
int j;
if(i<0||k<0||i+k>L->length)
return false;
for(j=i+k;j<L->length;j++)
{
L->elem[j-k]=L->elem[j];
}
L->length-=k;
return true;
}

//习题2.11
bool insert_increment_list(SqList *L,int x)
{
int i;
if(L->length>=L->listsize)
  return false;
for(i=L->length;i>=0;i--)
{
  if(L->elem<x)
  {
   L->elem[i+1]=x;
   return true;
  }
  L->elem[i+1]=L->elem;
}
L->length+=1;
return true;
}

//习题2.12
int compare_sqlist(SqList *La, SqList* Lb)
{
int i =0;
while((i<La->length)&&(i<Lb->length))
{
  if(La->elem>Lb->elem)
   return 1;
  if(La->elem<Lb->elem)
   return -1;
  i++;
}
if(i==La->length)
{
  if(i==Lb->length)
   return 0;
  return -1;
}
return 1;
}

typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
//初始化链表
bool init_linklist(LinkList *l)
{
if((*l=(LinkList)malloc(sizeof(LNode)))==NULL)
  return false;
(*l)->next=NULL;
return true;
}
//插入链表头
bool insert_linklist_head(LinkList l,int x)
{
LNode *pNode;
if((pNode=(LNode *)malloc(sizeof(LNode)))==NULL)
{
  return false;
}
pNode->data=x;
pNode->next=l->next;
l->next=pNode;
return true;
}

//习题2.13
int locate(LinkList l,int x)
{
int i="0";
/*
LinkList p="l";
while(p->next!=NULL)
{
  i++;
  p=p->next;
  if(p->data==x)
   return i;
}
return 0;//没找到
*/
while(l->next!=NULL)
{
  i++;
  l=l->next;
  if(l->data==x)
   return i;
}
return 0;//没找到
}

//习题2.15
LinkList *linklistcat(LinkList La, LinkList Lb)
{
LinkList *p;
if((p=(LinkList*)malloc(sizeof(LinkList)))==NULL)
  return NULL;

*p=La;
while(La->next!=NULL)
  La=La->next;
La->next=Lb->next;
return p;
}

//习题2.16
bool DeleteAndInsertSub(LinkList La, LinkList Lb,int i,int j,int len)
{
if(i<=0||j<=0||len<0)
  return false;
LNode *p=La;
int k="1";
while((k<i)&&(p->next!=NULL))
{
  p=p->next;
  k++;
}
LNode *s=p;
k=0;
while((k<len)&&(s->next!=NULL))
{
  s=s->next;
  k++;
}

LNode *q=Lb;
k=1;
while((k<j)&&(q->next!=NULL))
{
  q=q->next;
  k++;
}
//插入Lb
LNode *tmp=s->next;
s->next=q->next;
q->next=p->next;

//从La删除这些节点
p->next=tmp;

return true;
}

//习题2.17
bool insert_list(LinkList *l,int i,int x)
{
int j="1";
LinkList p;
if(*l==NULL&&i<1)
{
  p=(LinkList)malloc(sizeof(LNode));
  if(p==NULL)
   return false;
  p->next=NULL;
  p->data=x;
  *l=p;
  return true;
}

p=*l;
while((j<i-1)&&(p->next!=NULL))
{
  p=p->next;
  j++;
}
if(j<i-1)
  return false;

LNode *pNode=(LinkList)malloc(sizeof(LNode));
if(pNode==NULL)
  return false;
pNode->data=x;
pNode->next=p->next;
p->next=pNode;
return true;
}

//习题2.19
bool delete_range(LinkList l,int mink,int maxk)
{
if(mink>maxk)
  return false;
LinkList p="l";
LinkList begin,end;
while((p!=NULL)&&(p->data<mink))
{
  begin=p;
  p=p->next;
}

while((p!=NULL)&&(p->data<=maxk))
{
  p=p->next;
}
end=p;
if(begin==NULL)
  return false;
begin->next=end;
return true;
}

//习题2.21:对顺序表就地倒置
void reverse_sqlist(SqList *L)
{
int tmp;
int i="0";
while(i<L->length-1-i)
{
  tmp=L->elem;
  L->elem=L->elem[L->length-1-i];
  L->elem[L->length-i]=tmp;
  i++;
}
}

//习题2.22:对链表就地倒置
void reverse_linklist(LinkList L)
{
LinkList s,p,q,tmp;
s=NULL;
p=L->next;
q=p->next;
while(q!=NULL)
{
  p->next=s;
  s=p;
  tmp=q->next;
  q->next=p;
  p=q;
  q=tmp;
}
L->next=p;
}

int main(int argc, char* argv[])
{
//test ex2.10
SqList list;
int i;
if(!init_sqlist(&list))
{
  printf("init sqlist error\n");
  return 1;
}
for(i=0;i<LIST_INIT_SIZE;i++)
{
  list.elem=i;
}
list.length=LIST_INIT_SIZE;
printf("before delete, the list hold the following data:\n");
for(i=0;i<LIST_INIT_SIZE;i++)
{
  printf("%d\t",list.elem);
}
printf("\n");
if(!delete_slistk(&list,10,20))
{
  printf("delete error\n");
  return 1;
}
printf("after delete, the list hold the following data:\n");
for(i=0;i<list.length;i++)
{
  printf("%d\t",list.elem);
}
printf("\n");

//test ex 2.11
int x="37";
if(!insert_increment_list(&list,x))
{
  printf("insert error\n");
  return 1;
}
printf("after insert, the list hold the following data:\n");
for(i=0;i<list.length;i++)
{
  printf("%d\t",list.elem);
}
printf("\n");

//test ex2.12
SqList La,Lb;
if(!init_sqlist(&La))
{
  printf("init sqlist error\n");
  return 1;
}

if(!init_sqlist(&Lb))
{
  printf("init sqlist error\n");
  return 1;
}

for(i=0;i<20;i++)
{
  La.elem=0x20+i;
}
La.length=20;
for(i=0;i<20;i++)
{
  Lb.elem=0x20+i;
}
Lb.length=20;
int ret="compare"_sqlist(&La,&Lb);
switch(ret)
{
case 0:
  printf("La=Lb\n");
  break;
case 1:
  printf("La>Lb\n");
  break;
case -1:
  printf("La<Lb\n");
  break;
default:
  printf("compare error\n");
  break;
}

//test ex2.13
LinkList llist,pa;
if(!init_linklist(&llist))
{
  printf("init linklist error\n");
  return 1;
}
for(i=0;i<14;i++)
{
  if(!insert_linklist_head(llist,0x10+i))
  {
   printf("insert linklist error\n");
   return 1;
  }
}
printf("Now link list hold:\n");
pa=llist->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");
int k="24";
i=locate(llist,k);
printf("%d locate in %d address\n",k,i);
//printf("%d\n",llist->next->data);

//test ex2.15
LinkList llist1;
if(!init_linklist(&llist1))
{
  printf("init linklist error\n");
  return 1;
}
for(i=0;i<14;i++)
{
  if(!insert_linklist_head(llist1,0x70+i))
  {
   printf("insert linklist error\n");
   return 1;
  }
}
printf("Now link list hold:\n");
pa=llist1->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");
//now 连接
LinkList *plc=linklistcat(llist,llist1);
if(plc==NULL)
{
  printf("cat linklist error\n");
  return 1;
}
printf("after cat............\n");
pa=(*plc)->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");

//test ex2.16
if(!DeleteAndInsertSub(llist,llist1,5,7,4))
{
  printf("delete and insert sub error\n");
  return 1;
}
printf("now llist hold:\n");
pa=llist->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");

printf("llist1 now hold:\n");
pa=llist1->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");

//test ex2.17
LinkList llist2=NULL;

//插入第一个元素
insert_list(&llist2,0,80);
for(i=0;i<9;i++)
{
  insert_list(&llist2,i+1,81+i);
}
printf("after insert 10 data element, the list hold:\n");
pa=llist2;
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->^\n",pa->data);

//test ex2.19
  LinkList llist3;
if(!init_linklist(&llist3))
{
  printf("init linklist error\n");
  return 1;
}
for(i=0;i<14;i++)
{
  if(!insert_linklist_head(llist3,90-i))
  {
   printf("insert linklist error\n");
   return 1;
  }
}
printf("before delete range link list hold:\n");
pa=llist3->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");
if(!delete_range(llist3,80,85))
{
  printf("delete range error\n");
  return 1;
}
printf("after delete range link list hold:\n");
pa=llist3->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");

//test ex2.21
printf("------------------------------------------\n");
printf("before reverse, sqlist hold\n");
for(i=0;i<list.length;i++)
{
  printf("%d\t",list.elem);
}
printf("\n");
reverse_sqlist(&list);
printf("------------------------------------------\n");
printf("after reverse, sqlist hold\n");
for(i=0;i<list.length;i++)
{
  printf("%d\t",list.elem);
}
printf("\n");

//test ex2.22
printf("------------------------------------------\n");
printf("before reverse, linklist hold\n");
pa=llist2->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");
reverse_linklist(llist2);
printf("after reverse, linklist hold\n");
pa=llist2->next;
printf("|-->");
while(pa->next!=NULL)
{
  printf("%d-->",pa->data);
  pa=pa->next;
}
printf("%d-->",pa->data);
printf("^\n");
return 0;
}

写原创有奖励！2024面包板原创奖励正在进行中

 点赞（6）

 收藏

分享到： 
 

上一篇：数据结构第三章习题参考答案(2)

下一篇：数据结构第二章习题参考答案(第二部分)

IIC Shenzhen - 2024国际集成电路展览会暨研讨会（深圳，11.5-6）

2024 AI& Connect 是德创新技术峰会（深圳，10.22）

第六届意法半导体工业峰会2024（深圳，10.29）

2024 Arm Tech Symposia 年度大会（上海/深圳，11月19/21日）

文章评论（0条评论）
登录后参与讨论

您需要登录后才可以评论登录 | 立即注册

用户1361860

文章：289 阅读：1051915 评论：266 赞：2508

 好友  私信个人主页

文章 289

原创 0

阅读 1051915

评论 266

赞 2508

最新评论更多

写的好，学习参考，很实用，拆的很细，老物件，电子产品

开发工匠 ... 评论博文 2024-12-12

不得不拆解修理台式组合音响

图片失效了呢

OPTIMIST 评论博文 2024-12-10

美的风扇灯拆解：如何实现极致高效的稳定输 ...

期待续更

Jun2024 评论博文 2024-12-10

比较器检测模拟脉冲说明（四） ...

最新博文

康谋方案 | 多源相机数据采集与算法集 ...

PCBA打样需要哪些准备？

实施TPM过程中如何进行设备的全面清查 ...

资料下载

本周热帖

[14章附电子书]Springboot+ChatGLM 实 ...

24LC02芯片手册以及注意事项 ...

《高等代数自学教程》（下册，贺昌亭 ...

11-19学习笔记

SATA specification

【2024年末活动】工程师写总结，送示 ...

【STM32F103C8T6教程】（七）串口通信 ...

【富芮坤FR3068x-C】+上手及点灯 ...

ESD保护二极管的四大特点丨浪拓 ...

【富芮坤 FR3068x-C低功耗开发板】-01 ...

最新资讯

芯语最新

马斯克刷新世界首富记录：身家超过400 ...

欧洲港口自动化战略：在AI浪潮中增强 ...

为什么说机器人的“ChatGPT时刻”将至 ...

用4200A和矩阵开关搭建自动智能的可靠 ...

1961年的金色功率音频放大器，挑战当 ...

马斯克身价突破4000亿美元！ ...

苏姿丰获年度最佳CEO

分享PA大佬的2个PPT，内容详实! ...

传：欧洲半导体巨头英飞凌将在中国生 ...

《DFT设计与实现》

EE直播间
更多

提升毫米波信号测试精度直播时间： 12月18日 14:00

EE Talk主题专访系列直播-对话：释放 Wi-Fi 7 在高带宽应用中的技术潜力直播时间： 12月19日 10:00

在线研讨会
更多

ADAS系统中采用的MEMS时钟

PLL基础知识及其在时钟系统中的应用

PIC16F13145单片机可配置逻辑模块（CLB）概览

适用于安全连接的新一代PIC32CK SG/GC系列单片机

热门推荐

精密双向电流感应放大器设计方案
【有奖直播】提升毫米波信号测试精度
【有奖直播】深入学习Microchip时钟和全新单片机方案