数据结构第02章.ppt

第2章 线性表 2.1 线性表抽象数据类型 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 (2)头指针、头结点和首元结点的区别 2.4 循环单链表 2.5 双向链表 2.6 静态链表 2.7 设计举例 作业 （3）插入ListInsert(head, i, x) int ListInsert(SLNode *head, int i, DataType x) { SLNode *p, *q; int j; ? p = head; j = -1; while(p-next != NULL j i - 1) { p = p-next; j++; } if(j != i - 1) { printf(“插入位置参数错！”); return 0; } q = (SLNode *)malloc(sizeof(SLNode)); q-data = x; q-next = p-next; p-next = q; return 1; } 说明：①要在带头结点的单链表第i（0 ≤ i ≤ size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q-data = x），最后修改新结点的指针域指向ai结点（即q-next = p-next），并修改ai-1结点的指针域指向新结点q（即p-next = q）。 ②循环条件由两个子条件逻辑与组成，其中子条件p-next != NULL保证指针所指结点存在，子条件j i - 1保证最终让指针p指向ai-1结点。 （4）删除ListDelete(head, i, x) int ListDelete(SLNode *head, int i, DataType *x) { SLNode *p, *s; int j; ? p = head; j = -1; while(p-next != NULL p-next-next!= NULL j i - 1) { p = p-next; j++; } if(j != i - 1) { printf(“插入位置参数错！”); return 0; } ? s = p-next; *x = s-data; p-next = p-next-next; free(s); return 1; }? 说明：要在带头结点的单链表中删除第i（0 ≤ i ≤ size - 1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s = p-next），并把数据元素ai的值赋予x（即*x = s-data），最后把ai结点脱链（即p-next = p-next-next），并动态释放ai结点的存储空间（即free(s)）。删除过程如图2-14所示。图中的①对应算法中的删除语句。 （5）取数据元素ListGet(head, i, x) int ListGet(SLNode *head, int i, DataType *x) { SLNode *p; int j; ? p = head; j = -1; while(p-next != NULL j i) { p = p-next; j++; } ? if(j != i) { printf(“取元素位置参数错！”); return 0; } ? *x = p-data; return 1; } （6）撤消单链表Destroy(head) void Destroy(SLNode **head) { SLNode *p, *p1; ? p = *head; while(p != NULL)