做网站常用的软件,网站建设流程详细,惠州市网站建设公司,淮安做网站就找卓越凯欣2.1、线性表的定义和基本操作
如有侵权请联系删除。
2.1.1、线性表的定义#xff1a;
线性表是具有相同数据类型的 n (n0) 个数据元素的有限序列#xff0c;其中 n 为表长#xff0c;当 n 0 时线性表是一个空表。若用 L 命名线性表#xff0c;则其一般表示为
线性表是具有相同数据类型的 n (n0) 个数据元素的有限序列其中 n 为表长当 n 0 时线性表是一个空表。若用 L 命名线性表则其一般表示为 L ( a 1 , a 2 , a 3 , . . . , a i , x i 1 , . . . , a n ) L(a_1,a_2,a_3,...,a_i,x_{i1},...,a_n) L(a1,a2,a3,...,ai,xi1,...,an) 式中 a 1 a_1 a1 是唯一的“第一个元素”又称表头元素 a n a_n an 是唯一的“最后一个元素”又称表尾元素。除第一个元素外每个元素有且仅有一个直接前驱。除最后一个元素外每个元素有且仅有一个直接后驱。
由此线性表的特点是
表中元素的个数有限。表中元素具有逻辑上的顺序性表中数据有其先后次序。表中元素都是数据元素每个元素都是单个数据。表中元素的数据类型都相同这意味着每个元素都占有相同大小的存储空间。表中元素具有抽象性即仅讨论元素间的逻辑关系而不考虑元素究竟表示什么内容。
2.1.2、线性表的操作
线性表的主要操作如下 InitList(L) 初始化表。构造一个空的线性表。 Length(L) 求表长。返回线性表 L 的长度即 L 中数据元素的个数。 LocateElem(L,e) 按值查找操作。在表 L 中查找具有给定关键字值的元素。 GetElem(L,i) 按位查找操作。获取表 L 中第 i 个位置的元素的值。 ListInsert(L,i,e) 插入操作。在表 L 中的第 i 个位置上插入指定元素 e 。 ListDelete(L,i,e) 删除操作。删除表 L 中第 i 个位置的元素并用 e 返回删除元素的值。 PrintList(L) 输出操作。按前后顺序输出线性表 L 的所有元素值。 Empty(L) 判空操作。若 L 为空表则返回 true否则返回 false。 DestroyList(L) 销毁操作。销毁线性表并释放线性表 L 所占用的内存。 2.2、线性表的顺序表示
2.2.1、顺序表的定义
线性表的顺序储存又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在线性表的起始位置第 i 个元素的存储位置后面紧跟着存储位置的是第 i 1 个元素称 i 为元素 a i a_i ai 在线性表中的位序。因此顺序表的特点是表中元素的逻辑顺序与物理顺序相同。
假设线性表 L 存储的起始地址为 LOC(A)sizeof(ElemType) 是每个数据元素所占用内存空间的大小则表 L 所对应的顺序存储如下图所示。 通常用高级语言中的数组来描述线性表的顺序存储结构。
假定线性表的元素类型为 ElemType 则线性表的顺序存储类型描述为
#define MaxSize 50 //定义线性表的最大长度
typedef struct {ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度
} SqList; //顺序表的类型定义 一维数组可以是静态分配的也可以是动态分配的。在静态分配时由于数组的大小和空间事先已经固定一旦空间占满再加入新的数据就会产生溢出进而导致程序崩溃。
而在动态分配时存储数组的空间实在程序执行过程中通过动态存储分配语句分配到一旦数据空间占满就另外开辟一块更大的存储空间用以替换原来的存储空间从而达到扩充存储数组空间的目的而不需要为线性表依次性地划分所有空间。
#define InitSize 100 //表长度的初始定义
typedef struct {ElemType *data; //指示动态分配数组的指针int MaxSize,length; //数组的最大容量和当前个数
} SeqList; //动态分配数组顺序表定义 C语言初始动态分配语句为
L.data (ElemType*)malloc(sizeof(ElemType)*InitSize); 顺序表最主要的特点是随机访问即通过首地址和元素序号可在时间 O(1) 内找到指定的元素。
顺序表的存储密度高每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻所以插入和删除操作需要移动大量元素。
2.2.2、顺序表上基本操作的实现
1、插入操作
在顺序表 L 的第 i (1 i L.Length1) 个位置插入新元素 e 。若 i 的输入不合法则返回 false 表示插入失败否则将第 i 个元素及其后的所有元素依次往后移动一个位置腾出一个空位置插入新元素 e 顺序表长度增加 1插入成功返回 true。
#include stdio.h
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;int ListInsert(SqList *L,int i , int e);int main(){SqList L;L.length 0;for (int i 0; i 9; i){L.data[i] i 1;L.length 1;}ListInsert(L,4,10);for (int i 0; i L.length; i){printf(%d,,L.data[i]);}printf(\n%d,L.length);return 0;
}//实现插入算法的主体函数
int ListInsert(SqList *L,int i , int e){if (i 1 || i L-length 1)return 0;if (L-length MaxSize)return 0;for (int j L-length;j i;j--)L-data[j] L-data[j-1];L-data[i - 1] e;L-length ;return 1;
} 注意区别顺序表的为序和数组下标。
最好情况在表尾插入i n 1元素后移语句将不执行时间复杂度为 O(1)。
最坏情况在表头插入i 1元素后移语句将执行 n 次时间复杂度为 O(n)。
平均情况假设 p i p_i pi p i 1 / ( n − 1 ) p_i1/(n-1) pi1/(n−1)是在第 i 个位置上插入一个结点的概率则在长度为 n 的线性表中插入一个结点时所需移动的结点平均次数为 ∑ i 1 n 1 p i ( n − i 1 ) ∑ i 1 n 1 1 n 1 ( n − i 1 ) 1 n 1 ∑ i 1 n 1 ( n − i 1 ) 1 n 1 n ( n 1 ) 2 n 2 \sum_{i1}^{n1}p_i(n-i1)\sum_{i1}^{n1}\frac{1}{n1}(n-i1)\frac{1}{n1}\sum_{i1}^{n1}(n-i1)\frac{1}{n1}\frac{n(n1)}{2}\frac{n}{2} i1∑n1pi(n−i1)i1∑n1n11(n−i1)n11i1∑n1(n−i1)n112n(n1)2n 因此顺序表插入算法的平均时间复杂度为 O(n)
2、删除操作
删除顺序表 L 中第 i 1 i L.length个位置的元素用引用变量 e 返回。若 i 的输入不合法则返回 false 否则将被删元素赋给引用变量 e 并将 i 1 个元素及其后的所有元素依次往前移动一个位置返回 true。
#include stdio.h
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;int ListInsert(SqList *L,int i , int e);
int ListDelete(SqList *L,int i , int *e);int main(){SqList L;int e;L.length 0;for (int i 0; i 9; i){L.data[i] i 1;L.length 1;}ListInsert(L,4,10);ListDelete(L,4,e);for (int i 0; i L.length; i){printf(%d,,L.data[i]);}printf(\n%d,e);return 0;
}int ListInsert(SqList *L,int i , int e){if (i 1 || i L-length 1)return 0;if (L-length MaxSize)return 0;for (int j L-length;j i;j--)L-data[j] L-data[j-1];L-data[i - 1] e;L-length ;return 1;
}//实现删除算法的主体函数
int ListDelete(SqList *L,int i , int *e){if (i 1 || i L-length)return 0;*e L-data[i-1];for (int j i;jL-length;j)L-data[j-1] L-data[j];L-length--;return 1;
} 最好情况删除表尾元素即 i n无须移动元素时间复杂度为 O(1)。
最坏情况删除表头元素即 i 1需移动除表头元素以外的所有元素时间复杂度为 O(n)。
平均情况假设 p i p_i pi p i 1 / n p_i1/n pi1/n是删除第 i 个位置上结点的概率则在长度为 n 的线性表中删除一个结点时所需移动结点的平均次数为 ∑ i 1 n 1 p i ( n − i ) ∑ i 1 n 1 1 n 1 ( n − i ) 1 n ∑ i 1 n 1 ( n − i ) 1 n n ( n − 1 ) 2 n − 1 2 \sum_{i1}^{n1}p_i(n-i)\sum_{i1}^{n1}\frac{1}{n1}(n-i)\frac{1}{n}\sum_{i1}^{n1}(n-i)\frac{1}{n}\frac{n(n-1)}{2}\frac{n-1}{2} i1∑n1pi(n−i)i1∑n1n11(n−i)n1i1∑n1(n−i)n12n(n−1)2n−1 因此顺序表删除算法的平均时间复杂度为 O(n)。
可见顺序表中插入和删除操作的时间主要耗费在移动元素上而移动元素的个数取决于插入和删除元素的位置。如下图所示 3、按值查找顺序查找
在顺序表 L 中查找第一个元素值等于 e 的元素并返回其位序。
#include stdio.h
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;int ListInsert(SqList *L,int i , int e);
int ListDelete(SqList *L,int i , int *e);
int LocateElem(SqList *L,int e);int main(){SqList L;int e,index;L.length 0;for (int i 0; i 9; i){L.data[i] i 1;L.length 1;}ListInsert(L,4,10);ListDelete(L,4,e);for (int i 0; i L.length; i){printf(%d,,L.data[i]);}printf(\n%d,e);index LocateElem(L,4);printf(\n%d,index);return 0;
}int ListInsert(SqList *L,int i , int e){if (i 1 || i L-length 1)return 0;if (L-length MaxSize)return 0;for (int j L-length;j i;j--)L-data[j] L-data[j-1];L-data[i - 1] e;L-length ;return 1;
}int ListDelete(SqList *L,int i , int *e){if (i 1 || i L-length)return 0;*e L-data[i-1];for (int j i;jL-length;j)L-data[j-1] L-data[j];L-length--;return 1;
}//实现按值查找算法的主体函数
int LocateElem(SqList *L,int e){int i;for (i 0;i L-length;i)if (L-data[i] e)return i 1;return 0;
} 最好情况查找到元素在表头仅需比较一次时间复杂度为 O(1)。
最坏情况查找到元素在表尾或不存在需要比较 n 次时间复杂度为 O(n)。
平均情况假设 p i p_i pi p i 1 / n p_i1/n pi1/n是查找到元素在第 i (1 i L.length)个位置上的概率则长度为 n 的线性表中查找值为 e 的元素所需比较多平均次数为 ∑ i 1 n p i × i ∑ n 1 n 1 n × i 1 n n ( n 1 ) 2 n 1 2 \sum_{i1}^{n}p_i\times i\sum_{n1}^{n}\frac{1}{n}\times i\frac{1}{n}\frac{n(n1)}{2}\frac{n1}{2} i1∑npi×in1∑nn1×in12n(n1)2n1 因此顺序表按值查找算法的平均时间复杂度为 O(n)。
2.3、线性表的链式表示
链式存储线性表时不需要使用地址连续的存储单元即不要求逻辑上相邻的元素在物理位置上也相邻它通过 “链”建立起元素之间的逻辑关系因此插入和删除操作不需要移动元素而只需修改指针但也会失去顺序表可随机存取的优点。
2.3.1、单链表的定义
线性表的链式存储又称单链表它是指通过一组任意的存储单位来存储线性表中的数据元素。为了建立数据元素之间的线性关系对每个链表结点除存放元素自身的信息外还需存放一个指向其后继的指针。单链表结点一般存放两个域一个时 data 数据域用于存放数据另一个 next 为指针域用于存放后继结点的地址。
单链表中结点类型的描述如下
typedef struct LNode {ElemType data;struct LNode *next;
}LNode,*LinkList; 利用单链表可以解决顺序表需要大量连续存储单元的缺点但单链表附加指针域也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中所以单链表是非随机存取的存储结构即不能直接找到表中某个特定的结点。查找某个特定的接待你时需要从头开始遍历依次查找。
通常用头指针来表示一个单链表如单链表 L 头指针为 NULL 时表示一个空表。此外为了操作上的方便在单链表第一个结点之前附加一个结点成为头结点。头结点的数据域可以不设任何信息也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点如下图
头结点和头指针的区分不管带不带头结点头指针都始终指向链表的第一个结点而头结点时带头节点的链表中的第一个结点结点内通常不存储信息。
引入头结点后可以带来两个优点。
由于第一个数据结点的位置被存放在头结点的指针域中因此在链表的第一个位置上的操作和在表的其他位置上的操作一致无需进行特殊处理。无论链表是否为空其头指针都是指向头结点的非空指针空表中头结点的指针域为空因此空表和非空表的处理也就得到了统一。
2.3.2、单链表上基本操作和实现
1、采用头插法建立单链表
该方法从一个空表开始生成新节点并将读取到的数据存放到信结点的数据域中然后将新结点插入到当前链表的表头即头结点之后如下图: 头插法建立单链表的算法如下
#include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);int main(){LinkList L,p;L List_HeadInsert(L);p L-next;while(p){printf(%d,,p-data);p p-next;}return 0;
}//实现头插法建立链表的函数输出结果是输入的逆序输入1 2 3输出结果是321
LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
} 采用头插法建立单链表时读入数据的顺序与生成的链表的元素的顺序时相反的。每个结点插入的时间为 O(1)设单链表长为 n 则总时间复杂度为 O(n)。
2、采用尾插法建立单链表
头插法建立单链表的算法虽然简单但生成的链表中节点的次序和输入数据的顺序不一致。若希望两者次序一致则可采用尾插法。该方法将新结点插入到当前链表的表尾为此必须增加一个尾指针 r 使其始终指向当前链表的尾结点如下图 #include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);int main(){LinkList L,p;//头插法建立链表的函数调用
// L List_HeadInsert(L);//尾插法建立链表的函数调用L List_TailInsert(L);p L-next;while(p){printf(%d,,p-data);p p-next;}return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
}//实现尾插法建立链表的函数
LinkList List_TailInsert(LinkList L){int x;L (LinkList)malloc(sizeof(LNode));LinkList s,r L;scanf(%d,x);while (x ! 9999){s (LinkList) malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}3、按序号查找结点
在单链表中从第一个结点出发顺时针 next 域逐个往下搜索直到找到第 i 个结点为止否则返回最后一个结点指针域 NULL。
按序号查找结点值的算法如下
#include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);int main(){LinkList L,p;//头插法建立链表的函数调用
// L List_HeadInsert(L);//尾插法建立链表的函数调用L List_TailInsert(L);p L-next;while(p){printf(%d,,p-data);p p-next;}LinkList target GetElem(L,4);printf(\n%d,target-data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L (LinkList)malloc(sizeof(LNode));LinkList s,r L;scanf(%d,x);while (x ! 9999){s (LinkList) malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}//实现按序号查找结点算法的函数
LinkList GetElem(LinkList L,int i){if (i 1)return NULL;int j 1;LinkList p L-next;while(p ! NULL j i){p p-next;j ;}return p;
} 按序号查找操作的时间复杂度为 O(n)。
4、按值查找表结点
从单链表的第一个结点开始由前往后依次比较表中各结点数据域的值若某结点数据域的值等于给定值 e 则返回该结点的指针若整个单链表中没有这样的结点则返回 NULL。
按值查找表结点的算法如下
#include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);int main(){LinkList L,p;//头插法建立链表的函数调用
// L List_HeadInsert(L);//尾插法建立链表的函数调用L List_TailInsert(L);p L-next;while(p){printf(%d,,p-data);p p-next;}LinkList target GetElem(L,4);printf(\n%d,target-data);target LocateElem(L,5);printf(\n%d,target-data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L (LinkList)malloc(sizeof(LNode));LinkList s,r L;scanf(%d,x);while (x ! 9999){s (LinkList) malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i 1)return NULL;int j 1;LinkList p L-next;while(p ! NULL j i){p p-next;j ;}return p;
}//实现按值查找结点的函数如下
LinkList LocateElem(LinkList L,int e){LinkList p L-next;while (p!NULL p-data ! e)p p-next;return p;
}5、插入结点操作
通过查找到指定结点的前驱结点进行后插操作
插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性然后找到待插入位置的前驱结点即第 i - 1个结点再在其后插入新结点。
算法先调用按序号查找算法 GetElem(L,i-1)查找第 i - 1 个结点。假设返回的第 i - 1 个结点为 *p然后令新结点 *s 的指针域指向 *p 的后继结点再领结点 *p 的指针域指向新插入的结点 *s。如下图所示 实现插入结点的代码如下
#include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);int main(){LinkList L,p;//头插法建立链表的函数调用
// L List_HeadInsert(L);//尾插法建立链表的函数调用L List_TailInsert(L);L PreInsert(L,5,99);p L-next;while(p){printf(%d,,p-data);p p-next;}LinkList target GetElem(L,4);printf(\n%d,target-data);target LocateElem(L,5);printf(\n%d,target-data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L (LinkList)malloc(sizeof(LNode));LinkList s,r L;scanf(%d,x);while (x ! 9999){s (LinkList) malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i 1)return NULL;int j 1;LinkList p L-next;while(p ! NULL j i){p p-next;j ;}return p;
}LinkList LocateElem(LinkList L,int e){LinkList p L-next;while (p!NULL p-data ! e)p p-next;return p;
}//实现通过第 i 个数据的前驱结点进行插入的函数算法
LinkList PreInsert(LinkList L,int i,int e){ //实现在第i个结点之后进行插入LinkList p,s;s (LinkList) malloc(sizeof(LNode));p GetElem(L,i-1); //获取第i个结点的前驱结点s-data e;s-next p-next;p-next s;return L;
}扩展对指定结点进行前插操作
假设我们想将结点 s 插入到 p 之前。那么则需要将 s 插到 p 的后面然后交换 p-data 与 s-data 域这样既可以满足了逻辑关系又能使得时间复杂度为 O(1)。
代码实现如下
#include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);
LinkList backInsert(LinkList L,int i,int e);int main(){LinkList L,p;//头插法建立链表的函数调用
// L List_HeadInsert(L);//尾插法建立链表的函数调用L List_TailInsert(L);L backInsert(L,5,99);p L-next;while(p){printf(%d,,p-data);p p-next;}LinkList target GetElem(L,4);printf(\n%d,target-data);target LocateElem(L,5);printf(\n%d,target-data);return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L (LinkList)malloc(sizeof(LNode));LinkList s,r L;scanf(%d,x);while (x ! 9999){s (LinkList) malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i 1)return NULL;int j 1;LinkList p L-next;while(p ! NULL j i){p p-next;j ;}return p;
}LinkList LocateElem(LinkList L,int e){LinkList p L-next;while (p!NULL p-data ! e)p p-next;return p;
}LinkList PreInsert(LinkList L,int i,int e){ //实现在第i个结点之后进行插入LinkList p,s;s (LinkList) malloc(sizeof(LNode));p GetElem(L,i-1); //获取第i个结点的前驱结点s-data e;s-next p-next;p-next s;return L;
}//实现后插结点的函数主题如下
LinkList backInsert(LinkList L,int i,int e){LinkList p,s;int temp;s (LinkList) malloc(sizeof(LNode));p GetElem(L,i); //获取第i个结点的前驱结点s-data e;s-next p-next;p-next s;temp p-data;p-data s-data;s-data temp;return L;
}6、删除结点操作
删除结点操作是将单链表的第 i 个结点删除。先检查删除位置的合法性后查找表中第 i - 1 个结点即被删结点的前驱结点再将其删除。如下图 代码实现如下
#include stdio.h
#include stdlib.h
typedef struct Node {int data;struct Node *next;
}LNode,*LinkList;LinkList List_HeadInsert(LinkList L);
LinkList List_TailInsert(LinkList L);
LinkList GetElem(LinkList L,int i);
LinkList LocateElem(LinkList L,int e);
LinkList PreInsert(LinkList L,int i,int e);
LinkList backInsert(LinkList L,int i,int e);
LinkList DeleteNode(LinkList L,int i);int main(){LinkList L,p;L List_TailInsert(L);p L-next;L DeleteNode(L,4);while(p){printf(%d,,p-data);p p-next;}return 0;
}LinkList List_HeadInsert(LinkList L){LNode *s;int x;L (LinkList)malloc(sizeof(LNode));L-next NULL;scanf(%d,x);while (x!9999) {s (LinkList)malloc(sizeof(LNode));s-data x;s-next L-next;L-next s;scanf(%d,x);}return L;
}LinkList List_TailInsert(LinkList L){int x;L (LinkList)malloc(sizeof(LNode));LinkList s,r L;scanf(%d,x);while (x ! 9999){s (LinkList) malloc(sizeof(LNode));s-data x;r-next s;r s;scanf(%d,x);}r-next NULL;return L;
}LinkList GetElem(LinkList L,int i){if (i 1)return NULL;int j 1;LinkList p L-next;while(p ! NULL j i){p p-next;j ;}return p;
}LinkList LocateElem(LinkList L,int e){LinkList p L-next;while (p!NULL p-data ! e)p p-next;return p;
}LinkList PreInsert(LinkList L,int i,int e){ //实现在第i个结点之后进行插入LinkList p,s;s (LinkList) malloc(sizeof(LNode));p GetElem(L,i-1); //获取第i个结点的前驱结点s-data e;s-next p-next;p-next s;return L;
}LinkList backInsert(LinkList L,int i,int e){LinkList p,s;int temp;s (LinkList) malloc(sizeof(LNode));p GetElem(L,i); //获取第i个结点的前驱结点s-data e;s-next p-next;p-next s;temp p-data;p-data s-data;s-data temp;return L;
}//实现删除结点操作的函数的主体如下
LinkList DeleteNode(LinkList L,int i){LinkList p,q;int e;p GetElem(L,i-1);q p-next;p-next q-next;printf(被删除结点的元素的数据为%d\n,q-data);free(q);return L;
} 和插入算法一样该算法的主要时间也是耗费在查找操作上时间复杂度为 O(n)。
7、求表长操作
求表长操作要求计算单链表数据结点也就是不含头结点的结点的总个数需要从第一个结点开始遍历直到访问完所有的结点因为比较简单具体实现就不进行赘述了不过需要注意有的链表存在头结点有的不存在在计算的时候要做好相关的区分操作。
8、销毁整个表我自己写的
不多解释直接上源码
void AllFree(LinkList L){LinkList p L-next,r;while(p){r p;p p-next;free(r);}free(p);free(L);
}2.3.3、双链表
单链表结点中只有一个指向其后继的指针使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点插入、删除操作时只能从头开始遍历访问后继结点的时间复杂度为 O(1)访问前驱结点的时间复杂度为 O(n)。
为了克服单链表的上述缺点引入了双链表双链表结点中有两个指针 prior 和 next 分别指向其前驱和后继结点如下图 双链表中结点类型的描述如下
typedef struct DNode{ElemType data;struct DNode *prior,*next;
} Dnode,*DLinkList; 双链表在单链表的结点中增加了一个指向前驱的 prior 指针因此双链表中的按值查找和按位查找的操作与单链表相同。但双链表在插入和删除操作的实现上与单链表有着较大的不同。这是因为“链”变化时也需要对 prior 指针做出修改其关键是保证在修改的过程中不断链。此外双链表可以很方便地找到其前驱结点因此插入、删除操作的时间复杂度仅为 O(1)。
1、双链表的插入操作
在双链表中 p 所指的结点之后插入结点 *s 其指针的变化过程如下图 插入操作的代码如下
#include stdio.h
#include stdlib.htypedef struct DNode{int data;struct DNode *prior,*next;
} DNode,*DLinkList;DLinkList create(DLinkList DL);
DLinkList GetElem(DLinkList DL,int i);
DLinkList Insert(DLinkList DL,int i,int e);
void AllFree(DLinkList L);int main(){DLinkList DL,p;DL create(DL);p DL-next;while(p){printf(%d,,p-data);p p-next;}puts();DL Insert(DL,3,10);p DL-next;while(p){printf(%d,,p-data);p p-next;}AllFree(DL);return 0;
}DLinkList create(DLinkList DL){int x;DL (DLinkList)malloc(sizeof(DNode));DLinkList s,r DL;scanf(%d,x);while (x ! 9999){s (DLinkList) malloc(sizeof(DNode));s-data x;r-next s;r-next-prior r;r s;scanf(%d,x);}r-next NULL;return DL;
}DLinkList GetElem(DLinkList DL,int i){if (i 1)return NULL;int j 1;DLinkList p DL-next;while(p ! NULL j i){p p-next;j ;}return p;
}//实现插入操作的函数主体如下
DLinkList Insert(DLinkList DL,int i,int e){DLinkList s,p;s (DLinkList) malloc(sizeof(DNode));p GetElem(DL,i-1);s-data e;s-next p-next;p-next-prior s;s-prior p;p-next s;return DL;
}void AllFree(DLinkList DL){DLinkList p DL-next,r;while(p){r p;p p-next;free(r);}free(p);free(DL);
}2、双链表的删除操作
删除双链表的结点 *p 的后继结点 *q 指针变化过程如下图 删除操作的代码如下
#include stdio.h
#include stdlib.htypedef struct DNode{int data;struct DNode *prior,*next;
} DNode,*DLinkList;DLinkList create(DLinkList DL);
DLinkList GetElem(DLinkList DL,int i);
DLinkList Insert(DLinkList DL,int i,int e);
DLinkList Delete(DLinkList DL,int i);
void AllFree(DLinkList L);int main(){DLinkList DL,p;DL create(DL);p DL-next;while(p){printf(%d,,p-data);p p-next;}puts();DL Insert(DL,3,10);p DL-next;while(p){printf(%d,,p-data);p p-next;}puts();DL Delete(DL,3);p DL-next;while(p){printf(%d,,p-data);p p-next;}AllFree(DL);return 0;
}DLinkList create(DLinkList DL){int x;DL (DLinkList)malloc(sizeof(DNode));DLinkList s,r DL;scanf(%d,x);while (x ! 9999){s (DLinkList) malloc(sizeof(DNode));s-data x;r-next s;r-next-prior r;r s;scanf(%d,x);}r-next NULL;return DL;
}DLinkList GetElem(DLinkList DL,int i){if (i 1)return NULL;int j 1;DLinkList p DL-next;while(p ! NULL j i){p p-next;j ;}return p;
}DLinkList Insert(DLinkList DL,int i,int e){DLinkList s,p;s (DLinkList) malloc(sizeof(DNode));p GetElem(DL,i-1);s-data e;s-next p-next;p-next-prior s;s-prior p;p-next s;return DL;
}//实现删除结点的函数的主体
DLinkList Delete(DLinkList DL,int i){DLinkList p,q;q GetElem(DL,i);p q-prior;p-next q-next;q-next-prior p;free(q);return DL;
}void AllFree(DLinkList DL){DLinkList p DL-next,r;while(p){r p;p p-next;free(r);}free(p);free(DL);
}2.3.4、循环链表
1、循环单链表
循环单链表和单链表的区别在于表中最后一个结点的指针不是 NULL 而改为指向头结点从而整个链表形成一个环如下图 在循环单链表中表尾结点的 next 域指向 L 故表中没有指针域为 NULL 的结点因此循环单链表的判空条件不是头结点的指针是否为空而是它是否等于头指针。
循环单链表的插入、删除算法与单链表的几乎一样所不同的是若操作在表尾进行则执行的操作不同以让单链表继续保持循环的特性。当然正因为循环单链表是一个环因此在任何一个位址上的插入和删除操作都是等价的无需判断是否是表尾。
在单链表中只能从表头结点开始往后顺序遍历整个链表而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对循环链表不设头指针仅设尾指针以使得操作效率更高。其原因是若设的是头指针对在表尾插入元素需要 O(n) 的时间复杂度而若设的是尾指针 r r-next 即为头指针对在表头或表尾插入元素都只需要 O(1) 的时间复杂度。
2、循环双链表
由循环单链表的定义不难退出寻你换双链表。不同的是在循环双链表中头结点的 prior 指针还要指向表尾结点如下图 在循环双链表 L 中某节点 *p 为尾结点时p-next L 当循环双链表为空表时其头结点的prior 域和 next 域都等于 L 。
2.3.5、静态链表
静态链表借助数组来描述线性表的链式存储结构结点也有数据域 data 和 指针域 next 与之前的链表中的指针不同的是这里的指针是结点的相对地址数组下标又称游标。和顺序表一样静态链表也要预先分配一段连续的内存空间。
静态链表和单链表的对应关系如下。 静态链表结构类型的描述如下
#define MaxSize 50
typedef struct {ElemType data;int next;
}SLinkList[MaxSize]; 静态链表以 next 1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同只需要修改指针而不需要移动元素静态链表没有单链表使用起来方便但在一些不支持指针的高级语言中这是一种非常巧妙的设计方法。
