#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define elemType long /*元素类型*/
#define elemPrintType "%ld\t" /*元素打印类型*/
#define status int
#define OVERFLOW -1
#define ERROR 0
#define OK 1
/* 单链表数据结构 */
typedef struct lNode {
elemType data;
struct lNode *next;
} lNode, *linkList;
/******************************** 以下为函数声明 ********************************/
void initList (linkList *L); /* 初始化 */
void destroyList (linkList L); /* 销毁 */
status listIsEmpty (linkList L); /* 判断单链表是否为空 */
int listLength (linkList L); /* 获取单链表长度 */
status listInsertNode (linkList L, int i, elemType e); /* 单链表指定位置插入新元素 */
status listPrint (linkList L); /* 输出链表 */
status listReverse (linkList L); /* 逆置链表 */
/******************************** 以上为函数声明 ********************************/
/* 初始化 */
/* 操作结果:构造一个空的单链表L */
void initList (linkList *L) {
*L = (linkList) malloc (sizeof (struct lNode)); /* 产生头节点,并使L指向此头节点 */
if(!*L) /* 内存分配失败 */
exit (OVERFLOW);
(*L)->next = NULL; /* 指针域为空 */
}
/* 销毁 */
/* 初始条件:单链表L已存在。操作结果:销毁单链表L */
void destroyList (linkList L) {
linkList p,q;
p = L->next; /* p指向第一个结点 */
while (p) { /* 没到表尾 */
q = p->next;
free (p);
p = q;
}
free (L);
}
/* 判断单链表是否为空 */
/* 初始条件:单链表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
status listIsEmpty (linkList L) {
return L->next == NULL;
}
/* 获取单链表长度 */
/* 初始条件:单链表L已存在。操作结果:返回L中数据元素个数 */
int listLength (linkList L) {
int i = 0;
linkList p = L->next; /* p指向第一个结点 */
while (p) { /* 没到表尾 */
i++;
p=p->next;
}
return i;
}
/* 单链表指定位置插入新元素 */
/* 操作结果:在带头结点的单链表L中第i个位置之前插入元素e */
status listInsertNode (linkList L, int i, elemType e) {
int j=0;
linkList p=L,s;
while (p && j<i-1) { /* 寻找第i-1个结点 */
p = p->next;
j++;
}
if (!p || j>i-1) /* 插入位置不合理:i小于1或者大于表长 */
return ERROR;
/* 生成新结点,并插入L中 */
s = (linkList) malloc (sizeof (struct lNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
/* 输出链表 */
status listPrint (linkList L) {
if (listIsEmpty (L)) {
puts ("链表为空!");
return OK;
}
linkList p = L->next; /* p指向第一个结点 */
while (p!=NULL) {
printf (elemPrintType,p->data);
p = p->next;
}
putchar ('\n');
return OK;
}
/* 逆置链表 */
/* 初始条件:单链表L已存在。操作结果:链表元素逆置 */
status listReverse (linkList L) {
linkList p, q;
if (listIsEmpty (L)||listLength (L)==1) /* 若L为空表或只有一个元素 */
return ERROR;
p = L->next->next; /* p指向第2个结点 */
L->next->next = NULL; /* 首结点置为尾结点 */
/* 自第2个结点起遍历链表,循环将当前结点插入到头结点之后以逆置链表 */
while (p) {
q = p->next; /* q指向p的后继结点 */
/* 将p插入到头结点之后 */
p->next = L->next;
L->next=p;
/* 访问下一结点 */
p = q;
}
return OK;
}
int main (void) {
linkList head;
elemType a=1,b=2,c=3,d=4;
/* 初始化链表 */
initList (&head);
/* 插入若干元素 */
listInsertNode (head, 1, a);
listInsertNode (head, 1, b);
listInsertNode (head, 1, c);
listInsertNode (head, 1, d);
puts ("原链表内容:");
listPrint (head); /* 逆置链表 */
listReverse (head); /* 逆置链表 */
puts ("逆置后链表内容:");
listPrint (head);
destroyList (head); /* 销毁 */
getch ();
return 0 ;
}
运行结果