|
实现不带头结点的单链表
需要实现的基本操作为：初始化、遍历、求表长（元素个数）、取某序号位置的元素、头插法创建，尾插法创建、插入、删除、清空，销毁、查询并返回某元素e在链表中的序号。
==main中===
1）声明一个链表LA，初始化
2）遍历该链表
3）取第2号节点的值，并打印，如果非法，则打印“没有2号节点”
4）声明一个链表LB，并利用头插法使之具有n个节点，n个节点的数据由键盘输入，分别为：1,2,3,4,5
5）遍历输出LB
6）取第LB的1号节点的值，并打印，如果非法，则打印“没有1号节点”
7）取第LB的5号节点的值，并打印，如果非法，则打印“没有5号节点”
8）取第LB的6号节点的值，并打印，如果非法，则打印“没有6号节点”
7）声明一个链表LC，并利用尾插法使之具有n个节点，n个节点的数据由键盘输入，分别为：1,2,3,4,5
8）遍历输出LC
9）取第LC的0号节点的值，并打印，如果非法，则打印“没有0号节点”
10）取第LC的5号节点的值，并打印，如果非法，则打印“没有5号节点”
11）取第LC的6号节点的值，并打印，如果非法，则打印“没有6号节点”
12）清空LB
13）遍历LB
14）销毁LA,LB,LC
main中继续：
1、初始化一个单链表
2、在序号1位置，插入1,插入2,插入3,插入4,插入5
3、在序号6位置，插入6，在序号3位置，插入33，如果无法插入，则打印无法插入
4、遍历打印各个结点的数据
5、分别在该链表中查询5,6,3，12，并打印其序号，如果查不到，则打印没有该元素。
6、依次在序号1，5,3,20处删除结点，并打印返回的结点数据，如果无法删除，则打印无法删除该序号位置元素
7、遍历打印各个结点的数据
8、销毁该单链表
=======
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode {
ElemType data;
LinkNode* next;
}*LinkList;
void InitLinkList(LinkList& L) {
L = NULL;
}
void Traverse(const LinkList& L) {
LinkNode* p = L; //设p指向首元结点
while (p) { //有结点则进行
cout << p->data << endl;
p = p->next; //结点指针后移
}
}
int Count(const LinkList& L) {
LinkNode* p = L;
int i = 0;
while (p) {
i++;
p = p->next;
}
return i;
}
void CreatHead(LinkList& L, int n) {
L = NULL;
for (int i = 0; i < n; i++) {
LinkNode* s = new LinkNode;
cin >> s->data;
s->next = L;
L = s;
}
}
void CreatRear(LinkList& L, int n) {
L = NULL;
LinkNode* r = new LinkNode;
for (int i = 0; i < n; i++) {
LinkNode* s = new LinkNode;
cin >> s->data;
if (!L) L = r = s; //空表
else { r->next = s; r = s; } //非空表
}
r->next = NULL;
}
int GetElem(const LinkList& L, int i, ElemType& e) {
if (i < 1) return 0;
LinkNode* p = L; int j = 1;
while (p) {
if (j == i) { e = p->data; return 1; }
p = p->next;
j++;
}
return 0;
}
int Insert(LinkList& L, int i, ElemType e) {
LinkNode* p = L, * s;
int j = 1;
if (i == 1) { //在头部插入
s = new LinkNode;
s->data = e;
s->next = L;
L = s;
return 1;
}
while (p && j < i - 1) {
p = p->next; j++;
}
if (!p || i < 1) return 0;
s = new LinkNode;
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
int Delete(LinkList& L, int i, ElemType& e) {
LinkNode* p = L,
* q; int j = 1;
if (!L || i < 1) return 0;
if (i == 1) {
q = L; L = L->next; //删除首元
e = q->data; delete q; return 1;
}
while (p->next && j < i - 1) {
p = p->next; j++;
}
if (!p->next) return 0; //i>n
q = p->next;
p->next = q->next;
e = q->data;
delete q;
return 1;
}
int LocateElem(const LinkList& L, ElemType e) {
LinkNode* p = L; //第一个结点赋给p
int j = 1;
while (p && p->data != e) {
p = p->next;
j++;
}
if (!p) return 0;
return j;
//找到后返回该结点的序号，否则返回NULL
}
void DestroyList(LinkList& L) {
LinkNode* p = L;
while (p)
{
L = L->next;
delete(p);
p = L;
}
}
void ListClear(LinkList& L) {
LinkNode* p;
while (L->next) {
p = L->next;
L->next = p->next;
delete(p);
}
L = NULL;
}
int main() {
LinkList LA;//1）声明一个链表LA，初始化
InitLinkList(LA);
int e;
int n = 0;
Traverse(LA);//2）遍历该链表
if (GetElem(LA, 2, e)) {
printf("二号节点的值为%d\n", e);//3）取第2号节点的值，并打印，
}
else {
printf("没有2号节点\n");//如果非法，则打印“没有2号节点“
}
LinkList LB;//4）声明一个链表LB，
InitLinkList(LB);
cout << "请输入插入节点个数:";
cin >> n;
cout << "请依次输入插入节点值:" << endl;
CreatHead(LB, n);//并利用头插法使之具有n个节点，n个节点的数据由键盘输入，分别为：1,2,3,4,5
Traverse(LB);//5）遍历输出LB
if (GetElem(LB, 1, e)) {//6）取第LB的1号节点的值，并打印，
printf("1号节点的值为%d\n", e);
}
else {
printf("没有1号节点\n");//如果非法，则打印“没有1号节点”
}
if (GetElem(LB, 5, e)) {//取第LB的5号节点的值，并打印，
printf("5号节点的值为%d\n", e);
}
else {
printf("没有5号节点\n");//如果非法，则打印“没有5号节点”
}
if (GetElem(LB, 6, e)) {
printf("6号节点的值为%d\n", e);//取第LB的6号节点的值，并打印，
}
else {
printf("没有6号节点\n");//如果非法，则打印“没有6号节点”
}
LinkList LC; //7）声明一个链表LC
cout << "请输入插入节点个数:";
cin >> n;
cout << "请依次输入插入节点值:" << endl;
CreatRear(LC, n);//并利用尾插法使之具有n个节点，n个节点的数据由键盘输入，分别为：1, 2, 3, 4, 5
Traverse(LC);//8）遍历输出LC
if (GetElem(LC, 0, e)) {//9）取第LC的0号节点的值，并打印，
printf("0号节点的值为%d\n", e);
}
else {
printf("没有0号节点\n");//如果非法，则打印“没有0号节点”
}
if (GetElem(LC, 5, e)) {//10）取第LC的5号节点的值，并打印，
printf("5号节点的值为%d\n", e);
}
else {
printf("没有5号节点\n");//如果非法，则打印“没有5号节点”
}
if (GetElem(LC, 6, e)) {//11）取第LC的6号节点的值，并打印，
printf("6号节点的值为%d\n", e);
}
else {
printf("没有6号节点\n");//如果非法，则打印“没有6号节点”
}
ListClear(LB);//12）清空LB
Traverse(LB);//13）遍历LB
DestroyList(LA);//14）销毁LA,LB,LC
DestroyList(LB);
DestroyList(LC);
printf("========================================================================================\n");
printf("main中继续\n");
//main中继续：
LinkList L;//==========================
InitLinkList(L);//1、初始化一个单链表
for (int i = 1; i <= 5; i++) {
Insert(L, 1, i);//2、在序号1位置，插入1,插入2,插入3,插入4,插入5
}
if (Insert(L, 6, 6)) {//3、在序号6位置，插入6，
cout << "在位置6插入6成功" << endl;
}
else {
cout << "无法插入\n";//如果无法插入，则打印无法插入
}
if (Insert(L, 3, 33)) {//在序号3位置，插入33，
cout << "在位置3插入33成功" << endl;
}
else {
cout << "无法插入\n";//如果无法插入，则打印无法插入
}
Traverse(L);//4、遍历打印各个结点的数据
if (LocateElem(L, 5)) {//5、分别在该链表中查询5,6,3，12，并打印其序号，如果查不到，则打印没有该元素。==========
printf("该元素序号为%d\n", LocateElem(L, 5));// 第5题
}// 第5题
else {// ↓↓↓
printf("没有该元素\n");//
}//
if (LocateElem(L, 6)) {//
printf("该元素序号为%d\n", LocateElem(L, 6));//
}//
else {//
printf("没有该元素\n");//
}//
if (LocateElem(L, 3)) {//
printf("该元素序号为%d\n", LocateElem(L, 3));//
}//
else {//
printf("没有该元素\n");//
}//
if (LocateElem(L, 20)) {//
printf("该元素序号为%d\n", LocateElem(L, 20));//
}// ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
else {// ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ ↑↑↑
printf("没有该元素\n");// 第5题
}//===============================================================================================================
if (Delete(L, 1, e)) {//6、依次在序号1，处删除结点，并打印返回的结点数据
printf("删除的节点数据为%d\n", e);
}
else {
printf("无法删除该序号位置元素\n"); //如果无法删除，则打印无法删除该序号位置元素
}
if (Delete(L, 5, e)) {//5,处删除结点，并打印返回的结点数据
printf("删除的节点数据为%d\n", e);
}
else {
printf("无法删除该序号位置元素\n");//，如果无法删除，则打印无法删除该序号位置元素
}
if (Delete(L, 3, e)) {//3,处删除结点，并打印返回的结点数据
printf("删除的节点数据为%d\n", e);
}
else {
printf("无法删除该序号位置元素\n");//，如果无法删除，则打印无法删除该序号位置元素
}
if (Delete(L, 20, e)) {//20处删除结点，并打印返回的结点数据，
printf("删除的节点数据为%d\n", e);
}
else {
printf("无法删除该序号位置元素\n");//，如果无法删除，则打印无法删除该序号位置元素
}
Traverse(L);//7、遍历打印各个结点的数据
DestroyList(L); //8、销毁该单链表
}
|