链表之C实现

用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。每个数据的元素需要存储数据元素信息外，还要存储它的后继元素的存储地址。例如数据ai需要存储本身的数据信息之外还要存储ai+1的地址。把链表中第一个节点的存储位置叫做头指针，线性链表中最后一个节点的后继指针为NULL

Paste_Image.png

C语言中用结构指针来描述单链表

  typedef int ElemType
  typedef struct Node{
      ElemType data;      //数据域
      struct Node *next;   //指针域
  }Node;
typedef struct Node *LinkList;   /*链表*/

获得链表第i个数据

int getElem(LinkList L,int i,ElemType *e){
    int j;
    LinkList p;
    p = L->next;  //p指向链表L的第一个节点
    j = 1;
  while(p && j<i){
      p = p->next;
      ++j;
  }
  if (!p || j>i){
      return -1;   //表示没有找到 假定数据域没有负数
  }
   int e = p->data;
   retun e;
}

在第i个位置之前插入新的数据元素e

  void insertLink(LinkList *L,int i,ElemType e){
      int j;
      LinkList p,s;
      p = *L;
      j = 1;
      while(p && j<i){    //指针移动到指定位置
          p = p->next;
          ++j;
      }
      
      if(!p || j>i){ return;}
      s = (LinkList)malloc(sizeof(Node));/*生成一个新节点*/
      s->data = e;
      s->next = p->next;  //把s的后继节点改成p的后继节点
      p->next = s;          //再把p的后继节点改成s
  }

删除第i个元素

      void listdelete(LinkList *L,int i,ElemType *e){
          int j;
          LinkList p,q;
          p = *L;
          j = l;
          while(p->next && j<i){
              p = p->next;
              ++j;
          }
          
          if(!(p->next) || j>i){
              return;
          }
          q = p->next;  // 找到要删除的元素q
          p->next = q->next;   //将q的后继元素赋值给p
          *e = q->data;
           free(q);  //释放内存
      }

创建整个链表

    void createList(LinkList *L,int n){
          LinkList p,r;
          int i;
          srand(time(0));
          *L = (LinkList)malloc(sizeof(Node));
            r = *L;
            for(i=0;i<n;i++){
                p = (Node *)malloc(sizeof(Node));
                p->data = rand()%100 + 1;
                r->next = p;
                r = p;
            }
          
            r->next = NULL;
    }

删除整表

        void clearList(LinkList *L){
            LinkList p,q;
            p = (*L)->next;
            while(p){
                q = p->next;
                free(p);
                p=q;
            }
            (*L)->next = NULL;
        }