数据结构第04讲_一元多项式与线性表习题_C.ppt

用链表实现线性表的操作时，存在的问题： 1．表长是一个隐含的值； 2．插入元素时，可能需遍历整个链表； 3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。 改进链表结构： Typedef struct LNode //结点类型 ElemType data; struct LNode *next; *Link, *Position; Typedef struct LNode //链表类型 Link head, tail; int len; LinkList ; 基本操作…… 抽象数据类型一元多项式的定义 基本操作： CreatPolyn P, m DestroyPolyn P PrintPolyn P PolynLength P AddPolyn Pa, Pb SubtractPolyn Pa, Pb MultiplyPolyn Pa, Pb ADT Polynomial 在实际的应用程序中取用顺序结构存储一元多项式，还是链式存储结构存储多项式，要视多项式作何种运算而定，若只对多项式进行“求值”等不改变多项式的系数和指数的运算，则采用类似于顺序表的顺序存储结构即可，否则应采用链式存储表示。 例：设两个一元多项式为: A X 4 + 6X4 + 5X8 + 4X12 B X 2X3 - 5X8 + 3X12 + 7X15 求此两一元多项式之和: C x A x +B x 二、算法设计题 1.有一个有 n 个结点的单链表，设计一个函数将第 i-1 个结点与第 i 个结点互换，但指针不变。 2.已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为 x 的结点，使插入后该链表仍然递增有序。 3.有一个单链表 L（至少有一个结点），其头结点指针为head ，编写一个函数将 L 逆置，即最后一个结点变成第 1 个结点，原来倒数第 2 个结点变成第 2个结点…如此等等。 4.试编写一个在循环双向链表中进行删除操作的算法，要求删除的结点是指定结点 p 的前趋结点。 8.对以下单链表分别执行下列各程序段，画出结果示意图。 1 R- data P- next- data; 2 8 7 7 5 ^ P R H H 2 8 3 7 5 ^ P R 2 T P; while T! NULL T- data T- data *2; T T- next; H 2 ^ P 10 14 6 16 H 2 8 3 7 5 ^ P 3 T P; while T- next! NULL T- data T- data *2; T T- next; H 2 8 3 7 5 ^ P H 2 ^ P 10 14 6 8 4 P LNode* malloc sizeof LNode ; P- data 10; R- next P; P- next S; H S 2 8 3 7 5 ^ P R 4 P LNode* malloc sizeof LNode ; P- data 10; R- next P; P- next S; P H S 2 8 3 7 5 ^ P R H S 2 8 3 7 5 ^ R P 10 H S 2 8 3 7 5 ^ R H S 2 8 3 7 5 ^ P R 4 P LNode* malloc sizeof LNode ; P- data 10; R- next P; P- next S; 4 P LNode* malloc sizeof LNode ; P- data 10; R- next P; P- next S; P 10 H S 2 8 3 7 5 ^ P R H S 2 8 3 7 5 ^ R 4 P LNode* malloc sizeof LNode ; P- data 10; R- next P; P- next S; P 10 H S 2 8 3 7 5 ^ P R H S 2 8 3 7 5 ^ R 5 T H; T- next P- next; free P ; H 2 8 3 7 ^ P T 5 H 2 8 3 7 5 ^ P 6 S- next H; H S 2 8 3 7 5 如果 S- next H 则S所指向的结点为尾结点. H S 2 8 3 7 5 ^ 第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 2.3.3 双向链表 每个结点中设置两个指针，一个指向后继，一个指向前驱。