线性表顺序表链表顺序表与链表的比较

线性表顺序表链表顺序表与链表的比较内容摘要：

最前端，本身不带数据， 仅标志表头。  设置表头结点的目的是  统一空表与非空表的操作  简化链表操作的实现 非空表  an a1 L  空表 头指针 头结点 L a1 a2 a3 a4  L 活动指针 单链表的基本操作 p=Lnext。 //p指向第一个结点 p=pnext。 //p指向下一个结点 直到 p==  结束 P  p=Lnext。 //p指向第一个结点 while(p!=NULL) //当存在这个结点 { p=pnext。 //移动 p指向下一个结点 } 链表的基本操作形式 p L a1 a2 a3  n= 1 p L a1 a2 a3  n= 2 p L a1 a2 a3  n= 3 P=^ L a1 a2 a3  求单链表长度 n= 0 int ListLength ( LinkList *L ) { LinkList *p = Lnext。 //活动指针 p 指向第一个结点 int n = 0。 //计数器初值 while ( p != NULL ) { n++。 //逐个结点检测 p = plink。 } return n。 } 求单链表长度 建立单链表（尾插法）  建立一个空表。  依次将新结点插入在链表的表尾。 L  p  r r  r  p r 生成一个新结点 L  注意 ：要设置一个尾指针 r，总是指向表中最后一个结点， 新结点插在它的后面；尾指针 r 初始时置为指向表头结点地址。 p=malloc( )。 rnext=p。 r = p。 void InitList(LinkList *amp。 L ) //建立一个空表 { L=(LinkList *)malloc(sizeof(LinkList))。 //生成头结点 Lnext=NULL。 return(h)。 //返回头指针 } 建立单链表（尾插法） （ 1）建立一个空表 Initlist( )。 （ 2）依次将每个新结点插入链表中。 void CreatList( LinkList *amp。 L,Elemtype a[ ], int n ) //利用尾插法建立单链表 { LinkList *L, *s, *r。 InitList(L)。 //建立一个空表 r= L。 for(i=1。 i=n。 i++) { s=(LinkList *)malloc(sizeof(LinkList))。 //生成新结点 sdata=a[i]。 //存储数据元素 snext=NULL。 rnext=s。 //插入表尾 r= s。 //r总是指向表尾 } rnext=NULL。 } 在单链表中插入新结点 snext = pnext。 s 插入 p s p 注意：先确定 s的直接前驱 r,在 p之后插入新结点 p。 pnext = s。 生成新结点 s=malloc( ) pnext 在单链表中第 i个位置插入一个新元素 （ 1）确定第 i1个结点 GetElem(L, i1)。 （ 2）生成新结点 p （ 3）插入新结点 bool GetElem(LinkList *L, int i,LinkList *amp。 p) //取单链表中第 i个结点 { LinkList *p。 int j。 p=L。 j=0。 while( ji amp。 amp。 p!=NULL) //不是第 i个结点 { p=pnext。 j++。 } if(p==NULL) return false。 else return true。 } 扫描单链表 寻找第 i个结点 i初值 ? bool ListInsert (LinkList *amp。 L, int i, ElemType e) //将新元素 x 插入在链表中第 i 个结点位置 { linklist *p,*s。 GetElem (head,i1,p)。 //确定新结点的前驱 if ( p==NULL ) return false。 //插入失败 s=(LinkList *)malloc(sizeof(LinkList))。 sdata= e。 //生成新结点 p并赋值 snext=pnext。 pnext=s。 //将 p插入 r之后 return true。 //插入成功 } 在单链表中删除一个结 p pnext = qnext。 free(q)。 //释放 p p q 注意： 先确定 q的前驱 p 删除单链表中第 i个结点 （ 1）确定第 i1个结点 GetElem(L, i1, p)。 （ 2）确定第 i个结点； （ 3）删除该结点，并释放； int ListDelete (LinkList *L, int i) //将在链表中第 i 个结点删除 { LinkList *p,*q。 GetElem(L,i1,p)。 //确定第 i1个结点的前驱 if ( p==NULL ) return false。 //删除失败 q=pnext。 //p指向第 i个结点 pnext=qnext。 //删除 p free (q)。 return true。 //删除成功 } 单链表应用举例 例 1 单链表的逆置 a1 a2 a3 a4  逆置前 L a4 a3 a2 a1  逆置后 L a1 a2 a3 an1 an a1 a2 a3 an1 an 利用头插法 a5 p pnext=Lnext。 Lnext=p。 依次将每个结点头插到单链表中 （ 1）分成两个单链表 L1和 L2 a1 a2 a3 a4  L q 空表 L1 含所结点的无头链表 L2 （ 2）依次将 L2中每一个结点逆置到 L1中 a2 a1  L q 取出 L2中第一个结点 p (作为当前逆置的结点） a3 a4  p 将 p头插到 L1中。