1 //////////////////////////////////////////////////////////  2 // singlelist.cpp  3 //  4 // author:Leetao  5 //////////////////////////////////////////////////////////  6 // 简介：  7 //   线性链表的实现  8 //////////////////////////////////////////////////////////   9 /** 10 * 线性链表初始化，插入，删除功能的实现 11 * 12 * @author Leetao 13 * @version 1.0 14 * @date 2014.11.20   15 */  16  17 #include<stdio.h> 18 #include<malloc.h> 19  20 //类型宏定义，此处定义为int型  21 typedef int Elem; 22 typedef int Status; 23   24  //线性表的单链式储存结构  25  typedef struct LNode 26  {     27     Elem data; 28     struct LNode *next; 29      30  }LNode,*LinkList; 31   32  //创建链表 33  Status InitList(LinkList &list) 34  { 35      //逆位序输入n个元素值，建立带表头结点的单链表list  36      int i; 37      LinkList p; 38       39      printf("Input the length of the list:\n"); 40      scanf("%d",&i); 41       42      list=(LinkList)malloc(sizeof(LNode)); 43      list->next=NULL; 44   45       46      printf("Input the data:\n"); 47      while(i>0) 48     { 49         p=(LinkList)malloc(sizeof(LNode)); 50         scanf("%d",&p->data); 51          p->next=list->next; 52         list->next=p; 53           i--; 54     } 55     return 0; 56  }  57   58  //打印链表  59  Status PrintList(LinkList &list) 60  { 61      LinkList p; 62      printf("the list is:\n"); 63       64      p=list->next; 65       66      while(p!=NULL) 67      { 68          printf("%d->",p->data); 69          p=p->next; 70      } 71       72      printf("NULL\n"); 73       74      return 0; 75  } 76   77  //线性表插入 78  Status ListInsert(LinkList &list,int i,Elem e) 79  { 80      LinkList p,s; 81      int j=0; 82      p=list; 83                   84     while(p&&j<i-1)    //寻找第i-1个结点  85     { 86         p=p->next; 87         ++j; 88     }     89       90     if(!p||j>i-1)  //i小于1或者大于表长加1  91     { 92         printf("error!\n"); 93     } 94      95     s=(LinkList)malloc(sizeof(LNode));  //生成新结点  96     s->data=http://www.mamicode.com/e;                   //插入list中  97     s->next=p->next; 98     p->next=s; 99     100     return 0;    101  } 102  103  //链表删除 104  Status ListDelete(LinkList &list,int i)105  {106      //在带头结点的单链线性表list中，删除第i个元素值 107      LinkList p,q;108      int j=0;109      p=list;110      111      while(p->next&&j<i-1)  //寻找第i个结点，令p指向其前驱 112      {113          p=p->next;114          ++j;115      }116      117      if(!(p->next)||j>i-1) //删除位置不合理 118      {119          printf("error!\n");120      } 121     122     //删除并释放结点 123      q=p->next;124      p->next=q->next;125      free(q);126      127      return 0;128  }129  int main()130  {131      int iindex,dindex;132      Elem ie;133      LinkList list;134 135         //初始化     136          InitList(list);137          PrintList(list);138      139          //插入140         printf("Input the position and the number you want to insert:\n");141         scanf("%d%d",&iindex,&ie); 142          ListInsert(list,iindex,ie);143         PrintList(list); 144      145          //删除146         printf("Input the position you want to delete:\n");147         scanf("%d",&dindex);148         ListDelete(list,dindex);149         PrintList(list);150      151     return 0;152  }