线性链表的实现和应用

本文主要是介绍线性链表的实现和应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、采用书上第 28 页定义的线性表链式存储结构，编程实现书中算法 2.8、算法 2.9、算法 2.10、算法2.11，以及输出线性链表的算法。另外，编写主函数对所实现的算法进行测试。

2、采用线性表的链式存储结构，实现线性链表的合并操作：①设有线性链表 La 和 Lb，试设计算法将La 和 Lb 归并为新的线性链表 Lc；②设线性链表 La 和 Lb 中的数据元素为整数，且均已按值非递减有序排列，要求 Lc 中的数据元素也按值非递减有序排列

例题一：

#include <stdio.h>
#include <iostream>
using namespace std;
#include <stdlib.h>
#include<math.h>
#include <string.h>
#include <malloc.h>
#define TRUE 1
#define OVERFLOW -2
#define ERROR 0
#define OK 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;

}LNode,*LinkList;
void CreatList_L(LinkList& L, int n)
{
	LinkList p;
	int i;
	L = (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
	for (i = n; i>0; --i)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &p->data);
	p->next = L->next; L->next=p;
	}
}//CreateList_L

	Status OutputList_L(LinkList L)
	{
		LinkList p = L->next;
		if (!p) return ERROR;
		while (p)
		{
			printf("%d ", p->data);
				p = p->next;
		}
		printf("\n");
		return OK;
	}
	Status GetElem_L(LinkList& L, int i,ElemType &e){
		LinkList p;
		int j;
		p = L->next; j = 1;
		while (p && j < i) {
			p = p->next; ++j;
		}
		if (!p || j > i)return ERROR;
		e = p->data;
		return OK;

	}//
	Status ListInsert_L(LinkList &L,int i,ElemType e)
	{
		int j;
		LinkList p,s;
		p = L; j = 0;
		while (p && j < i - 1) {
			p = p->next;
			++j;
		}
		if (!p || j > i - 1)return ERROR;
		s= (LinkList)malloc(sizeof(LNode));
		s->data = e; s->next = p->next;
		p->next = s;
		return OK;
	}
	Status ListDelete_L(LinkList L, int i, ElemType& e) {
		LinkList p,q;
		int j;
		p = L; j = 0;
		while (p->next && j < i - 1) {
			p = p->next;
			++j;
		}
		if (!(p->next) || j > i - 1)return ERROR;
		q = p->next;
		p->next = q->next;
		e = q->data;
		free(q);
		return OK;
	}
	int main()
	{
		ElemType b, d, dd;
		LinkList L;
		printf("创建单链表，输入5个元素：\n");
		CreatList_L(L, 5);
		printf("输出单链表所有元素：\n");
		OutputList_L(L);
		printf("输出单链表第2个位置元素到dd：\n");
		GetElem_L(L, 2, dd);
		printf("dd=%d\n", dd);
		printf("插入元素b：");
		scanf("%d", &b);
		printf("在单链表第4个位置插入%d！\n",b);
		ListInsert_L(L, 4, b);
		printf("输出插入操作后单链表所有元素！\n");
		OutputList_L(L);
		printf("删除单链表第三个位置的元素！\n");
		ListDelete_L(L, 3, d);
		printf("输出删除操作后单链表所有元素！\n");
		OutputList_L(L);
	}

例题二：

#include <stdio.h>
#include <iostream>
using namespace std;
#include <stdlib.h>
#include<math.h>
#include <string.h>
#include <malloc.h>
#define TRUE 1
#define OVERFLOW -2
#define ERROR 0
#define OK 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;

}LNode, * LinkList;
void CreatList_L(LinkList& L, int n)
{
	LinkList p;
	int i;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	for (i = n; i > 0; --i)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &p->data);
		p->next = L->next; L->next = p;
	}
}//CreateList_L
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	LinkList pa, pb, pc;
	pa = La->next; pb = Lb->next;
	Lc = pc = La;
	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 OutputList_L(LinkList L)
	{
		LinkList p = L->next;
		if (!p) return ERROR;
		while (p)
		{
			printf("%d ", p->data);
				p = p->next;
		}
		printf("\n");
		return OK;
	}
int main()
{
	LinkList La,Lb,Lc;
	printf("从表尾创建单链表La，输入5个元素：\n");
	CreatList_L(La, 5);
	printf("La：");OutputList_L(La);
	printf("从表尾创建单链表Lb，输入5个元素：\n");
    CreatList_L(Lb, 5);
	printf("Lb：");OutputList_L(Lb);
	MergeList_L(La,Lb,Lc); 
    printf("输出合并操作后单链表Lc所有元素！\n");
    printf("Lc：");OutputList_L(Lc);
 } 

这篇关于线性链表的实现和应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！