资源描述：
《3线性表-单链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、链式存储结构-单链表线性表(List)部分操作的实现小结和作业复习复习1、a和p都是变量inta,*p//a和p的相同点是什么？2、有一些相似的运算a=5;a=a+3;a=a-1p=5;p=p+3;p=p-1a5p5复习a中存放的是整型数，p中存放的是地址inta,*p//a和p的不同点是什么？a5p5复习1、p和q都是变量，存放的都是地址int*p;//p和q的区别是什么？float*q;q5p5复习2、*p*qq5p55地址*p把地址为5的连续四个字节中的0-1串解释成整型数。*q把地址为5的连续四个字节中的0-1串解释成实型数。复习假设a是整型变量，存储单元的首地址是
2、5p是整型指针，执行下面的赋值语句：pap=&a;5当p的值是某个变量的地址时,形象的表示为：pa链式存储结构1、每个数据元素使用一个结点表示ai2、每个数据元素在物理存储空间可以不相邻3、数据元素之间的线性关系由指针链接保证a1a3a2链式存储结构的实现1、结点用一个结构表示typedefstructLNode{ElemTypedata;structLNode*next;}LNodeai2、定义一个指向LNode的指针类型typedefLNode*LinkList链式存储结构的实现a1a2a3L单链表a1a3a2L物理形态头指针LinkListL链式存储结构的实现0空链表
3、：L是一个空指针，即变量L的值为零。LL部分操作的实现InitList(&L)DestroyList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)GetItem(L,i,&e)ListMerge(&La,Lb)ListMerge(La,Lb,&Lc)ListLength(L)InitList原型StatusInitList(LinkList&L)作用形成一个空表LStatusInitList(ListLink&L){L=NULL;}return(OK);DestroyLista1a2a3L原型StatusDestroyList(LinkL
4、ist&L)作用将L变成空表LDestroyList分析:释放每个结点占用的存储空间1、如果L是空表，则返回a1a2a3L2、将L的第一个结点从链表摘除3、释放L的第一个结点，转1DestroyListStatusDestroyList(LinkList&L){a3La1a2while(L){p=L;L=L->next;free(p);}}preturn(OK);pp如何删除第一个结点？ListLength原型intListLength(LinkListL)作用求出L中的数据元素的个数a1a2a3L第一步：P=L,count=0ListLengthpa3La1a2LpCou
5、nt=0Count=0pCount=1pCount=2p=NULLCount=3第二步第三步：返回countListLengthintListLength(LinkListL){count=0;while(p){p=p->next;count++}}return(count);p=L;GetIem—功能原型StatusGetItem(LinkListL,inti,ElemType&e)作用取出第i个数据元素的值赋给eStatusGetItem(SqListL,inti,ElemType&e){if(i<1
6、
7、i>L.length)return(ERROR);e=L.elem
8、[i-1];return(OK);}GetIem—定位a5La1a2a3a4GetItem(L,4,e)ppppp=L,定位到ai需要移动i-1次指针,p=p->nexta5La1a2a3a4GetItem(L,1,e)pGetItemStatusGetIem(LinkListL,inti,ElemType&e){p=L,j=1;while(jnext;j++;e=p->data;}}return(OK);if(i<1
9、
10、i>ListLength(L)return(ERROR)GetItem1、在什么情况下，移动指针的次数最少2、在什么情况下，移动指针的次
11、数最多，如何改善？ListInsert原型StatusListInsert(LinkList&L,inti,ElemTypee)作用将e插入到链表，作为第i个结点ai-1eaiai-1ListInsert过程1、判断i的合法性2、找到第i-1个结点3、申请一个新结点的空间4、调整指针ListInsert—新结点生成一个新结点存放数据元素e的代码是：node=(LNode*)malloc(sizeof(LNode));if(!node)return(ERROR);node->data=e;node->next=NUL
