文档介绍：数据结构与算法分析第二章线性表(2),简称链表(LinkedList),可以免除移动大量的结点。链式存储是一种更灵活的存储方式,适合线性和非线性逻辑结构。用于线性表,主要有单链表、双链表和循环链表。今天内容:创建链表、定位(查找)、插入节点、删除节点链式存储概念链表数据元素的存储具有以下特点:分配独立。数据元素分配内存,不受链表的任何约束结点数据域data:存储数据元素的值。结点指针域next:保存直接后继数据元素的物理地址。链表第一个元素没有前趋,必须定义一个头结点保存该结点的地址链表中最后一个元素的next域为nil。数据元素间的全序关系靠链接维持,而非存储顺序。datanext数据元素:定义链式结构的线性表(字符元素):单链表的数据元素,包括两个数据项:数据域承载数据,可以是任何类型;指针域承载全序关系,要么为空,要么指向某结点。typedefchardatatype;数据元素的值类型为字符typedefstructnode//定义一个结点{}Listnode;datatypedata;//结点的值域*next;//结点的指针域。structnodenextdata^如何建立一个链表?typedef Listnode *linklist;//计算机表示?linklist p,head;nextdatapheadP和head是一般的指针变量,指向的类型为链表结点这时,完成了必要的变量定义,有了头指针,结点指针。后面需要完成的工作是创建一个结点将结点加入链表指针链表依靠指针类型定义,所以要很好的理解指针类型指针的本质是什么?指向整数,实数,或其它结构类型的指针有什么不同?如何定义指针?定义一个指向整数i的指针iptr如何改变指针的值?C例如何改变指针所指数据元素的值?C例预习:……110……130135……160165170……200205…………………hat200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………batcateathatiatlatmatnullhead单链表的每一个结点只有一个链域,故称为单链表。单链表中每个结点的存储地址是存放在其前趋结点next域中开始结点无前趋,故应设头指针head指向开始结点。终端结点无后继,指针域为空(null,也可用^表示)。fat创建单个结点第一步,为结点分配内存空间,然后令一个指针指向该结点:p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间,并将其首地址放入指针变量p中。此时的情况是,p指向一个孤立的结点,该结点没有加入链表。dataNullP结点入链head=p;p->data=‘‘; while(1); { p->data=getchar();if(p->data==‘d)break; p->next=(listnode*)malloc(sizeof(listnode)); p=p->next;};NullPheadNullNullPPPNullabcd