// list_example.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
#define N 5
typedef struct node //定义一个节点
{
int data;
struct node *next;
}Node;
Node* createList(int a[]); //用数组a建立链表，返回头结点地址
void outlist(Node *h); //输出链表的节点值
void destroylist(Node *h); //销毁链表
int sumlist(Node *h); //求和
int maxlist(Node *h); //求最大值
int countlist(Node *h); //统计链表中的节点值
void sortlist(Node *h); //从小到大排序
void insertNode(Node *h, int a, int d); //插入一个节点
void deleteNode(Node *h, int a); //删除一个节点
int _tmain(int argc, _TCHAR* argv[])
{
int a[5] = { 1, 2, 6, 5, 4 };
Node *head; //头地址
head = createList(a); //建立链表
outlist(head); //显示链表
cout << "链表中元素的和为：" << sumlist(head) << endl;
cout << "链表中最大的元素为：" << maxlist(head) << endl;
cout << "链表中数的和为：" << countlist(head) << endl;
insertNode(head, 6, 20); //在6后插入
cout << "插入20后的链表元素为：" << endl;
outlist(head); //显示链表
cout << endl;
deleteNode(head, 2);
cout << "删除2后的链表元素为：" << endl;
outlist(head); //显示链表
cout << endl;
sortlist(head); //由小到大排序
cout << "排序后链表中元素为：" << endl;
outlist(head); //显示链表
cout<< endl;
destroylist(head); //销毁链表
getchar();
return 0;
}
Node* createList(int a[]) //用数组a建立链表，返回头结点地址
{
Node *h=NULL; //指向头结点，即保存头结点的地址
Node *p, *q; //*p指向当前节点，*q指向上一节点
q = new Node; //开辟空间
h = q; //确定了头地址，现在h、q两个指针均指向头结点
//建立链表中的结点，现在的上一节点为头结点，q指向
for (int i = 0; i < N; i++) //暂定5个节点
{
p = new Node; //开辟空间
p->data = a[i]; //节点的值
p->next = NULL;
q->next = p; //上一节点，指向本当前节点
q = p; //等下次循环，p变为上一节点
}
q->next = NULL; //最后一个节点的指针域为空
return h; //返回链表的头结点地址
}
void outlist(Node *h) //输出链表的节点值
{
Node *p = NULL;
p = h->next; //p指向第一个节点
int i = 1;
while (p != NULL)
{
cout << " 第" << i << "个节点的值为" << p->data << endl;
i++;
p = p->next; //指向下一个节点
}
}
void destroylist(Node *h) //销毁链表
{
Node *p, *q; //定义两个结构体指针
p = h->next;
while (p != NULL)
{
q = p->next; //先备份
free(p);
p = q; //p指向下一个节点
}
free(h); //销毁头结点
cout << "已销毁链表!" << endl;
}
int sumlist(Node *h) //求和
{
Node *p = h->next; //存储地址
int sum = 0;
while (p != NULL) //遍历
{
sum = sum + p->data;
p = p->next;
}
return sum; //返回和
}
int maxlist(Node *h) //求最大值
{
Node *p = h->next; //存储地址
int a = 0; //用于比较
while (p != NULL) //遍历
{
if (a < p->data ) //如果新节点中的值更大，那把它替换为a
//保证a是已比较数中最大的
a = p->data;
p = p->next;
}
return a; //返回和
}
int countlist(Node *h) //统计链表中的节点值
{
Node *p = h->next;
int num = 0;
while (p != NULL) //遍历
{
num++;
p = p->next;
}
return num; //返回节点数量
}
//外层用指针变量p，内层用指针变量q
void sortlist(Node *h) //从小到大排序
{
Node *p, *q;
int temp =0;
p = h -> next; //指向第一个节点
while (p != NULL) //外层循环
{
q = p->next; //q指向第2个节点
while (q != NULL) //内层循环
{
if ((p->data) > (q->data)) //后面的数大于前面的数,则交换
{
temp = p->data;
p->data = q->data;
q->data = temp;
}
q = q->next;
}
p = p->next;
}
}
//插入节点，节点为a，值为d
void insertNode(Node *h, int a, int d) //插入一个节点
{
Node *p, *q; // p指向插入位置，q指向前一位置
Node *s; //新节点
s = new Node; //申请新节点空间
s->data = d;
//定位插入位置
q = h;
p = h->next; //节点q在前，p在后
while (p !=NULL)
{
if (p->data == a)
break;
q = p; //当p->data == 6时，q在p前
p = p->next;//节点q在前，p在后
}
//插入新节点，先连再断
s->next = q->next;
q->next = s;
}
void deleteNode(Node *h, int a) //删除节点
{
Node *p, *q; //p指向要删除节点，q指向前一节点
//定位要删除的节点
q = h;
p = h->next; //节点q在前，p在后
while (p != NULL)
{
if (p->data == a)
break;
q = p; //当p->data == 6时，q在p前
p = p->next;//节点q在前，p在后
}
//删除节点，只有找到才删除
if (p != NULL)
{
q->next = p->next; //
free(p);
}
}
运行结果：
?
