数据结构第二章 线性表part9

1、 2-2 已知一个顺序表中的元素按元素值非递减已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同有序排列，编写一个函数删除表中多余的值相同的元素。的元素。算法思想：算法思想： 由于顺序表中的元素按元素值非递减有序排由于顺序表中的元素按元素值非递减有序排列，值相同的元素必为相邻的元素。列，值相同的元素必为相邻的元素。 因此，依次比较相邻两个元素，若值相等，因此，依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找。则删除其中一个，否则继续向后查找。实现本题功能的函数如下：实现本题功能的函数如下：void del (SqList A, int n) / 表长

2、为表长为n int i=0, j; while (in-2) if (Ai!=Ai+1) i+ ; / 元素值不相等，继续向下找元素值不相等，继续向下找 else for (j=(i+2);j=n;j+) Aj-1=Aj; / 删除第删除第i+1个元素个元素 n-; / 表长减表长减1 2-3 已知一个顺序表已知一个顺序表A中有中有n个元素，且任何元个元素，且任何元素均不为素均不为0，将，将A拆成两个线性表拆成两个线性表B和和C，使，使A中大中大于于0 的元素存放在的元素存放在B中，小于中，小于0的元素存放在的元素存放在C中。中。算法思想：算法思想： 依次遍厉依次遍厉A的元素，判断当前的元素值

3、，大的元素，判断当前的元素值，大于于0 者赋给者赋给B（假设有（假设有p个元素），小于个元素），小于0 者赋给者赋给C（假设有（假设有q个元素）。个元素）。实现本题功能的函数如下：实现本题功能的函数如下：void ret (SqList A, int n, SqList B, int p, SqList C, int q) int i; p=0;q=0; for (i=0;i0 p+; Bp=Ai; if (Ai0) q+; Cq=Ai; 2-4 已知在一维数组已知在一维数组A1,m+n中依次存放着两中依次存放着两个顺序表个顺序表 ( a1,a2,am) 和和 (b1,b2,bn)，编写一，编

4、写一个 函 数 将 两 个 线 性 表 的 位 置 互 换 ， 即 把个 函 数 将 两 个 线 性 表 的 位 置 互 换 ， 即 把(b1,b2,bn)放到（放到（a1,a2,am)的前面。的前面。算法思想：算法思想： 由于顺序表的插入与删除操作需要移动大量的由于顺序表的插入与删除操作需要移动大量的元素，所用时间多，这里采用先将：元素，所用时间多，这里采用先将： A: ( a1,a2,am,b1,b2,bn)的所有元素逆置，即使之变为：的所有元素逆置，即使之变为： A:(bn, b2 , b1 ,am, , a2, a1)然后将然后将(bn, b2 , b1 )逆置为逆置为(b1,b2,b

5、n),将将(am, , a2, a1)逆置为逆置为( a1,a2,am )，便得到最终结果：便得到最终结果： A: (b1,b2,bn, a1,a2,am )先编写一个逆置的函数如下，其功能是逆置先编写一个逆置的函数如下，其功能是逆置A中的中的Al到到Ah部分。部分。逆置的函数如下：逆置的函数如下：void invert (SqList A, int l, int h) int i,x; for (i=l;i=(l+h)/2;i+) x=Ai;Ai=Al+h-i;Al+h-i=x; /将将Ai与与Al+h-i元素互换元素互换 实现本题功能的函数如下：实现本题功能的函数如下：void excha

6、ng (SqList A, int m, int n) invert(A, 0, m+n-1); invert(A,0,n-1); invert(A,n,m+n-1); 2-5 编写一个函数用不多于编写一个函数用不多于3n2的平均比较次的平均比较次数，在一个顺序表中找出最大和最小值的元素。数，在一个顺序表中找出最大和最小值的元素。算法思想：算法思想： 如果在查找出最大和最小值的元素时各扫描如果在查找出最大和最小值的元素时各扫描一遍所有元素，则至少要比较一遍所有元素，则至少要比较2n次，为此，使用次，为此，使用一躺扫描找出最大和最小值的元素。一躺扫描找出最大和最小值的元素。实现本题功能的函数如下

7、：实现本题功能的函数如下：void maxmin (SqList A, int n) int max,min,i; max=A0;min=A0; for (i=1;imax) max=Ai; else if (Aimax）条件均不成立，）条件均不成立，这时比较的次数为这时比较的次数为n-1，另外，每次都要比较，另外，每次都要比较Aimax）条件均成立，不会再执行）条件均成立，不会再执行else的的比较，所以总的比较次数为：比较，所以总的比较次数为： n-1 平均比较次数为：平均比较次数为： (2(n-1)+n-1) /2=3n /2-3/2 所以该函数的平均比较次数不多于所以该函数的平均比较次

8、数不多于3n/2 2-6 有一个单链表（不同结点的数据域值可能相有一个单链表（不同结点的数据域值可能相同），其头指针为同），其头指针为head，编写一个函数计算数据，编写一个函数计算数据域为域为 x 的结点个数。的结点个数。算法思想：算法思想： 本题是通过遍历该链表的每个结点，每遇到本题是通过遍历该链表的每个结点，每遇到一个数据域为一个数据域为x的结点，结点个数加的结点，结点个数加1，结点个数，结点个数存储在变量存储在变量n中。中。实现本题功能的函数如下：实现本题功能的函数如下：int count ( LinkList head) LNode *p; int n=0; p=head; whil

9、e (p!=NULL) if (p-data=x) n+; p=p-next; return(n); 2-7 已知一个单链表如图所示，编写一个函数将已知一个单链表如图所示，编写一个函数将该单链表复制一个拷贝。该单链表复制一个拷贝。算法思想：算法思想： 依次查找该单链表（其头指针为依次查找该单链表（其头指针为head1）中的）中的每个结点，对每个结点复制一个新结点并链接到每个结点，对每个结点复制一个新结点并链接到新的单链表（其头指针为新的单链表（其头指针为head2）中。）中。 a1 ai . an head实现本题功能的函数如下：实现本题功能的函数如下：void copy ( LinkList

10、 head1, LinkList head2) LNode *p,*q; head2=(Lnode *)malloc(sizeof(Lnode); /建立头结点建立头结点 q=head2;p=head1; while (p!=NULL) s=(Lnode *)malloc(sizeof(Lnode); /复制一个新结点复制一个新结点 s-data=p-data; q-next=s; /把把s链接到链接到q之后之后 q=s; p=p-next; q-next=NULL; /将最后一个结点的将最后一个结点的next域置为域置为NULL p=head2; /删除头结点删除头结点 head2=head

11、2-next; free(p); 2-8 有一个单链表（至少有一个结点），其头指有一个单链表（至少有一个结点），其头指针为针为head，编写一个函数将，编写一个函数将L逆置，即最后一个结逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。二个结点，如此等等。算法思想：算法思想： 从头到尾扫描单链表从头到尾扫描单链表L，将第一个结点的，将第一个结点的next域置为域置为NULL，将第二个结点的，将第二个结点的next域指向第一个域指向第一个结点，将第三个结点的结点，将第三个结点的next域指向第二个结点，域指向第二个结点，如此

12、等等，直到最后一个结点，便用如此等等，直到最后一个结点，便用head指向它，指向它，这样达到了本题的要求。这样达到了本题的要求。实现本题功能的函数如下：实现本题功能的函数如下：Void invert ( LinkList head) LNode *p,*q,*r; p=head; q=p-next; while (q!=NULL) /当当L没有后续结点时终止没有后续结点时终止 r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; / p指向指向L的最后一个结点，现改为头结点的最后一个结点，现改为头结点 2-9 已知一个循环单链表如图所示，编

13、写一个函已知一个循环单链表如图所示，编写一个函数将所有箭头方向取反。数将所有箭头方向取反。算法思想：算法思想： 从头到尾扫描循环单链表从头到尾扫描循环单链表L，将第一个结点的，将第一个结点的next域域置为置为NULL，将第二个结点的，将第二个结点的next域指向第一个结点，将域指向第一个结点，将第三个结点的第三个结点的next域指向第二个结点，如此等等，直到最域指向第二个结点，如此等等，直到最后一个结点，便用后一个结点，便用head指向它，这样达到了本题的要求。指向它，这样达到了本题的要求。因为不是普通单链表，所以判定最后一个结点时不能用因为不是普通单链表，所以判定最后一个结点时不能用p-n

14、ext=NULL作为条件，而是用作为条件，而是用q指向第一个结点，以指向第一个结点，以p!=q作为条件。作为条件。heada1a2an实现本题功能的函数如下：实现本题功能的函数如下：void invert ( LinkList head) LNode *p,*q,*r; p=head; q=p-next; /指向数据为指向数据为a1的结点的结点 while (p!=q) /p不是第一个结点时循环不是第一个结点时循环 r=head; while (r-next!=p) r=r-next; p-next=r; /结点的结点的next逆向逆向 p=p-next; q-next=head; / 数据域

15、为数据域为a1的结点的结点next指向指向head所指的结点所指的结点 2-10 有一个有序单链表（从小到大排列），其有一个有序单链表（从小到大排列），其头指针为头指针为head，编写一个函数向该链表中插入一，编写一个函数向该链表中插入一个元素为个元素为x的结点，使插入后该链表仍然有序。的结点，使插入后该链表仍然有序。算法思想：算法思想： 先建立一个待插入的结点，然后依次与链表先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。的位置，最后插入该结点。实现本题功能的函数如下：实现本题功能的函数如下：L

16、node *insertorder ( LinkList head, int x) LNode *s ,*p,*q; s=(Lnode *)malloc(sizeof(Lnode); /建立一个待插入的结点建立一个待插入的结点 s-data=x;s-next=NULL; if (head=NULL | xdata /若单链表为空或若单链表为空或x小于第一个结点的小于第一个结点的data域域 s-next=head; head=s; else q=head; / 为为s结点寻找插入插入位置，结点寻找插入插入位置， / p指向待比较的结点，指向待比较的结点，q指向指向p的前驱的前驱 p=q-nex

17、t; while (p!=NULL & xp-data) /若若x小于小于p所指结点的所指结点的data域值，则退出域值，则退出while循环循环 if (xp-data) q=p; p=p-next; s-next=p; /将将s结点插入到结点插入到q和和p之间之间 q-next=s; return(head); 2-11 有两个循环单链表，链表头指针分别为有两个循环单链表，链表头指针分别为head1和和head2，编写一个函数将链表，编写一个函数将链表head1链接到链接到head2之后，链之后，链接后的链表仍保持是循环链表形式。接后的链表仍保持是循环链表形式。算法思想：算法思想：

18、 先找到两链表的尾指针，将第一个链表的尾指针与第二先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的第一个结点链接起来，再使之成为循环的。个链表的第一个结点链接起来，再使之成为循环的。a1a2ana1a2anhead1head2实现本题功能的函数如下：实现本题功能的函数如下：LNode *link ( LinkList head1, LinkList head2) LNode *p,*q; p=head1; /找到找到head1的表尾，用的表尾，用p指向它指向它 while (p-next!=head1) p=p-next; q=head2; /找到找到head2的表尾，用的表尾，用q指

19、向它指向它 while (q-next!=head2) q=q-next; p-next=head2; /将将head2链表链接到链表链接到head1链表之后链表之后 q-next=head1; /仍保持是循环链表仍保持是循环链表 return (head1); / 数据域为数据域为an的结点的结点next指向指向head所指的结点所指的结点 2-12 某百货公司仓库中有一批电视机，按其价格从高某百货公司仓库中有一批电视机，按其价格从高到低的次序构成一个循环单链表，每个结点有价格，数量到低的次序构成一个循环单链表，每个结点有价格，数量和链指针三个域，现新到和链指针三个域，现新到m台价格为台价格为h的电视机，编写一个的电视机，编写一个函数修改原循环链表。函数修改原循环链表。算法思想：算法思想： 先建立一个待插入的结点，然后在循环单链表中找到先建立一个待插入的结点，然后在循环单链表中找到插入的位置，再把该结点插入。插入的位置，再把该结点插入。依题意建立如下链表结构：依题意建立如下链表结构： struct list float price; / 价格域价格域 int number; / 数量域数量域 struct list *