数据结构(C语言版)第2章

else { p=L; while(--i>1) p=p->next; p->next=p->next->next; //删除第 i 个元素 } }//Delete 2.19 Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表 L 中值大于 mink 且小于 maxk 的所有元素 { p=L; while(p->next->data<=mink) p=p->next; //p 是最后一个不大于 mink 的元素 if(p->next) //如果还有比 mink 更大的元素 { q=p->next; while(q->data<maxk) q=q->next; //q 是第一个不小于 maxk 的元素 p->next=q; } }//Delete_Between 2.20 Status Delete_Equal(Linklist &L)//删除元素递增排列的链表 L 中所有值相同的元 素 { p=L->next;q=p->next; //p,q 指向相邻两元素 while(p->next) { if(p->data!=q->data) { p=p->next;q=p->next; //当相邻两元素不相等时,p,q 都向后推一步 } else { while(q->data==p->data) { free(q); q=q->next; } p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 }//else
{ pc=pc->next; pc->data=p->data; p=p->next;q=q->next; } }//while }//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C) { i=0;j=0;k=0;m=0; //i 指示 A 中元素原来的位置,m 为移动后的位置 while(i<A.length&&j<B.length&& k<C.length) { if(B.elem[j]<C.elem[k]) j++; else if(B.elem[j]>C.elem[k]) k++; else { same=B.elem[j]; //找到了相同元素 same while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; //j,k 后移到新的元素 while(i<A.length&&A.elem[i]<same) A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置 while(i<A.length&&A.elem[i]==same) i++; //跳过相同的元素 } }//while while(i<A.length) A.elem[m++]=A.elem[i++]; //A 的剩余元素重新存储。 A.length=m; }// SqList_Intersect_Delete 分析:先从 B 和 C 中找出共有元素,记为 same,再在 A 中从当前位置开始, 凡小于 same 的 元素均保留(存到新的位置),等于 same 的就跳过,到大于 same 时就再找下一个 same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上 重做上题 { p=B->next;q=C->next;r=A-next; while(p&&q&&r) { if(p->data<q->data) p=p->next;

数据元素，返回一特殊值（例如0），表示查找失败。
(5) 插入元素Inselem (L,i,x) 在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样 使原序号为 i , i+1, ..., n 的数据元素的序号变为 i+1,i+2, ..., n+1，要求1≤i≤Getlen(L)+1，插入后原表长增1。 (6) 删除元素Delelem(L,i) 在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号i, i+1,...,n-1，要求1≤i≤Getlen(L)， 删除后表长减１。
typedef int ElemType //在实际应用中，将ElemType定义成实际类型 typedef struct{ ElemType data[MaxLen]; //定义存储表中元素的数组 int length; //线性表的实际长度 }sqList; sqList L; //定义表结构的变量
E in
2012-9-12

i 1
n 1
p i ( n i 1)
1 n 1

i 1
n 1
( n i 1)
n 2
18
由此可以看出，在线性表上做插入操作需要移动表中一 半的数据元素，当n较大时，算法的效率是比较低的，所以 在线性表上进行插入操作的时间复杂度为Ｏ(n)。 6．顺序表的删除运算Delelem(L,i)的实现 顺序表的删除运算是指将表中第 i 个元素从线性表中去
i+1。
线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实现则 是在存储结构上进行的。
2012-9-12

同理可证:顺序表删除一元素的时间效率为: 同理可证:顺序表删除一元素的时间效率为: T（n)=(n-1)/2 ≈O(n) O(n) （
插入效 E = ∑ is 率： i=0
n
1 n n pi ( n − i ) = ∑ (n − i) = 2 n + 1 i=0
n −1 删除效 1 n −1 n −1 Edl = ∑ qi (n − i ) = ∑ (n − i ) = 率： n i =0 2 i =0
2.2 线性表的顺序表示和实现
顺序存储结构的线性表称作顺序表 1.顺序表的存储结构 顺序表的存储结构
实现顺序存储结构的方法是使用数组。数组把线性表 实现顺序存储结构的方法是使用数组。 使用数组 的数据元素存储在一块连续地址空间的内存单元中， 连续地址空间的内存单元中 的数据元素存储在一块连续地址空间的内存单元中，这样 线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。 线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。 数据元素间的逻辑上的前驱、 数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据 元素的存储单元的物理前后位置上。 元素的存储单元的物理前后位置上。 顺序表的存储结构如图所示
2.线性表抽象数据类型 2.线性表抽象数据类型
数据集合:｛ 的数据类型为DataType 数据集合 ｛ a0, a1, … , an-1 ｝, ai的数据类型为 (1) ListInitiate(L) 初始化线性表 (2) ListLength(L) 求当前数据元素个数 操作集合: 操作集合 (3) ListInsert(L,i,x) 插入数据元素 (4) ListDelete(L,i,x) 删除数据元素 (5) ListGet(L,i,x) 取数据元素
printf("参数 不合法 \n"); 参数i不合法 参数 不合法! return 0;

数据结构（C语言版）（第二版）（目录）第1章导论
1 算法和数据结构
2 什么是数据结构
3 符号，引理，定理与证明
4 说明文篇
5 C语言和程序设计
6 总结
第2章算法分析
1 算法的衡量标准
2 时间和空间复杂度分析
3 运行时复杂度分析
4 递归分析
第3章线性表
1 一维数组
2 线性表
3 顺序表
4 链表
5 循环链表
6 树表
7 双向链表
第4章栈
1 栈的定义
2 栈的抽象数据类型
3 栈的基本操作
4 栈的应用——后缀表达式的求算
第7章树
1 树的定义
2 树的抽象数据类型
3 树的存储
4 树的遍历
5 二叉树
6 二叉排序树（搜索树）
7 平衡二叉树
8 哈夫曼树
9 图的存储
第8章查找
1 静态查找
2 哈希表
3 动态单值查找
第10章数据结构综合应用
1 树的遍历
2 贪心法
3 回溯法
4 分析与评价
附录 A C语言库
1 算法入口及时区函数
2 内存处理函数
3 字符串处理函数
4 文件处理函数
附录 B 内存分配方式。