第3章 线性表与其存储结构.ppt

若用换行符‘\n’作为输入结束标志，用rear作为总是指向链表尾结点的尾指针，则建立带表头结点的先进先出单链表的算法如下： LinkList CreateList_ff( ) { LinkList H,p,rear; char ch; H=(LinkList)malloc(sizeof( ListNode)); /*生成表头结点*/ if(!H) { printf(\n 存储分配失败); exit(1); } H-next=NULL; /*表初值为空*/ rear=H; /*尾指针指向表头结点*/ while((ch=getchar())!=\n) { p=(LinkList)malloc(sizeof( ListNode)); /*生成新结点*/ if(!p) { printf(\n 存储分配失败); exit(1); } p-data=ch; p-next=p; /*新结点插入表尾*/ rear=p; /*尾指针指向新结点*/ } return(H); /*返回头指针*/ } ② 后进先出表：在建立单连表时，将每次生成的新结点，总是插入到当前链表的表头结点之后作为当前链表的首结点。若用换行符‘\n’作为输入结束标志，则建立带表头结点的后进先出单链表的算法如下： LinkList CreateList_fr( ) { LinkList H,p; char ch; H =(LinkList)malloc(sizeof( ListNode)); /*生成表头结点*/ if(!H) { printf(\n 存储分配失败); exit(1); } H-next=NULL; /*表初值为空*/ while((ch=getchar())!=\n) { p=(LinkList)malloc(sizeof( ListNode)); /*生成新结点*/ if(!p) { printf(\n 存储分配失败); exit(1); } p-data=ch; p-next=H-next; H-next=p;/*插入表头结点之后*/ } return(H); /*返回头指针*/ } ③ 有序单链表：是指原表中结点的数据值，按从小到大（或从大到小）的顺序排列。为了建立一个有序单链表，每次生成的新结点，总是插入到当前链表的合适位置。在带表头结点的单链表中，所有位置上的插入操作都是一致的，不需要做特殊处理。 若用换行符‘\n’作为输入结束标志，pre为指向当前结点前件的指针、cur为指向当前结点的指针，则建立带表头结点的有序单链表的算法如下： LinkList CreateList_or( ) { LinkList H,pre,cur; /*pre将指向当前结点的前件，cur将指向当前结点*/ char ch; H =(LinkList)malloc(sizeof( ListNode)); /*生成表头结点*/ if(!H) { printf(\n 存储分配失败); exit(1); } H-next=NULL;/*表初值为空*/ while((ch=getchar( ))!=’\n’) { pre=H;/*pre指向当前结点的前件*/ cur=H-next;/*cur指当前结点*/ while(curcur-datach) /*找出新结点在表中的合适位置*/ { pre=cur; cur=cur-next; } cur=(LinkList)malloc(sizeof( ListNode)); /*生成新结点*/ if(!cur) { printf(\n 存储分配失败); exit(1); } cur-data=ch; cur-next=pre-next; /*新结点插在pre所指结点的后面*/ pre-next=cur;/*尾指针指向新结点*/ } return(H); /*返回头指针*/ } 容易看出，以上3个算法的时间复杂度均为O(n)。 2）查找结点 在对单链表进行插入或删除运算时，总是首先要找到插入或删除的位置，这就需要对线性链表进行扫描查找。 通常，有查找第i个结点或查找具有给定元素值的结点，两种情况。 ①?查找单链表中的第i个结点 在带表头结点的单链表中，查找第i个结点。不能像在顺序表中那样，只能从单链表的头指针出发，沿着结点的链域逐个向下，直到有哪些信誉好的足球投注网站到第i个结点为止。此时