线性表-链式表示和实现.ppt

线性表的链式表示和实现 线性表的顺序表示是指用一组地址连续的存储单元依次存放线性表的数据元素

以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑相邻线性表的顺序表示线性表的链式表示线性表的链式表示单链表单链表

typedefstructLNode{
ElemTypedata; //数据域
structLNode*next; //指针域
}LNode,*LinkList;

LinkListL; //L为单链表的头指针带头结点的单链表带头结点的单链表单链表的遍历p=L->next;j=1;//可替换为：p=L;j=0;
while(p!=NULL&&j<i){
p=p->next;j++;
}

if(p!=NULL)
对第i个结点操作；
else
第i个结点不存在；

voidListInit_L(LinkList&L)
//构造一个空链表
{
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
}StatusGetElem_L(LinkListL,inti,ElemType&e){
//L是带头结点的单链表的头指针，以e返回第i个结点的值

//确定第i个结点的位置
p=L->next;j=1;
while(p&&j<i){p=p->next;++j;}

if(!p||j>i) //第i个结点不存在
returnERROR;

e=p->data; //取得第i个结点的值

returnOK;
}

算法时间复杂度为:O(ListLength(L))成正比StatusListInsert_L(LinkList&L,inti,ElemTypee){
//L是带头结点的单链表的头指针，在第i个结点之前插入元素e

//确定第i-1个结点的位置
p=L;j=0;
while(p&&j<i-1){p=p->next;++j;}

if(!p||j>i-1)
returnERROR;

s=(LinkList)malloc(sizeof(LNode));
s->data=e;

s->next=p->next;//先连后！
p->next=s;//再改前！

returnOK;
}StatusListDelete_L(LinkList&L,inti,ElemType&e){
//L是带头结点的单链表的头指针，删除第i个结点，并用e返回其值

//确定第i-1个结点的位置
p=L;j=0;
while(p->next&&j<i-1){p=p->next;++j;}

if(!(p->next)||j>i-1)
returnERROR;

q=p->next;//q指向第i个结点
p->next=q->next;
e=q->data;
free(q);

returnOK;
}voidCreateList_L(LinkList&L,intn){
//逆序输入n个数据元素，建立带头结点的单链表

//先建立一个带头结点的单链表
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;

for(i=n;i>0;--i){
p=(LinkList)malloc(sizeof(LNode));//分配空间
scanf(&p->data); //输入元素值
p->next=L->next;L->next=p; //插入L之后!
}
}

算法的时间复杂度为:O(Listlength(L))voidClearList(&L){
//将单链表重新置为一个空表

while(L->next){
p=L->next;
L->next=p->next;
free(p);
}
}
销毁Destory头结点也要释放掉
算法时间复杂度：O(ListLength(L))voidMergeList_L(LinkList&La,LinkList&Lb,
LinkList&Lc){
//单链表La、Lb的结点按值非递减排列，归并La和Lb得到新链表Lc，且
Lc的结点按值非递减排列。
pa=La->next;pb=Lb->next;
Lc=pc=La;//用La的头结点作为Lc的头结点

while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}
else{pc->next=pb;pc=pb;pb=pb->next;}
}

pc->next=pa?pa:pb;//插入剩余段
free(Lb);//释放Lb的头结点
}特点：最后一个结点的指针域指向头结点