数据结构复习线表课件.pptVIP

例1-2 阅读下列算法，并回答问题。 float what (float x, int n) { float y; y=x; while(n1) { y= y*x; n=n–1; } return y; } 问题： (1) 该算法的功能是计算 xn 。 (2) 该算法的时间复杂度是 0(n) 。 (3) 若执行一次条件判断和执行一次赋值所需时间相同， 　　都是一个单位时间，则该算法的执行时间等于 3n–1 　　个单位时间。 #define MAXSIZE 10000 int a[MAXSIZE+1]; /* 线性表的容量 */ int n; /* 线性表的表长 */ （１）插入算法设计 输入：长度为n的线性表a[1]..a[n], 插入位置 i 和插入元素 x 输出：在第i处插入新元素x后，得到长度为n+1的线性表 void list_insert( ) { /* 在长度为n的线性表a[1..n]的第i处插入新元素x */ int j; if (n==MAXSIZE) error(“表满”); else if(i1||in+1)error(“ 插入位置错”); else { for (j=n; j=i; j--) a[j+1]= a[j]; /* 元素后移 */ a[i]= x; /* 在第i处插入x */ n++ ；/* 表长加1 */ } } （２）删除算法设计 输入：长度为n的线性表a[1]..a[n], 删除位置 i ; 　 输出：删除第i个元素后，得到长度为n-1的线性表 void list_delete( ) { /* 删除线性表a[1..n]中的第i个元素 */ int j; if (i1||in) error(“删除位置错”) ; else if (n==0) error(“表空”)； else { for (j=i+1; j=n; j++) a[j-1]=a[j]; /* 元素前移 */ n-- ；/* 表长减1 */ } } （１）查找（定位）算法设计 1. 功能 在链表中查找（定位于）第i个结点，若存在， 则返回该结点的地址，否则，返回空（NULL）。 2. 算法思想 从第一个结点开始，逐个查找（后移）并计数， 直到第i个结点止。 3. 算法设计 node *loc(node *head, int i){ /*head:带头结点的单链表的头指针，该算法定位于表中的第i个结点*/ node *p=head; /*指针初始化, p指向头结点*/ int j=0; /* j为计数器，初值为0*/ while ((p!=NULL)(ji)) { p=p-next; j++;} /* p后移，j计数,p移至第i个结点止 */ return (p); /* p指向第i个结点（返回第i个结点的地址）*/ } (2)插入算法设计 1.功能：在线性表第i处插入其数值为x新结点。 2.算法思想： 首先，找到第i-1个结点（p指向第i-1个结点）； 　然后，在p结点之后插入值为x新结点q。 在结点p之后插入新结点q: 3.算法设计 void ins(node *head, int i, elemtype x,node *q) { /* head:带头结点的单链表的头指针，该算法在第i个结 点后面插入其数值为x新结点q*/ node *p; p=loc(head,i-1); /* 令 p 指向第i-1个结点 if (p!=NULL) {q-next=p-next; p-next=q; /*在p结点之后插入值为x新结点q */ } } (3)删除算法设计 1.功能：删除第i个结点。 2.算法思想： 　首先，找到第i-1个结点（p指向第i-1个结点）； 　然后，删除p的下一个结点。 3.算法设计 void del (node* head, int i, elemtype *e){ /* head:带头结点的单链表的头指针，删除表中的i个结点，并将结点的值