链式线性表源码

素颜马尾好姑娘i 2022-06-18 01:55 115阅读 0赞

链式线性表源码 （c++）

//
 //Description:自定义链式线性表
 //
 #include <iostream>
 #include <malloc.h> 
 using namespace std;
 
 typedef int ElemType;
 typedef int Status;
 
 //--------链式线性表定义--------
 typedef struct LNode
 {
 	ElemType data;
 	struct LNode *next;
 }LNode, *LinkList;
 //----------全局变量----------
 LNode *p=NULL, *q=NULL;
 LNode *s=NULL;
 LNode *pa=NULL;
 LNode *pb=NULL;
 LNode *pc=NULL;
 
 int j=0;
 static int num=0;
 //---------------创建链表-----------------------
 void CreateList_L(LinkList &L, int n)
 {
 	####逆位序输入n个元素的值，建立###带表头结点##的单链线性表L
 	L = (LinkList)malloc(sizeof(LNode));
 	L->next = NULL;
 	for (int i = n; i > 0; i--)
 	{
 		p = (LinkList)malloc(sizeof(LNode));//-----
 		cout << "\n请输入第" <> (p->data);
 		p->next = L->next;
 		L->next = p;
 	}
 	cout << endl;
 }
 
 //---------链式线性表中查找第i个结点的值------------
 Status GetElem_L(LinkList L, int i, ElemType &e)
 {
 
 	if (i <= 0 || i > num)
 	{
 		cout << "\t查找位置不合法！" << endl;
 		return 0;
 	}//-------------------
 
 	p = L->next; ///------------------
 	j = 1; ///------------------
 	while (p&&j<i)
 	{
 		p = p->next;
 		++j;
 	}
 
 	if (!p || j>i)
 		return 0;
 	e = p->data;
 	return 1;
 }
 //------------------链式线性表 合并非递减有序链表---------
 void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
 {
 	//已知单链线性表La和Lb的元素按值非递减排列
 	//归并La和Lb得到新的单链线表Lc,Lc的元素也按值非递减排列
 	pa = La->next;
 	pb = Lb->next;
 	Lc = pc = La;//用La头结点作为Lc的头结点
 	while (pa&&pb)
 	{
 		if (pa->data <= pb->data)
 		{
 			pc->next = pa;
 			pc = pa;
 			pa = pa->next;
 		}
 		else
 		{
 			pc->next = pb;
 			pc = pb;
 			pb = pb->next;
 		}
 	}
 	pc->next = pa ? pa : pb;
 	free(Lb);
 }
 //--------------------链式线性表 插入-----------------
 Status ListInsert_L(LinkList &L, int i, ElemType e)
 {
 	if (i <= 0 || i > num + 1)
 	{
 		cout << "\t插入位置不合法！" << endl;
 		return 0;
 	}//-------------------
 
 	p = L;
 	j = 0;
 	while (p&&jnext;
 		j++;
 	}
 	if (!p || j>i - 1)
 		return 0;
 	s = (LinkList)malloc(sizeof(LNode));
 	s->data = e;
 	s->next = p->next;
 	p->next = s;
 	num++;//--------
 	return 1;
 }
 
 //--------------------链式线性表 删除-----------------
 Status ListDelete_L(LinkList &L, int i, ElemType &e)
 {
 	if (i <= 0 || i > num)
 	{
 		cout << "\t删除位置不合法！" << endl;
 		return 0;
 	}//-------------------
 	p = L;
 	j = 0;
 	while (p->next&&jnext;
 		j++;
 	}
 	if (!(p->next) || j>i - 1)
 		return 0;
 	q = p->next;
 	p->next = q->next;
 	e = q->data;
 	free(q);
 	num--;//--------
 	return 1;
 }
 //--------------------链式线性表 输出-----------------
 void output(LinkList &L, int n)
 {
 	cout << "\n\n当前各结点值为：" << endl;
 	p = L->next;
 	for (int i = 1; i <= n; i++)
 	{
 		cout << "第" <data) << endl;
 
 		p = p->next;
 	}
 }
 //-------------主函数---------------
 void main()
 {
 	cout << "\n\t======================链式线性表操作===========\n";
 	cout << "-------------------------初始化---------------------------" << endl;
 	cout << "请输入初始时链接线性表中结点的个数" << endl;
 	cin >> num;
 	LinkList L;
 	CreateList_L(L, num);
 	output(L, num);
 
 	cout << "--------------------------查找----------------------------" << endl;
 	int i;
 	cout << "请输入欲查找的结点所处的次序\t" << endl;
 	cin >> i;
 	ElemType s;
 	GetElem_L(L, i, s);
 	cout << "所查找的第" <> i >> s;
 	ListInsert_L(L, i, s);
 	output(L, num);
 
 	cout << "--------------------------删除-----------------------------" << endl;
 	cout << "请输入欲删除的结点所处的位置\t" << endl;
 	cin >> i;
 	ListDelete_L(L, i, s);
 	cout << "所删除的元素位置为" <> num_La;
 	LinkList La;
 	CreateList_L(La, num_La);
 
 	cout << "\n请输入初始时 *非递减* 链式线性表 Lb 中结点的个数" << endl;
 	int num_Lb;
 	cin >> num_Lb;
 	LinkList Lb;
 	CreateList_L(Lb, num_Lb);
 	cout << "\n La中" << endl;
 	output(La, num_La);
 	cout << "Lb中" << endl;
 	output(Lb, num_Lb);
 	LinkList Lc;
 	MergeList_L(La, Lb, Lc);
 	num = num_La + num_Lb;
 	cout << "\n\n合并后 *非递减* 链式线性表Lc中" << endl;
 	output(Lc, num);
 }