链表及相关算法

1、2010-3-112010-3-11胡俊峰胡俊峰|胡老师： 关于算法与数据结构的课，我有两个小问题：|1。3月4号讲的作业分析，插入元素的例程的第一个，里面用的是 i = binary search(r,0,high,key); /i是应该插入的位置 我觉得这句不对，因为当搜不到的时候，返回值是-1，i=-1是不能插入的。您觉得呢？|2。插入排序里，您说基本思想是将待排序的记录按排序码大小插到已经排好的序列里。我想知道排序码是什么？谢谢！|-Meng Jin？|free(palist-element);|free(palist);|如果在插入元素操作过程中 n = MAXz申请二倍空间；z复制

2、数据；z释放原空间z继续完成插入操作element|链式表|不同形式的链表|链表的顺序存储方案|链表的应用|采用链表为存储方案|链接关系形成线性关系|对外提供一致的线性表接口操作。|采用一个向后的节点间链接构成的链表。|数据结构定义：18第一种类型：struct Node *head = NULL；第二种类型：struct Node head.link = NULL; |带头节点链表操作函数：无头节点，插入操作无头节点，插入操作（续）23Creat an empty linked list无头节点，插入操作（续）|struct Node DataType num; int next; /nex

3、t pointer ; struct Slinklist Node listMAXNUM; int elementNum; 1290-1634-1120 1 2 3 4|循环链表|双链表2829|尾部插入： ptr = clist-next; clist-next = newNode; newNode-next = ptr; clist = newNode;|头部删除： if (ptr = clist-next) != clist) clist-next = clist-next -next; free(ptr); newNodepclista0a2an-130palista0an-1pbli

4、stb0bn-1palista0an-1pblistb0bn-131infollinkrlink结点结构：结点结构：pdlistk0k1kn-1headrear|单链表缺点：找后继容易，找前驱必须从单链表缺点：找后继容易，找前驱必须从头开始查找。头开始查找。|双向链表：双向链表： 既可以找前驱，也可以找后既可以找前驱，也可以找后继。继。32struct DoubleNode; /* 双链表结点 */typedef struct DoubleNode * PDoubleNode; /*结点指针类型 */struct DoubleNode /* 双链表结点结构 */DataType info;PD

5、oubleNode llink, rlink;struct DoubleList /* 双链表类型 */ PDoubleNode head; /* 指向第一个结点 */ PDoubleNode rear; /* 指向最后一个结点 */; infollinkrlink结点结构：结点结构：pdlistk1k2knheadrear空表判断空表判断 ： pdlist-head = NULL最后一个节点：最后一个节点： p-rlink = NULL第一个节点：第一个节点： p-llink = NULL 访问第一个节点：访问第一个节点： pdlist-head访问最后结点：访问最后结点： pdlist-r

6、earP-rlink-llink = p-llink-rlink = p3434删除双向链表中删除双向链表中p指向的结点指向的结点ABCpp-llink-rlink = p-rlinkp-rlink-llink = p-llinkfree(p)双链双链表结表结点删点删除除35|往双向链表中往双向链表中p前插入结点：前插入结点： q = (PDoubleNode)malloc (sizeof(struct DoubleNode)1.q-llink = p-llink;2.p-llink-rlink = q;3.q-rlink = p;4.p-llink = q;ABCqp(1)(2)(4)(3)

7、ABCpq(1)(4)(3)(2)|p指向结点后插入新结点指向结点后插入新结点:zq-llink = p; z p-rlink-llink = q; zq-rlink = p-rlink;zp-rlink = q;37struct CDoubleList /* 循环双链表类型循环双链表类型 */ PDoubleNode head; /*指向头结点指向头结点CDoubleList cdlist;pdlistk0k1kn-1headpdlistk0k1kn-1head|链表操作链表操作z空表判断：pdlist-head-rlink = NULLz最后结点判断：p-rlink = pdlist-he

8、ad 或 p = pdlist-head-llink39 Josephus问题问题|设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此反复直到所有的人全部出列为止。|对于任意给定的n,s和m，求出按出列次序得到的n个人员的序列。40以以n=8，s=1，m=4为例为例 41|数据结构设计|算法设计|程序实现|算法分析42|数据结构设计z顺序表Mod n?元素移动z链表单链表循环链表l元素删除l判停标准？43main( ) /*主函数*/ PSeqList jos_alist; int i，k; int n,s,m; p

9、rintf(“n please input the values(100) of n = “); scanf(“%d”,&n); printf(“ please input the values of s = “); scanf(“%d”,&s); printf(“ please input the values of m = “); scanf(“%d”,&m); jos_alist = createNullList_seq( n ); /* 创建空顺序表 */ if (jos_alist != NULL) for( i = 0; i element); free(j

10、os_alist); s：开始序号；m：步长；44s：开始序号；m：步长；void josephus_seq( PSeqList palist, int s, int m) int s1, i, w; s1 = s - 1; for( i = palist-n; i0; i-) /* 找出列的元素 */ s1 = ( s1 + m - 1 ) % i ; /*下一个出列的元素*/ w = palist-elements1; /* 求下标为s1的元素的值 */ printf(“Out element %d n”,w); /* 元素出列 */ delete_seq(palist,s1); /* 删除出列的元素 */45|步骤：z1: 建立顺序表z2: 出列|时间复杂度分析：出列元素的删除（移动实现）为基本运算，每次最多i-1个元素移动，需要n-1次。 (n-1)+(n-2)+1 = n(n-1)/2 = O(n2)|步骤：z(1)建立循环链表；z(2)找循环单链表中的第s个结点放在指针变量p中z(3)从p所指结点开始计数寻找