原创数据结构第4章习题参考答案

 2008-3-31 21:10  4537 9 9 分类: 软件与OS

这个是第4章的习题,只有关于KMP算法的几个题目没做

---------------------------------------------------------------------------------

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

//heap string 定义
typedef struct _HString
{
char *str;
int length;
}HString;

void init_hstring(HString *s)
{
s->str=NULL;
s->length=0;
// return true;
}
//ex4.15
bool StrAssign(HString *s,char *c)
{
int i,len=0;
if(s->str)
free(s->str);

while(*(c+len))
  len++;
if((s->str=(char*)malloc(sizeof(char)*len))==NULL)
{
  return false;
}

for(i=0;i<len;i++)
{
  s->str=c;
}
s->length=len;
return true;
}

bool StrCopy(HString *s,HString *t)
{
int len,i;
len=t->length;
if(s->str)
  free(s->str);

if((s->str=(char*)malloc(sizeof(char)*len))==NULL)
{
  return false;
}

for(i=0;i<len;i++)
{
  s->str=t->str;
}
s->length=len;
return true;
}

//ex4.16
int StrCompare(HString s1,HString s2)
{
int i,ret=0;
for(i=0;i<s1.length&&i<s2.length;i++)
{
  if(s1.str<s2.str)
   return -1;
  if(s1.str>s2.str)
   return 1;
}
if(i<s1.length)
  return 1;
if(i<s2.length)
  return -1;
return 0;
}
//ex4.24
HString *StrCat(HString *s1,HString *s2)
{
int i;
if((s1->str=(char*)realloc(s1->str,sizeof(char)*(s1->length+s2->length)))==NULL)
  return NULL;
for(i=0;i<s2->length;i++)
  s1->str[s1->length+i]=s2->str;
s1->length+=s2->length;
return s1;
}

int StrLength(HString s)
{
return s.length;
}

void ClearString(HString s)
{
if(s.str)
  free(s.str);
s.length=0;
}

HString *SubString(HString *s,int pos,int len)
{
int k="len";
HString *tmp;

if(pos<0||pos>=s->length||len<1)
  return NULL;
if(pos+len>s->length)
  k=s->length-pos;
if((tmp=(HString *)malloc(sizeof(HString)))==NULL)
  return NULL;
tmp->str=s->str+pos;
tmp->length=k;
return tmp;
}

//ex4.10
void string_reverse(HString *s,HString *t)
{
int i="s-">length-1;
int j;
for(j=0;j<s->length;j++,i--)
{
  StrCat(t,SubString(s,i,1));
  //StrAssign(t,&s->str);
}

}

//ex4.11
void string_substract(HString *s,HString *t,HString *p,int *pos)
{
int i,j,k;
HString *tmp,*q;

for(i=0,k=0;i<s->length;i++)
{
  tmp=SubString(s,i,1);
  for(j=0;j<i;j++)
  {
   q=SubString(s,j,1);
   if(!StrCompare(*tmp,*q))
    break;
  }
  if(i==j)
  {
   for(j=0;j<t->length;j++)
   {
    if(!StrCompare(*(SubString(t,j,1)),*tmp))
     break;
   }
   if(j==t->length){
    StrCat(p,tmp);
    //StrCopy(p,q);
    pos[k++]=i;
   }
  }

}
p->length=k;
}

//ex4.12,ex4.17,ex4.25
bool string_replace(HString *s, HString t,HString v)
{
HString *tmp;
int i,j;
int vlen="StrLength"(v);
int tlen="StrLength"(t);

for(i=0;i<s->length;)
{
  tmp=SubString(s,i,tlen);
  if(StrCompare(*tmp,t)==0)
  {
   if(vlen<=tlen)
   {
    for(j=0;j<vlen;j++)
    {
     s->str[i+j]=v.str[j];
    }
    for(j=0;j<StrLength(*s)-i-tlen;j++)
    {
     s->str[i+vlen+j]=s->str[i+tlen+j];
    }
    s->length-=tlen-vlen;
    i+=vlen;
   }
   else
   {
    s->str=(char*)realloc(s->str,sizeof(char)*(StrLength(*s)+vlen-tlen));
    if(s->str==NULL)
     return false;

    for(j=0;j<StrLength(*s)-i-tlen;j++)
    {
     s->str[StrLength(*s)-1-j+vlen-tlen]=s->str[StrLength(*s)-1-j];
    }
    for(j=0;j<vlen;j++)
    {
     s->str[i+j]=v.str[j];
    }

    s->length+=vlen-tlen;
    i+=vlen;
   }
  }
  else
  {
   i++;
  }
}
return true;

}

//ex4.13
void string_delete(HString *s, HString t)
{
HString *tmp;
int i,j;
int slen="StrLength"(*s);
int tlen="StrLength"(t);

for(i=0;i<s->length;i++)
{
  tmp=SubString(s,i,tlen);
  if(StrCompare(*tmp,t)==0)
  {
   for(j=0;j<s->length-i-tlen;j++)
   {
    s->str[i+j]=s->str[i+tlen+j];
   }
   s->length-=tlen;
  }
}
}

//ex4.18
typedef struct _INFO
{
char c;
int num;
struct _INFO *next;
}info,*pinfo;

void update_list(pinfo list,char c)
{
pinfo p,q;

p=list->next;
q=list;
while(p!=NULL)
{
  if(p->c==c)
  {
   p->num++;
   break;
  }
  q=p;
  p=p->next;
}
if(p==NULL)
{
  p=q;
  q=(pinfo)malloc(sizeof(info));
  if(q!=NULL)
  {
   q->c=c;
   q->num=1;
   q->next=p->next;
   p->next=q;
  }
}
}


pinfo count_chars(HString s)
{
pinfo head=(pinfo)malloc(sizeof(info));
if(head==NULL)
  return NULL;
head->next=NULL;

int i;
int len="StrLength"(s);
char c;

for(i=0;i<len;i++)
{
  c=s.str;
  update_list(head,c);
}
return head;
}

//ex 4.21
//带头结点的链表描述string
typedef struct _LStringNode
{
char c;
struct _LStringNode *next;
}LStringNode,*LString;

bool init_lstring(LString *s)
{
*s=(LString)malloc(sizeof(LStringNode));
if(*s==NULL)
  return false;
(*s)->next=NULL;
return true;
}

bool LStrAssign(LString s, char *c)
{
LStringNode *p=s->next;
LStringNode *q,*k;
int i;

k=s;
for(i=0;i<strlen(c);i++)
{
  if(p!=NULL)
   p->c=c;
  else
  {
   q=(LString)malloc(sizeof(LStringNode));
   if(q==NULL)
    return false;
   q->c=c;
   q->next=NULL;
   k->next=q;
  }
  k=k->next;
  p=k->next;
}
return true;
}

bool LStrCopy(LString s,LString t)
{

if(s==NULL||t==NULL)
  return false;
LStringNode *p=s->next;
LStringNode *q=t->next;
LStringNode *tmp,*k;
k=s;
while(q!=NULL)
{
  if(p!=NULL)
   p->c=q->c;
  else
  {
   tmp=(LString)malloc(sizeof(LStringNode));
   if(tmp==NULL)
    return false;
   tmp->c=q->c;
   tmp->next= NULL;
   k->next=tmp;
  }
  k=k->next;
  p=k->next;
  q=q->next;
}
return true;
}

int LStrCompare(LString s,LString t)
{
LStringNode *p=s->next;
LStringNode *q=t->next;

while(p!=NULL&&q!=NULL)
{
  if(p->c>q->c)
   return 1;
  if(p->c<q->c)
   return -1;
  p=p->next;
  q=q->next;
}
if(p==NULL&&q==NULL)
  return 0;
if(p==NULL)
  return -1;
else
  return 1;
}

int LStrLength(LString s)
{
int i="0";
LStringNode *p=s->next;
while(p!=NULL)
{
  i++;
  p=p->next;
}
return i;
}

LString LStrCat(LString s,LString t)
{
LStringNode *p=s;
LStringNode *q=t->next;
while(p->next!=NULL)
{
  p=p->next;
}
p->next=q;
return s;
}

LString LSubString(LString s,int pos,int len)
{
LString sub;

LStringNode *p=s->next;
LStringNode *q,*k;

int i="0";
while(p!=NULL&&i<pos-1)
{
  p=p->next;
  i++;
}
if(p==NULL&&i<pos-1||len<1)//pos or len参数无效
  return NULL;
sub=(LString)malloc(sizeof(LStringNode));
if(sub==NULL)
  return NULL;
sub->next=NULL;
q=sub;
i=0;
while(i<len&&p!=NULL)
{
  if((k=(LString)malloc(sizeof(LStringNode)))==NULL)
   goto clear;
  k->c=p->c;
  k->next=q->next;
  q->next=k;
  q=k;
  p=p->next;
  i++;
}
return sub;

clear://出错处理，free所有已经分配的结点，并返回NULL
q=sub;
while(q!=NULL)
{
  k=q->next;
  free(q);
  q=k;
}
return NULL;
}

//ex4.23
/**************************************************
**思路是：
**设置一个stack和一个queue
**把string的前一半字符放进queue中，把后半段push到stack中
**然后逐个从queue和stack中各取一个字符，比较，
**如果所有的都相等，则是对称的string
**************************************************/

//////////////////////////////////////////////////////
//
//下面实现一个stack及其基本操作
//ex4.23会用到
//
/////////////////////////////////////////////////////
#define STACK_INIT_SIZE 1024

typedef struct _sqstack
{
int *bottom;
int top;
int size;
}sqstack,*psqstack;

//初始化stack
bool init_stack(sqstack *s)
{
if((s->bottom=(int *)malloc(sizeof(int)*STACK_INIT_SIZE))==NULL)
  return false;
s->top=-1;
s->size=STACK_INIT_SIZE;
return true;
}

bool push(psqstack s,int x)
{
if(s->top>=s->size-1)
  return false;
s->bottom[++s->top]=x;
return true;
}

bool pop(sqstack *s,int *x)
{
if(s->top==-1||s->size<=0)
  return false;
*x=s->bottom[s->top--];
return true;
}

bool stack_empty(sqstack *s)
{
if(s->top==-1)
  return true;
return false;
}

bool get_stack_top(sqstack *s,int *x)
{
if(s->top==-1||s->size<=0)
  return false;
*x=s->bottom[s->top];
return true;
}

void destroy_stack(psqstack s)
{
free(s->bottom);
s->size=0;
s->top=-1;
}

void clean_stack(psqstack s)
{
s->top=-1;
}

int stack_length(psqstack s)
{
return s->top+1;
}

///////////////////////////////////////////
//
//再定义一个queue及相关操作
//
///////////////////////////////////////////
typedef struct _squeue
{
int data[512];
int front;
int rear;
}squeue;

void init_squeue(squeue *q)
{
q->front=-1;
q->rear=0;

}

bool EnSqueue(squeue *q,int x)
{
if(q->rear>=512)
  return false;
q->data[q->rear++]=x;
return true;
}

bool DeSqueue(squeue *q,int *x)
{
if(q->front+1==q->rear)//空
  return false;
*x=q->data[++q->front];
return true;
}
///////////////////////////////////////
//
//我们重新定义LString,链表结构的string
//上面的那种定义有一些不方便的地方，采用
//课本上的定义，更方便点
//因此，其实上面那些题目如果采用这种定义，
//还可以写的好些
//
///////////////////////////////////////
#define CHUNKSIZE    1

typedef struct _chunk
{
char ch[CHUNKSIZE];
struct _chunk *next;
}chunk;

typedef struct _LLString
{
chunk *head,*tail;
int curlen;
}LLString;

//初始化
void init_llstring(LLString *s)
{
s->head=s->tail=NULL;
s->curlen=0;
}

bool LLStrAssign(LLString *s,char *c)
{
chunk *p=s->head;
chunk *q;
int i="0";

if(c[0]==0)
  return false;
if(s->tail==NULL)//s是空的
{
  q=(chunk*)malloc(sizeof(chunk));
  if(q==NULL)
   return false;
  q->ch[0]=c[0];
  s->head=s->tail=q;
  s->curlen=1;
  i=1;
}
while(i<s->curlen&&c!='\0')
{
  p->ch[0]=c[i++];
  p=p->next;
}
s->curlen=i;
if(c==0)
  return true;
while(c!=0)
{
  q=(chunk*)malloc(sizeof(chunk));
  if(q==NULL)
   return false;
  q->ch[0]=c[i++];
  //p->next=q;
  s->curlen++;
  s->tail->next=q;
  s->tail=q;
}
return true;
}

int LLStrLength(LLString s)
{
return s.curlen;
}

//////////////////////////////////////
//
//下面是ex4.23的代码
//
//////////////////////////////////////
/***************************
**return:
* -1----error
* 0----是对称string
* 1----不是对称string
***************************/
int StrSymmetry(LLString s)
{
sqstack stack;
squeue queue;
if(!init_stack(&stack))
  return -1;
init_squeue(&queue);
char a,b;
int len="LLStrLength"(s);
int i;
chunk *p=s.head;

//将前半段入queue
for(i=0;i<len/2;i++)
{
  if(!EnSqueue(&queue,(int)(p->ch[0])))
  {
   destroy_stack(&stack);
   return -1;
  }
  p=p->next;
}
//将后半段入stack
if(len%2)
  p=p->next;
for(i=0;i<len/2;i++)
{
  if(!push(&stack,(int)(p->ch[0])))
  {
   destroy_stack(&stack);
   return -1;
  }
  p=p->next;
}
//比较
while(!stack_empty(&stack))
{
  pop(&stack,(int*)&a);
  DeSqueue(&queue,(int*)&b);
  if(a!=b)
  {
   destroy_stack(&stack);
   return 1;
  }
}
destroy_stack(&stack);
return 0;
}

int main(int argc, char* argv[])
{
//test HString operations

int i,j;
#if 0
HString s1,s2,*ps1;
init_hstring(&s1);
init_hstring(&s2);

if(!StrAssign(&s1,"qwhkjdjh828393930djd"))
{
  printf("StrAssign error\n");
  return 1;
}
printf("s1--length:%d\nhold :\n",s1.length);
for(i=0;i<s1.length;i++)
{
  printf("%c",s1.str);
}
printf("\n");

if(!StrAssign(&s1,"gslksky93dsjhgy743wekjhdkjsdkjdnciu39083-1112311!%^@&@*@"))
{
  printf("StrAssign error\n");
  return 1;
}
printf("s1--length:%d\nhold :\n",s1.length);
for(i=0;i<s1.length;i++)
{
  printf("%c",s1.str);
}
printf("\n");

ps1=SubString(&s1,5,10);
printf("SubString...ps1->length:%d\thold:\n",ps1->length);
for(i=0;i<ps1->length;i++)
{
  printf("%c",ps1->str);
}
printf("\n");
//ClearString(s1);
free(ps1);
#endif
//test ex4.11
#if 0
HString s,t,p;
int pos[256];
init_hstring(&s);
init_hstring(&t);
init_hstring(&p);

StrAssign(&s,"sdsj8789320390-ifdkdckkddjdjiur989riir85i55iekd");
StrAssign(&t,"dhhd740jd8409");
for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
for(i=0;i<t.length;i++)
{
  printf("%c",t.str);
}
printf("\n");

string_substract(&s,&t,&p,pos);
printf("after string substract:\n");
printf("length:%d\n",p.length);
for(i=0;i<p.length;i++)
{
  printf("%c",p.str);
}
printf("\n");
for(i=0;i<p.length;i++)
{
  printf("%d-",pos);
}
printf("\n");
#endif
//test ex4.10
#if 0
HString s,t;

init_hstring(&s);
init_hstring(&t);

StrAssign(&s,"sdsj8789320390-ifdkdckkddjdjiur989riir85i55iekd");

for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
string_reverse(&s,&t);
printf("after reverse\n");
for(i=0;i<t.length;i++)
{
  printf("%c",t.str);
}
printf("\n");

#endif

//test ex4.12
# if 0
HString s,t,p;

init_hstring(&s);
init_hstring(&t);
init_hstring(&p);

StrAssign(&s,"shdjjeuekdkfeynmansjfeynmanjdkdl;edd344");
StrAssign(&t,"feynman");
StrAssign(&p,"schwinger");
for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
for(i=0;i<t.length;i++)
{
  printf("%c",t.str);
}
printf("\n");
for(i=0;i<p.length;i++)
{
  printf("%c",p.str);
}
printf("\n");
if(!string_replace(&s,t,p))
{
  printf("string replace error\n");
  return 1;
}
for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
#endif

//test ex4.13
#if 0
HString s,t;

init_hstring(&s);
init_hstring(&t);

StrAssign(&s,"shdjjeuekdkfeynmansjfeynmanjdkdl;edd344");
StrAssign(&t,"feynman");
for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
for(i=0;i<t.length;i++)
{
  printf("%c",t.str);
}
printf("\n");
string_delete(&s,t);
for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
#endif

//test ex4.18
#if 0
HString s;
init_hstring(&s);

StrAssign(&s,"shdjjeuekdkfeynmansjfeynmanjdkdl;edd344");
for(i=0;i<s.length;i++)
{
  printf("%c",s.str);
}
printf("\n");
pinfo L="count"_chars(s);
if(L==NULL)
{
  printf("count error\n");
  return 1;
}
pinfo p="L-">next;
printf("||-->");
while(p!=NULL)
{
  printf("%c(%d)-->",p->c,p->num);
  p=p->next;
}
printf("^\n");
#endif

//test ex4.21
#if 0
LString s,t,p;
// int i;
LStringNode *k;
init_lstring(&s);
init_lstring(&t);
init_lstring(&p);
if(!LStrAssign(s,"hdd87993d&&*##))_##*$($$)fjmfjdjfo38505kj"))
{
  printf("LStrAssign error\n");
  return 1;
}
printf("after LStrAssign, the Lstring hold:\n");
k=s->next;
while(k!=NULL)
{
  printf("%c",k->c);
  k=k->next;
}
printf("\n");

if(!LStrCopy(t,s))
{
  printf("LStrCopy error\n");
  return 1;
}
printf("after LStrCopy, the Lstring hold:\n");
k=t->next;
while(k!=NULL)
{
  printf("%c",k->c);
  k=k->next;
}
printf("\n");

LStrAssign(p,"hdd87993d&&*##))_##*$($$)fjmfjd");
i=LStrCompare(s,t);
switch(i)
{
case -1:
  printf("string s < string t\n");
  break;
case 0:
  printf("string s= string t\n");
  break;
case 1:
  printf("string s > string t\n");
  break;
default:
  printf("shit, unknown error\n");
  break;
}

printf("string p now:\n");
k=p->next;
while(k!=NULL)
{
  printf("%c",k->c);
  k=k->next;
}
printf("\n");

i=LStrCompare(s,p);
switch(i)
{
case -1:
  printf("string s < string p\n");
  break;
case 0:
  printf("string s= string p\n");
  break;
case 1:
  printf("string s > string p\n");
  break;
default:
  printf("shit, unknown error\n");
  break;
}

LStrAssign(p,"hdd87993d&&*##))_##*$($$)fjmfjejfo38505kjhjdk");
printf("string p now:\n");
k=p->next;
while(k!=NULL)
{
  printf("%c",k->c);
  k=k->next;
}
printf("\n");
i=LStrCompare(s,p);
switch(i)
{
case -1:
  printf("string s < string p\n");
  break;
case 0:
  printf("string s= string p\n");
  break;
case 1:
  printf("string s > string p\n");
  break;
default:
  printf("shit, unknown error\n");
  break;
}
printf("string p length:%d\nstring s length:%d\nstring t length:%d\n",LStrLength(p),LStrLength(s),LStrLength(t));

if(LStrCat(s,p)==NULL)
{
  printf("LStrCat error\n");
  return 1;
}
printf("after strcat string s length=%d\n",LStrLength(s));
printf("string s now:\n");
k=s->next;
while(k!=NULL)
{
  printf("%c",k->c);
  k=k->next;
}
printf("\n");

t=LSubString(s,13,19);
if(t==NULL)
{
  printf("LSubString error\n");
  return 1;
}
printf("after LStrCopy, the string t hold:\n");
k=t->next;
while(k!=NULL)
{
  printf("%c",k->c);
  k=k->next;
}
printf("\n");

#endif

//test ex4.23
#if 1
LLString lls;
chunk *p;
init_llstring(&lls);
if(!LLStrAssign(&lls,"abcdefggfedcba"))
{
  printf("LLStrAssign error\n");
  return 1;
}
printf("LLString lls now is:\n");
p=lls.head;
for(i=0;i<lls.curlen;i++)
{
  printf("%c",p->ch[0]);
  p=p->next;
}
printf("\n");
printf("LLString lls length is :%d\n",LLStrLength(lls));
i=StrSymmetry(lls);
switch(i)
{
case -1:
  printf("invalid string check\n");
  break;
case 0:
  printf("it is a symmetry string\n");
  break;
case 1:
  printf("it is not a symmetry string\n");
  break;
default:
  printf("Unknown error occurred\n");
  break;
}

#endif

return 0;
}

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

 点赞（9）

 收藏

分享到： 
 

上一篇：算法导论chapter2的笔记

下一篇：数据结构第3章习题参考答案(1)

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

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

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

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

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

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

用户1361860

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

 好友  私信个人主页

文章 289

原创 0

阅读 1051880

评论 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教程】（七）串口通信 ...

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

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

什么是半导体芯片的失效切片分析？ ...

最新资讯

芯语最新

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

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

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

前11个月中国集成电路出口额，突破万 ...

上海应用技术大学等联合团队突破二维 ...

【喜讯】Littelfuse荣获电路保护行业 ...

AI医生已上线，内测中！打造高效便捷 ...

免费领900元鸿蒙先锋权益，抢先体验原 ...

喜讯 | 盘古信息荣获2024年度数字化转 ...

重磅！310亿！宁德时代成立合资企业 ...

EE直播间
更多

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

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

在线研讨会
更多

ADAS系统中采用的MEMS时钟

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

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

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

热门推荐

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