1单链表的定义及应用
单链表的定义及基本操作（构造 销毁 插入 删除 取值） #include
#include
#include
typedef char ElemType;
typedef struct LNode /*定义单链表结点类型*/
{
ElemType data;
struct LNode *next;
} LinkList;
void InitList(LinkList *&L) /*初始化单链表L*/
{
} L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=NULL;
void DestroyList(LinkList *&L) /*释放单链表L*/
{
LinkList *p=L,*q=p->next;
while (q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
}
int ListEmpty(LinkList *L) /*判断单链表L 是否为空表*/ {
return(L->next==NULL);
}
int ListLength(LinkList *L) /*返回单链表个数*/
{
LinkList *p=L;int i=0;
while (p->next!=NULL)
{
i++;
p=p->next;
}
return(i);
}
void DispList(LinkList *L) /*输出*/
{
LinkList *p=L->next;
while (p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
int GetElem(LinkList *L,int i,ElemType &e)/*获取*/
{
int j=0;
LinkList *p=L;
while (j
{
j++;
p=p->next;
}
if (p==NULL)
return 0;
else
{
e=p->data;
return 1;
}
}
int LocateElem(LinkList *L,ElemType e) /*查找*/
{
LinkList *p=L->next;
int n=1;
while (p!=NULL && p->data!=e)
{
p=p->next;
n++;
}
if (p==NULL)
return(0);
else
return(n);
}
int ListInsert(LinkList *&L,int i,ElemType e) /*插入*/
{
int j=0;
LinkList *p=L,*s;
while (j
{
} p=p->next; } if (p==NULL) /*未找到第i-1个结点*/ return 0; else /*找到第i-1个结点*p*/ { s=(LinkList *)malloc(sizeof(LinkList)); s->data=e; } s->next=p->next; p->next=s; return 1; /*创建新结点*s*/ /*将*s插入到*p之后*/
int ListDelete(LinkList *&L,int i,ElemType &e) /*删除*/
{
int j=0;
LinkList *p=L,*q;
while (j
{
j++;
p=p->next;
}
if (p==NULL) /*未找到第i-1个结点*/
return 0;
else { /*找到第i-1个结点*p*/
q=p->next; /*q指向要删除的结点*/
p->next=q->next; /*从单链表中删除*q结点*/
free(q); /*释放*q结点*/
return 1;
}
}
void main()
{
LinkList *h;
ElemType e;
printf("(1)初始化单链表h\n");
InitList(h);
printf("(2)依次采用尾插法插入a,b,c,d,e 元素\n");
ListInsert(h,1,'a');
ListInsert(h,2,'b');
ListInsert(h,3,'c');
ListInsert(h,4,'d');
printf("(3)输出单链表h:"); DispList(h); printf("(4)单链表h 长度=%d\n",ListLength(h)); printf("(5)单链表h 为%s\n",(ListEmpty(h)?"空":"非空")); GetElem(h,3,e); printf("(6)单链表h 的第3个元素=%c\n",e); printf("(7)元素a 的位置=%d\n",LocateElem(h,'a')); printf("(8)在第4个元素位置上插入f 元素\n"); ListInsert(h,4,'f'); printf("(9)输出单链表h:"); DispList(h);
printf("(10)删除h 的第3个元素\n");
ListDelete(h,3,e);
}
printf("(11)输出单链表h:"); DispList(h); printf("(12)释放单链表h\n"); DestroyList(h); getch();
用单链表实现一元多项式的相加
#include
#include
#include
#define MAX 20
typedef struct
{ /*多项式最多项数*/ /*定义存放多项式的数组类型*/
/*系数*/
/*指数*/
/*定义单链表结点类型*/ float coef; int exp; } PolyArray[MAX]; typedef struct pnode
{
float coef; /*系数*/
int exp; /*指数*/
struct pnode *next;
} PolyNode;
void DispPoly(PolyNode *L) /*输出多项式*/
{
PolyNode *p=L->next;
while (p!=NULL)
{
printf("%gX^%d ",p->coef,p->exp);
p=p->next;
}
printf("\n");
}
void CreateListR(PolyNode *&L,PolyArray a,int n) /*尾插法建表*/ {
PolyNode *s,*r;int i;
L=(PolyNode *)malloc(sizeof(PolyNode)); L->next=NULL; r=L; for (i=0;i
s=(PolyNode *)malloc(sizeof(PolyNode));/*创建新结点*/ s->coef=a[i].coef;
s->exp=a[i].exp;
r->next=s; /*将*s插入*r之后*/
r=s;
}
r->next=NULL; /*终端结点next 域置为NULL*/ }
void Sort(PolyNode *&head) /*按exp 域递减排序*/
{
PolyNode *p=head->next,*q,*r; if (p!=NULL) /*若原单链表中有一个或以上的数据结点*/ { r=p->next; p->next=NULL; p=r; while (p!=NULL) { /*r保存*p结点后继结点的指针*/ /*构造只含一个数据结点的有序表*/ r=p->next; /*r保存*p结点后继结点的指针*/ q=head; while (q->next!=NULL && q->next->exp>p->exp)
q=q->next; /*在有序表中找插入*p的前驱结点*q*/ p->next=q->next; /*将*p插入到*q之后*/
q->next=p;
p=r;
}
}
}
void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) /*求两有序集合的并*/ {
PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;
float c;
hc=(PolyNode *)malloc(sizeof(PolyNode)); /*创建头结点*/ tc=hc;
while (pa!=NULL && pb!=NULL)
{
if (pa->exp>pb->exp)
{
s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/ s->exp=pa->exp;s->coef=pa->coef;
tc->next=s;tc=s;
pa=pa->next;
}
else if (pa->expexp)
{
s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/ s->exp=pb->exp;s->coef=pb->coef;
tc->next=s;tc=s;
pb=pb->next;
}
else /*pa->exp=pb->exp*/
{
c=pa->coef+pb->coef;
} } if (c!=0) /*系数之和不为0时创建新结点*/ { s=(PolyNode *)malloc(sizeof(PolyNode)); /*复制结点*/ s->exp=pa->exp;s->coef=c; tc->next=s;tc=s; } pa=pa->next; pb=pb->next; if (pb!=NULL) pa=pb; while (pa!=NULL) { /*复制余下的结点*/
}
tc->next=NULL;
}
void main()
{
PolyNode *ha,*hb,*hc;
PolyArray a={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}};
PolyArray b={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}}; CreateListR(ha,a,4);
CreateListR(hb,b,5);
}
printf("原多项式A: ");DispPoly(ha); printf("原多项式B: ");DispPoly(hb); Sort(ha); Sort(hb); printf("有序多项式A: ");DispPoly(ha); printf("有序多项式B: ");DispPoly(hb); Add(ha,hb,hc); printf("多项式相加: ");DispPoly(hc); getch(); s=(PolyNode *)malloc(sizeof(PolyNode)); s->exp=pa->exp; s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; /*复制结点*/