用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素歉秫，這組存儲單元可以是連續(xù)的葛躏，也可以是不連續(xù)的。每個數(shù)據(jù)的元素需要存儲數(shù)據(jù)元素信息外僧须，還要存儲它的后繼元素的存儲地址纲刀。例如數(shù)據(jù)ai需要存儲本身的數(shù)據(jù)信息之外還要存儲ai+1的地址。把鏈表中第一個節(jié)點(diǎn)的存儲位置叫做頭指針担平，線性鏈表中最后一個節(jié)點(diǎn)的后繼指針為NULL

Paste_Image.png

C語言中用結(jié)構(gòu)指針來描述單鏈表

  typedef int ElemType
  typedef struct Node{
      ElemType data;      //數(shù)據(jù)域
      struct Node *next;   //指針域
  }Node;
typedef struct Node *LinkList;   /*鏈表*/

獲得鏈表第i個數(shù)據(jù)

int getElem(LinkList L,int i,ElemType *e){
    int j;
    LinkList p;
    p = L->next;  //p指向鏈表L的第一個節(jié)點(diǎn)
    j = 1;
  while(p && j<i){
      p = p->next;
      ++j;
  }
  if (!p || j>i){
      return -1;   //表示沒有找到 假定數(shù)據(jù)域沒有負(fù)數(shù)
  }
   int e = p->data;
   retun e;
}

在第i個位置之前插入新的數(shù)據(jù)元素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));/*生成一個新節(jié)點(diǎn)*/
      s->data = e;
      s->next = p->next;  //把s的后繼節(jié)點(diǎn)改成p的后繼節(jié)點(diǎn)
      p->next = s;          //再把p的后繼節(jié)點(diǎn)改成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);  //釋放內(nèi)存
      }

創(chuàng)建整個鏈表

    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;
        }