C++编程 数据结构
发布网友
发布时间：2022-05-26 13:46
共1个回答
热心网友
时间：2023-10-20 06:49
#include <iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node *next;
}LNode, *LinkList;
// (1）编写函数建立循环单链表CreateLinkList(int n), 函数返回值类型为LinkList。
LinkList CreateLinkList(int n)
{
/*按照升序输入n个整数，建立带表头结点的循环单链表*/
LinkList header = new Node(), nowNode = header;
header->data = n;//表头结点，存放链表长度
if (header == NULL)//检查内存申请是否成功
{
cout << "内存申请失败..";
return NULL;
}
cout << "输入" << n << "个升序的整数：";
for (int i = 0; i < n;++i)
{
nowNode->next = new Node();
nowNode = nowNode->next;
cin >> nowNode->data;
}
nowNode->next = header;//将末结点指向头结点，形成循环单链表
return header;
}
// (2) 编写查找函数QueryLinkList(LinkList *L, int x)实现查找并插入功能，函数返回值类型int。
int QueryLinkList(LinkList *L, int x)
{
/*查找值为x的元素，若查找成功返回1，否则返回0，并把x插入到相应的位置。*/
LinkList nowNode = (*L)->next;
LinkList preNode = nowNode;//上一结点
while (nowNode!=*L)
{
if (nowNode->data == x)
{
return 1;
}
else if (preNode->data>x&&x<nowNode->data)//x小于链表首元素
{
LinkList node = new Node();
node->data = nowNode->data;
node->next = nowNode->next;
nowNode->data = x;
nowNode->next = node;
return 0;
}
else if (preNode->data<x&&x<nowNode->data)//x应插入到链表中间
{
LinkList node = new Node();
node->data = x;
node->next = nowNode;
preNode->next = node;
return 0;
}
preNode = nowNode;
nowNode = nowNode->next;
}
//x大于链表中所有元素
LinkList node = new Node();
node->data = x;
node->next = nowNode;
preNode->next = node;
return 0;
}
// (3)编写函数Display(LinkList L), 输出线性表中的元素。
void Display(LinkList L)
{
LinkList nowNode = L->next;
while (nowNode!=L)
{
cout << nowNode->data << " ";
nowNode = nowNode->next;
}
}
void main()
{
int n;
cout << "输入元素个数n（n>0）：";
cin >> n;
LinkList header= CreateLinkList(n);
while (true)
{
int x;
cout << "\n\n输入待查找的元素值x：";
cin >> x;
cout <<QueryLinkList(&header, x) << endl;
Display(header);
}
}
