学步园

  1/**//*========带头节点的线性链表类型=========*/
  2/**//*=======================================*/
  3
  4
  5/**//*===============包含头文件以及类型定义==============*/
  6#include <stdio.h>
  7#include <malloc.h>
  8#define NULL 0
  9#define NODE_NUM 10
 10
 11
 12typedef struct lnode{
 13    char data;
 14    struct lnode *next;
 15}*link,*position;
 16
 17
 18typedef struct{
 19    link head,tail;
 20    int len;
 21}linklist;
 22
 23
 24/**//*======================================================*/
 25/**//*=======一些在其他函数定义中会调用的函数===============*/
 26/**//*======================================================*/
 27
 28int compare(char a,char b){  /**//*---compare---比较两个元素的大小关系*/
 29    return a-b;
 30}
 31
 32
 33int visit(link p){
 34    if(p->data>=65&&p->data<=97)/**//*---visit---判断结点的元素是否为大写元素*/
 35        return 1;
 36    else
 37        return 0;
 38
 39}
 40
 41
 42int length(link s){ /**//*---length---求链的长度*/
 43    int i=0;/**//*i不赋初值，编译错误“可能在i定义以前使用了它在length函数中”*/
 44    link p=NULL;
 45    p=s;
 46    while(p->next!=NULL){
 47        p=p->next;
 48        i++;
 49    }
 50    return i;
 51}
 52
 53
 54void print(linklist l){     /**//*---print---在屏幕上输出链表的所有元素*/
 55    link p=NULL;
 56    p=l.head;
 57    if(!p->next){
 58        printf("\nThe linklist is empty.\n\n");
 59        return ;
 60    }
 61    printf("The list:");
 62    while(p){
 63        printf("%c-",p->data);
 64        p=p->next;
 65    }
 66}
 67
 68
 69
 70/**//*======================================================*/
 71/**//*==========对带头结点的单链线性表进行操作的函数的定义==================*/
 72/**//*======================================================*/
 73
 74position makenode(char e){       /**//*---分配由p指向的结点并赋值为e---*/
 75    link p=NULL;
 76    p=(link)malloc(sizeof(struct lnode));
 77        /**//*---struct lnode 才能表示一个结构体类型并可用于分配空间的元素类型定义-*/
 78    if(p){
 79        p->data=e;
 80        p->next=NULL;
 81    }
 82    else return;
 83    return p;
 84}
 85
 86
 87void freenode(link p){          /**//*---释放p所指向的结点-*/
 88    free(p);
 89}
 90
 91
 92
 93int initlist(linklist *l){      /**//*---构造一个由l指向的空的线性表-*/
 94    l->head=makenode('L');
 95    l->head->next=NULL;/**//*不是l->head=NULL*/
 96    l->tail=l->head;
 97    l->len=0;
 98    return 1;
 99}
100
101
102position priorpos(linklist l,link p){    /**//*---返回p所指结点的直接前驱的位置-*/
103    link q;
104    q=l.head;
105    if(q->next==p) return 0;
106    while(q->next!=p)   q=q->next;
107    return q;
108}
109
110
111int insfirst(linklist *l,link s){    /**//*---将s指向的结点插入线性链表的第一个结点之前-*/
112    s->next=l->head->next;
113    if(!l->head->next) l->tail=s;/**//*当向一个空的线性表执行该操作时*/
114    l->head->next=s;
115    l->len++;
116
117}
118
119
120int append(linklist *l,link s){  /**//*---将指针s所的一串结点链接在线性表L的最后一个结点-*/
121    link q;
122    q=l->head;
123    if(!l->tail){/**//*考虑到链表为空的情况*/
124        l->head->next=s;
125        while(q->next) q=q->next;/**//*尾结点的处理*/
126        l->tail=q;
127    }
128    l->tail->next=q=s;
129    while(q->next) q=q->next;/**//*不能忘了对尾结点的处理*/
130    l->tail=q;
131    l->len+=length(s);
132
133}
134
135