第二章 线性数据结构 2012.ppt

* * 算法2-4 void insert(NODE *head, int i, int x) { NODE *p, *s; int j=0; p = head; while (( p!=NULL) (j i-1)) { p = p - next; j++; } * * if ((p == NULL) || (j i-1)) printf( i值不合法 \n); /* 找不到,in或i=0 */ else { s = (NODE *)malloc(sizeof(NODE)); /* ? */ s - data = x; /* ? */ s - next = p - next; /* ? */ p - next = s; /* ? */ } } 如果事先告之p指针所指的位置，则这种在p指针后插入一个元素算法的时间复杂度T(n)=O(1)，否则平均时间复杂度T(n)=O(n)。 * * 4.单链表的删除 删除操作和插入操作一样， (1) 首先要有哪些信誉好的足球投注网站单链表以找到指定删除结点的前趋结点(假设为p)； (2) 然后改变链接，即只要将待删除结点的指针域内容赋予p结点的指针域即可。 设有线性表(a1，a2，...，ai-1，ai，ai+1，...，an)，用带头结点的单链表存储，删除前的逻辑状态如图2-8所示。 删除元素ai所在的结点之后，单链表的逻辑状态如图2-9所示。 * * 图2-8 带头结点的单链表 图2-9 在单链表中删除一个结点 * * 算法2-5 void delete(NODE *head, int i) { NODE *p, *s; int j=0; p = head; while (( p-next != NULL) (j i-1)) { p = p - next; j++; } * * if ((p-next == NULL) || (j i-1)) printf(“i值不合法 \n”); /* 找不到,in或i=0 */ else { s = p - next; p - next = s - next; free(s); } } 如果事先告之p指针所指的位置，则这种在p指针后删除一个元素算法的时间复杂度T(n)=O(1)，否则平均时间复杂度T(n)=O(n)。 * * 4) 动态建立单链表的算法 要对单链表进行操作，首先要掌握怎样建立单链表。链表是一种动态存储结构，所需的存储空间只有在程序执行malloc之后，才可能申请到一个可用结点空间；free(p)的作用是系统回收一个结点，回收后的空间可以备作再次生成结点时用。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统应需求即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。 * * 动态建立线性表的链式存储结构有两种基本方法，分别适用于不同的场合。可根据所建链表结点的顺序要求选择采用一种方法。 单链表建立方法一：反向建立链表（头插法）。 思想：若线性表的元素已顺序存放在一维数组A[N]中，建表方法是从线性表的最后一个元素开始，从后向前依次插入到当前链表的第一个结点之前。 * * 算法2-6 #define N m /* m为链表中数据元素的个数,如m=10 */ int A[N]; NODE * creatlink1( ) { NODE *head, *s; int i; head = (NODE *)malloc(sizeof(NODE)); /*生成头结点*/ head - next = NULL; /* 置空表 */ for(i=N-1; i=0; i--) /* 插入10个数据 */ * * { s = (NODE *)malloc(sizeof(NODE)); /*生成新结点*/ s - data = A[i]; /*将输入数据放入新结点数据域*/