数据结构课件110章全第二章幻灯片.ppt

ListLink createlist(int n) { int data; LinkList head; LNode *p; head=null; for(i=n;i0;--i){ p=(LNode*)malloc(sizeof(LNode)); scanf(“%d”，p–data); p–next=head; head=p; } return(head); } 2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例： LinkList creater( ) { char ch; LinkList head; LNode *p，*r; //(， *head;) head=NULL;r=NULL; while((ch=getchar( )!=‵\n′){ p=(LNode *)malloc(sizeof(LNode)); 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=(LinkList)malloc(sizeof(LNode)); LNode *p，*r; r=head; while((ch=getchar( ))!=‵\n′{ p=(LNode*)malloc(sizeof(LNode)); p–data=ch; r–next=p; r=p; } r–next=NULL; return(head); } 上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(LNode*)malloc(sizeof(LNode)) if(p==NULL){ error(〝No space for node can be obtained〞); return ERROR; } 以上算法的时间复杂度均为O(n)。 二、查找运算 1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下有哪些信誉好的足球投注网站，直到有哪些信誉好的足球投注网站到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，