用链式存储实现线性表详解代码

用链式存储实现思想：

不要求逻辑上相邻的两个元素物理上相邻，通过“链”建立起数据之间的逻辑关系。

逻辑相邻：指两个元素是挨着的，（比如1，2，3）

物理相邻：指两个元素存在内存地址上是挨着的，地址相邻（比如0x00000000, 0x00000004)

链式存储实现线性表基本操作代码：

• 定义结构,用于存取线性表中的元素。

• 链表中按值查找元素，时间性能为O(n)
  
  链表中按值查找元素

  C++

  1 2 3 4 5 6 7 8

  List Find(ElementType X, List PtrL) {     List p = PtrL;     while(p!=NULL && p->Data != X){         p = p->Next;     }     return p; }

• 链表中按序号查找元素，时间性能为O(n)
  
  链表中按序号查找元素

  C++

  1 2 3 4 5 6 7 8 9 10 11

  List Find(int k, List PtrL) {     List p = PtrL;     int i = 1;     while(p!=NULL && i<k){         p = p->Next;         i++;     }     if (i == K) return p;  //找到返回List     else return NULL;    //没找到 }

• 链表中插入元素

  

• 链表中删除操作
  
  链式存储线性表删除操作实现

  C++

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  List Delete(int i,List PtrL) { List p,s; if(i==1){ s = PtrL; if (PtrL!=NULL) PtrL = PtrL->Next; else return NULL; delete s; return PtrL; } p = Find(i-1,PtrL); if (p==NULL){ printf(""); return NULL; }else if(p->Next == NULL){ printf(""); return NULL; }else{ s = p->Next; p->Next = s->Next; delete s; return PtrL; } }

• 求链表长度，时间性能为O(n)
  
  链表求长度

  C++

  1 2 3 4 5 6 7 8 9 10

  int Length(List PtrL) {     List p = PtrL;     int j =0;     while(p){         p = p->Next;         j++;     }     return j; }