C程序设计第九章ppt西工大

1第9章链表快速排序法A[1]A[N]2关键数据一趟快速排序：将所有比关键数据小的数据放在它左边，所有比关键数据大的数据放在它右边i=1，j=N33456781233719ij1）利用j从后向前扫描，找到第一个比关键数据小的数，交换1956781233734ij2）利用i从前向后扫描，找到第一个比关键数据大的数，交换19

34781233756ij3）重复（1）即利用j从后向前扫描，找到第一个比关键数据小的数，交换19

778123334

56419

778123334

5619

7

34123378

5619

7

331234

78

56条件i<j不满足了，一趟排序结束19

7

331234

78

56递归递归5voidquicksort(inta[],intleft,intright){

inti,j,temp;i=left;j=right;temp=a[left];

if(left>=right)return;while(i<j){

while(a[j]>=temp&&j>i)j--;

if(j>i)a[i++]=a[j];

while(a[i]<=temp&&j>i)i++;

if(j>i)a[j--]=a[i];

}

a[i]=temp;

quicksort(a,left,i-1);

quicksort(a,i+1,right);}6intmain()

{

inta[7]={17,2,6,12,1,9,5};

inti;

quicksort(a,0,6);

/*排好序的结果*/

for(i=0;i<7;i++)

printf("%4d",a[i]);return0;

}7第9章链表9.1链表概述9.2链表的创建9.3链表的运算9.4结点的插入与删除8本知识点在本课程知识体系中地位链表是一种常见的重要的数据结构，它是动态的进行内存存储分配的一种结构，存储空间能动态进行增长或缩小的数据结构。链表主要用于两个目的：一是建立不定长度的数组。二是链表可以在不重新安排整个存储结构的情况下，方便且迅速地插入和删除数据元素。9例如：建立一个学生管理程序，要求实现学生的数据动态录入、查询和删除链表概述2006-2007学年第二学期成绩表序号姓名性别高等数学大学英语大学物理平均分总评1李亦铮女89969493.0优秀2李凌飞男98878991.3优秀3马云燕女84938687.7优秀4陈牧笛女84898686.3优秀5林溢洋女85868184.0良好插入新数据删除问题特点：事先不确定学生人数，如果采用事先确定长度的存储结构，将会带来存储空间的浪费必须用动态存储结构存放数据10程序中存放大量数据：链表和数组数组存放数据：必须事先定义固定的长度（即元素个数数组存放数据：物理存储单元要求在内存中分配连续存储空间链表存放数据：可以根据需要，动态开辟内存单元。链表存放数据：物理存储单元非连续，非顺序的存储结构11链表：是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。节点节点：数据+指针数据:存放数据存储单元指针：指示后继元素存储位置129.1.1链表的概念一种称为结点（node）的数据类型：这个结构体类型中，data成员表示数据域，代表结点的数据信息。typedefstructtagNODE{//结点数据类型

ElemTypedata;//数据域

structtagNODE*link;//指针域}NODE;例如：节点的构成上图每个节点具有如下结构体类型：

structtagSTU{longnum;floatscore;structertagSTU*next;};//链节成员其中：成员num、score用于存放一个节点的具体数据；成员next是指针类型，用于存放下一节点指针，最后一个节点的next成员存放空指针NULL；成员next是指向与自身同一类型的结构，这种结构称为自引用结构。(只有指针成员可自引用)动态链表的节点是在运行时动态生成的。

动态内存分配和释放建立和维护动态数据结构需要实现动态内存分配；如在链表中插入节点需要先申请一段存储区域，而删除一个节点需要释放该节点原先占用的存储区域，这可由标准函数实现。内存分配函数原形：

void*malloc(unsignedsize);功能：申请长度为size个字节的内存空间；若申请成功，返回存储块起始指针，该指针类型为

void*；否则返回空指针(NULL)。内存释放函数原形：voidfree(void*p);功能：释放p所指向的内存块。包含文件：malloc.h、stdlib.h中均有其原型声明。链表的类型单链表：每个节点只有一个指向后继节点的指针双向链表：每个节点有两个用于指向其它节点的指针；一个指向前趋节点，一个指向后继节点循环链表：使最后一个节点的指针指向头节点链表构造方式用多个结构体变量可构成——静态链表将动态申请空间而建立的节点链接——动态链表采用动态链表的意义与定长数据结构数组相比，链表能更好地利用内存，按需分配和释放存储空间。在链表中插入或删除一个节点，只需改变某节点“链节”成员的指向，而不需要移动其它节点，相对数组元素的插入和删除效率高。即：链表特别适合于对大线性表频繁插入和删除元素、或数据域成员数目不定的数据结构。17链表类型--单向链表：包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值18链表类型--双向链表：每个节点有两个指针域：一个指向前一个节点；而另一个指向下一个节点19链表类型—循环链表：首节点和末节点被连接在一起用单链表实现双向链表209.1.1链表的概念可以看出，链表是一种物理存储非连续（非顺序）的存储结构，数据元素的逻辑顺序是通过链表中的指针域实现的。链表由一系列结点组成，结点可以在运行时动态生成，因而链表可以动态增长或缩短。同时，结点是按指针域连接起来的，插入或删除结点非常简便和迅速。通常，链表包含创建、遍历、插入、删除等运算。219.1.2单链表与双链表1．单链表单链表每个结点包含一个指向直接后继结点的指针域，其形式为：next指向直接后继结点，由它构成了一条链。typedefstructtagLNode{//单链表结点类型

ElemTypedata;//数据域

structtagLNode*next;//指针域：指向直接后继结点}LNode,*LinkList;//LNode为单链表结构体类型，LinkList为单链表指针类型229.1.2单链表与双链表图9.2单链表结构指针L指向单链表头结点，头结点指向开始结点，开始结点又指向下一个结点，……，直到最后一个尾结点。尾结点的next为0，表示NULL指针，约定单链表的结点的next为0时表示尾结点。上述链表称为带头结点的单链表，若开始结点为头结点，则称这样的链表为不带头结点的单链表。239.1.2单链表与双链表2．双链表双链表每个结点包含指向前驱结点和指向直接后继结点的指针域，其形式为：typedefstructtagDNode{//双链表结点类型

ElemTypedata;//数据域

structtagDNode*prev,*next;//指针域：分别指向前驱结点和直接后继结点}DNode,*DLinkList;//DNode为双链表结构体类型，DLinkList为双链表指针类型249.1.2单链表与双链表图9.3双链表结构指针L指向双链表头结点，其每个结点分别有指向前一个结点和后一个结点的指针。沿着next指针，头结点指向开始结点，开始结点又指向下一个结点，……，直到尾结点，尾结点的next为0。沿着prev指针，尾结点指向前一个结点，直到头结点head，头结点的prev为0。约定双链表的结点的next为0时表示尾结点，prev为0时表示头结点。双链表也有带头结点和不带头结点之分。259.1.2单链表与双链表与单链表相比，双链表可以从前向链和后向链遍历整个链表，这样简化了链表排序方法及运算。同时，当一个链数据受损（如数据库设备故障）时可以根据另一个链来恢复它。269.1.2单链表与双链表3．循环链表若单链表尾结点指向头结点而不是0，则该链表是循环单链表。同理，若双链表尾结点next指向头结点而不是0，头结点prev指向尾结点而不是0，则该链表是循环双链表。279.1.2单链表与双链表图9.4循环单链表和循环双链表289.2链表的创建299.2.1创建单链表通过第7章介绍的内存动态分配技术可以产生新结点的内存单元，例如：调用malloc、realloc内存分配函数或free释放函数时，在程序中需要文件包含命令：LinkListp;//链表指针p=(LinkList)malloc(sizeof(LNode));//分配LNode类型内存单元且将地址保存到p中#include<stdlib.h>309.2.1创建单链表创建链表常用两种方法：头插法和尾插法。（1）头插法建立链表CreateLinkF(&L,n,input())该方法先建立一个头结点*L，然后产生新结点，设置新结点的数据域；再将新结点插入到当前链表的表头，直至指定数目的元素都增加到链表中为止。其步骤为：①创建头结点*L，设置*L的next为0。②动态分配一个结点s，输入s的数据域。③将s插入到开始结点之前，头结点之后，即s->next=p->next，p->next=s。④重复②～④步骤加入更多结点。319.2.1创建单链表采用头插法创建单链表的算法如下：1voidCreateLinkF(LinkList*L,intn,

void(*input)(ElemType*))2{//头插法创建单链表，调用input输入函数输入数据

3LinkLists;4

*L=(LinkList)malloc(sizeof(LNode));5(*L)->next=NULL;//初始时为空表

6

for(;n>0;n--){//创建n个结点链表

7s=(LinkList)malloc(sizeof(LNode));8input(&s->data);9s->next=(*L)->next;10(*L)->next=s;//头结点之后

11}12}指向头节点的头指针329.2.1创建单链表1voidCreateLinkF(LinkList*L,intn,

void(*input)(ElemType*))参数L表示将要创建出来的单链表指针，之所以是LinkList类型的指针类型（即指针的指针），其原因是需要将链表返回到调用函数中。n表示创建链表时需要输入的元素数目，由实际应用中的具体要求确定。339.2.1创建单链表图9.5头插法建立的单链表L运行时若输入5个元素：1、2、3、4、5，则调用建立的单链表如图所示。LinkListL;CreateLinkF(&L,5,input);//创建单链表L349.2.1创建单链表（2）尾插法建立链表CreateLinkR(&L,n,input())头插法建立的链表中结点的次序与元素输入的顺序相反，若希望两者次序一致，可采用尾插法建立链表。该方法是将新结点插到当前链表的末尾上，359.2.1创建单链表采用尾插法创建单链表的算法如下：1voidCreateLinkR(LinkList*L,intn,

void(*input)(ElemType*))2{//尾插法创建单链表，调用input输入函数输入数据

3LinkListp,s;4p=*L=(LinkList)malloc(sizeof(LNode));5

for(;n>0;n--){//创建n个结点链表

6s=(LinkList)malloc(sizeof(LNode));7input(&s->data);8p->next=s,p=s;9}10p->next=NULL;//尾结点

11}369.2.1创建单链表图9.6尾插法建立的单链表L运行时若输入5个元素：1、2、3、4、5，则调用CreateLinkR(&L,5,input)建立的单链表如图所示。37链表的建立操作例题：建立一个学生管理系统管理学生各门课程信息，需要在程序运行过程中动态输入多个学生的成绩信息。2006-2007学年第二学期成绩表学号姓名性别高等数学大学英语大学物理平均分总评1李亦铮女89969493.0优秀2李凌飞男98878991.3优秀3马云燕女84938687.7优秀4陈牧笛女84898686.3优秀问题解决思路：利用单向链表解题，不断循环，为每一个有效数据动态开辟新节点，并保存数据，直到输入学号数据为0时结束.核心问题：如何将新节点加入到整个链表结构中

38链表的建立操作39首先设计一种称为结点的数据类型：typedefstructtagNODE{//结点数据类型intno；//数据域floateng;//数据域structtagNODE*next;//指针域}LNODE，*LinkList;//LNode为单链表结构体类型，LinkList为单链表指针类型数据域包含两个个成员，代表学生信息结点中的学号、英语成绩。next成员表示指针域，存放另一个结点的地址，是链表中的组织者。链表的建立操作40通过第7章介绍的内存动态分配技术可以产生新结点的内存单元，例如：调用malloc、realloc内存分配函数或free释放函数时，在程序中需要文件包含命令：LinkListp;//链表指针p=(LinkList)malloc(sizeof(LNode));//分配LNode类型内存单元且将地址保存到p中#include<stdlib.h>链表的建立操作41第一步：新节点加入链表过程核心问题：维护链表结构，假定有一个LNODE类型的对象指针L，通过将一个新结点的地址赋给L的最后一个节点的link成员，则可以通过尾节点的link成员（next）“链接”到新结点上，重复这个过程可以得到完整链表结构。链表的建立操作新产生一个节点新节点指针q尾指针p42第二步更新尾指针，使得始终指向当前链表中最后一个节点链表的建立操作新产生一个节点新节点指针q尾指针p第三步如果未到链表末尾，重复第一步和第二步总结：建立过程中始终需要有一个节点指针指向当前链表中最后一个节点的位置动态单链表的建立完整过程1）定义与节点同类型的链表头指针变量L并赋值0，表示链表在建立之前是空的；2)定义与节点同类型的工作指针变量p、q。链表的建立操作3)开辟第一个节点的存储区域，输入第一个节点数据；并使L、p、q指向第一个节点，210189.5Lpq实现代码：Len=sizeof(LNODE);q=(LinkLlist)malloc(len);scanf("%ld,%f",&q->num,&q->eng);L=p=q;链表的建立操作4)开辟下一节点的存储区域，使q指向新节点并输入新节点数据，然后使上一节点的next成员指向新节点；210189.5Lqp2304901048实现代码q=(LinkList)malloc(len);scanf("%ld,%f",&q->num,&q->eng);p->next=p;//更新尾指针

13701370pq链表的建立操作3)重复第4步，建立并链接多个节点直至所需长度，将末尾节点的next成员赋值0。210189.51370Lp2230490291885pNULL10481370q10121012pq实现代码q=(LinkList)malloc(len);scanf("%ld,%f",&q->num,&q->eng);p->next=q;p=p->next;//p2跟进p->next=NULL;//末尾节点next赋值0链表的建立操作采用尾插法创建单链表的算法如下：

1voidCreateLinkR(LinkListL,intn)

2{//尾插法创建单链表

3LinkListp,q;4p=L=(LinkList)malloc(sizeof(LNode));5

for(;n>0;n--){//创建n个结点链表

6q=(LinkList)malloc(sizeof(LNode));7scanf(“%d,%f”,&q->num,&q->eng);8p->next=q,p=q;9}10p->next=NULL;//尾结点

11}生成新节点更新尾指针实现建立链表过程链表的建立操作489.2.1创建单链表（3）初始化链表InitList(&L)构造一个空链表（即没有数据结点）的算法如下：1voidInitList(LinkList*L)

//构造一个空的单链表L2{3

*L=(LinkList)malloc(sizeof(LNode));4(*L)->next=NULL;//初始时为空表

5}499.2.1创建单链表（4）判断链表是否为空表ListEmpty(L)检测一个链表是否为空表的算法如下：1intListEmpty(LinkListL)//检测L是否为空表

2{//若L为空表返回TRUE，否则返回FALSE3

returnL->next==NULL;4}509.2.2创建双链表双链表每个结点有两个指针域，next指向直接后继结点，prev指向前驱结点。建立双链表的过程与单链表相似，只是需要再处理prev指针，建立前向链即可。519.2.2创建双链表采用头插法创建双链表的算法如下：1voidCreateLinkF(DLinkList*L,intn,

void(*input)(ElemType*))2{//头插法创建双链表，调用input输入函数输入数据

3DLinkLists;4

*L=(DLinkList)malloc(sizeof(DNode));5(*L)->prev=(*L)->next=NULL;6

for(;n>0;n--){//创建n个结点链表

7

s=(DLinkList)malloc(sizeof(DNode));8input(&s->data);9s->next=(*L)->next;10

if((*L)->next!=NULL)(*L)->next->prev=s;11(*L)->next=s,s->prev=*L;12}13}529.2.2创建双链表采用尾插法创建双链表的算法如下：1voidCreateLinkR(DLinkList*L,intn,

void(*input)(ElemType*))2{//尾插法创建双链表，调用input输入函数输入数据

3DLinkListp,s;4p=*L=(DLinkList)malloc(sizeof(DNode));5(*L)->prev=(*L)->next=NULL;6

for(;n>0;n--){//创建n个结点链表

7

s=(DLinkList)malloc(sizeof(DNode));8input(&s->data);9s->next=NULL;//当前结点是尾结点

10p->next=s,s->prev=p,p=s;11}12}539.2.2创建双链表构造一个空的双链表（即没有数据结点）的算法如下：1voidInitList(DLinkList*L)

//构造一个空的单链表L2{3

*L=(DLinkList)malloc(sizeof(DNode));4(*L)->prev=(*L)->next=NULL;5}549.3链表的运算双链表与单链表的基本运算大多数是相同的，本节仅讨论单链表的情形。559.3.1链表的遍历（1）链表遍历ListTraverse(L,visit())与数组不同，链表不是用下标而是用指针运算查找数据元素的。通过链表的头结点L可以访问开始结点p=L->next，令p=p->next，即p指向直接后继结点，如此循环可以访问整个链表中的全部结点，这就是链表的遍历（traverse）。链表的输出、销毁、查找和逆序等运算都需要遍历链表。链表遍历算法的实现步骤为：①令指针p指向L的开始结点。②若p为0，表示已到链尾，遍历结束。③令p指向直接后继结点，即p=p->next。重复②～③步骤直至遍历结束。【例】建立并输出有3名学生数据的单链表。#include<stdio.h>//包含NULL定义#defineN3structtagSTU//全局结构体类型定义{longnum;floatscore;structtagSTU*next;//自引用结构体指针};intmain(){┇}intmain(){structtagSTU*head,*p1,*p2;inti,len;head=NULL;//head初始化

len=sizeof(structtagSTU);//求类型长

for(i=1;i<=N;i++)//↙强制转换为结构体指针类型

{p1=(structtagSTU*)malloc(len);//申请

printf("Enternum,score:");//↓输入数据

scanf("%ld,%f",&p1->num,&p1->score);if(i==1)head=p2=p1;//指向首节点

else{p2->next=p1;p2=p1;}//节点链接

if(i==N)p2->next=NULL;//标记末尾节点

}

┇┇intmain(){┇for(i=1;i<=N;i++)//建立链表

{┇}for(i=1;i<=N;i++)//遍历输出N个节点链表

{if(i==1)p1=head;

//p1指向头节点

elsep1=p1->next;//p1指向下一节点

printf("num=%ld,score=%5.2f\n",p1->num,p1->score);}return0;}//mainSX09-10更适用的链表输出：┇p1=head;while(p1!=NULL)//适用于任意节点数链表{printf("num=%ld,score=%5.2f\n",p1->num,p1->score);p1=p1->next;}┇注：本形式的链表输出具有通用性，可适应由于删除或插入节点引起的链表长度的变化。609.4结点的插入与删除链表中每个结点都有指针域指向其前后结点，在进行结点插入和删除时，不能仅仅只对该结点进行操作，还要考虑其前后结点。619.4.1单链表插入结点插入结点操作是指将一个新结点插入到已知的链表中。插入位置可能在头结点、尾结点或者链表中间，插入操作前需要定位插入元素的位置和动态分配产生新结点。假设将新结点s插入到单链表的第i个结点位置上。方法是先在单链表中找到第i-1个结点p，在其后插入新结点s，如图（a）所示。为了插入结点s，先让结点s的指针域指向结点p的后一个结点（即p->next），如图（b）所示；然后修改结点p的指针域，令其指向结点s，如图（c）所示，从而实现3个结点指向关系的变化。629.4.1单链表插入结点图9.8单链表插入结点示意639.4.1单链表插入结点图9.8单链表插入结点示意649.4.1单链表插入结点图9.8单链表插入结点示意659.4.1单链表插入结点图9.8单链表插入结点示意总结：插入节点需要知道插入点之前的节点位置p。669.4.1单链表插入结点实现上述步骤的C语言语句如下：请注意，这两个表达式的顺序不能颠倒。因为若先修改结点p的指针域指向结点s，结点p的后一个结点（p->next）就此从链表中断开，再让结点s的指针域指向结点p的后一个结点已成错误的。在单链表中第i个位置上插入元素e的新结点s的算法如下：s->next=p->next,p->next=s;//结点插入算法节点的插入插入可分为随意插入和按顺序插入，随意插入包括插入到头部、尾部或中间指定位置；按顺序插入是指按某关键字的顺序插入，而在插入前链表必须已按该关键字进行了排序。按顺序插入的步骤：开辟待插入节点的存储区域并输入数据；2)查找插入位置：从链表首节点开始按关键字成员与待插入节点相同成员进行比较，直到确定了插入位置；3)将插入位置前一节点的“链节”成员赋给待插入节点的“链节”成员；4)将待插入节点的指针赋给前一节点“链节”成员；若：插入点在链头，先将头指针赋给插入节点的指针域，再将待插入节点的指针赋给头指针变量。210189.51370head10482304901012241478

104813701012101226802680291885NULL139491104820302030【例】在上例增加“按学号插入节点的函数”插入函数：structtagSTU*insert(structtagSTU*head){structtagSTU*p0,*p1,*p2;longn;intlen;len=sizeof(structtagSTU);p0=(structtagSTU*)malloc(len);//申请新节点

printf("Enternum,scoretoinsert:");scanf("%ld,%f",&p0->num,&p0->score);n=p0->num;//产生学号副本np1=head;//从首节点开始查找

┇

┇

p1=head;//↓插入在头部

if(n<p1->num){p0->next=head;head=p0;}else{do//查找插入位置

{p2=p1; p1=p1->next;}while(p1!=NULL&&n>p1->num);p0->next=p2->next;//插入点在p1之前位置

p2->next=p0;}return(head);}//insertSX09-12719.4.2单链表删除结点结点删除操作是指将链表中的某个结点从链表中删除。删除位置可能在头结点、尾结点或者链表中间，删除操作后需要释放删除结点的内存空间。将链表中第i个结点删去的方法是先在单链表中找到第i-1个结点p，再删除其后的结点，如图（a）所示。若要删除结点p的后一个结点（即p->next），只需要将p的指针域指向p->next的后一个结点（即p->next->next），如图（b）所示。729.4.2单链表删除结点图9.9单链表删除结点示意739.4.2单链表删除结点图9.9单链表删除结点示意第一步：将予删除节点后一个节点连到d前一个节点749.4.2单链表删除结点图9.9单链表删除结点示意第二步：将予删除节点的内存空间释放free(d);//释放结点实现分析：需要保存访问节点的前一个节点的位置，指针p。759.4.2单链表删除结点实现上述步骤的C语言语句如下：p->next=p->next->next;//结点删除算法769.4.2单链表删除结点1intListDelete(LinkList*L,ElemType*ep)2{//删除第i个结点,并由*ep返回其值

3LinkListp=NULL,q=*L;//q指向头结点

4

while(q!=NULL&&i>=1){//直到第i个结点

5p=q;//p是q的前驱

6q=q->next;//q指向直接后继结点

7i--;8}9

if(p==NULL||q==NULL)return0;10p->next=q->next;//结点删除算法

11

if(ep!=NULL)*ep=q->data;12free(q);//释放结点

13

return1;//操作成功返回真（1）

14}77约瑟夫问题，又称为约瑟夫环。据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。问题：站在哪个位置上可以成为最后剩下的那个人？链表的删除操作例题：有N个人围坐一圈，从第一个开始报数，凡是报到3就退出圈子，请找出最后一个留在圈子里的序号？数组的声明和引用问题解决思路：利用循环链表解题，不断循环，删除逢3的节点，直到最后剩一个节点核心问题：删除节点

78分析：结点删除操作是指将链表中的某个结点从链表中删除。删除操作后需要释放删除结点的内存空间。799.1.1链表的概念首先设计一种称为结点（node）的数据类型：这个结构体类型中，data成员表示数据域，代表结点的数据信息。typedefstructtagNODE{//结点数据类型

intdata;//数据域

structtagNODE*next;//指针域}NODE;next成员表示指针域，存放另一个结点的地址，是链表中的组织者。80PNum=1Num=2Num=3删除81剩余数为1？删除当前节点计数等于3计数加1更新剩余数否输出剩余节点序号是是否单链表删除结点问题解决流程图表示829.4.2单链表删除结点1voidsearch(LinkList*L，intN)2{//约瑟夫环

3LinkListp=*L;intsum=N;intNum=1//p指向首结点

4

while(sum!=1){//直到剩余1个结点

5Num++;//计数加一

6if(Num==3){q=p->next;p=p->next->next;free(q);Num=1;sum--;//释放计数为3的节点}

7}

8*L=p;9}【例】创建一个链表,当输入数据小于等于0时创建结束，先输出原始链表，然后将这个链表按反转重新排列，即将链头当链尾，链尾当链头，输出反转后的链表。输入格式:123497620输出格式:

原始表:12->34->9->7->6->2

反转表:2->6->7->9->34->12注意:

输入以0表示数据结束,建立链表要具有通用第一个输出为12,第二个为->34,因此需做计数#include<stdi