回 帖 发 新 帖 刷新版面

主题:新手求助:一个关于单链表的插入排序问题

要求如下;
1、从键盘读入一个英文句子,取出其中每一个单词,并按单词的字顺排序输出。
2、假定每个单词以空格隔开,句子以‘.’为结束符。
3、给出源程序和可执行文件。
  下面是偶的代码,大家忙我看看,编译时不出错,但只能处理一个单词的句子,不知道为什么,如果在句子中加入空格,则无法跳出tc,必须强制关掉它。
  先orz....
#define MAXNUM1 500
#define MAXNUM2 30
#define MAXNUM3 100
#include <string.h>
#include <stdio.h>
struct Node;                 /*单链表数据类型*/          
typedef struct Node *PNode;       /*单链表节点类型*/ 
struct Node{
    char     *info;
    PNode     link;
        };               /*单链表节点结构*/
typedef struct Node *LinkList;      /*单链表类型*/
 /*创建带头节点的空链表&申请一个节点空间*/
LinkList creatNullList_link(void){
    LinkList llist=(LinkList)malloc(sizeof(struct Node));         

            /*申请表头节点空间*/
    if(llist)    llist->link=NULL;
    else          printf("Out of flow!\n");/*创建失败*/
    return(llist);
}
/*判断链表是否为空*/
int isNullList_link(LinkList llist){
    return(llist->link==NULL);
    }
/*单链表插入(带排序)*/
int insertList_link(LinkList llist,char *x){
/*在llist带头节点的单链表中,有序地插入一个元素*/    
    PNode p;
    PNode q=(PNode)malloc(sizeof(struct Node));
    if(!q){
        printf("Out of space!!   \n");
        return(0);
        }
    q->info=(char*)malloc(sizeof(char)*MAXNUM2);
    q->info=strdup(x);
   /*库函数strdup是用来把数组x复制到指定空间里*/
   /*另一个库函数strcmp是一个字符串比较函数*/
    if(isNullList_link(llist)){
        p=llist;
        p->link=q;
        q->link=NULL;
        return(1);}/*空表*/
    else if(llist->link->link==NULL){
        p=llist;
        if(strcmp(p->link->info,q->info)>0){
            q->link=p->link;
            p->link=q;
            return(1);
            }
        else{
            p=p->link;
            p->link=q;
            q->link=NULL;
            }
        }/*只有一个实节点*/
    else{/*有不少于两个实节点*/
        p=llist->link;
        if(strcmp(p->info,q->info)>0){
            q->link=p;
            p=q;
            return(1);
            }
        else{
            while(p->link){
                if(strcmp(p->info,q->info)

<=0&&strcmp(p->link->info,q->info)>0){
                    q->link=p->link;
                    p->link=q;
                    return(1);    
                    }
                p=p->link;
                }
            }
        p->link=q;
        q->link=NULL;
        return(1);
        }
    }
/*释放链表空间*/
void  deleteList_link(LinkList llist){
       PNode p,q;
    p=llist;
    while(p){
        q=p->link;
        free(p);
        p=q;
    }
}
/*求从串s中第i个字符开始连续取j个字符所构成的子串 */
char *substr(char *s,int i,int j){
    char *s1;
    int k;
    s1=(char*)malloc(sizeof(char)*MAXNUM2);
    if(!s1)        return(NULL);
    if(i>0&&i<strlen(s)&&j>0){
        if(strlen(s)<i+j-1)
            j=strlen(s)-i+1;
/*若从i开始取不了j个字符,则能取几个就取几个*/
        for(k=0;k<j;k++)
            s1[k]=s[i+k-1];
        s1[j]='\n';
        }
    return(s1);
    } 
int main(void){
    int i=0,j=1;
    char *s,*sub;
 /*s存放我们输入的句子,sub用来存放句子中的各个单词*/
    int *pos,*len;
 /*pos是一个存放特殊位置(首位,末尾,以及空格)的数组,*/
       /*数组len存放单词长度*/
    PNode p;
    LinkList llist=creatNullList_link();
    s=(char*)malloc(sizeof(char)*MAXNUM1);
    sub=(char*)malloc(sizeof(char)*MAXNUM2);
    pos=(int*)malloc(sizeof(int)*MAXNUM3);
    len=(int*)malloc(sizeof(int)*MAXNUM2);
                 /*为以上指针申请空间*/
    if(!(s&&sub&&pos&&len))
        printf("Out of space!! \n");
                    /*申请失败*/
    printf("Enter your sentence:(xx xxx xx.)  \n");
    gets(s);     /*输入句子*/
    pos[0]=1;
    while(s[i]!='.'){
        while(s[i]==' '){
            pos[j]=i+1;
            j++;
            }
        i++;
        }
    pos[j]=i+1;
    len[0]=pos[1]-pos[0];
    for(i=0;i<j;i++)
        len[i]=pos[i+1]-pos[i]-1;
         /*以上都在确定数组pos和len*/
    for(i=0;i<j;i++){
        sub=strdup(substr(s,pos[i],len[i]));
        /*得到一个单词*/
        insertList_link(llist,sub);/*插入*/
        }
    p=llist;
    while(p->link){
        p=p->link;
        printf("%s\n",p->info);
        }
    /*输出*/
    free(s);
    free(sub);
    free(pos);
    free(len);
    deleteList_link(llist);
    /*释放空间*/
    }

回复列表 (共1个回复)

沙发

我自己改过后已经可以运行了,代码如下:
#define MAXNUM1 500
#define MAXNUM2 30
#include <string.h>
#include <stdio.h>
struct Node;                 /*单链表数据类型*/
typedef struct Node *PNode;       /*单链表节点类型*/
struct Node{
    char     *info;
    PNode     link;
        };               /*单链表节点结构*/
typedef struct Node *LinkList;      /*单链表类型*/
 /*创建带头节点的空链表&申请一个节点空间*/
LinkList creatNullList_link(void){
    LinkList llist=(LinkList)malloc(sizeof(struct Node));                     /*申请表头节点空间*/
    if(llist)    llist->link=NULL;
    else          printf("Out of flow!\n");/*创建失败*/
    return(llist);
}
/*判断链表是否为空*/
int isNullList_link(LinkList llist){
    return(llist->link==NULL);
    }
/*单链表插入(带排序)*/
int insertList_link(LinkList llist,char *x){
/*在llist带头节点的单链表中,有序地插入一个元素*/
    PNode p=llist;
    PNode q=(PNode)malloc(sizeof(struct Node));
    if(!q){
        printf("Out of space!!   \n");
        return(0);
        }
    q->info=(char*)malloc(sizeof(char)*MAXNUM2);
    q->info=strdup(x);
    p->info=NULL;
   /*库函数strdup是用来把数组x复制到指定空间里*/
   /*另一个库函数strcmp是一个字符串比较函数*/
    if(isNullList_link(llist)){
        p->link=q;
        q->link=NULL;
        return(1);}/*空表*/
    else{       /*非空表*/
        while(p->link){
            if(strcmp(p->info,q->info)<=0&&
            strcmp(p->link->info,q->info)>0){
                    q->link=p->link;
                    p->link=q;
                    return(1);
                    }
                p=p->link;
                }
        p->link=q;/*若为最大值,则在最后插入*/
        q->link=NULL;
        return(1);
        }
    }
/*释放链表空间*/
void  deleteList_link(LinkList llist){
    PNode p,q;
    p=llist;
    while(p){
        q=p->link;
        free(p);
        p=q;
    }
}
main(){
    int i=0,j=0;
    char *s,*sub;
 /*s存放用户输入的句子,sub用来存放句子中的各个单词*/
    PNode p;
    LinkList llist=creatNullList_link();
    s=(char*)malloc(sizeof(char)*MAXNUM1);
    sub=(char*)malloc(sizeof(char)*MAXNUM2);
                 /*为以上指针申请空间*/
    if(!s||!sub)
        printf("Out of space!! \n");
                    /*申请失败*/
    printf("Enter your sentence:(xx xxx xx.)  \n");
    gets(s);     /*输入句子*/
    for(;i<strlen(s);i++)
        if(s[i]==' ')
            j++; /*计算空格的数目*/
    sub = strtok(s," ");
/*库函数strtok将s1中首次出现s2中字符的位置置为NULL,*/
/*因此会破坏s1字符串。*/
/*该函数一般用于分解s1字符串为用特定分隔符分隔的多个字符串,*/
/*s2一般设置为s1中的分隔字符,比如空格,逗号等,*/
/*例如将一条自然英文语句分解为单词。*/
    insertList_link(llist , sub);
    for(i=1;i<j;i++){
        sub = strtok(NULL , " ");
        insertList_link(llist , sub);
        }
    sub = strtok(NULL , ".");
    insertList_link(llist , sub);
    p = llist;
    i=0;
    /*输出*/
    printf("____________________________________________________________\n");
    while(p->link){
        p = p->link;
        i++;
        printf("%-15s" , p->info);
        if(i%4==0)
            printf("\n");/*每四个一行*/
        }
    printf("\n____________________________________________________________\n");
    free(s);
    free(sub);
    deleteList_link(llist);
    /*释放空间*/
    }
哈哈哈,好高兴啊。。。

我来回复

您尚未登录,请登录后再回复。点此登录或注册