C语言线性链表

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

1、1线性表的链式存储结构每个元素由结点(Node)构成;结点间的逻辑关系是线性的，即线性表;结点在计算机中可以不连续存储;链表可以扩充，只受存储介质大小的限制;数据和数据间的关系分别存储Node:链表分类按照链式存储的原则，可以有多种形式的链表线性链表（单链表）循环链表双向链表a1ana3a2H^3typedefintElemType;typedefstructLNode{ElemTypedata;//结点的数据域structLNode*next;//结点的指针域}LNode,*LinkList;单链表的定义4单链表的存储映像Phead初始化：InitList(&L)销毁：Destroy

2、List(&L)清空：ClearList(&L)判表空：ListEmpty(L)求表长：ListLength(L)取元素值：GetElem(L,i,&e)查找某元素：LocateElem(L,e)求前驱：PriorElem(L,cur_e,&pre_e)求后继：NextElem(L,cur_e,&next_e)插入：ListInsert(&L,i,e)删除：ListDelete(&L,i,&e)遍历：ListTraverse(L,Visit())单链表的基本操作6单链表的插入操作Step1：s->next=p->next;Step2：p->next=s；当!当!当!万无一失吗???有没

3、有问题呢?7单链表插入操作的特殊情况（1）Xss->nextbahead核心语句：s->next=p;//head;head=s；在第一个结点前插入……原语句：s->next=p->next;p->next=s；p8单链表插入操作的特殊情况（2）在末尾插入Xss->next核心语句：s->next=NULL;p->next=s；pbahead原语句：s->next=p->next;p->next=s；9单链表插入操作的特殊情况（3）空表插入核心语句：s->next=NULL;head=s；head==NULLXheads原语句：s->next=p->next;p->next=s；

4、太麻烦了！！！赶快想个办法吧！10解决之道：带表头结点的单链表^头指针表头结点head空表：头指针表头结点head^…首结点：存储第一个数据元素11s->next=p->next;p->next=s；Xss->next带表头节点单链表的插入操作abheadp(1)表头插入：(2)空表插入：headp^Xs^欧耶！太给力了!!!单链表插入操作的算法描述statusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的链表中的第i个结点前插入元素ep=L;j=0;while(p&&jnext;++j;}//查找第i-1个结点i

5、f(!p

6、

7、j>i-1)return-1;//i值不合法s=(LNode*)malloc(sizeof(LNode));//申请新结点的空间s->data=e;s->next=p->next;p->next=s;//插入操作returnOK;}//ListInsert_LP29算法2.913小结：带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅做标志。有时可用来存储附加信息。设置表头结点的好处：统一了链表第一位置和其他位置的操作；统一了空表和非空表的操作；以空间赢得时间使得各种链表（单向链表、双向链表、单向循环链表和双向循环链表）的空链表状态得到区分；亦表明各种空链表结构是不

8、同的。Note：只要不特殊说明，用的就是带头结点的链表。14课后作业对照不带头结点和带头结点两种单链表的插入操作，自行分析两种单链表对于删除操作的不同。（书面作业）说明：必须要做！虽然不讲，但是是考试内容！2.3.3链表基本算法实现(1)——初始化生成一个带头结点的空链表^头指针表头结点headStatusInitList_L(LinkList&L){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//创建头结点returnOK;}//InitList_L;16链表基本算法实现(2)——建立单链表建立链表的过程是一个动态生成的过程：从空表状

9、态，依次建立各元素结点，并逐个插入head^步骤：（1）找到单链表的末尾；（2）将新结点插入。尾插法方法1：调用基本算法建立链表；使用基本算法:voidInitList(&L)；voidListInsert(&L,i,e)思想：1.初始化链表；2.将结点逐个插入表尾方法2：自编算法建立思想：1.初始化链表；2.申请一个结点；3.初始化它的值；4.结点链入表尾；5.结束否？6.Yes，结束创建操作；7.No，重复步骤2-6；尾插法建立单链表算法1