2.3_线性表-链表

《2.3_线性表-链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、12.3线性表的链式表示和实现2ListofContent2.3.1什么是线性链表2.3.2线性链表的定义2.3.3线性表的操作在链表中的实现2.3.4线性链表数据结构2.3.5静态链表2.3.6其它链表32.3.1什么是线性链表用一组地址任意的存储单元存放线性表中的数据元素。元素+指针(指示后继元素存储位置)=结点（表示数据元素的映象)以“结点的序列”表示线性表称作链表a1a2…...an^4以线性表中第一个数据元素a1存储地址作为线性表的地址，称作线性表的头指针。头结点a1a2…...an^头指

2、针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空2.3.1什么是线性链表5头结点头指针2.3.1什么是线性链表单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。a1…...an^空指针a26typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;LinkListL；//L为单链表的头指针2.3

3、.2线性链表的定义72.2.3线性表操作在链表中的实现GetElem(L,i,e)//取第i个数据元素ListInsert(&L,i,e)//插入数据元素ListDelete(&L,i,e)//删除数据元素ClearList(&L)//重置线性表为空表8L211830754256∧pppj123基本操作为：移动指针i次。令指针p始终指向线性表中第j个数据元素。结束条件：找到第个结点，或i大于链表的长度即j=i，或者p＝null线性表的操作GetElem(L,i,&e)9线性表的操作GetElem(L,i

4、,&e)算法的基本过程p指向第一个结点，初始化计数器j为1顺指针向后查找，直到j＝i或p为空如果找不到第i个结点（j>i或p=null）,则返回ERROR取出第i个结点的数据,放在e中，返回OKp=Lnext;j=1;while(p&&j

5、

6、j>i)returnERROR;e=pdata;returnOK;10StatusGetElem_L(LinkListL,inti,ElemType&e){//L是带头结点的链表的头指针，以e返回第i个元素p=Ln

7、ext;j=1;//步骤1while(p&&j

8、

9、j>i)returnERROR;//步骤3:第i个元素不存在e=pdata;//步骤4：取得第i个元素returnOK;}//GetElem_L算法时间复杂度为:O(ListLength(L))11ai-1eai-1ai线性表的操作ListInsert(&L,i,e)在第i个结点之前插入元素e有序对改变为和

10、ai>12在链表中插入结点只需要修改指针。修改第i-1个结点的指针。基本操作：找到线性表中第i-1个结点,修改其后继指针ai-1eai线性表的操作ListInsert(&L,i,e)pssnext=pnext;pnext=s;13线性表操作ListInsert(&L,i,e)基本过程p指向头结点，初始化计数器j＝0顺指针向后查找，直到j＝i－1或p为空如果找不到第i个结点,则返回ERROR创建新结点，若创建失败,则返回ERROR将新结点插入到i结点之前p=L;j=0;while(p&&j

11、{p=pnext;++j;}if(!p

12、

13、j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));If(!s)exit(OVERFLOW);sdata=e;snext=pnext;pnext=s;14StatusListInsert_L(LinkListL,inti,ElemTypee){//L为带头结点的单链表的头指针p=L;j=0;//步骤1while(p&&j

14、

15、

16、j>i-1)returnERROR;//步骤3：找不到is=(LinkList)malloc(sizeof(LNode));//步骤4If(!s)exit(OVERFLOW);sdata=e;//步骤5插入snext=pnext;pnext=s;returnOK;}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))15在单链表中删除第i个结点基本操作为:找到线性表中第i-1个结点，修改其指向后继的指