数据结构与：ch2 线性表 .pptVIP

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 *2.4 一元多项式的表示及相加 例3、学生健康情况登记表如下： 单链表示意图如下： …… 110 …… 130 135 …… 160 头指针 head 165 170 …… 200 205 …… 2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例： Linklist CreateLista( ) { char ch; Linklist head; Listnode *p，*r; //(， *head;) head=NULL;r=NULL; while((ch=getchar( )!=‵\n′){ p=(Listnode *)malloc(sizeof(Listnode)); p–data=ch; if(head=NULL) head=p; else r–next=p; r=p; } if (r!=NULL) r–next=NULL; return(head); } 说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。 算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。 如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。 其算法如下： Linklist createListr1( ){ char ch; Linklist head； head=(Linklist)malloc(sizeof(Listnode)); Listnode *p，*r 其算法如下： Linklist CreateListr1( ){ char ch; Linklist head； head=(Linklist)malloc(sizeof(Listnode)); Listnode *p，*r=head; while((ch=getchar( ))!=‵\n′{ p=(Listnode*)malloc(sizeof(Listnode)); p–data=ch; r–next=p; r=p; } r–next=NULL; return(head); } 上述算法里动态申请新结点空间时未加错