3°步骤第1至最后所有元素后移一个元素在第i个位置插入元素x表长增14°℃算法bool" Listlnsert(SqList& L, int i, DataType x)if(L.length=-MAXSIZEK1Ii>L.length+1）returnfalse,//失败1元素后移I这里j为下标，从L.length-1到i-1for(j=L.length-1; j>=i-1; j--)L.elem[j+1] = L.elem[i];/若作为位序，有如何修改？I插入xL.elem[i-1] = x;表长增1L.length++:returntrue,I插入成功(6）删除算法ListDelete(&L,i,&x)1°前提：表非空2°合理的删除范围：1≤i≤L.length3°步骤取出第1个元素第1个元素之后的元素向前移动一个位置表长减14°算法bool ListDelete(SqList&L,inti,DataType&x)if(L.length==0Il<1li>L.length）returnfalse;/失败x = L.elem[i-1];for (j=i, j<L.length, j++)L.elem[i-i] = L.elem[i];L.length--,returntrue;I删除成功e8这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。- 10 -
- 10 - 3°. 步骤 第 i 至最后所有元素后移一个元素 在第 i 个位置插入元素 x 表长增 1 4°. 算法 bool8 ListInsert ( SqList& L, int i, DataType x ) { if ( L.length==MAXSIZE || i<1 || i>L.length+1 ) return false; // 失败 // 元素后移 for ( j=L.length-1; j>=i-1; j- ) // 这里 j 为下标，从 L.length-1 到 i-1 L.elem[j+1] = L.elem[j]; // 若作为位序，有如何修改？ // 插入 x L.elem[i-1] = x; // 表长增 1 L.length++; return true; // 插入成功 } (6) 删除算法 ListDelete(&L,i,&x) 1°. 前提：表非空 2°. 合理的删除范围：1≤i≤L.length 3°. 步骤 取出第 i 个元素 第 i 个元素之后的元素向前移动一个位置 表长减 1 4°. 算法 bool ListDelete ( SqList& L, int i, DataType& x ) { if ( L.length==0 || i<1 || i>L.length ) return false; // 失败 x = L.elem[i-1]; for ( j=i; j<L.length; j++ ) L.elem[j-1] = L.elem[j]; L.length-; return true; // 删除成功 } 8 这里返回 true 表示正确插入，返回 false 表示插入失败。以下常用来区分操作是否正确执行
(7）算法分析表2.1顺序表插入和删除算法的分析删除插入基本操作移动元素移动元素平均移动次Ynn-11(n-1)=(n-/+1)=数22n+1n0(n)0(n)时间复杂度尾端操作插入第n+1个元素，不移删除第n个元素，不移动动插入、删除需移动大量元素O(n）：但在尾端插入、删除效率高O(1)。(8）其他算法1°.InitList (&L), ClearList (&L)L.length = 0:2°. ListEmpty (L)return L.length =- O;3°. ListLength (L)return L.length:4°.GetElem(L,i,&e)e = L.elem[i-1];3.单链表线性表的链式存储结构之一(1) 概念线性链表，单链表，结点；数据域，指针域；头指针，头结点。(2) 特点用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）(3)类型定义简而言之，“数据+指针”9typedef struct LNode dataDataType data,next9不准确的说法，只为便于理解和记忆，不要在正式场合引用。- 11 -
- 11 - (7) 算法分析 表 2.1 顺序表插入和删除算法的分析 插入 删除 基本操作 平均移动次 数 移动元素 2 ( 1) 1 1 1 1 n n i n n i 移动元素 2 1 ( ) 1 1 n n i n n i 时间复杂度 O(n) O(n) 尾端操作 插入第 n+1 个元素，不移 动 删除第 n 个元素，不移动 插入、删除需移动大量元素 O(n)；但在尾端插入、删除效率高 O(1)。 (8) 其他算法 1°. InitList (&L), ClearList (&L) L.length = 0; 2°. ListEmpty (L) return L.length == 0; 3°. ListLength (L) return L.length; 4°. GetElem (L, i, &e) e = L.elem[i-1]; 3. 单链表——线性表的链式存储结构之一 (1) 概念 线性链表，单链表，结点；数据域，指针域；头指针，头结点。 (2) 特点 用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。 (3) 类型定义 简而言之，“数据 + 指针”9。 typedef struct LNode { DataType data; 9 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 data next
struct LNode *next.↓ LNode, *LinkList,(4）基本形态带头结点的单链表的基本形态有：1°.单链表空条件：L->next=02°单链表不空福aian条件：L->next!=0(5)基本算法（遍历）1°顺序访问所有元素借助指针，“顺藤摸瓜”（沿着链表访问结点)。p = L->next,/注意起始位置的考虑while（p!=NULL）(I判表尾，另外(pl=0)或(p)均可/访问：可以换成各种操作visit(p->data);/指针沿着链表向后移动p= p->next,例：打印单链表中的数据。void PrintLinkList (LinkList L)1p = L->next,while（pl=NULL)(Ⅱ访问：打印数据域print (p->data );p=p->next,22°查找元素×I/在单链表L中查找元素xⅡ若找到，返回指向该结点的指针：否则返回空指针LinkList Find (LinkList L, DataType x)p= L->next:while（p=NULL））returnp1/找到xif(p->data =x)p=p->next;returnNULL//未找到- 12 -
- 12 - struct LNode *next; } LNode, *LinkList; (4) 基本形态 带头结点的单链表的基本形态有： 1°. 单链表空 条件： L->next == 0 2°. 单链表不空 条件：L->next != 0 (5) 基本算法 （遍历） 1°. 顺序访问所有元素 借助指针，“顺藤摸瓜 ．．．．”(沿着链表访问结点)。 p = L->next; // 注意起始位置的考虑 while ( p!=NULL ) { // 判表尾，另外 (p!=0)或(p)均可 visit( p->data ); // 访问:可以换成各种操作 p = p->next; // 指针沿着链表向后移动 } 例：打印单链表中的数据。 void PrintLinkList ( LinkList L ) { p = L->next; while ( p!=NULL ) { print ( p->data ); // 访问：打印数据域 p = p->next; } } 2°. 查找元素 x // 在单链表 L 中查找元素 x // 若找到，返回指向该结点的指针；否则返回空指针 LinkList Find ( LinkList L, DataType x ) { p = L->next; while ( p!=NULL ) { if ( p->data == x ) return p; // 找到 x p = p->next; } return NULL; // 未找到 /\ an /\ C B A ( b ) (a ) E a1 L L
ⅡI在单链表L中查找元素xⅡ若找到，返回该元素的位序：否则返回0int Find (LinkList L, DataType x)1p=L->next, j=1,while（p!-NULL)）if(p->data==x）returnj，I/找到x1计数器随指针改变p=p->next;j++;1returnO；1/未找到前一个算法的另一种写法：p= L->next,while(p&& p->data!=x)p=p->next:if(p&&p->data==x)returnp;elsereturn O,或者p= L->next,while(p&&p->data!=x)p=p->next,returnp；I为什么3°查找第i个元素LinkList Get (LinkList L, int i)p=L->next, j=1;while（p&&j<i）p=p->next, j++;1if(p&&j--i)returnp,elsereturn O,4°查找第i-1个元素p=L; j=0;while(p&& j<i-1)(p=p->next, j++;if(p&& j-=i-1)returnp,elsereturn O;- 13 -
- 13 - } // 在单链表 L 中查找元素 x // 若找到，返回该元素的位序；否则返回 0 int Find ( LinkList L, DataType x ) { p = L ->next; j = 1; while ( p!=NULL ) { if ( p ->data == x ) return j; // 找到 x p = p ->next; j++; // 计数器随指针改变 } return 0; // 未找到 } 前一个算法的另一种写法： p = L ->next; while ( p && p ->data!=x ) p = p ->next; if ( p && p ->data==x ) return p; else return 0; 或者 p = L ->next; while ( p && p ->data!=x ) p = p ->next; return p; // 为什么 3°. 查找第 i 个元素 LinkList Get ( LinkList L, int i ) { p = L ->next; j = 1; while ( p && j<i ) { p = p ->next; j++; } if ( p && j==i ) return p; else return 0; } 4°. 查找第 i - 1 个元素 p = L; j = 0; while ( p && j<i -1 ) { p = p ->next; j++; } if ( p && j==i -1 ) return p; else return 0;
(6）插入算法ListInsert(&Li,x）技巧：画图辅助分析。思路：先查找第i-1个元素若找到，在其后插入新结点booio Listlnsert (LinkList &L, int i, DataType x)I查找第i-1个元素pp=L; j=0,插入前while（p&&j<i-1)p=p->next, j++;aiiI若找到，在p后插入x0xif(p&&j-i-1)(执行①之后s =(LinkList) malloc(sizeof(LNode),s->data = xai-ll?s->next = p->next;p->next= s;DSXreturntrue，//插入成功执行②之后elseai②returnfalse;插入失败1D注意：a）要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。b）能够插入的条件：p&&j-=i-1。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。c）新建结点时需要动态分配内存。s=(LinkList) malloc(sizeof(LNode);若检查是否分配成功，可用if（s==NULL）exit(1)；II分配失败则终止程序d）完成插入的步骤：①②。技巧：先修改新结点的指针域。(7)删除算法ListDelete(&L,i,&x）思路：先查找第i-1个元素若找到且其后存在第i个元素，则用x返回数据，并删除之10这里返回true表示正确插入，返回false表示插入失败。- 14 -
- 14 - (6) 插入算法 ListInsert(&L,i,x) 技巧：画图辅助分析。 思路： 先查找第 i-1 个元素 若找到，在其后插入新结点 bool10 ListInsert ( LinkList &L, int i, DataType x ) { // 查找第 i-1 个元素 p p = L; j = 0; while ( p && j<i-1 ) { p = p->next; j++; } // 若找到，在 p 后插入 x if ( p && j==i-1 ) { s = (LinkList) malloc(sizeof(LNode)); s->data = x; s->next = p->next; // ① p->next = s; // ② return true; // 插入成功 } else return false; // 插入失败 } 注意： a) 要让 p 指向第 i-1 个而不是第 i 个元素（否则，不容易找到前驱以便插入）。 b) 能够插入的条件： p && j==i-1 。即使第 i 个元素不存在，只要存在第 i-1 个元 素，仍然可以插入第 i 个元素。 c) 新建结点时需要动态分配内存。 s = (LinkList) malloc(sizeof(LNode)); 若检查是否分配成功，可用 if ( s==NULL ) exit(1); // 分配失败则终止程序 d) 完成插入的步骤：①②。技巧：先修改新结点的指针域。 (7) 删除算法 ListDelete(&L,i,&x) 思路： 先查找第 i-1 个元素 若找到且其后存在第 i 个元素，则用 x 返回数据，并删除之 10 这里返回 true 表示正确插入，返回 false 表示插入失败。 ai-1 · - 插入前 执行①之后 执行②之后 · - p s x ai-1 · - · - p x · - s ai-1 · - · - p x · - s ① ② ①