西安电子科技大学出版社：算法与数据结构-C语言描述（樊希平）：第2章

第2章 线性表要求：
掌握线性表的逻辑结构；
线性表的顺序存储表示及其算法；
线性表的链式存储表示及其算法；
教材习题参考解答：
2.1 略
2.2 (1)n/2与(n-1)/2 n
(2)也(一定) 不一定
(3)L L->next 上一元素结点的指针域指示。
2.3 a 4,1 b 7,11,8,4,1 c 5,12 d 11,9,6,1或11,9,13,1或11,9,1,6
2.4 /*P49 习题2.4示例程序 */
#define Maxsize 100
typedef int ElemType;
typedef struct
{
ElemType elem[Maxsize];
int last;
}SqList;
int InsertList(SqList *pL,ElemType x)
{
int k;
if(pL->last>=Maxsize-1)
return (0);
k=pL->last;
/*k>=0保证线形表不为空,pL->elem[k]>x保证插入位置正确*/
while((k>=0) && (pL->elem[k] > x))
{
pL->elem[k+1]=pL->elem[k];
k--;
}
pL->elem[k+1]=x;
pL->last++;
return (1);
}
void main()
{
int i;
ElemType e;
SqList L; /*定义线形表变量*/
L.last=-1; /*置线形表为空表状态*/
/*任意输入10个整数*/
for(i=0;i<10;i++)
{
scanf("%d",&e);
InsertList(&L,e);
}
/*将结果输出*/
for(i=0;i<=L.last;i++)
printf("%d\t",L.elem[i]);
printf("\n");
}
2.5 /*P49 习题2.5示例程序 */
#include <stdio.h>
#define Maxsize 100
typedef int ElemType;
typedef struct
{
ElemType elem[Maxsize];
int last;
}SqList;
int DelElem(SqList *pL,int i,int k)
{
int j;
/*判断i和k的值的合法性*/
if(i<=0||i+k>pL->last+1)
return(0);
for(j=i+k-1;j<=pL->last;j++)
pL->elem[j-k]=pL->elem[j];
pL->last-=k;
return(1);
}
void Print(SqList *pL)
{
int i;
for(i=0;i<=pL->last;i++)
printf("%d\t",pL->elem[i]);
printf("\n");
}
void main()
{
int i,k;
SqList L; /*定义线形表变量*/
L.last=-1; /*置线形表为空表状态*/
/*向线形表中顺序存入1-20*/
for(i=0;i<20;i++)
L.elem[i]=i+1;
L.last=19;
Print(&L); /*将原结果输出*/
printf("请输入起始位置和删除元素的个数：");
scanf("%d %d",&i,&k);
/*将删除后结果输出*/
DelElem(&L,i,k);
Print(&L);
}
2.6 /*P49 习题2.6示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}Node,*LinkList;
/*初始化带头结点的单链表*/
void InitList(LinkList *pL)
{
*pL=(LinkList)malloc(sizeof(Node));
(*pL)->next=NULL;
}
/*头插法插入元素*/
void InsertList(LinkList L,ElemType e)
{
LinkList p;
p=(LinkList)malloc(sizeof(Node));
p->data=e;
p->next=L->next;
L->next=p;
}
void shanchu(LinkList L,int mink,int maxk)
{
LinkList p,q;
q = L;
p = L->next;
//让指针p指向第一个元素比mink大的结点，q指向p前面的结点
while(p != NULL && p->data <= mink)
{
q = p;
p = p->next;
}
//删除所有比mink大比maxk小的结点
while(p != NULL && p->data < maxk)
{
q->next = p->next;
free(p);
p = q->next;
}
}
void Print(LinkList L)
{
LinkList p;
for(p = L->next; p != NULL; p = p->next)
printf("%d\t",p->data);
printf("\n");
}
void main()
{
int i;
LinkList L;
InitList(&L); /*初始化链表*/
/*向线形表中顺序存入1-20*/
for(i=10; i>0; i--)
InsertList(L,i);
Print(L); /*将原结果输出*/
shanchu(L,6,9); //将大于6小于9地元素删除
Print(L); /*将逆置后结果输出*/
}
2.7 /*P49 习题2.71示例程序 */
/*采用顺序存储方法进行线形表的逆置*/
#include <stdio.h>
#define Maxsize 100
typedef int ElemType;
typedef struct
{
ElemType elem[Maxsize];
int last;
}SqList;
void Nizhi(SqList *pL)
{
ElemType temp;
int i,j;
i=0;
j=pL->last;
while(i<j)
{ /*交换i和j位置的元素*/
temp=pL->elem[i];
pL->elem[i]=pL->elem[j];
pL->elem[j]=temp;
i++;
j--;
}
}
void Print(SqList *pL)
{
int i;
for(i=0;i<=pL->last;i++)
printf("%d\t",pL->elem[i]);
printf("\n");
}
void main()
{
int i;
SqList L; /*定义线形表变量*/
L.last=-1; /*置线形表为空表状态*/
/*向线形表中顺序存入1-20*/
for(i=0;i<20;i++)
L.elem[i]=i+1;
L.last=19;
Print(&L); /*将原结果输出*/
Nizhi(&L);
Print(&L); /*将逆置后结果输出*/
}
/*P49 习题2.71示例程序 */
/*采用链式存储方法进行线形表的逆置*/
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}Node,*LinkList;
/*初始化带头结点的单链表*/
void InitList(LinkList *pL)
{
*pL=(LinkList)malloc(sizeof(Node));
(*pL)->next=NULL;
}
/*头插法插入元素*/
void InsertList(LinkList L,ElemType e)
{
LinkList p;
p=(LinkList)malloc(sizeof(Node));
p->data=e;
p->next=L->next;
L->next=p;
}
void Nizhi(LinkList L)
{
LinkList p,q,w;
p=L->next;
/*将原来的第一个结点变为最后一个*/
if(p != NULL)
{
q=p->next;
p->next=NULL;
}
while(q != NULL)
{
w=q->next;
q->next=p;
p=q;
q=w;
}
L->next=p;
}
void Print(LinkList L)
{
LinkList p;
for(p = L->next; p != NULL; p = p->next)
printf("%d\t",p->data);
printf("\n");
}
void main()
{
int i;
LinkList L;
InitList(&L); /*初始化链表*/
/*向线形表中顺序存入1-20*/
for(i=0;i<20;i++)
InsertList(L,i+1);
Print(L); /*将原结果输出*/
Nizhi(L);
Print(L); /*将逆置后结果输出*/
}
2.8 /*P49 习题2.8示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}Node,*LinkList;
/*初始化带头结点的单链表*/
void InitList(LinkList *pL)
{
*pL=(LinkList)malloc(sizeof(Node));
(*pL)->next=NULL;
}
/*向递增有序的线性表中插入元素，插入后仍递增有序*/
void InsertList(LinkList L,ElemType e)
{
LinkList p,q;
p=(LinkList)malloc(sizeof(Node));
p->data=e;
q = L;
while(q->next != NULL && q->next->data < e)
q = q->next;
p->next=q->next;
q->next=p;
}
//归并LA和LB到LC中
void Guibing(LinkList LA,LinkList LB,LinkList LC)
{
LinkList p,q,t;
p = LA->next;
q = LB->next;
while(p != NULL && q != NULL)
{
if(p->data < q->data)
{
t = p;
p = p->next;
}
else
{
t = q;
q = q->next;
}
t->next = LC->next;//将t所指结点插入LC头结点之后
LC->next = t;
}
LA->next = NULL;
LB->next = NULL;
}
void Print(LinkList L)
{
LinkList p;
for(p = L->next; p != NULL; p = p->next)
printf("%d\t",p->data);
printf("\n");
}
void main()
{
int i,e;
LinkList LA,LB,LC;
InitList(&LA); /*初始化链表*/
InitList(&LB);
InitList(&LC);
/*向线形表LA中按递增有序地插入5个数*/
for(i=0; i<5; i++)
{
printf("请输入第 %d 个数：",i+1);
scanf("%d",&e);
InsertList(LA,e);
}
Print(LA); /*将LA输出*/
/*向线形表LA中按递增有序地插入5个数*/
for(i=0; i<5; i++)
{
printf("请输入第 %d 个数：",i+1);
scanf("%d",&e);
InsertList(LB,e);
}
Print(LB); /*将LA输出*/
Guibing(LA,LB,LC); //将大于6小于9地元素删除
Print(LC); /*将逆置后结果输出*/
}
2.9 /*P49 习题2.8示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}Node,*LinkList;
/*向环行链表中插入元素*/
void InsertList(LinkList *pH,ElemType e)
{
LinkList p;
p=(LinkList)malloc(sizeof(Node));
p->data=e;
if(*pH == NULL)
{
p->next = p;
*pH = p;
}
else
{
p->next = (*pH)->next;
(*pH)->next = p;
}
}
//删除H所指结点的前一个结点
void Delete(LinkList H,int *pe)
{
LinkList p,t;
if(H->next == H) //若环行链表中只有一个结点，则返回
return;
for(p = H; p->next->next != H; p = p->next);
t = p->next;
p->next = t->next; //或者p->next = H
*pe = t->data;
free(t);
}
//将环行链表输出
void Print(LinkList H)
{
LinkList p;
if(H == NULL)
return;
for(p = H; p->next != H; p = p->next)
printf("%d\t",p->data);
printf("%d\n",p->data);
}
void main()
{
int i,e;
LinkList H;
H = NULL; //初始化无头结点的环行链表
/*向环行表H中输入5个数*/
for(i=0; i<5; i++)
{
printf("请输入第 %d 个数：",i+1);
scanf("%d",&e);
InsertList(&H,e);
}
Print(H); /*将环行链输出*/
Delete(H,&e); //删除H所指结点的前一个结点
Print(H); //将删除后的环链输出
printf("%d\n",e); //将所删除结点的元素输出
}
2.11 /*P50 习题2.11示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}Node,*LinkList;
/*初始化带头结点的单链表*/
void InitList(LinkList *pL)
{
*pL=(LinkList)malloc(sizeof(Node));
(*pL)->next=NULL;
}
//向带头结点的单链表中用尾插法插入元素
void Insert(LinkList L,ElemType e)
{
LinkList p,q;
q = L;
while(q->next != NULL) //让p指向链表的最后结点
q = q->next;
p = (LinkList)malloc(sizeof(Node));
p->data = e;
p->next = q->next;
q->next = p;
}
//将两个单链表归并成一个单链表
void Guibing(LinkList LA,LinkList LB,LinkList LC)
{
LinkList p,q,t;
p = LA->next;
q = LB->next;
t = LC;
while(p != NULL && q != NULL)
{
t->next = p;
t = t->next;
p = p->next;
t->next = q;
t = t->next;
q = q->next;
}
if( p != NULL)
t->next = p;
else
t->next = q;
LA->next = NULL;
LB->next = NULL;
}
//将单链表输出
void Print(LinkList L)
{
LinkList p;
for(p = L->next; p != NULL; p = p->next)
printf("%d\t",p->data);
printf("\n");
}
void main()
{
int m,n;
ElemType e;
LinkList LA,LB,LC;
InitList(&LA);
InitList(&LB);
InitList(&LC);
printf("请输入链表 A 的元素个数：");
scanf("%d",&m);
for(n = 1; n <= m; n++)
{
printf("请输入第 %d 个数：",n);
scanf("%d",&e);
Insert(LA,e);
}
printf("请输入链表 B 的元素个数：");
scanf("%d",&m);
for(n = 1; n <= m; n++)
{
printf("请输入第 %d 个数：",n);
scanf("%d",&e);
Insert(LB,e);
}
Print(LA);
Print(LB);
Guibing(LA,LB,LC);
Print(LC);
}
2.12 /*P50 习题2.12示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef struct polynode
{
int coef; //多项式的系数
int exp; //多项式的指数
struct polynode *next;
}Polynode,*Polylist;
/*初始化带头结点的环形链表*/
void InitList_H(Polylist *pL)
{
*pL=(Polylist)malloc(sizeof(Polynode));
(*pL)->next = *pL;
}
/*按指数由小到大顺序插入元素*/
void InsertList(Polylist L,int coef,int exp)
{
Polylist p,q;
q = L;
while( q->next != L && q->next->exp < exp)
q = q->next;
//若同一指数已经存在，则不添加
if(q->next != NULL && q->next->exp == exp)
return;
p = (Polylist)malloc(sizeof(Polynode));
p->coef = coef;
p->exp = exp;
p->next=q->next;
q->next=p;
}
//L是原环形链表，LA是奇数项链表，LB是偶数项链表
void Fenjie(Polylist L,Polylist LA,Polylist LB)
{
Polylist p,pa,pb;
p = L->next;
pa = LA;
pb = LB;
while(p != L)
{
if((p->exp % 2) ==1)
{
pa->next = p;
pa = pa->next;
}
else
{
pb->next = p;
pb = pb->next;
}
p = p->next;
}
pa->next = LA;
pb->next = LB;
L->next = L;
}
void Print(Polylist L)
{
Polylist p;
for(p = L->next; p != L; p = p->next)
printf("(%d,%d)\t",p->coef,p->exp);
printf("\n");
}
void main()
{
int coef,exp;
Polylist L,LA,LB;
InitList_H(&L); /*初始化链表*/
InitList_H(&LA);
InitList_H(&LB);
printf("请输入指数：");
scanf("%d",&exp);
while(exp>=0)
{
printf("请输入 %d 次项的系数：",exp);
scanf("%d",&coef);
InsertList(L,coef,exp);
printf("请输入指数：");
scanf("%d",&exp);
}
Print(L); /*将原结果输出*/
Fenjie(L,LA,LB);
Print(LA);
Print(LB);
}
2.13 /*P50 习题2.13示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *next;
}Node,*LinkList;
/*初始化带头结点的单链表*/
void InitList(LinkList *pL)
{
*pL=(LinkList)malloc(sizeof(Node));
(*pL)->next=NULL;
}
/*头插法插入元素*/
void InsertList(LinkList L,ElemType e)
{
LinkList p;
p=(LinkList)malloc(sizeof(Node));
p->data=e;
p->next=L->next;
L->next=p;
}
//通过递归调用实现从链尾向前加
int Add(LinkList p)
{
int k,t;
if(p == NULL)
return(0);
if(p->next == NULL)
{
k = (p->data + 1) / 2;
p->data = (p->data + 1) % 2;
return(k);
}
else
{
t = Add(p->next);
k = (p->data + t) / 2;
p->data = (p->data + t) % 2;
return(k);
}
}
void Print(LinkList L)
{
LinkList p;
for(p = L->next; p != NULL; p = p->next)
printf("%d\t",p->data);
printf("\n");
}
void main()
{
int i;
LinkList L;
InitList(&L); /*初始化链表*/
printf("请输入一个整数：");
scanf("%d",&i);
while(i > 0)
{
InsertList(L,i % 2);
i = i / 2;
}
Print(L); /*将原结果输出*/
i = Add(L->next);
if(i==1)
InsertList(L,1);
Print(L);
}
2.14
/*P50 习题2.14示例程序 */
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
typedef struct polynode
{
int coef; //多项式的系数
int exp; //多项式的指数
struct polynode *next;
}Polynode,*Polylist;
/*初始化带头结点的单链表*/
void InitList_H(Polylist *pL)
{
*pL=(Polylist)malloc(sizeof(Polynode));
(*pL)->next = NULL;
}
/*按指数由小到大顺序插入元素*/
void InsertList(Polylist L,int coef,int exp)
{
Polylist p,q;
q = L;
while( q->next != NULL && q->next->exp < exp)
q = q->next;
//若同一指数已经存在，则不添加
if(q->next != NULL && q->next->exp == exp)
return;
p = (Polylist)malloc(sizeof(Polynode));
p->coef = coef;
p->exp = exp;
p->next=q->next;
q->next=p;
}
//求幂函数
int Power(int x,int n)
{
int i,y;
y = 1;
if(n==0)
return (1);
for(i = 1; i <= n; i++)
y = y * x;
return(y);
}
//求值函数
int Qiuzhi(Polylist L,int x)
{
Polylist p;
int zhi;
zhi = 0;
p = L->next;
while(p)
{
zhi = zhi + p->coef * Power(x,p->exp);
p = p->next;
}
return(zhi);
}
void Print(Polylist L)
{
Polylist p;
for(p = L->next; p != NULL; p = p->next)
printf("(%d,%d)\t",p->coef,p->exp);
printf("\n");
}
void main()
{
int coef,exp,x;
Polylist L;
InitList_H(&L); /*初始化链表*/
printf("请输入指数：");
scanf("%d",&exp);
while(exp>=0)
{
printf("请输入 %d 次项的系数：",exp);
scanf("%d",&coef);
InsertList(L,coef,exp);
printf("请输入指数：");
scanf("%d",&exp);
}
Print(L); /*将原结果输出*/
printf("请输入 x,");
scanf("%d",&x);
printf("%d\n",Qiuzhi(L,x));
}
补充习题：
1、已知L是带头结点的单链表，P,Q,L均为结点结构体类型的指针变量，P指向链表的结点既不是首元结点，也不是尾元结点，试从下列提供的语句中选择合适的语句序列。
a,删除P结点的直接后继结点的语句序列是 。
b,删除P结点的直接前驱结点的语句序列是 。
c,删除P结点的语句序列是 。
d,删除首元结点的语句序列是 。
e,删除尾元结点的语句序列是 。
(1) P=P->next;
(2) P->next=P;
(3) P->next=P->next->next;
(4) P=P->next->next;
(5) while(P!=NULL)P=P->next;
(6) while(Q->next!=NULL){P=Q;Q=Q->next;}
(7) while(P->next!=Q)P=P->next;
(8) while(P->next->next!=Q)P=P->next;
(9) while(P->next->next!=NULL)P=P->next;
(10) Q=P;
(11) Q=P->next;
(12) P=L;
(13) L=L->next;
(14) free(Q);
参考解答：a：11，3，14 b：10，12，8，11，3，14 c：10，12，7，3，14 d：12，11，3，14
e：12，9，11，3，14
2、试写一算法，在无头结点的单链表上实现线性表元素插入操作:
int Insert(LinkList *pL,int i,ElemType b); 并将此算法和带头结点的单链表的插入操作算法进行比较。
参考解答：
int Insert(LinkList *pL,int i,ElemType b)
{ int i,j,n=0;
p=*pL;
while(p){ n++; p=p->next; } //用n统计链表的长度
if(i<1 || i>n+1) return 0; //判断插入位置是否合法
if(i==1){ //对第一位置单独处理
s=(LinkList)malloc(sizeof(Node));
s->data=b;
s->next=*pL; *pL=s; return OK;}
p=*pL; j=1 //余下情况肯定i>1，且L不为空
while(j<i-1){j++; p=p->next;} //找到插入位置的前一个结点，用p指向
s=(LinkList)malloc(sizeof(Node));
s->next=p->next; s->data=b; p->next=s;
return 1;
}
对带有头结点的链表来说，无论在什么位置插入元素，指向头结点的指针的指向关系都不会改变，这样只需要知道头结点的存储地址（指向头结点的指针），就可以实现对链表的操作；而无头结点的链表在最前面进行插入或删除操作时，指向首元结点的指针均会改变，所以需要把指向首元结点的指针变量的地址作为参数传递给被调函数，即使用二级指针。
3、已知有一个无头结点的单向循环链表，其每个结点中含三个域：pre,data,next，其中data为数据域，next为指向后继结点的指针域，pre为与next同类型的指针域，但它的值为空(NULL),试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。提示：指针变量H指向首元结点。
参考解答：
typedef struct Node{
ElemType data;
struct Node *pre,*next;
}Node,*LinkList;
void Double(LinkList L) //L为指向单向循环链表中任一结点的指针
{ LinkList p=L;
while(p->next!=L)
{ p->next->pre=p; //使p指向结点的后继结点的前驱指针指向p所指结点
p=p->next;}
L->pre=p; //L所指结点的前驱结点为p所指结点
}
4、试以循环链表作稀疏多项式的存储结构，编写求其一阶导数的算法，要求利用原多项式中的结点空间存放导数多项式，同时释放所有无用结点（系数为0）。
参考解答：
typedef struct Node{
float coef,index; //coef表示系数，index表示该项的指数
struct Node *next;
}Node,*PolyList ;
void derivative(PolyList L)
{ PolyList p,q=L;
if(!L) return; //若为空链，则退出
p=q->next;
while(p!=L->next)
{ p->coef=p->coef*p->index; p->index=p->index-1; //求p所指项的导数
if(p->coef==0){ q->next=p->next; free(p); p=q->next;}
else{ q=p; p=p->next;}
}
5、在线性表的顺序存储中，元素之间的逻辑关系是通过 存储位置相临 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 结点的指针域 决定的。
6、线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对于栈只能在一端插入和删除元素，可以进行插入和删除操作的一端叫 栈顶,另一端叫 栈底 ；对于队列能插入元素的一端称 队尾,能删除元素的一端称 队头 。
7、线性表采用链式存储时，其数据元素的存储地址 D 。
A)必须是连续的 B)部分地址必须是连续的
C)一定是不连续的 D)连续与否均可以
8、线性表的链接存储有利于 A 运算。
A)插入 B)读表元素 C)查找 D)定位
9、线性表是 C 。
A)一个无限序列，可以为空 B)一个有限序列，不可以为空
C)一个有限序列，可以为空 D)一个无限序列，不可以为空
10、若在单链表中，对在指针p所指的结点之前插入一个指针s所指的结点，可执行的操作为：（先将s所指结点插入p所指结点之后，再将s所指结点的值与p所指结点的值交换）
s->next= ;
p->next=s;
t=p->data;
p->data= ;
s->data= ;
参考解答,p->next s->data t
11、简述以下算法的功能
typedef struct Node{
ElemType data;
struct Node *next;
}LNode,*LinkList;
Status A(LinkList L){ //L是指向无头结点链表中首元结点的指针
if(L&&L->next){
Q=L;L=L->next;P=L;
while(p->next) P=P->next;
p->next=Q; Q->next=NULL;
}
return OK;
}
参考解答：将L所指的含有两个以上结点的链表的首元结点移到链尾，原第二个结点成为首元结点。
12、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于链表中最大值max但大于链表中最小值min的元素结点的算法。
参考解答：
void Delete(LinkList L)
{ LinkList max,min,p,q;
p=L;
if(p->next&&p->next->next)
{ if(p->next->data>p->next->next->data){ max=p; min=p->next;}
else { max=p->next; min=p;}
p=p->next->next;
while(p->next)
{ if(p->next->data>=min->next->data&&p->next->data<=max->next->data)
{ q=p->next;
p->next=q->next;
free(q);continue;
}
if(p->next->data<min->next->data)
{ q=min->next;
min->next=q->next;
free(q);
min=p;
p=p->next; continue;
}
if(p->next->data>max->next->data)
{ q=max->next;
max->next=q->next;
free(q);
max=p;
p=p->next; continue;
}
}
}
}
13、某家电超市对仓库中的电视机信息按价格从低到高构成一个单链表存于计算机中，链表结点的结构体定义如下，链表为带头结点的链表。若现在又新到m台价格为n的电视机入库，试编写相应算法。
typedef struct Tvnode{
float price;
int num;
struct Tvnode *next;
}TvNode,*TvList;
int AddTv(TvList L,float m,int n){,..}//L为指向头结点的指针参考解答：
int AddTv(TvList L,float m,int n)
{ TvList p=L,q;
while(p->next&&p->next->price<m)p=p->next;
if(p->next==NULL||p->next->price>m){
q=(TvList)malloc(sizeof(TvNode));
q->price=m; q->num=n;
q->next=p->next;
p->next=q;
}
else p->next->num+=n;
}