|
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int elemtype;
typedef int status;
typedef struct node
{
?? ?elemtype elem;
?? ?node* next;
}lnode ,*linklist;
void menu1();//申明链表菜单函数
status initiallist(linklist& l)
{
?? ?l = new lnode;
?? ?if (l != NULL)
?? ?{
?? ??? ?l->next = NULL;//头结点
?? ??? ?cout << "初始化成功" << endl;
?? ??? ?return true;
?? ?}
?? ?else
?? ??? ?cout << "初始化失败" << endl;
?? ?return false;
}
void headinsert(linklist &l,int n)
{
?? ?int t = 1;
?? ?for (t; t <= n; t++)
?? ?{
?? ??? ?cout << "请输入第" << t << "个数据" << endl;
?? ??? ?linklist p = new lnode;
?? ??? ?cin >> p->elem;
?? ??? ?p->next = l->next;
?? ??? ?l->next = p;
?? ?}
}//头插法建立
void rearinsert(linklist& l, int n)
{
?? ?int t = 1;
?? ?linklist q;
?? ?q = l;
?? ?for (t; t <= n; t++)
?? ?{
?? ??? ?cout << "请输入第" << t << "个数据" << endl;
?? ??? ?linklist p = new lnode;
?? ??? ?cin >> p->elem;
?? ??? ?q->next = p;
?? ??? ?q = p;
?? ?}
?? ?q->next = NULL;
}//尾插法建立链表
void listoutput(linklist& l)
{
?? ?int t = 1;
?? ?linklist p;
?? ?p = l->next;
?? ?while (p != NULL)
?? ?{
?? ??? ?cout << "第" << t << "个位置的数据为" << p->elem << endl;
?? ??? ?t++;
?? ??? ?p = p->next;
?? ?}
}//输出链表
int ?length(linklist& l)
{
?? ?linklist p;
?? ?int t = 0;
?? ?p = l->next;
?? ?while (p != NULL)
?? ?{
?? ??? ?p = p->next;
?? ??? ?t++;
?? ?}
?? ?return t;
}//链表长度
void insertlist(linklist& l, linklist& p, int i)
{
?? ?if (i < 1 || i>(length(l) + 1))
?? ?{
?? ??? ?cout << "插入位置错误" << endl;
?? ?}
?? ?else
?? ?{
?? ??? ?int j;
?? ??? ?linklist q;
?? ??? ?q = l;
?? ??? ?for (j = 1; j < i; j++)
?? ??? ?{
?? ??? ??? ?q = q->next;
?? ??? ?}
?? ??? ?p->next = q->next;
?? ??? ?q->next = p;
?? ??? ?listoutput(l);
?? ?}
}//链表插入
void deletelist(linklist& l, int i)
{
?? ?if (i<1 || i>length(l))
?? ?{
?? ??? ?cout << "删除位置错误" << endl;
?? ?}
?? ?else
?? ?{
?? ??? ?int j;
?? ??? ?linklist q;
?? ??? ?linklist t;
?? ??? ?q = l;
?? ??? ?for (j = 1; j < i; j++)
?? ??? ?{
?? ??? ??? ?q = q->next;
?? ??? ?}
?? ??? ?t = q->next;
?? ??? ?q->next = t->next;
?? ??? ?delete t;
?? ??? ?listoutput(l);
?? ?}
}//链表删除
void listsort(linklist& l)
{
?? ?int t;
?? ?linklist p, q;
?? ?p = l->next;
?? ?while (p != NULL)
?? ?{
?? ??? ?q = p->next;
?? ??? ?while (q != NULL)
?? ??? ?{
?? ??? ??? ?if (p->elem > q->elem)
?? ??? ??? ?{
?? ??? ??? ??? ?t = q->elem;
?? ??? ??? ??? ?q->elem = p->elem;
?? ??? ??? ??? ?p->elem = t;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ??? ?q = q->next;
?? ??? ?}
?? ??? ?p = p->next;
?? ?}
}//链表排序
void sortinsert(linklist& l,linklist ?&t)
{
?? ?linklist p, q,s;
?? ?p = l->next;
?? ?q = p->next;
?? ?s = l->next;
?? ?while (s->next != NULL)
?? ?{
?? ??? ?s = s->next;
?? ?}
?? ?if (t->elem > s->elem)
?? ?{
?? ??? ?t->next = s->next;
?? ??? ?s->next = t;
?? ?}
?? ?else?
?? ?if (t->elem < l->next->elem)
?? ?{
?? ??? ?t->next = l->next;
?? ??? ?l->next = t;
?? ?}//头部插入
?? ?else
?? ?{
?? ??? ?while (q != 0)
?? ??? ?{
?? ??? ??? ?if (p->elem <= t->elem && t->elem <= q->elem)
?? ??? ??? ?{
?? ??? ??? ??? ?t->next = p->next;
?? ??? ??? ??? ?p->next = t;
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?p = q;
?? ??? ??? ??? ?q = q->next;
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?listoutput(l);
}//有序链表排序插入
int main()
{
?? ?menu1();
?? ?return 0;
}
void menu1()
{
?? ?int t;
?? ?int m;
?? ?linklist l;
?? ?linklist n;
?? ?while (1)
?? ?{
?? ?
?? ??? ?cout << "根据所做操作选择以下数字符号" << endl;
?? ??? ?cout << endl << endl;
?? ??? ?cout << "8:单链表的建立" << endl;
?? ??? ?cout << endl;
?? ??? ?cout << "1:头插法创建单链表" << '\t' << "2:尾插法创建单链表" << '\t' << "3:执行插入操作" << endl;
?? ??? ?cout << "4:执行删除操作" << '\t' <<'\t' << "5:执行输出操作" << '\t' << '\t' << "6:执行排序操作" << endl;
?? ??? ?cout << "7:执行有序表的插入操作" << '\t' << "0:退出" << ? endl;
?? ??? ?cin >> t;
?? ??? ?switch (t)
?? ??? ?{
?? ??? ?case 1:
?? ??? ??? ?cout << "请输入要输入数据个数" << endl;
?? ??? ??? ?cin >> m;
?? ??? ??? ?headinsert(l, m);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 2:
?? ??? ? ? ?cout << "请输入要输入数据个数" << endl;
?? ??? ??? ?cin >> m;
?? ??? ??? ?rearinsert(l, m);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 3:
?? ??? ??? ?n = new lnode;
?? ??? ??? ?cout << "请输入插入的数据" << endl;
?? ??? ??? ?cin >> n->elem;
?? ??? ??? ?cout << "请输入插入的位置" << endl;
?? ??? ??? ?cin >> m;
?? ??? ??? ?insertlist(l, n, m);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 4:
?? ??? ??? ?cout << "请输入删除元素的位置" << endl;
?? ??? ??? ?cin >> m;
?? ??? ??? ?deletelist(l, m);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 5:
?? ??? ??? ?listoutput(l);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 6:
?? ??? ??? ?listsort(l);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 7:
?? ??? ??? ?n = new lnode;
?? ??? ??? ?cout << "请输入插入的数据" << endl;
?? ??? ??? ?cin >> n->elem;
?? ??? ??? ?sortinsert(l,n);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 8:
?? ??? ??? ?initiallist(l);
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ??? ?case 0:
?? ??? ??? ?cout << endl << endl;
?? ??? ??? ?cout << '\t' << "谢谢使用" << '\t' << "欢迎下次再来" << endl;
?? ??? ??? ?return;
?? ??? ?default:
?? ??? ??? ?cout << "输入有错请重新输入" << endl;
?? ??? ??? ?system("pause");
?? ??? ??? ?system("cls");
?? ??? ??? ?break;
?? ? ?}
?? ?}
}
?
|