C语言程序设计 链表及其操作和应用.ppt

1.链表的建立 程序段 head = tail = NULL; scanf(%d%s%d, num,name, score); while(num != 0){ p = (struct stud_node *) malloc(size); p-num = num; strcpy(p-name, name); p-score = score; p-next = NULL; if(head == NULL) head = p; else tail-next = p; tail = p; scanf(%d%s%d, num, name, score); } 2. 链表的遍历 ptr-num ptr-score ptr ptr for(ptr = head; ptr != NULL; ptr = ptr - next) printf(%ld, %d, ptr - num, ptr - score); ptr=ptr-next head 9905 Qian 80 NULL 9901 Wang 80 9902 Li 90 链表的遍历－函数 void Print_Stu_Doc(struct stud_node * head) { struct stud_node * ptr; if(head == NULL){ printf(\nNo Records\n); return; } printf(\nThe Students Records Are: \n); printf( Num Name Score\n); for(ptr = head; ptr!=NULL; ptr = ptr-next) printf(%8d %20s %6d \n, ptr-num, ptr-name, ptr-score); } s-next = ptr-next ptr-next = s 先连后断 head ptr s 3. 插入结点 ptr2=ptr1-next ptr1-next=ptr2-next head ptr1 ptr2 free(ptr2) 先接后删 4. 删除结点 ptr2 head ptr1 5.线性表的链式存储实现 ? 线性表的链式存储实现 不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系。因此对线性表的插入、删除不需要移动数据元素，只需要修改“链”。 typedef struct{ ElementType Data; struct Node *Next; } List; List L, *PtrL; 访问序号为 i 的元素？ 求线性表的长度？ 12/25 1.求表长 ? 主要操作的实现 int Length ( List *PtrL ) { List *p = PtrL; /* p指向表的第一个结点*/ int j = 0; while ( p ) { p = p-Next; j++; /* 当前p指向的是第 j 个结点*/ } return j; } 时间性能为 O(n)。 13/25 2. 查找 List *FindKth( int K, List *PtrL ) { List *p = PtrL; int i = 1; while (p !=NULL i K ) { p = p-Next; i++; } if ( i == K ) return p; /* 找到第K个，返回指针 */ else return NULL; /* 否则返回空 */ } List *Find( ElementType X, List *PtrL ) { List *p = PtrL; while ( p!=NULL p-Data != X ) p = p-Next; return p; } （1）按序