链表

用一组地址任意的存储单元依次存储表中各个数据元素，数据元素之间的逻辑关系通过指针间接地反映出来。

区别于需要预先分配连续空间的线性表，链表的空间占用可以随时分配或释放，使用时更加自由。

因为一般使用不连续的空间，链表必须用一个单元的指针连接下一个单元，这也意味着它没法像struct数组那样使用[n]来任意访问第n个单元。

与线性表不同，链表高度依赖指针操作，因此有->运算符用于访问指针对应结构体的元素。

显然，如果一个单元只记录后继单元的指针，那么就无法访问到指定单元的上一个单元。这个问题可以通过添加前导单元的指针来解决，但是操作会更加繁琐。一个简单的解决方案是将链表的首个单元置空，这样总是可以从第一个单元开始访问到任意单元，更符合数组操作的习惯，但运行可能更费时。

struct test
{
    int t;
};
struct test st;
struct test *stp=&st;
//st.t和(*stp).t和stp->t具有同样的效果

常用的链表操作

下面以

typedef struct unit unit;//定义unit，替代struct unit
typedef struct unit *unitp;//定义unit的指针类型
struct unit
{
    int xn,n;//单元中的数据
    unitp link;//指向链表中下一个单元的指针
};

为例，介绍常用函数。

实际应用时，应当根据需求进行修改。

题目

题解

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct voc voc;
typedef struct voc *vocp;
struct voc
{
    char word[100];
    int count;
    vocp link;
};
vocp createlist(int n);
vocp search(vocp st,char *tgt);
vocp insertafter(vocp p);
int main()
{
    //读入文本
    int total=1;
    FILE *in;
    in=fopen("article.txt","r");
    char inword[20];
    vocp st=NULL,now=NULL,max=NULL;
    int end=0;
    while(1)
    {
        char into;
        if(fscanf(in,"%c",&into)==EOF)
        {
            end=1;
            break;
        }
        int wordl=0;
        if(!(('A'<=into&&into<='Z')||('a'<=into&&into<='z')))
        {
            continue;
        }
        //读入一个单词
        do
        {
            inword[wordl]=into;
            wordl++;
            inword[wordl]='\0';
            if(fscanf(in,"%c",&into)==EOF)
            {
                end=1;
                break;
            }
        } while (('A'<=into&&into<='Z')||('a'<=into&&into<='z'));
        //处理大小写
        for(int i=0;i<strlen(inword);i++)
        {
            if(inword[i]<'a')
            {
                inword[i]+='a'-'A';
            }
        }
        //若为第一个单词则创建链表
        if(st==NULL)
        {
            st=createlist(2);
            st->link->count=1;
            strcpy(st->link->word,inword);
            max=st->link;
            continue;
        }
        //搜索是否存在该单词，否则新建单元
        vocp temp=search(st->link,inword);
        if(temp==NULL)
        {
            total++;
            temp=insertafter(max);
            temp->count=1;
            strcpy(temp->word,inword);
            max=temp;
        }
        else
        {
            temp->count++;
        }
        if(end)
        {
            break;
        }
    }
    fclose(in);

    //排序
    for(int i=0;i<total-1;i++)
    {   
        vocp a=st,b=a->link,c=b->link;
        for(int ii=0;ii<total-1;ii++)
        {
            //printf("%d\n",strcmp(b->word,c->word));
            if(strcmp(b->word,c->word)>0)
            {
                int tempc=b->count;
                char tempw[20];
                strcpy(tempw,b->word);
                b->count=c->count;
                c->count=tempc;
                strcpy(b->word,c->word);
                strcpy(c->word,tempw);
            }
            a=b;
            b=c;
            c=c->link;
        }
    }

    //输出
    vocp noww=st->link;
    for(int i=0;i<total;i++)
    {
        printf("%s %d\n",noww->word,noww->count);
        noww=noww->link;
    }
    return 0;
}

//函数定义
vocp insertafter(vocp p)
{
    vocp temppp=p->link;
    vocp temp=(vocp)malloc(sizeof(voc));
    p->link=temp;
    temp->link=temppp;
    return temp;
}

vocp createlist(int n)
{
    if(n<=0)
    {
        return NULL;
    }
    vocp last=NULL,current=NULL;
    vocp st=(vocp)malloc(sizeof(voc));
    last=st;
    st->link=NULL;
    for(int i=0;i<n-1;i++)
    {
        current=(vocp)malloc(sizeof(voc));
        current->link=NULL;
        last->link=current;
        last=current;
    }
    return st;
}

vocp search(vocp st,char *tgt)
{
    vocp now=st;
    int flag=0;
    while(now!=NULL)
    {
        if(!strcmp(tgt,now->word))
        {
            flag=1;
            break;
        }
        now=now->link;
    }
    if(flag)
    {
        return now;
    }
    return NULL;
}

拓展