线性表的链式表示与实现

2．3线性表的链式表示与实现顺序表示的优点是随机存取表中的任意元素；顺序表示的弱点是在作插入或删除操作时，需移动大量元素。链式表示----没有顺序表示的弱点，也失去了顺序表示的优点。2．3．1线性链表线性表的链式表示------是可以用一组任意的存储单元存储线性表的数据元素。例：线性表（赵，钱，孙，李，周，伍，张，王）的链式表示（赵，钱，孙，李，周，伍，张，王）

的链式表示11319253137437头指针：31(赵的地址)存储地址:钱孙李周赵伍张王H链表相关的名称数据域、指针域结点、头结点指针(链)链表、单链表(线性链表)a1a2a3LaiantypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*Linklist;线性表的单链表存储结构StatusGetElem_L(LinkListL,

inti,ElemType&e){//L为带头结点的单链表的头指针;当第i个元素//存在时，其值赋给e并返回OK,否则返回ERROR.LinkListp;intj;p=L->next;j=1;

while(p&&j<i){p=p->next;++j;}

if(!p||j>i)returnERROR;e=p->data;

returnOK;}//GetElem_L插入结点：

指针p所指的结点后插入指针s所指的结点s->next=p->next;p->next=s;

a1a2a3a1a3s->next=p->nexta2ppssp->next=s插入前：插入后：插入结点程序StatusListInsert_L(LinkList&L,

inti,ElemTypee){LinkLists,p;intj;p=L;j=0;while(p&&j<i-1){p=p->next;++j}if(!p||j>i-1)returnERROR;s=(Lnode*)malloc(sizeof(Lnode));if(!s)returnOVERFLOW;s->data=e;s->next=p->next;p->next=s;returnOK;}删除结点：

删除指针p所指的结点后的结点p->next=p->next->next;

a1a3a2p删除前：删除后：a1a3a2pp->next=p->next->nextss=p->next释放结点后：a1a3pfree(s)删除结点程序

删除第i个元素，并由e返回其值Status

ListDlete_L(LinkListL,

inti,ElemType&e){LinkLists,p;intj;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j}if(!(p->next)||j>i-1)returnERROR;s=p->next;p->next=s->next;e=s->data;free(s);returnOK;}循环链表的特点----表中的最后一个结点的指针域指向头结点,整个链表形成一个环。从表的任意结点出发可以找到表中其它结点。2．3．2循环链表a1a2a3Laian2．3．3双向链表双向链表的特点----表中的每个结点有两个指针域，一个指向后继结点，一个指向前趋结点,整个链表形成两个环。从表的任意结点出发可以通过正向环（或反向环）找到表中其它结点。typedefstructDuLnode{ElemTypedata;StructDuLnode*prior;StructDuLnode*next;}DuLnode,*DuLinklist;priordatanext结点：插入结点：

指针p所指的结点前插入指针s所指的结点s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;

a1a3a2ps插入前：ps插入后：a1a2a3插入结点程序Status

ListInsert_DuL(DuLinklistL,int

i,ElemTypee){DuLinklists,p;

if(!(p=GetElemP_DuL(L,i)))

//在L中确定第i个元素的位置指针p

returnERROR;

if(!(s=(DuLinklist)malloc(sizeof(DuLNode))))returnERROR;s->data=e;//构造数据为e的结点ss->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;

returnOK;}//ListInsert_DuL删除结点：

删除指针p所指的结点a1a2p删除前：删除后：p->prior->next=p->nexta3a1a2pa3p->next->proir=p->prior释放结点：free(p);删除结点程序

删除第i个元素，并由e返回其值Status

ListDelete_DuL(DuLinklistL,

int

i,ElemType&e){DuLinklistp;

if(!(p=GetElemP_DuL(L,i)))

//在L中确定第i个元素的位置指针p

returnERROR;e=p->data;//删除的结点的值存入ep->prior->next=p->next;p->next->prior=p->prior;

free(p);

returnOK;}//ListDelete_DuL顺序存储线性表的插入和删除

的一个完整C程序实例typedefintElemType;typedefint

Status;#defineOK1#defineOVERFLOW-2#defineERROR0#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{

ElemType*elem;intlength;intlistsize;}Sqlistmain(){SqlistLst;inti,n=101;ElemTypee;if(InitList_Sq(&Lst)==OK){ //线性表Lst初始化成功

for(i=1;i<=n;i++) if(ListInsert_Sq(&Lst,i,i)!=OK)break;//插入值1到n

printf(“\n”); //换行StatusListInsert_Sq(Sqlist*L,inti,ElemTypee);StatusInitList_Sq(Sqlist*L);StatusListDelete_Sq(Sqlist*L,inti,ElemType*e);

for(i=0;i<Lst.length;i++) printf("i,e=%d,%d\n",i,Lst.elem[i]); //打印值1到n

getch();//等待键盘响应

if(ListDelete_Sq(&Lst,5,&e)==OK){

//删除第5个元素

printf("delete_elem=%d\n",e); //打印被删除的元素

getch();//等待键盘响应

for(i=0;i<Lst.length;i++)

printf("i,e=%d,%d\n",i,Lst.elem[i]);//打印线性表Lst的所有元素 }}} StatusInitList_Sq(Sqlist*L) //

算法2.3{//构造一个空的线性表LL->elem=(ElemType*)malloc

(LIST_INIT_SIZE*sizeof(ElemType));

if(!L->elem)exit(OVERFLOW);//存储分配失败

L->length=0; //空表长度为0

L->listsize=LIST_INIT_SIZE;//初始存储容量

returnOK;}//

算法2.3StatusListInsert_Sq(Sqlist*L,inti,ElemTypee){//在顺序线性表L的第i个位置之前插入新的元素e//i的合法值为1<=i<=ListLength_Sq(L)+1ElemType*q,*p,*newbase;if(i<1||i>L->length+1)returnERROR;

//i值不合法

if(L->length>=L->listsize){//当前存储空间已满,增加分配

newbase=(ElemType*)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(ElemType)); //算法2.4

if(!newbase)exit(OVERFLOW);//存储分配失败

L->elem=newbase;L->listsize+=LISTINCREMENT;

//增加存储容量}

q=&(L->elem[i-1]);//q为插入位置

for(p=&(L->elem[L->length-1]);p>=q;--p)*(p+1)=*p; //插入位置及之后的元素后移*q=e;//插入e++L->length; //表长增1

returnOK;}StatusListDelete_Sq(Sqlist*L,inti,ElemType*e){//在顺序线性表L中删除第i个元素,并用e返回其值//i的合法值为1<=i<=ListLength_Sq(L)

ElemType*p,*q;if((i<1)||(i>L->length))returnERROR;//i值不合法

p=&(L->elem[i-1]);//p为被删除元素的位置*e=*p;