definition.h
===========================
typedef char ElemType;
typedef struct{//定义单链表
ElemType data;
struct Node* next;
}Node, *LinkList;
LinkList FormList();//正向形成链表
LinkList FormList2();//逆向形成链表
void Insert(LinkList, unsigned);//插入数据
void Delete(LinkList, unsigned, unsigned);//删除数据
void Disp(LinkList);//显示数据
void Destroy(LinkList);//释放内存
void Bubble(LinkList);//冒泡排序
unsigned CountLen(LinkList);//计算链表长度
void Merge(LinkList, LinkList);//合并有序链表
void Exchange(LinkList, unsigned);//前 m 个结点和后 n 个结点的互换
void Purge(LinkList);//删除单链表中重复的数据元素
======================================================
functions.c
========================
#include
#include
#include"definition.h"
LinkList FormList()//正向形成链表
{ ElemType temp;
LinkList h, head, end;
if( !( h=head=(LinkList)malloc(sizeof(Node)) ) ){
printf("Not Enough Memory!\n");
return 0;
} head->next=0;
while( (temp=getchar())!='\n' ){
if( !( end=(LinkList)malloc(sizeof(Node)) ) ){
printf("Not Enough Memory!\n");
return 0;
} head->next=end;
head=end;
head->data=temp;
head->next=0;
}
return h;
}
LinkList FormList2()//逆向形成链表
{ LinkList head, end;
ElemType temp;
if( !( head=(LinkList)malloc(sizeof(Node)) ) ){
printf("Not Enough Memory!\n");
return 0;
} head->next=0;
while( (temp=getchar())!='\n' ){
if( !( end=(LinkList)malloc(sizeof(Node)) ) ){
printf("Not Enough Memory!\n");
return 0;
} end->data=temp;
end->next=head->next;
head->next=end;
}
return head;
}
void Insert(LinkList L, unsigned i)//插入数据
{//若单链表没有头结点，需对在第一个结点之前进行插入的情况单独进行处理。很麻烦
unsigned j;
LinkList T;
ElemType temp;
getchar();
for(j=1; L&&jnext, j++)
; if(!L||j>i){
printf("Error!\n");
return;
} printf("请输入您要插入的数据：");
while( (temp=getchar())!='\n' ){
if( !( T=(LinkList)malloc(sizeof(Node)) ) ){
printf("Not Enough Memory!\n");
return;
} T->data=temp;
T->next=L->next;
L->next=T;
L=T;
} }
void Delete(LinkList L, unsigned i, unsigned j)//删除数据
{ LinkList T;
getchar();
for(i--; i&&L; L=L->next, i--)
; if(!L){
printf("Error!\n");
return;
} for(T=L->next; j&&T; j--){
L->next=T->next;
free(T);
T=L->next;
} }
void Disp(LinkList L)//显示数据
{ for(L=L->next; L; L=L->next)
printf("%c", L->data);
printf("\n");
}
void Destroy(LinkList L)//释放内存
{ LinkList T=L;
for(L=L->next; L; T=L, L=L->next)
free(T);
free(T);
}
void Bubble(LinkList L)//冒泡排序
{ ElemType temp;
LinkList T, H;
unsigned i, j, flag=1;
i=CountLen(L);//计算链表长度
H=L->next;
while(flag){
L=H;
T=H->next;
flag=0;
j=1;
while(j if(L->data > T->data){
temp=T->data;
T->data=L->data;
L->data=temp;
flag=1;
} L=L->next;
T=T->next;
j++;
} i--;
} }
void Merge(LinkList A, LinkList B)//合并有序链表
{ LinkList C=A, D=B;
A=A->next;
B=B->next;
while(A&&B){
if(A->datadata){
C->next=A;
C=A;
A=A->next;
} else{
C->next=B;
C=B;
B=B->next;
} }
C->next=A?A:B;
free(D);
}
unsigned CountLen(LinkList L)//计算链表长度
{ unsigned i=0;
for(L=L->next; L; L=L->next, i++)
; return i;
}
void Exchange(LinkList L, unsigned i)//前 m 个结点和后 n 个结点的互换
{ LinkList A, B;
A=B=L->next;
for(i--; i&&A; A=A->next, i--)
; if(!A){
printf("Error!\n");
return;
} L->next=A->next;
A->next=0;
A=L->next;
while(A->next)
A=A->next;
A->next=B;
}
void Purge(LinkList L)//删除单链表中重复的数据元素
{ LinkList A, B, C, D;
B=C=L->next;
L->next=0;
while(B){
A=L->next;
D=L;
while(A){
if(A->data==B->data){
B=B->next;
free(C);
C=B;
break;
} else{
A=A->next;
D=D->next;
} }
if(!A){
D->next=B;
B=B->next;
C->next=0;
C=B;
} }
} ======================================================
main.c
===================
#include
#include
#include"definition.h"
int main()
{ LinkList A, B;
unsigned i, j;
//形成链表
printf("请为表A输入数据：");
A=FormList();
printf("请为表B输入数据：");
B=FormList2();
//显示数据
printf("表A：");
Disp(A);
printf("表B：");
Disp(B);
//插入数据
printf("请问您要在表A的哪个位置插入数据：");
scanf("%d", &i);
Insert(A, i);
printf("请问您要在表B的哪个位置插入数据：");
scanf("%d", &i);
Insert(B, i);
printf("表A：");
Disp(A);
printf("表B：");
Disp(B);
//冒泡排序
Bubble(A);
Bubble(B);
printf("表A排序后：");
Disp(A);
printf("表B排序后：");
Disp(B);
//删除数据
printf("请问您要从表A的哪个位置开始删除数据：");
scanf("%d", &i);
printf("请问您要删除几个元素：");
scanf("%d", &j);
Delete(A, i, j);
printf("请问您要从表B的哪个位置开始删除数据：");
scanf("%d", &i);
printf("请问您要删除几个元素：");
scanf("%d", &j);
Delete(B, i, j);
printf("表A：");
Disp(A);
printf("表B：");
Disp(B);
Merge(A, B);//合并有序链表
printf("合并链表后：");
Disp(A);
//前m个结点和后n个结点的互换
printf("前m个结点和后n个结点的互换。请输入一个整数：");
scanf("%d", &i);
Exchange(A, i);
printf("前m个结点和后n个结点的互换后：");
Disp(A);
//删除单链表中重复的数据元素
Purge(A);
printf("删除重复元素后：");
Disp(A);
//释放内存
Destroy(A);
}
