nullnull2.1 线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
的类型定义2.3 线性表链式表示和实现2.4 一元多项式的表示2.2 线性表顺序表示和实现
第二章 线性表null线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个 “最后元素” ；3．除最后元素在外，均有 唯一的后继；4．除第一元素之外，均有 唯一的前驱。 线性结构 是
一个数据元素的有序（次序）集线性表是一种最简单的线性结构null2.1
线性表的类型定义null抽象数据类型线性表的定义如下：ADT List { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
{称 n 为线性表的表长;
称 n=0 时的线性表为空表。}数据关系：R1＝{
|ai-1 ,ai∈D, i=2,...,n }{设线性表为 (a1，a2, . . . ，ai，. . . ，an),
称 i 为 ai 在线性表中的位序。}
null 基本操作： 结构创建/构造型操作结构销毁型操作 观察/
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
型操作 变换/加工型操作 } ADT Listnull InitList( &L )
操作结果：构造一个空的线性表L。结构创建/构造操作null 结构销毁操作DestroyList( &L )初始条件：
操作结果：线性表 L 已存在。销毁线性表 L。nullListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( ))观察/报告型操作:null ListEmpty( L )
初始条件：
操作结果：线性表L已存在。若L为空表，则返回
TRUE，否则FALSE。（线性表判空）nullListLength( L )初始条件：
操作结果：线性表L已存在。
返回L中元素个数。（求线性表的长度）null PriorElem( L, cur_e, &pre_e )
初始条件：
操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）nullNextElem( L, cur_e, &next_e )初始条件：
操作结果：线性表L已存在。
若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）nullGetElem( L, i, &e ) 初始条件：
操作结果：线性表L已存在，
且 1≤i≤LengthList(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）nullLocateElem( L, e, compare( ) )初始条件：
操作结果：线性表L已存在，e为给定值，
compare( )是元素判定函数。返回L中第1个与e满足关系
compare( )的元素的位序。
若这样的元素不存在，
则返回值为0。（定位函数）null ListTraverse(L, visit( ))初始条件：
操作结果：线性表L已存在，
Visit() 为某个访问函数。依次对L的每个元素调用
函数visit( )。一旦visit( )失败，则操作失败。（遍历线性表）null加工/变换型操作 ClearList( &L )ListInsert( &L, i, e )
ListDelete(&L, i, &e) nullClearList( &L )初始条件：
操作结果：线性表L已存在。将L重置为空表。
（线性表置空）nullnull ListInsert( &L, i, e )初始条件：
操作结果：线性表L已存在，
且 1≤i≤LengthList(L)+1 。在L的第i个元素之前插入
新的元素e，L的长度增1。（插入数据元素）nullListDelete(&L, i, &e）初始条件：
操作结果：线性表L已存在且非空，
1≤i≤LengthList(L) 。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）null利用上述定义的线性表
可以实现其它更复杂的操作例 2-1 例 2-2 null 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。
现要求一个新的集合A＝A∪B。例 2-1 上述问题可演绎为： 要求对线性表作如下操作：
扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。null1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访; 3．若不存在，则插入之。GetElem(LB, i)→e
LocateElem(LA, e, equal( ))
ListInsert(LA, n+1, e)
操作步骤：null GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e
if (!LocateElem(La, e, equal( )) )
ListInsert(La, ++La_len, e);
// La中不存在和 e 相同的数据元素，则插入之void union(List &La, List Lb) {
La_len = ListLength(La); // 求线性表的长度
Lb_len = ListLength(Lb); for (i = 1; i <= Lb_len; i++) {}} // union例算法 2-1null 已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。仍选用线性表表示集合。null集合 B集合 A从集合 B 取出物件放入集合 A
要求集合A中同样物件不能有两件以上因此，算法的策略应该和例2-1相同nullvoid union(List &La, List Lb) {
La_len=ListLength(La); Lb_len=ListLength(Lb);
} // union GetElem(Lb, i, e); // 取Lb中第 i 个数据元素赋给 e
if (!LocateElem(La, e, equal( )) )
ListInsert(La, ++La_len, e);
// La中不存在和 e 相同的数据元素，则插入之for (i = 1; i <= Lb_len; i++) {
}InitList(La); // 构造(空的)线性表LA例算法 2-1null若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即
ai≥ai-1 或 ai≤ai-1(i = 2,3,…, n)，则称该线性表为有序表(Ordered List)。试改变结构，以有序表表示集合。数据结构改变了，
解决问题的策略也相应要改变。nullvoid MergeList(List La, List Lb, List &Lc) {
// 将非递减的有序表 La 和 Lb 归并为有序表 Lc
} // merge_listwhile ((i <= La_len) && (j <= Lb_len))
{ // La 和 Lb 均不空 }
while (i<=La_len) // 若 La 不空
while (j<=Lb_len) // 若 Lb 不空InitList(Lc); // 构造空的线性表 Lc
i = j = 1; k = 0;
La_len = ListLength(La);
Lb_len = ListLength(Lb);例算法 2-2例 2-2 null while ((i <= La_len) && (j <= Lb_len))
// La 和 Lb 均非空，i = j = 1, k = 0
GetElem(La, i, ai); // 取表La中第i个数据元素的值赋给ai GetElem(Lb, j, bj);
if (ai <= bj) { // 将 ai 插入到 Lc 中
ListInsert(Lc, ++k, ai); ++i; }
else { // 将 bj 插入到 Lc 中
ListInsert(Lc, ++k, bj); ++j; }null while (i <= La_len) { // 当La不空时
GetElem(La, i++, ai);
ListInsert(Lc, ++k, ai);
} // 插入 La 表中剩余元素 while (j <= Lb_len) { // 当Lb不空时
GetElem(Lb, j++, bj);
ListInsert(Lc, ++k, bj);
} // 插入 Lb 表中剩余元素nullvoid MergeList(List La,List Lb,List &Lc) // 算法2.2
{ // 已知线性表La和Lb中的数据元素按值非递减排列。
// 归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列(不改变表La和表Lb)
int i=1,j=1,k=0;
int La_len,Lb_len;
ElemType ai,bj;
InitList(Lc); // 创建空表Lc
La_len=ListLength(La); // 求线性表La的长度
Lb_len=ListLength(Lb); // 求线性表Lb的长度
while(i<=La_len&&j<=Lb_len) // i、j分别指示表La和表Lb中的元素序号
{ GetElem(La,i,ai); // 取表La中第i个数据元素的值赋给ai
GetElem(Lb,j,bj); // 取表Lb中第j个数据元素的值赋给bj
if(ai<=bj) // 表La的当前元素不大于表Lb的当前元素
{ ListInsert(Lc,++k,ai); // 在表Lc的最后插入元素ai
++i; // i指示表La中的下一个元素
}
else
{ ListInsert(Lc,++k,bj); // 在表Lc的最后插入元素bj
++j; // j指示表Lb中的下一个元素
}
} // 以下两个while循环只会有一个被执行
while(i<=La_len) // 表La中还有元素未插入到表Lc
{ GetElem(La,i++,ai); // 取表La中第i个数据元素的值赋给ai，i指示表La中的下一个元素
ListInsert(Lc,++k,ai); // 在表Lc的最后插入元素ai
}
while(j<=Lb_len) // 表Lb中还有元素未插入到表Lc
{ GetElem(Lb,j++,bj); // 取表Lb中第j个数据元素的值赋给bj，j指示表Lb中的下一个元素
ListInsert(Lc,++k,bj); // 在表Lc的最后插入元素bj
}
}nullnull 用一组地址连续的存储单元
依次存放线性表中的数据元素 a1 a2 … ai-1 ai … an
线性表的起始地址
称作线性表的基地址
线性表的顺序表示：null基本特点：
(1)占用的存储空间是连续的；
(2) 各数据元素在存储空间中是按逻辑顺序依次存放的。线性表的顺序存储结构：线性表中第i个元素ai在计算机存储空间中的存储地址为
LOC(ai) = LOC(a1) + (i-1)×ll:一个数据元素所占存储量
LOC(a1):基地址线性表的顺序存储结构是一种随机存取的存储结构。null顺序表示的 C 语言描述typedef struct {
} SqList; // 俗称 顺序表#define LIST_INIT_SIZE 100
// 线性表存储空间的初始分配量
#define LISTINCREMENT 10
// 线性表存储空间的分配增量ElemType *elem; // 存储空间基址int length; // 当前长度int listsize; // 当前分配的存储容量
// (以sizeof(ElemType)为单位)动态一维数组表示null线性表的基本操作在顺序表中的实现InitList(&L) // 结构初始化LocateElem(L, e, compare()) // 查找ListInsert(&L, i, e) // 插入元素ListDelete(&L, i) // 删除元素nullStatus InitList_Sq( SqList& L ) {
// 构造一个空的线性表
} // InitList_Sq算法时间复杂度：O(1)L.elem = (ElemType*) malloc (LIST_
INIT_SIZEsizeof (ElemType));
if (!L.elem) exit(OVERFLOW);L.length = 0;
L.listsize = LIST_INIT_SIZE
return OK;动态一维数组表示null例如：顺序表e =38i12341850可见，基本操作是：
将顺序表中的元素
逐个和给定值 e
相比较。null int LocateElem_Sq(SqList L, ElemType e,
Status (*compare)(ElemType, ElemType)) {
// 在顺序表中查询第一个满足判定条件的数据元素，
// 若存在，则返回它的位序，否则返回 0
} // LocateElem_Sq O( ListLength(L) )算法的时间复杂度为：i = 1; // i 的初值为第 1 元素的位序
p = L.elem; // p 的初值为第 1 元素的存储位置while (i <= L.length &&
!(*compare)(*p++, e)) ++i;if (i <= L.length) return i;
else return 0;(*compare)(*p++, e)null线性表操作
ListInsert(&L, i, e)的实现：首先分析:插入元素时，
线性表的逻辑结构发生什么变化？
null (a1, …, ai-1, ai, …, an) 改变为
(a1, …, ai-1, e, ai, …, an), null Status ListInsert_Sq(SqList &L, int i, ElemType e) {
// 在顺序表L的第 i 个元素之前插入新的元素e,
// i 的合法范围为 1≤i≤L.length+1
} // ListInsert_Sq 算法时间复杂度为:O( ListLength(L) )q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入e
++L.length; // 表长增1
return OK;……元素右移null考虑移动元素的平均情况: 若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：nullif (L.length >= L.listsize) {
// 当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) exit(OVERFLOW);
// 存储分配失败
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}if (i < 1 || i > L.length+1) return ERROR;
// 插入位置不合法null例如：ListInsert_Sq(L, 5, 66) L.length-1087564266q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;null线性表操作
ListDelete(&L, i, &e)的实现：首先分析：删除元素时，
线性表的逻辑结构发生什么变化？null (a1, …, ai-1, ai, ai+1, …, an) 改变为
(a1, …, ai-1, ai+1, …, an)ai+1…an, 表的长度减少nullStatus ListDelete_Sq
(SqList &L, int i, ElemType &e) {
} // ListDelete_Sqfor (++p; p <= q; ++p) *(p-1) = *p;
// 被删除元素之后的元素左移
--L.length; // 表长减1
return OK;算法时间复杂度为: O( ListLength(L))p = &(L.elem[i-1]); // p 为被删除元素的位置
e = *p; // 被删除元素的值赋给 e
q = L.elem+L.length-1; // 表尾元素的位置if ((i < 1) || (i > L.length)) return ERROR;
// 删除位置不合法元素左移null考虑移动元素的平均情况:若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：nullL.length-108756p = &(L.elem[i-1]);
q = L.elem+L.length-1;
for (++p; p <= q; ++p) *(p-1) = *p; 例如：ListDelete_Sq(L, 5, e) nullnull一、单链表二、结点和单链表的 C 语言描述三、线性表的操作在单链表中的实现四、一个带头结点的单链表类型五、静态链表思考：线性表的逻辑顺序与存储顺序 ？一致的。六、其它形式的链表null 用一组地址任意的存储单元存放线性表中的数据元素。一、单链表以元素(数据元素的映象)
+ 指针(指示后继元素存储位置)
= 结点
(表示数据元素 或 数据元素的映象)以“结点的序列”表示线性表 称作链表单链表的结点结构null头结点头指针头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，
头结点的指针域为空null Typedef struct LNode // 结点类型定义
{
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode, *LinkList; //LinkList为结构指针类型二、结点和单链表的 C 语言描述LinkList L； // L 为单链表的头指针null三、单链表操作的实现GetElem(L, i, e) // 取第i个数据元素ListInsert(&L, i, e) // 插入数据元素ListDelete(&L, i, e) // 删除数据元素ClearList(&L) // 重置线性表为空表CreateList(&L, n)
// 生成含 n 个数据元素的链表InitList(LinkList &L) //构造一个空的线性表Lnull 线性表的操作
GetElem(L, i, &e)
在单链表中的实现:j123null 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 I 。 单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 令指针 p 始终指向线性表中第 j 个数据元素。null Status GetElem_L(LinkList L, int i, ElemType &e) {
// L是带头结点的链表的头指针，以 e 返回第 i 个元素
} // GetElem_L算法时间复杂度为:O(ListLength(L))p = L->next; j = 1; // p指向第一个结点，j为计数器while (p && jnext; ++j; }
// 顺指针向后查找，直到 p 指向第 i 个元素
// 或 p 为空if ( !p || j>i )
return ERROR; // 第 i 个元素不存在
e = p->data; // 取得第 i 个元素
return OK;null 线性表的操作 ListInsert(&L, i, e)
在单链表中的实现： 有序对
改变为 和
null 因此，在单链表中第 i 个结点之前进行插入的基本操作为:
找到线性表中第i-1个结点，然后修改其指向后继的指针。 可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。null Status ListInsert_L(LinkList L, int i, ElemType e) {
// L 为带头结点的单链表的头指针，本算法
// 在链表中第i 个结点之前插入新的元素 e
} // LinstInsert_L算法的时间复杂度为:O(ListLength(L))……p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 寻找第 i-1 个结点
if (!p || j > i-1)
return ERROR; // i 大于表长或者小于1 nulls = (LinkList) malloc ( sizeof (LNode));
// 生成新结点
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;spnull线性表的操作ListDelete (&L, i, &e)在链表中的实现:有序对 和
改变为 null 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。q = p->next; p->next = q->next;
e = q->data; free(q);pqnull Status ListDelete_L(LinkList L, int i, ElemType &e) {
// 删除以 L 为头指针(带头结点)的单链表中第 i 个结点
} // ListDelete_L算法的时间复杂度为:O(ListLength(L))p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 寻找第 i 个结点，并令 p 指向其前趋
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; free(q);
return OK;null操作 ClearList(&L) 在链表中的实现:void ClearList(&L) {
// 将单链表重新置为一个空表
while (L->next) {
p=L->next; L->next=p->next;
}
} // ClearListfree(p);算法时间复杂度：O(ListLength(L))null如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。null例如：逆位序输入 n 个数据元素的值，
建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，
建立结点并插入；三、输入数据元素an-1，
建立结点并插入；ananan-1四、依次类推，直至输入a1为止。nullvoid CreateList_L(LinkList &L, int n) {
// 逆序输入 n 个数据元素，建立带头结点的单链表
} // CreateList_L算法的时间复杂度为:O(Listlength(L))L = (LinkList) malloc (sizeof (LNode));
L->next = NULL; // 先建立一个带头结点的单链表for (i = n; i > 0; --i) {
p = (LinkList) malloc (sizeof (LNode));
scanf(&p->data); // 输入元素值
p->next = L->next; L->next = p; // 插入
}思考：不带头结点的单链表如何操作？InitList_L(L) // 先建立一个带头结点的单链表null void MergeList(LinkList La,LinkList &Lb,LinkList &Lc) // 算法2.12
{ // 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。(销毁Lb，Lc即新的La)
LinkList pa=La->next,pb=Lb->next,pc; // pa、pb分别指向La、Lb的首元结点(待比较结点)
Lc=pc=La; // 用La的头结点作为Lc的头结点，pc指向La的头结点(Lc的尾结点)
while(pa&&pb) // La和Lb中的元素都未比较完
if(pa->data<=pb->data) // La的当前元素不大于Lb的当前元素
{ pc->next=pa; // 将pa所指结点归并到Lc中
pc=pa; // pc指向表Lc的最后一个结点
pa=pa->next; }// 表La的下一个结点成为待比较结点
else // Lb的当前元素小于La的当前元素
{ pc->next=pb; // 将pb所指结点归并到Lc中
pc=pb; // pc指向表Lc的最后一个结点
pb=pb->next; } // 表Lb的下一个结点成为待比较结点
pc->next=pa?pa:pb; // 插入剩余段
free(Lb); // 释放Lb的头结点
Lb=NULL; // Lb不再指向任何结点
}算法2.12与算法2.7比较null回顾 2.1 节中例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？nullvoid union(List &La, List Lb) {
La_len = ListLength(La); Lb_len =ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb, i, e);
if (!LocateElem(La, e, equal( ))
ListInsert(La, ++La_len, e);
}//for
} // union控制结构：
基本操作：for 循环
GetElem, LocateElem 和 ListInsert当以顺序映像实现抽象数据类型线性表时为:
O( ListLength(La)×ListLength(Lb) ) 当以链式映像实现抽象数据类型线性表时为:
O( ListLength(La)×ListLength(Lb) )例2-1算法时间复杂度null用上述定义的单链表实现线性表的操作时，
存在的问题： 改进链表的设置：1．单链表的表长是一个隐含的值； 1．增加“表长”、“表尾指针” 和 “当前位置的
指针” 三个数据域；2．在单链表的最后一个元素之后插入元素时，
需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的
“位置”概念加强。2．将基本操作中的“位序 i ”改变为“指针 p ”。null四、一个带头结点的线性链表类型typedef struct LNode { // 结点类型
ElemType data;
struct LNode *next;
} *Link, *Position;typedef struct { // 链表类型
Link head, tail; // 分别指向头结点和
// 最后一个结点的指针
int len; // 指示链表长度
Link current; // 指向当前被访问的结点
//的指针，初始位置指向头结点
} LinkList;
(p37)nullnull链表的基本操作:(p37){结构初始化和销毁结构}Status InitList( LinkList &L );
// 构造一个空的线性链表 L，其头指针、
// 尾指针和当前指针均指向头结点，
// 表长为零。Status DestroyList( LinkList &L );
// 销毁线性链表 L，L不再存在。 O(1) O(n)Status MakeNode( Link &p, ElemType e );
// 分配由 p 指向的值为e的结点，并返回OK，
// 若分配失败，则返回 ERRORvoid FreeNode( Link &p );
// 释放 p 所指结点 O(1) O(1)null{报告/观察型操作}Status ListEmpty ( LinkList L ); //判表空int ListLength( LinkList L ); // 求表长Status Prior( LinkList L );
// 改变当前指针指向其前驱Status Next ( LinkList L );
// 改变当前指针指向其后继ElemType GetCurElem ( LinkList L );
// 返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1)null Status LocatePos( LinkList L, int i );
// 改变当前指针指向第i个结点Status LocateElem (LinkList L, ElemType e,
Status (*compare)(ElemType, ElemType));
// 若存在与e 满足函数compare( )判定关系的元
// 素，则移动当前指针指向第1个满足条件的
// 元素的前驱，并返回OK; 否则返回ERRORStatus ListTraverse(LinkList L, Status(*visit)() );
// 依次对L的每个元素调用函数visit()O(n)O(n)O(n)null {变换/加工型操作}Status ClearList ( LinkList &L );
// 重置 L 为空表Status SetCurElem(LinkList &L, ElemType e );
// 更新当前指针所指数据元素Status Append ( LinkList &L, Link s );
// 在表尾结点之后链接一串结点Status InsAfter ( LinkList &L, Elemtype e );
// 将元素 e 插入在当前指针之后Status DelAfter ( LinkList &L, ElemType& e );
// 删除当前指针之后的结点 O(1)O(n) O(s) O(1) O(1)nullStatus InsAfter( LinkList& L, ElemType e ) {
// 若当前指针在链表中，则将数据元素e插入在线性链
// 表L中当前指针所指结点之后,并返回OK;
// 否则返回ERROR。
} // InsAfter if ( ! L.current ) return ERROR;
if (! MakeNode( s, e) ) return ERROR;
s->next = L.current->next;
L.current->next = s;
if (L.tail = L.current) L.tail = s;
L.current = s; return OK;nullStatus DelAfter( LinkList& L, ElemType& e ) {
// 若当前指针及其后继在链表中，则删除线性链表L中当前
// 指针所指结点之后的结点，并返回OK; 否则返回ERROR。
} //DelAfterif ( !(L.current && L.current->next ) )
return ERROR;
q = L.current->next;
L.current->next = q->next;
if (L.tail = q) L.tail = L.current;
e=q->data; FreeNode(q);
return OK;null 1. 双向链表五、其它形式的链表typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior;
// 指向前驱的指针域
struct DuLNode *next;
// 指向后继的指针域
} DuLNode, *DuLinkList;null 最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 … ... an
2. 循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。null双向循环链表空表非空表 a1 a2 … ... an
null双向链表的操作特点：“查询” 和单链表相同。“插入” 和“删除”时需要同时修改两个方向上的指针。nulls->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;ps插入null删除p->next = p->next->next;
p->next->prior = p;pnullnull在计算机中，可以用一个线性表来表示:
P = (p0, p1, …，pn)一元多项式但是对于形如
S(x) = 1 + 3x10000 – 2x20000
的多项式，上述表示
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
是否合适？null 一般情况下的一元稀疏多项式可写成
Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem
其中：pi 是指数为ei 的项的非零系数，
0≤ e1 < e2 < ┄ < em = n可以下列线性表表示：
（（p1, e1）, (p2, e2), ┄, (pm,em) ）nullADT Polynomial {
数据对象：
数据关系：抽象数据类型一元多项式的定义如下：D＝{ ai | ai ∈TermSet, i=1,2,...,m, m≥0
TermSet 中的每个元素包含一个
表示系数的实数和表示指数的整数 }R1＝{ |ai-1 ,ai∈D, i=2,...,n
且ai-1中的指数值＜ai中的指数值 }null CreatPolyn ( &P, m )
DestroyPolyn ( &P )
PrintPolyn ( &P ) 基本操作：操作结果：输入 m 项的系数和指数，
建立一元多项式 P。初始条件：一元多项式 P 已存在。
操作结果：销毁一元多项式 P。初始条件：一元多项式 P 已存在。
操作结果：打印输出一元多项式 P。null PolynLength( P )
AddPolyn ( &Pa, &Pb )
SubtractPolyn ( &Pa, &Pb )
… …
} ADT Polynomial初始条件：一元多项式 P 已存在。
操作结果：返回一元多项式 P 中的项数。初始条件：一元多项式 Pa 和 Pb 已存在。
操作结果：完成多项式相加运算，即：
Pa = Pa＋Pb，并销毁一元多项式 Pb。null一元多项式的实现：typedef struct { // 项的表示
float coef; // 系数
int expn; // 指数
} term, ElemType; typedef OrderedLinkList polynomial;
// 用带表头结点的有序链表表示多项式结点的数据元素类型定义为:null例如:多项式的单链表表示法 A（x）=7+3x+9x8+5x17 B(x)=8x+22x7-9x8多项式相加得到的多项式和 nullStatus CreatPolyn ( polynomail &P, int m ) {
// 输入m项的系数和指数，建立表示一元多项式的有序链表P
} // CreatPolynInitList (P); e.coef = 0.0; e.expn = -1;
SetCurElem (h, e); // 设置头结点的数据元素for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项
}
return OK;scanf (e.coef, e.expn);
if (!LocateElem ( P, e, (*cmp)()) )
if ( !InsAfter ( P, e ) ) return ERROR; 注意: 1.输入次序不限;
2.指数相同的项只能输入一次。nullStatus AddPolyn ( polynomial &Pc,
polynomial &Pa, polynomial &Pb) {
// 利用两个多项式的结点构成“和多项式” Pc = Pa＋Pb
… …
if (DelAfter(Pa, e1)) a=e1.expn else a=MAXE;
if (DelAfter(Pb, e2)) b=e2.expn else b=MAXE;
while (!(a=MAXE && b=MAXE)) {
… …
}
… …
} // AddPolynnullswitch (*cmp(e1, e2)) {
case -1: { // 多项式PA中当前结点的指数值小
… … break; }
case 0: { // 两者的指数值相等
e1.coef= a.coef + b.coef ;
if ( a.coef != 0.0 ) InsAfter(Pc, e1);
… … break;
}
case 1: { //多项式PB中当前结点的指数值小
… … break; }
}
null // func2-2.cpp 几个常用的函数
Status equal(ElemType c1,ElemType c2)
{ // 判断是否相等的函数
if(c1==c2)
return TRUE;
else
return FALSE;
}
int comp(ElemType a,ElemType b)
{ // 根据a<、=或>b，分别返回-1、0或1
if(a==b)
return 0;
else
return (a-b)/abs(a-b);
}null 顺序存储结构可以借助于高级程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
语言中的一堆数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言定义如下： ＃define MAXSIZE=线性表可能达到的最大长度
typedef struct
{
ElemType elem［MAXSIZE］； /* 线性表占用的数组空间 */
int last； /* 记录线性表中最后一个元素在数组elem［ ］中
的位置（下标值）， 空表置为-1 */
} SeqList； 线性表顺序存储结构（静态一维数组）表示null调用InitList (L)void InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
L=(LinkList)malloc(sizeof(LNode)); // 产生头结点，并使L指向此头结点
if(!L) // 存储分配失败
exit(OVERFLOW);
L->next=NULL; // 头结点的指针域为空
}构造一个空的线性表Lnull void MergeList(LinkList La,LinkList &Lb,LinkList &Lc) // 算法2.12
{ // 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。(销毁Lb，Lc即新的La)
LinkList pa=La->next,pb=Lb->next,pc; // pa、pb分别指向La、Lb的首元结点(待比较结点)
Lc=pc=La; // 用La的头结点作为Lc的头结点，pc指向La的头结点(Lc的尾结点)
while(pa&&pb) // La和Lb中的元素都未比较完
if(pa->data<=pb->data) // La的当前元素不大于Lb的当前元素
{ pc->next=pa; // 将pa所指结点归并到Lc中
pc=pa; // pc指向表Lc的最后一个结点
pa=pa->next; }// 表La的下一个结点成为待比较结点
else // Lb的当前元素小于La的当前元素
{ pc->next=pb; /
浙公网安备 33021202002483