实例:建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位,并在此链表上实现对二进制数加1的运算
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
/*定义单链表*/
typedef struct Node {
char data;
struct Node * next;
} Node,* LinkList; /*LinkList为结构指针类型*/
/*单链表初始化*/
InitList(LinkList *L) {
*L=(LinkList)malloc(sizeof(Node)); /*建立头结点*/
(*L)->next=NULL; /*建立空的单链表L*/
}
/*尾插法建立单链表*/
void CreateFromTail(LinkList L) {
/* L是带头结点的空链表头指针,通过键盘输出元素值,利用尾插法建立单链表L*/
Node *r,*s;
char c;
int flag=1; /*设置一个标志,初值为1,当输入'$'时,flag=0*/
r=L; /*r指针动态指向链表的当前表尾,以便于做尾插入,其初值指向头结点*/
while(flag) { /*循环输入表中元素值,将建立新结点s插入表尾*/
c=getchar();
if(c!='$') {
s=(Node *)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
} else {
flag=0;
r->next=NULL;/*将最后一个结点的next链域置为空,表示链表的结束。*/
}
}
}
/*输出链表*/
void PrintList(LinkList L) {
Node *r;
r=L->next;
puts("下面将输出该表:");
while(r!=NULL) {
printf(" %c ",r->data);
r=r->next;
}
}
/*实例:建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位,并在此链表
上实现对二进制数加1的运算*/
void BinaryAdd(LinkList l) { /*用带头结点的单链表L存储二进制数,实现加1运算*/
Node *q,*r;
Node *s;
q=l->next;
r=l;
while(q!=NULL) { /*查找最后一个值域为0的结点*/
if(q->data==0) {
r=q;
}
q=q->next;
}
/*如果r!=l意味着找到值域为0的结点,所以将该结点的值域赋值为1,以方便将后面的值域全部置为0*/
if(r!=l)
r->data=1; /*将最后一个值域为0的结点的值域赋为1*/
/*如果r==l,意味着找不到值域为0的结点,所以要从新申请一个结点用来存储二进制最高位,以方便将后面的值域全部置为0*/
else {
s=(LinkList)malloc(sizeof(Node)); /*申请新结点存放到最高位*/
s->data=1; /*值域赋为1*/
s->next=l->next;
l->next=s; /*该结点插入到头结点之后*/
r=l->next; /*指针r指向最高位结点*/
}
r=r->next; /*从值域0被改为1的结点或最高二进制位的结点后移*/
while(r!=NULL) { /*将后面所有的结点的值域赋值为0*/
r->data=0;
r=r->next;
}
}
/*主函数*/
void main() {
LinkList L_1,L_2;
InitList(&L_1);
puts("下面将用尾插法插入单链表:");
CreateFromTail(L_1);
PrintList(L_1);
BinaryAdd(L_1); /*链表存放二进制位并且+1计算*/
printf("\n");
PrintList(L_1);
}